一種LT碼編碼生成矩陣的偽隨機(jī)產(chǎn)生方案

盛 潔，雷維嘉，謝顯中

(重慶郵電大學(xué) 移動通信技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室，重慶 400065)

一種LT碼編碼生成矩陣的偽隨機(jī)產(chǎn)生方案

盛 潔，雷維嘉，謝顯中

(重慶郵電大學(xué) 移動通信技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室，重慶 400065)

常用的LT碼編碼生成矩陣的傳輸方案是在每個(gè)編碼數(shù)據(jù)包的頭部額外增加一個(gè)開銷，用于放置該數(shù)據(jù)包對應(yīng)的編碼生成矢量。該方案會產(chǎn)生較大的開銷，造成傳輸效率降低。給出了一種編碼生成矩陣在編碼器和譯碼器間偽隨機(jī)同步產(chǎn)生的方案。采用該方案時(shí)，只要編碼器和譯碼器偽隨機(jī)數(shù)發(fā)生器的算法相同，種子也相同，就能產(chǎn)生一樣的均勻偽隨機(jī)數(shù)序列，將其進(jìn)行轉(zhuǎn)化后就能得到相同的編碼生成矩陣。種子數(shù)據(jù)量小，且只需要在偽隨機(jī)數(shù)發(fā)生器初始化時(shí)編碼器和譯碼器間交換一次即可。實(shí)驗(yàn)結(jié)果顯示，生成的偽隨機(jī)度值符合指定的度分布函數(shù)，數(shù)據(jù)包的偽隨機(jī)選擇也符合泊松分布。相比較傳統(tǒng)方案，該方案避免了編碼生成矩陣的直接傳輸，減少了傳輸開銷，提高了傳輸效率。

數(shù)字噴泉碼；LT碼；編碼生成矩陣；偽隨機(jī)產(chǎn)生

0 引 言

1998年，Michael Luby等提出了數(shù)字噴泉碼的概念。發(fā)送端可隨機(jī)地、源源不斷地產(chǎn)生編碼數(shù)據(jù)包，而接收端不需要關(guān)心具體接收到了哪些編碼數(shù)據(jù)包，只要其數(shù)量略大于源數(shù)據(jù)包的個(gè)數(shù)，那么源信息就能以很大的概率被完全恢復(fù)出來。2002年Luby[1]提出了第一種實(shí)用的噴泉碼LT碼，同時(shí)提出了2種度分布[1]：理想孤子度分布(ideal soliton distribution, ISD)；改良的魯棒孤子度分布(robust soliton distribution, RSD)。其中，RSD是目前LT碼最常用的編碼度分布[2-4]。

在LT碼編碼過程中，編碼器利用特定的度分布函數(shù)產(chǎn)生隨機(jī)度值，并隨機(jī)選擇相應(yīng)個(gè)數(shù)的源數(shù)據(jù)包，得到一個(gè)編碼生成矢量，根據(jù)該矢量進(jìn)行編碼得到一個(gè)編碼數(shù)據(jù)包。編碼生成矢量構(gòu)成了編碼生成矩陣。在譯碼過程中，不論是采用置信傳播(belief propagation, BP)還是高斯消元(Gaussian elimination, GE)算法譯碼，譯碼器都需要根據(jù)編碼生成矩陣來處理編碼數(shù)據(jù)包。相關(guān)文獻(xiàn)中通常假設(shè)譯碼器對編碼生成矩陣是已知的[5]。由于編碼生成矩陣是隨機(jī)生成的，實(shí)際上需要由編碼器傳輸給譯碼器。常用的方法是在編碼數(shù)據(jù)包的頭部額外增加一個(gè)開銷，用于放置該數(shù)據(jù)包對應(yīng)的編碼生成矢量。這種方案的傳輸效率較低，參與編碼的源數(shù)據(jù)量越大，編碼生成矢量就越長，傳輸開銷就越大。為提高傳輸效率，另一種可行的方案是在編碼器和譯碼器之間采用偽隨機(jī)的方式同步產(chǎn)生編碼生成矩陣。采用該方案時(shí)，只要編碼器和譯碼器偽隨機(jī)數(shù)發(fā)生器的算法相同，種子也相同，就能產(chǎn)生一樣的編碼生成矩陣。種子數(shù)據(jù)量小且只需要在偽隨機(jī)數(shù)發(fā)生器初始化時(shí)交換一次即可，避免了編碼生成矩陣在信道上的傳輸，減少了傳輸開銷，提高了傳輸效率。其缺點(diǎn)是產(chǎn)生的編碼生成矢量不是真正的隨機(jī)數(shù)，有一定的規(guī)律，但只要偽隨機(jī)數(shù)的周期足夠長，也能滿足需要。

1 LT碼

1.1 LT碼的編碼

設(shè)源數(shù)據(jù)包為s1,s2,…，編碼數(shù)據(jù)包為t1,t2,…，LT碼生成編碼數(shù)據(jù)包的過程如下。

1)每k個(gè)源數(shù)據(jù)包分為一組，編碼在一個(gè)分組內(nèi)以數(shù)據(jù)包為單位進(jìn)行。不失一般性，假設(shè)一個(gè)分組內(nèi)的k個(gè)源數(shù)據(jù)包為(s1,s2,…,sk)。

2)根據(jù)編碼度分布函數(shù)隨機(jī)產(chǎn)生一個(gè)度d，并從一個(gè)分組內(nèi)的k個(gè)源數(shù)據(jù)包中隨機(jī)地選出d個(gè)數(shù)據(jù)包(sn,1,sn,2, …,sn,d)。

3)對選出的源數(shù)據(jù)包進(jìn)行異或運(yùn)算，生成一個(gè)編碼數(shù)據(jù)包，tn=sn,1⊕sn,2⊕…⊕sn,d。

重復(fù)以上3步，可生成無限長編碼數(shù)據(jù)包。

LT碼的編碼過程還可以用矩陣的形式表示為

(1)

每個(gè)編碼數(shù)據(jù)包對應(yīng)一個(gè)編碼生成矢量，如第n個(gè)編碼數(shù)據(jù)包對應(yīng)的編碼生成矢量為Gn=[gn1,gn2,…,gn(k-1),gnk]T，其中被選中的源數(shù)據(jù)包對應(yīng)元素位為1，其余為0，最終產(chǎn)生的編碼數(shù)據(jù)包tn由Gn中元素1所對應(yīng)的源數(shù)據(jù)包異或得到。編碼過程中每個(gè)編碼數(shù)據(jù)包對應(yīng)的編碼生成矢量Gn共同組成了編碼數(shù)據(jù)包的生成矩陣。

1.2LT碼的BP譯碼

LT碼的譯碼通常采用BP譯碼算法，該算法的譯碼過程相對簡單，具有較低的譯碼復(fù)雜度，且接收到少量數(shù)據(jù)包即可開始譯碼。

BP譯碼的過程如下。

1)在接收到的編碼數(shù)據(jù)包中找出度為1的編碼數(shù)據(jù)包tn，設(shè)其關(guān)聯(lián)的源數(shù)據(jù)包為si，令si=tn。

2)將其他所有與si相關(guān)連的編碼數(shù)據(jù)包(記為tm)與si進(jìn)行異或運(yùn)算，tm=tm⊕si。

3)去除所有編碼數(shù)據(jù)包與源數(shù)據(jù)包si的關(guān)聯(lián)。

重復(fù)以上3步譯碼過程，直到恢復(fù)出所有源數(shù)據(jù)包或者沒有度為1的編碼數(shù)據(jù)包為止。

無論采用何種算法譯碼，譯碼器在譯碼時(shí)都需要知道編碼生成矩陣信息。

1.3 編碼度分布

LT碼常用的編碼度分布是魯棒孤子度分布，是在理想孤子度分布的基礎(chǔ)上構(gòu)造的。理想孤子度分布函數(shù)為

(2)

(2)式中：d表示編碼數(shù)據(jù)包的度值；k表示源數(shù)據(jù)包個(gè)數(shù)；ρ(d)表示編碼數(shù)據(jù)包度為d的概率。魯棒孤子度分布在理想孤子度分布基礎(chǔ)上，引入2個(gè)參數(shù)c和δ來確保譯碼過程中期望的度為1的編碼數(shù)據(jù)包個(gè)數(shù)為

(3)

(3)式中：s為編碼數(shù)據(jù)包個(gè)數(shù)；δ為譯碼器未能完全恢復(fù)源信息的概率；c為0～1的常數(shù)。同時(shí)還引入了一個(gè)τ函數(shù)來增加編碼數(shù)據(jù)包取較大度值的概率：

(4)

將τ函數(shù)與理想孤子度分布函數(shù)歸一化合并即可得到魯棒孤子度分布函數(shù)：

(5)

(5)式中，

(6)

(6)式中，μ(d)表示采用魯棒孤子度分布編碼時(shí)，產(chǎn)生的編碼數(shù)據(jù)包度為d的概率。

2 均勻偽隨機(jī)數(shù)發(fā)生器

服從任意概率分布的偽隨機(jī)數(shù)都可以通過反函數(shù)法、舍選抽樣法等對(0,1)上均勻分布的偽隨機(jī)數(shù)進(jìn)行變換得到[6-7]。偽隨機(jī)數(shù)是利用數(shù)學(xué)遞推公式生成的隨機(jī)數(shù)，只要給定了初值就能重復(fù)生成完全相同的隨機(jī)數(shù)序列。雖不是真正的隨機(jī)數(shù)，但是如果采用性能良好的遞推算法，可以使得生成的隨機(jī)數(shù)具有類似真隨機(jī)數(shù)的統(tǒng)計(jì)特性。下面對幾類常用的均勻偽隨機(jī)發(fā)生器作簡要介紹，這些偽隨機(jī)發(fā)生器都能產(chǎn)生(0,1)上的均勻隨機(jī)數(shù)。

2.1 線性同余發(fā)生器

線性同余發(fā)生器[6]的其遞推公式為

(7)

(7)式中：a為乘量；c為增量；x0為初值，也就是種子；m為模數(shù)，0≤xi0時(shí)，則為混合線性同余發(fā)生器。若線性同余發(fā)生器的增量c=0，則稱為乘線性同余發(fā)生器。若m≤2L的最大素?cái)?shù)，L為一個(gè)正整數(shù)，則可獲得周期T=m-1、統(tǒng)計(jì)性能良好的素?cái)?shù)模乘同余發(fā)生器。

2.2 滿拋物線映射隨機(jī)數(shù)發(fā)生器

滿拋物線映射的表達(dá)式為

(8)

遞推時(shí)的初值x0為初值，就是種子。其中，x為狀態(tài)變量，φ為參數(shù)。

當(dāng)φ=2時(shí)，滿拋物線映射的表達(dá)式為

(9)

其迭代值概率密度函數(shù)為

(10)

區(qū)間兩端有奇異性，對其求積分，分布函數(shù)為

(11)

(11)式中，y(x)為(-0.5,0.5)上均勻分布的偽隨機(jī)數(shù)列，將其變換為(0,1)上的均勻偽隨機(jī)數(shù)列為

(12)

滿拋物線映射隨機(jī)數(shù)發(fā)生器作為一種混沌偽隨機(jī)數(shù)發(fā)生器[8]，具有較好的統(tǒng)計(jì)特性，但其高維偽隨機(jī)數(shù)列的獨(dú)立性較差。

2.3 組合發(fā)生器

為了得到周期更長、統(tǒng)計(jì)特性更優(yōu)的偽隨機(jī)數(shù)列，把多個(gè)獨(dú)立偽隨機(jī)數(shù)發(fā)生器組合在一起，以這樣的方式得到的新的發(fā)生器被稱為組合發(fā)生器[5]。

一類組合發(fā)生器算法的具體步驟如下。

1)用第1個(gè)偽隨機(jī)數(shù)發(fā)生器生成q個(gè)偽隨機(jī)數(shù)，將這q個(gè)偽隨機(jī)數(shù)按順序保存在T=(t1,t2,…,tq)中，令i=1；

2)用第2個(gè)偽隨機(jī)數(shù)發(fā)生器生成一個(gè)偽隨機(jī)整數(shù)j，1≤j≤q；

3)令ri=tj，再次用第一個(gè)偽隨機(jī)數(shù)發(fā)生器生成一個(gè)偽隨機(jī)數(shù)y，令tj=y,i=i+1；

4)重復(fù)步驟2)、3)，獲得的數(shù)列{ri}就是組合發(fā)生器生成的偽隨機(jī)數(shù)列。

3 編碼生成矩陣的偽隨機(jī)產(chǎn)生

LT碼的一個(gè)編碼數(shù)據(jù)包的生成過程分成2個(gè)步驟：首先產(chǎn)生出符合指定度分布的隨機(jī)度值；然后再根據(jù)產(chǎn)生的度值隨機(jī)選取相應(yīng)個(gè)數(shù)的源數(shù)據(jù)包進(jìn)行異或運(yùn)算，得到一個(gè)編碼數(shù)據(jù)包。因此，產(chǎn)生編碼生成矩陣需要2個(gè)偽隨機(jī)數(shù)發(fā)生器，一個(gè)產(chǎn)生符合指定度分布的隨機(jī)度值；另一個(gè)產(chǎn)生選取源數(shù)據(jù)包的編號，它們都可以采用離散分布的直接抽樣法[6]由(0,1)上的均勻偽隨機(jī)數(shù)轉(zhuǎn)換得到。

3.1 編碼數(shù)據(jù)包度值的產(chǎn)生

設(shè)需要由均勻偽隨機(jī)數(shù)產(chǎn)生符合度分布函數(shù)μ(d)的偽隨機(jī)度值。若源數(shù)據(jù)包個(gè)數(shù)為k，首先求出不同度的概率值μ(1)～μ(k)，然后根據(jù)這些度值將(0,1)劃分為k個(gè)取度區(qū)間，如表1所示。

表1 各度值的取度區(qū)間

由服從(0,1)上均勻分布的偽隨機(jī)變量的概率密度函數(shù)可知，落在(0, 1)內(nèi)任何子區(qū)間上的概率僅與此子區(qū)間的長度成正比，而與子區(qū)間所在的位置無關(guān)。根據(jù)各個(gè)度的取值概率μ(1)～μ(k)，在(0, 1)內(nèi)依次劃分不同長度的子空間。如度為2的取度概率為μ(2)，則對應(yīng)劃分區(qū)間(μ(1),μ(1)+μ(2)]，該區(qū)間長度為μ(2)，那么均勻隨機(jī)數(shù)落在該區(qū)間的概率就為μ(2)，其他度值情況依次類推。調(diào)用偽隨機(jī)數(shù)發(fā)生器，產(chǎn)生(0, 1)上的均勻偽隨機(jī)數(shù)后，判斷偽隨機(jī)數(shù)落在劃分的哪個(gè)區(qū)間，就相應(yīng)得到符合指定度分布函數(shù)的偽隨機(jī)度值。

為驗(yàn)證這種度值的取得是否符合指定度分布函數(shù)，首先利用3個(gè)發(fā)生器分別產(chǎn)生1.02×107個(gè)均勻偽隨機(jī)數(shù)。各發(fā)生器的遞推公式如下。

1)發(fā)生器A：素?cái)?shù)模乘同余發(fā)生器

(13)

2)發(fā)生器B：滿拋物線映射隨機(jī)數(shù)發(fā)生器

(14)

3)發(fā)生器C：發(fā)生器A和發(fā)生器B形成的組合發(fā)生器，首先用發(fā)生器A生成長度為127的隨機(jī)數(shù)列，即q=127，然后用發(fā)生器B將生成的隨機(jī)數(shù)列打亂重排，并最終生成1.02×107個(gè)(0,1)上的均勻隨機(jī)數(shù)。

上述發(fā)生器生成的隨機(jī)數(shù)列皆通過參數(shù)、均勻性及獨(dú)立性檢驗(yàn)。各統(tǒng)計(jì)檢驗(yàn)方法詳見文獻(xiàn)[5]。

然后由這些偽隨機(jī)數(shù)產(chǎn)生符合k=1 000，c和δ皆為0.05的魯棒孤子度分布的偽隨機(jī)度值。統(tǒng)計(jì)產(chǎn)生的偽隨機(jī)度中各度值出現(xiàn)的個(gè)數(shù)，求出取得各個(gè)度值的頻率，并將其與魯棒孤子度分布概率作對比。對比情況如表2所示。根據(jù)魯棒孤子度分布的特征，將取較大概率值的度1～30，64的概率值和偽隨機(jī)產(chǎn)生的度值的頻率值進(jìn)行對比。表2中，第2列“概率值”為根據(jù)魯棒孤子度分布的數(shù)學(xué)表達(dá)式計(jì)算得到的各度值的概率值，第3～5列為不同偽隨機(jī)數(shù)發(fā)生器輸出各度值的頻率值，即某種度值出現(xiàn)的次數(shù)與產(chǎn)生的偽隨機(jī)數(shù)總數(shù)的比值?？梢?，各個(gè)偽隨機(jī)數(shù)發(fā)生器產(chǎn)生的度值頻率值都與魯棒孤子度分布的概率值非常契合，產(chǎn)生的偽隨機(jī)度值均符合魯棒孤子度分布。

表2 按魯棒孤子度分布偽隨機(jī)產(chǎn)生的度值的頻率

3.2 根據(jù)度值偽隨機(jī)選擇源數(shù)據(jù)包

LT碼的編碼中，產(chǎn)生出符合指定度分布的偽隨機(jī)度值后，還需要隨機(jī)選取相應(yīng)個(gè)數(shù)的源數(shù)據(jù)包進(jìn)行異或運(yùn)算，最終得到編碼數(shù)據(jù)包。

設(shè)源數(shù)據(jù)包個(gè)數(shù)為k，由于是均勻選擇，每個(gè)源數(shù)據(jù)包被選中的概率均為1/k，因此，將(0,1)劃分為k個(gè)子區(qū)間，如表3所示。調(diào)用偽隨機(jī)數(shù)發(fā)生器，產(chǎn)生(0,1)上的均勻偽隨機(jī)數(shù)后，判斷這個(gè)偽隨機(jī)數(shù)落在劃分的哪個(gè)區(qū)間，就確定了具體選擇哪個(gè)編號的源數(shù)據(jù)包。

表3 源數(shù)據(jù)包被選中的區(qū)間

實(shí)際編碼時(shí)，產(chǎn)生每個(gè)編碼數(shù)據(jù)包時(shí)需按照其度值選擇完全不同的d個(gè)源數(shù)據(jù)包進(jìn)行異或。因此，對同一個(gè)編碼數(shù)據(jù)包而言，選擇源數(shù)據(jù)包的過程是不放回抽樣，即當(dāng)選到同一個(gè)源數(shù)據(jù)包編號時(shí)應(yīng)舍棄重選，直至選出完全不同的d個(gè)編號為止；而對不同的編碼數(shù)據(jù)包而言，選擇源數(shù)據(jù)包的過程才是真正的放回抽樣。理論上各個(gè)源數(shù)據(jù)包被選中的次數(shù)應(yīng)漸近服從泊松分布。其概率函數(shù)為

(15)

泊松參數(shù)λ的表達(dá)式為

(16)

(16)式中，Ωavg表示編碼數(shù)據(jù)包的平均度值；k為源數(shù)據(jù)包個(gè)數(shù)；n為編碼數(shù)據(jù)包的個(gè)數(shù)。

對源數(shù)據(jù)包選擇過程進(jìn)行實(shí)驗(yàn)驗(yàn)證。首先由發(fā)生器A產(chǎn)生1 200個(gè)(0,1)上的偽隨機(jī)數(shù)，然后利用3.1節(jié)的方法將其轉(zhuǎn)化為1 200個(gè)符合k=1 000，c和δ皆為0.05的魯棒孤子度分布的偽隨機(jī)度值，最后再利用上述方法隨機(jī)選取源數(shù)據(jù)包。然后對各個(gè)源數(shù)據(jù)包被選中的次數(shù)進(jìn)行統(tǒng)計(jì)，計(jì)算得到各次數(shù)出現(xiàn)的頻率值。共進(jìn)行20 000次這樣的實(shí)驗(yàn)，將實(shí)驗(yàn)結(jié)果平均得到實(shí)驗(yàn)的平均頻率值。理論上，源數(shù)據(jù)包被選中次數(shù)的概率應(yīng)服從泊松分布P(λ)，λ=12.225811858256170×1.2。實(shí)驗(yàn)得到的次數(shù)的頻率值與泊松分布概率值的對比情況如表4所示，表中列出取較大概率值的3～30次的情況。從表4可知，實(shí)驗(yàn)得到的源數(shù)據(jù)包被選中次數(shù)的頻率值與泊松分布概率值非常接近。

表4 源數(shù)據(jù)包被選中次數(shù)頻率與相應(yīng)泊松分布概率的對比

3.3 傳輸開銷分析

由于生成編碼數(shù)據(jù)包的過程中度值及對應(yīng)編碼數(shù)據(jù)包的選取都是利用偽隨機(jī)發(fā)生器產(chǎn)生的，只要發(fā)送端與接收端采用相同的偽隨機(jī)發(fā)生器并取相同初值，就能實(shí)現(xiàn)生成矩陣在編譯碼器間的同步產(chǎn)生。因此，只需要在數(shù)據(jù)傳輸開始時(shí)在編、譯碼器間交換1次2個(gè)偽隨機(jī)數(shù)發(fā)生器的種子(即發(fā)生器的初值)即可，可降低編碼生成矩陣信息傳輸?shù)拈_銷。下面簡單分析一下開銷的降低情況。

假設(shè)一個(gè)編碼數(shù)據(jù)包的信息數(shù)據(jù)長度為Lp字節(jié)，每k個(gè)編碼數(shù)據(jù)包為一組進(jìn)行LT碼編碼傳輸。采用傳統(tǒng)的方法時(shí)，需要在數(shù)據(jù)包頭增加一個(gè)開銷，傳輸對應(yīng)的編碼生成矢量(長度就是k)，開銷大小就是k比特，相對的開銷為

(17)

(18)

采用本文提出的方案時(shí)，僅需要每k個(gè)編碼數(shù)據(jù)包交換一次2個(gè)偽隨機(jī)數(shù)發(fā)生器的種子，設(shè)種子長度為Ls比特，則相對開銷為

(19)

4 總 結(jié)

編碼生成矩陣對LT碼的編譯碼都具有十分重要的意義，其在編碼器和譯碼器之間傳輸時(shí)常用的方法是在每個(gè)編碼數(shù)據(jù)包的頭部額外增加一個(gè)開銷，用于存放該數(shù)據(jù)包對應(yīng)的編碼生成矢量。這種方法的傳輸效率較低，特別當(dāng)一次LT編碼時(shí)源數(shù)據(jù)包的數(shù)量較大時(shí)，傳輸開銷會大大增加。為提高傳輸效率，本文給出一種編碼生成矩陣在編碼器和譯碼器間偽隨機(jī)同步產(chǎn)生的方案。首先利用素?cái)?shù)模乘同余發(fā)生器、滿拋物線映射隨機(jī)數(shù)發(fā)生器或它們組合得到的偽隨機(jī)發(fā)生器產(chǎn)生(0,1)上均勻分布的偽隨機(jī)數(shù)，然后利用離散分布的直接抽樣法將均勻偽隨機(jī)數(shù)轉(zhuǎn)化為符合度分布的隨機(jī)度值以及選擇源數(shù)據(jù)包時(shí)所需的隨機(jī)序號值。通過實(shí)驗(yàn)驗(yàn)證了生成的隨機(jī)度值符合指定的度分布函數(shù)，數(shù)據(jù)包被隨機(jī)選擇的次數(shù)也服從泊松分布。采用該方案時(shí)，只要編碼器和譯碼器偽隨機(jī)數(shù)發(fā)生器的算法相同，種子也相同，就能產(chǎn)生一樣的隨機(jī)度值以及選擇源數(shù)據(jù)包時(shí)所需要的隨機(jī)序號值，即得到相同的編碼生成矩陣。種子數(shù)據(jù)量小，且只需要在偽隨機(jī)數(shù)發(fā)生器初始化時(shí)在編碼器和譯碼器間交換一次即可。相比較將編碼生成矩陣在信道中傳輸?shù)姆桨?，該方案顯著提高了傳輸效率。

[1] LUBY M. LT codes[C]//The 43rd annual IEEE symposium on Foundations of Computer Science. Vancouver: IEEE Press, 2002: 271-280.

[2] SUH Y K, BAIK J Y, RAHNAVARD N, et al. Fountain code design for broadcasting systems with intermediate-state users[J]. IEEE Transactions on Communications, 2015, 63(9): 3057-3068.

[3] MENG Z,CALDERBANK R,SHUGUANG C.On design of rateless codes over dying binary erasure channel[J].IEEE Transactions on Communications,2012,60(4):889-894.

[4] RAFIE B R, ARDAKANI M. Fountain code design for the Y-network[J]. IEEE Communications Letters, 2015, 19(5): 703-706.

[5] MACKAY D J C. Fountain codes[J]. IEE Proceedings Communications, 2005, 152(6): 1062-1068.

[6] 高惠璇. 統(tǒng)計(jì)計(jì)算[M]. 北京: 北京大學(xué)出版社, 1995: 80-223. GAO H X. Statistical calculations[M]. Beijing: The Peking University Publishing House, 1995: 80-223.

[7] CHEN J, MOON J, BAZARGAN K. Reconfigurable readback-signal generator based on a field-programmable gate array[J]. IEEE Transactions on Magnetics, 2004, 40(3): 1744-1750.

[8] BEIRAMI A, NEJATI H. A framework for investigating the performance of chaotic-map truly random number generators[J]. IEEE Transactions on Circuits and Systems, 2013, 60(7): 446-450.

(編輯：劉 勇)

A pseudo-random scheme to generate the generator matrix of LT codes

SHENG Jie, LEI Weijia, XIE Xianzhong

(Chongqing Key Laboratory of Mobile Communication Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, P.R. China)

The generator vector of LT codes is transmitted by using an overhead in the header of each encoded packet to place code generation vector correspondingly in the traditional scheme.This scheme brings a large overhead, which causes the decline of transmission efficiency. Based on this, a pseudo-random generation scheme is given in this paper, which generates the generator matrix at encoder and decoder synchronously. The generator matrices generated in this way will be identical to each other, as long as the encoder and decoder use the same pseudo-random generator and the same seed. The seed is small data-wise, and it only needs to be exchanged once between the encoder and decoder when the pseudo-random generators are initialized. Experimental results show that the generated pseudo-random values are in accordance with the specified degree distribution, and the pseudo-random indices of source packets for encoding obey Poisson distribution values. Compared with traditional methods, this scheme avoids direct transmission of the generator matrix, which can reduce transmission cost and improve transmission efficiency.

digital fountain codes; LT codes; generator matrix; pseudo-random generation

10.3979/j.issn.1673-825X.2017.02.003

2016-05-10

2016-09-28 通訊作者：盛 潔 1220315828@qq.com

國家自然科學(xué)基金(61471076， 61301123)；長江學(xué)者和創(chuàng)新團(tuán)隊(duì)發(fā)展計(jì)劃(IRT1299)；重慶市科委重點(diǎn)實(shí)驗(yàn)室專項(xiàng)經(jīng)費(fèi)

Foundation Items：The National Nature Science Foundation of China(61271259,61471076); The Changjiang Scholars and Innovative Research Team Plan(IRT1299); The Special Fund of Chongqing Key Laboratory

TN919.3

A

1673-825X(2017)02-0155-06

盛 潔(1991-)，女，重慶人，碩士研究生。主要研究方向?yàn)槊嫦蛭锢韺影踩膰娋幋a編譯碼方案。E-mail:1220315828@qq.com。

雷維嘉(1969-)，男，云南元謀人，博士，教授。主要研究方向?yàn)闊o線和移動通信技術(shù)。E-mail: leiwj@cqupt.edu.cn。

謝顯中(1966-)，男，四川通江人，博士，教授、博士生導(dǎo)師。主要研究方向?yàn)闊o線和移動通信技術(shù)。E-mail: xiexzh@cqupt.edu.cn。