Parallel HARQ processes 平行的HARQ程序

概念是從這篇介紹UMTS中HARQ程序的文章中看到的
http://letstalkumts.blogspot.tw/2011/10/harq-procedure.html

此篇前面敘述的前提應是UMTS中downlink部分，最後下面分點敘述才提到uplink部分



Automatic Repeat Request(ARQ)
是基本的重傳機制，reciver一旦發現收到的資料有誤，就全部捨棄，然後向sender要求重傳

Hybrid ARQ(HARQ)
則是檢查錯誤後，若有錯 就把資料buffer起來，並向sender要求重傳，然後根據buffer的data與重傳的data合併成無誤的結果 ( channel decoding and error detection)

Parallel HARQ processes
是用來避免重傳對throughput的影響。
當一個HARQ程序正在等待ACK時，第二個HARQ程序就可以趁此機會 在接下來的TTI傳送資料
這些parallel processes就稱為Stop and Wait processes

3GPP中，允許最大8個parallel HARQ processes被config給同一個UE (DL)



原文應在TS 36.213 section 7，其中註名HARQ process的最大數量

[Linear Programming] The Simplex Method in tableau / /線性規劃的Tableau方法之教學 (youtube)

影片有步驟，一步一步代數字很清楚，

原本的object funciton   MAX z =  x1 + 2 x2

subject to
x1 <= 2  ... (L1)
x2 <= 2  ... (L2)

x1+x2 <= 3  ... (L3)

加入slack variable以後變成

x1+       x3               = 2
      x2 +     + x4       = 2
x1+x2                +x5 = 3


然後先找一個initial的解(不一定最佳)

( basis = {x3,x4,x5} ,  non-basis = {x1,x2} )
x1 = x2 = 0,   x3 = 2, x4 = 2, x5 = 3 明顯式子會滿足限制式L1~L3

然後找一個能讓z增加的column, 影片中是先選x2, 作為working column

於是乎三條限制式都限制x2, 它找其中那個ratio最大的那一步, 就是在找哪一條式子限制x2最多

因此2:49那邊L2限制x2最多, 因此把代表該行的x4踢掉, x2近來( x2長大變成x2=2, x2進入basis),

此時basis = {x3, x2, x5}     non-basis={x1, x4}

接著把其它L1,L3的兩行內的x2消掉(為的讓L1,與L3都跟x2無關, 使x2固定在2)



照類似的步驟 5:08, L3對x1最嚴格, 因此把L3代表的x5踢離basis,

basis = {x1, x2, x3},   non-basis={x4,x5}

之後發現L4的係數皆負,

0 0 0 -1 -1

如此無法藉由增加non-basis而讓z變好(增加x4,x5的話, 乘上-號會使z變小)，所以得到了最佳解(最大值)



影片如下↓

一份較親民的EMBMS介紹 (English)

An introduction about EMBMS in LTE source: http://www.slideshare.net/allabout4g/embmb-in-lte

e-MBMS in LTE from All About 4G

Entropy(熵) in information一篇不錯的文章

http://ccckmit.wikidot.com/st:mutualinformation
中文的 good

十個圖解說明如何使用匈牙利演算法(Matching Problem) 10 steps to show you how to use the "Hungarian Algorithm" (with 10 pictures)

Good links here (english) :
http://www.wikihow.com/Use-the-Hungarian-Algorithm


Good video describing how to use Hungarian Algo.
(you can open the auto-generated subtitle and most of them is correct)

Definition of Proportional / Envy-free division

N人均分一塊蛋糕，蛋糕上面的東西不均勻，可能某部份奶油多，某部份水果多，總之就是每個人偏好的部分可能不一樣；意即大家對於同一蛋糕的每一部分有不同的偏好程度。


Proportional division ( simple fair division)
對於每一個人來說，自己至少拿到1/N的蛋糕，而此1/N是以自己的價值觀來看(by their own valuation)
在此也暗示了說，可能除了自己有另外兩個人A, B，然後A拿到的那一份蛋糕在自己眼裡是少於1/N的，B拿到的那一份則多餘1/N。因此自己可能會想要拿自己的蛋糕跟B換，這說明此分法並非envy-free

Envy-Free
一個分法被稱為是Envy-free，如果每個拿蛋糕的人都覺得其他人拿到的蛋糕，都沒有自己拿到的多(i.e. 以自己的價值觀來看，覺得自己分最多所以不會想跟任何一個人交換)
因此Envy-Free的定義比Proportional更嚴格。
A division is envy-free if each recipient believes that according to his measure no other recipient has received more than he has. This requirement is stronger than proportional division.


http://en.wikipedia.org/wiki/Proportional_(fair_division)
http://en.wikipedia.org/wiki/Envy-free

什麼是HARQ; What is HARQ(Hybrid automatic repeat request)

全名是Hybrid automatic repeat request，混種的ARQ

其實就是FEC + ARQ


傳統的ARQ只在資料末添加一點redundant bits，作為"偵"錯碼(only for error-detection)
比如 cyclic redundancy check (CRC);  同位元檢查(parity bit)

然後FEC指的是添加在資料，並且可以"糾"錯的那些FEC code
比如 Reed-Solomon code (RS code); Hamming(7,4) code


HARQ就是data連同FEC code, parity bit 一起傳，如果parity bit告知內有錯誤，即用FEC code糾正錯誤，糾正失敗的話才採用ARQ的機制，因此ARQ在HARQ中可算是一備案


明顯的，用FEC code需要多傳比較多的bit，因此有代價

在channel quality很差的時候，HARQ比ARQ好；
在channel quality不錯的時候，原始的ARQ比較適合。就依現況做選擇


資料來源:
http://en.wikipedia.org/wiki/Hybrid_automatic_repeat_request