LT碼的性能分析及仿真

楊 玲，宋時立，劉國超，陳 霄，文 紅

（①電子科技大學 通信抗干擾國家級重點實驗室，四川 成都610054；②東南大學 移動通信國家重點實驗室，江蘇 南京 210096）

0 引言

噴泉碼是一類基于圖的線性糾刪碼，在廣播方式的通信系統中，發送端對原始信息進行編碼，得到源源不斷的編碼信息并且發送，只要接收端能正確接收到足夠的編碼信息就可以譯出原始數據信源，反饋重傳的差錯控制方式相比，其更為有效，尤其適用于深空通信環境。

Michael Luby[1]于1998年提出了噴泉碼[2-3]的概念，噴泉碼的設計需要主要考慮2方面的問題：①譯碼開銷ε盡量小，使其趨近于0；②編譯碼復雜度盡量低：理想情況下，希望做到每個編碼分組需要的運算量是一個與K無關的常量，獲得K個原始數據分組的成功譯需要的運算量是K的線性函數。

本文首先介紹LT碼隨機度分布，進而剖析LT的編碼、譯碼算法[4-5]，對各種長度的LT進行了仿真。本論文的結果對LT碼的選用有參考意義。

1 LT碼的編碼譯碼算法

LT碼指：其編碼由K個信源包生成任意數量的編碼包，譯碼器接收到編碼包中任意N個，即可以高概率通過譯碼成功恢復出全部信源包，這里，每個信源包代表一個數據包，可以是1比特，也可以是多個比特[4-7]。通常情況下，N略大于K，由此會有一定的譯碼開銷 β=N/ K-1。

LT碼的關鍵就是設計隨機度。也就是LT碼的隨機行為完全由度ρ（d）來決定。

度：與該編碼包相連的原始數據分組數目。

度分布：對于所有的d，ρ（d）表示編碼分組中出現度為d的概率。

目前研究得較為成熟的度分布主要有4種：全“1”分布、理想孤波分布、均勻分布和魯棒孤波分布。其中魯棒孤波分布是最為廣泛使用的一種度分布。

1.1 LT碼的編碼算法具體實現

1)從度分布概率函數 ρ（d）中隨機選取編碼數據包的度d。本文我們選用的魯棒孤波分布。

2)從K個原始數據包中，等概率地隨機選取d個源始數據包 sk。其中這里的d就是剛從度分布函數中選的度數。

3)將這d個源始數據包進行模二和，生成一個編碼數據包。

圖1 一個編碼數據包的生成過程

以圖1為例，我們先從魯棒孤波度分布函數中選取得度d=4，然后從K個源數據包中等概的選出4個數據包，圖中我們選的是s1、s3、s4和sk。最后將這4個數據包進行模二和。這樣就得到了一個編碼數據包。

1.2 LT碼譯碼算法

目前 LT碼的譯碼算法主要有消息傳遞算法(MP，Message Passing)和高斯消元法(GE，Gaussian Elimination Decoding)2種。

1.2.1 消息傳遞算法（MP）

LT碼在刪除信道條件下的MP譯碼過程如下：

1）首先尋找度為1的編碼符號nt，即該編碼包只與一個ks相連。如果找不到這樣的編碼包，譯碼過程就此終止，信源包無法恢復。

①令ks=nt；②將ks與所有和ks有聯系的nt異或；③刪除所有與ks的聯系。

2）重復過程步驟1，當所有的ks都確定后，譯碼停止。

1.2.2 高斯消元算法（GE）

高斯消元法的譯碼步驟如下：

1）對生成矩陣進行列變換，對應列接收的數據包進行相同的變換，將生成矩陣G變換為[Ek*k|P]形式，對應的t1,t2,…,tn變換為

以圖2為例說明LT碼的譯碼過程。

在圖2（a）中 t1是度為1，與t1相連的是 s1。所以令 t1=s1。在圖2（b）中，令 t1=s1后，恢復出了 s1，然后釋放掉t1。圖 2（c）中，恢復出 s1后，刪除了與 s1相連的 t2和 t4的連線。此時，t4的度此時為1，令 t4=s2，然后 s2數據得到恢復，刪除 t4。圖2（d）中，s2已經恢復出來了，然后讓 s2與和它相連的 t2和t3相異或，并且刪除與其的連線。圖 2（e）中，此時 t2和 t3的度都為1，與他們相連的是 s3，所以 s3也就恢復出來了；圖2（f）是恢復出來的原始數據包。

圖2 LT碼的譯碼算法實現過程

2 仿真分析

本節對LT碼的性能進行仿真。仿真所用的軟件是：VC 6.0、Matlab。所用參數是：LT隨機度生成用的是魯棒孤波分布；源數據包的長度K=255、K=2 000、K=4 000、K=6 000、K=8 000；二進制刪除信道的刪除概率 p分別等于起始值為 0.05，步長為0.05，終值為0. 5；常數c=0.03；譯碼允許失敗概率δ= 0.5；幀長=200；

2.1 短碼長的LT碼的性能分析

[6-8]。本小節采用發送數據包長度為K=255，結果如圖3所示，發送數據包長度K=255，刻畫短碼長的性能我們用冗余度和成功譯碼概率關系圖來描述。從圖中我們可以看到，在源數據包長度比較短的情況，當我們依次增加信道噪聲(即丟包率)時，只有當冗余度不斷的增加才能完全的恢復出所有的原始數據包。

圖3 不同刪除概率下譯碼概率和冗余度比較

以 K=255，q=0.5為例說明，當接收端接收到520個包時 200次迭代才能正確譯碼一次，此時圖中冗余度是信息源包的2.03倍左右。再繼續接收成功譯碼的概率也隨之增大。直到接收到1 080個包即冗余度為信息源包的4.23倍時，譯碼概率才達到1，之后就達到一個成功譯碼的穩定狀態。

2.2 長碼長的LT碼的性能分析

圖4是數據包長度分別為2 000、4 000、6 000和8 000的性能仿真。

圖4 魯棒孤子分布的LT碼成功譯碼數據包數目

從圖4中看到，當源信息包為K=2 000時，當接收端接收到2 800個左右數據包就能成功地譯出源數據包，我們還可以看到，隨著接收數據包的數目增加，接收端能達到接近100%的成功譯碼。當信源數據包分別為K=4 000，K=6 000，K=8 000時，在接收端如果接收到接近于5 000、7 500和10 000個數據包就能幾乎完全成功譯碼。同時當接收數據包數目增多，幾乎每次都能譯碼成功。

3 結語

本文主要介紹了4種設計LT碼隨機度分布的方法并進行了Matlab仿真驗證，從圖中得到魯棒孤波分布產生的隨機度是一種比較好的方式。同時也仿真得到了短碼長的LT，因為碼長K比較小，編譯碼的復雜度比較低，相應譯碼時間也比較少。短碼LT的缺點就是譯碼[9-11]所用的編碼包的數量不再趨于原始包長，冗余度會增加。噴泉碼的性能受碼長的影響較大，要取得好的性能，通常需要較長的碼長，但是，碼長太長會增加編譯碼復雜度。

參考文獻

[1] LUBY M.LT Codes[M].USA:ACM,2002:6-7.

[2] SHOKROLLAHI A.Raptor Codes[J].IEEE Transactions on Information Theory,2006,52(06): 2551-2555.

[3] 冀保峰，高宏峰. Fountain碼編譯碼技術的研究[J]. 通信技術, 2008,41(11):66-68.

[4] FINAMORE, WEILER A, RAMOS, et al. Improving the Performance of LT Codes[C].USA:IEEE,2010:566-570.

[5] ZHANG Fan, XU Lixin, PAN Xi. Comparison of BP and Gauss Code base on Fountain Code Measuring[C]. USA:ICMTMA,2011:737-740.

[6] ZHU Hongjie,ZHANG Chao,LU Jianhua.Designing of Fountain Codes with Short Code-Length[C].USA:IWSDA, 2007:65-68.

[7] 黃誠,易本順,吳雄斌,等.短碼長 LT碼的蟻群算法度分布優化[J].北京郵電大學學報,2011(06):129-133.

[8] 郭春梅，畢雪堯.LT碼的性能分析與研究[J].信息網絡安全,2010(10):53-55.

[9] 任祥維，文紅，張頌.LDPC碼的全并行概率譯碼[J].通信技術，2011,44(08):42-44.

[10] 張威，徐熙宗，張克，等.RS級聯編碼在超短波通信與衛星通信信道的仿真分析[J].通信技術，2009,42(02):27-29.

[11] 伊立新，劉云莉，袁成剛，等.基于LDPCA的分布式視頻編碼實現及應用[J].信息安全與通信保密，2012(02):42-47.