特定條件下的LT碼關鍵參數性能研究

摘 要：針對LT碼的編譯碼過程、度數分布以及應用環境特性，提出了LT碼度數分布中的關鍵參數分析模型，其核心思想是在對LT碼的編譯碼參數進行極限值研究，在數學分析的基礎上得出了最優化參數條件下的LT碼性能，并且對各個參數的重要性進行分析，提出了數字噴泉碼譯碼失敗概率的具體值。在極限值條件下研究了接收的數據量對LT碼的影響以及得出了最佳接收數據量。理論研究和仿真結果表明：提出的關鍵參數分析模型，能夠較好的擬合實際LT碼性能條件。

關鍵詞：數字噴泉碼 LT碼 度數分布 應用模型

中國分類號：TN911.22 文獻標識碼：A 文章編號：1672-3791（2013）07（c）-0001-02

數字噴泉碼是近年來興起的一種新型信道編碼技術。在1998年，M.Luby等國外專家提出數字噴泉碼原理后[1]，其理論與應用也越來越受到關注。它具有一些特殊的優點，數字噴泉碼不需要數據重傳信道，可以大大節省信道資源。在通信中，有效性和可靠性是一對矛盾，信道編碼技術是保證信息傳輸可靠性的必要方法。信道編碼實質上是通過增加信息的冗余來提高信息傳輸的可靠性。在信號衰減很嚴重，傳輸信號淹沒在噪聲中時，可靠性問題就尤為嚴重的凸現出來了。為了使信號具有較強的抗噪聲干擾的能力，需要對信號加以改造，使信號內部結構具有更強的規律性或相關性，以保證在噪聲干擾下仍能發現錯誤，甚至糾正錯誤，恢復原來的信息。

數字噴泉碼作為一種信道編碼可以改進無反饋信道的通信方式，它是一種前向糾錯編碼技術。信息在發送端經過糾錯編碼后送入信道，接收端通過糾錯譯碼自動糾正傳輸中的差錯，這樣的方式叫做前向糾錯（FEC）[2]，前向則是指過程是單向的，沒有反饋。這種方法具有較低的開銷和較精確的差錯恢復能力。而傳統的FEC存在一些缺陷[3]：（1）在傳輸過程當中，數據組與組之間有時延。（2）當接收端在沒有接收到系統所要求數據包個數的情況下，需要發送端重傳整個數據塊，不符合實時傳輸。而對于數字噴泉碼，不需要發送端與接收端之間的交互，可以大大減少傳輸時延。而且，當沒有接收到應有的數據包個數時，不需要重傳整個數據塊。

數字噴泉碼的應用環境主要是刪除信道，刪除信道主要是指的一種類似于糾錯概率很高的噪聲信道，在其中傳輸的數據要么徹底丟失，要么完全正確無誤的被接收。

1 數字噴泉碼

數字噴泉碼可以從K個原始數據分組生成得到無窮多個編碼分組，是一種無碼率的碼。當接收端收到足以譯碼的編碼分組的個數時，便能成功譯碼，該種碼便被形象的稱為噴泉碼。數字噴泉碼不需要數據重傳信道，可以提高信息傳輸的可靠性。在數字噴泉碼的研究當中，將其分為三類[4，5]：（1）隨機線性噴泉碼。（2）LT碼（Luby Transtion Code）（3）Raptor碼。嚴格意義上說，隨機線性噴泉碼不算是噴泉碼，其編譯碼復雜度太大且成功譯碼概率較低；LT碼是第一種可以實現的噴泉碼算法，它也是一種稀疏碼，其編譯碼過程是做二分圖的過程；Raptor碼是在LT碼基礎上進行的編碼，其編碼時平均度數較低。本文主要研究LT碼，將會詳細討論LT碼的編譯碼過程[5，6]，其余兩類具體編碼可參見參考文獻[7，8，9]。

1.1 LT編碼

（1）從合適的度數分布當中，隨機地選擇一個值，該值即為該編碼分組由幾個原始數據生成，叫做該次編碼分組的度數。

（2）從原始數據分組（比特）當中隨機的選擇個數據，將該個數據進行模2和。

（3）重復以上步驟，生成編碼分組。

1.2 LT譯碼

噴泉碼的譯碼，目前普遍采用MP（message passing）算法，過程如下。

（1）在得到的編碼分組數據當中，找到度數為1的編碼分組，若沒有，則譯碼失敗。

（2）在二分圖當中，將該度數為1的編碼分組直接復制為原始數據分組。

（3）將上一步生成的原始數據分別模2和到與之相連的其余編碼分組當中，并且去除該原始數據和這些編碼分組的連接關系。

（4）將上一步當中的編碼分組數據的度數減少1。

（5）重復以上四個步驟，直至恢復原始數據，譯碼完成。

1.3 LT碼的度數分布

在上述LT碼的編碼過程當中，需要一個合適的度數分布，這是該種算法最關鍵的問題，它必須滿足以下兩個條件。

（1）在一定意義上度數分布較高，使得生成的編碼分組能夠盡可能包含所有原始數據。

（2）要求編碼分組的度數不能太高，使LT譯碼能夠成功開始以及進行下去。

2 LT碼編譯碼過程的研究與仿真

2.1 有關參數的研究

在數字噴泉碼編譯碼過程當中，一個重要的指標就是譯碼失敗的概率。根據提出的理論，它不需要反饋信道，通過發送端可以給出無窮多個編碼分組，是無碼率的，只要接收端收到足夠的編碼分組，便能以高概率譯碼。而進行整個過程時，度數分布是一個重要的概念，直接關系到譯碼能否開始進行以及譯碼成功的概率。

在本文的研究過程中，信源（原始數據）選擇的均是相關性不大的隨機數據比特。通過對魯棒孤子分布的參數進行改進，得到最優化參數情況下的譯碼失敗概率，本文在對參數的研究過程當中，得出參數c較參數的影響大，c會直接影響譯碼失敗概率，而的變化基本對譯碼失敗概率沒有影響。據圖1和圖2可得出最優化的參數c在0.2處轉折，可選擇c大于或等于0.2，這里我們選擇c=0.2，因影響較小，對可以根據實際應用情況而定，研究當中我們選擇=0.01。

用最優化的參數可以使譯碼失敗的概率降到相對很低的范圍。

2.2 接收數據量對譯碼性能影響的研究

如上所述，數字噴泉碼是一種無碼率的碼，而在數字噴泉碼的研究過程當中，得出數字噴泉碼能成功譯碼所需接收的最少數據量有三種[5，6]：、以及。其中N是接收數據量。本文針對固定的原始數據比特K=512比特，當接收到的編碼分組個數不同時得到的譯碼效果如圖3所示。

圖3中顯示了接收數據分別為以上三種情況時的譯碼性能。由圖可以看出，隨著接收端收到的數據比特數的增加，譯碼失敗概率在減少，當收到的數據比特數在接近K值時，該概率減少非常迅速，之后速度下降，基本維持穩定。在收到 個編碼分組時效果最好，可以得到最佳接收數據至少為。而且，對于一定的原始數據信息，并不是收到的編碼分組越多，譯碼概率就越高，是取決于其中度數1的編碼分組S的個數。

2.3 譯碼失敗概率具體值的研究

噴泉碼的譯碼概率和以下幾個因素有關：（1）收到編碼分組的個數。（2）度數為1的編碼分組個數。因為噴泉碼是一種無碼率的碼，可以生成無窮多個編碼分組，能夠保證接收端有足夠的編碼分組成功譯碼。Luby指出，選擇一個合適的參數c后（本文得出最優參數c=0.2），當接收端收到個編碼分組時便能以高概率成功譯碼，該譯碼成功的概率在Luby的理論上的理想值為1-，但實際過程中做不到。經過本文的研究仿真，得出在Luby理論下的譯碼失敗概率平均值為10-2數量級左右，而使用噴泉碼最初的理論值以及使用（該值是僅僅保證接收端可以開始進行譯碼到完成所需的編碼分組個數，并不能保證高概率）時，譯碼失敗概率平均值則比Luby理論下的值大，如圖4所示。

由圖4可得，接收數據量為 和時其譯碼失敗概率在～數量級之間，波動相對較大，而且當收到時較效果好。在具體數值上，平均值基本為10-2數量級左右，如表1所示。而接收數據量為時，其譯碼失敗概率比較大，但較平穩，為10-1左右。

3 數字噴泉碼的進一步研究

數字噴泉碼的應用環境只能是刪除信道，而理想的刪除信道是不存在的。在實際應用過程當中，糾錯能力較強的噪聲信道近似于刪除信道，那么可以設想，在實際應用時，可以將數字噴泉碼與糾錯能力較強的糾錯碼進行級聯，從而體現出數字噴泉碼的性能。如圖5所示

該圖是數字噴泉碼在實際當中應用的一種可能模型。其中由糾錯碼編碼到糾錯碼譯碼部分相對數字噴泉碼來說相當于刪除信道，因為糾錯碼對信道進行了“改造”。只要糾錯碼的糾錯性能達到一定要求，就能體現出數字噴泉碼在通信當中的優越性能。其中糾錯碼可以采取Turbo碼，LDPC碼等糾錯性能較好的碼。

4 結論

數字噴泉碼是在前向糾錯碼的基礎上發展而來的，它應用于刪除信道，且不需要顧及信道中刪除事件的統計特性。它在發送端發送無窮多個編碼分組，只要接收端收到一定數量的編碼分組數據，就能夠以高概率成功譯碼。數字噴泉碼在提出的時候只是一個概念，并沒有可行的算法，而LT是第一種實現的數字噴泉碼，它充分繼承了數字噴泉碼的優點，但是LT碼的編譯碼復雜度比較大，實時性較差。同時，刪除信道也是數字噴泉碼理論的一個重要組成部分，本文首先對LT碼的各個方面性能及參數做了較深入的研究，給出了LT碼的一些結論，并且提出了一種可能的刪除信道應用模型，當應用糾錯能力較強的碼時，可以實現數字噴泉碼的實際應用。在后續的研究當中，需要對數字噴泉碼的算法進行改進，使其編譯碼復雜度下降，提高在應用時的可靠性和有效性。

參考文獻

[1]盧守信.噴泉碼技術研究[J].信息科技，2007，6：101-102.

[2]張宗橙.糾錯編碼原理和應用[M].北京：電子工業出版社，2003，4：25-27.

[3]熊鷹，金心宇.前向糾錯編碼傳輸機制的優化[J].江南大學學報，2006，4：127-131.

[4]MacKay D J C.Fountain codes[J].IEE Proc.Commun，2005，152（6）：1062-1068.

[5]AminShokrollahi.FountainCodes[J].EPFL.2003.

[6]Michael Luby.LT Codes[C].Proceedings of the 43r Annual IEEE Symposium on Foundations of Computer Science，2002：1-10.

[7]王仕奎，張愛清.基于噴泉碼的分布式魯棒存儲[J].武漢大學學報：工學版，2007，6.

[8]孟慶春，王曉京.Raptor Code預編碼技術的研究[J].計算機工程，2007，1.

[9]Amin Shokrollahi.Raptor Codes[C].IEEE Transactionson Information Theory，2006，52（6）：2551-2567.