一種短碼長LT碼的度分布選擇優化方法

梁桃紅 何麗 張洪革

摘要：在LT碼碼長較短的條件下，針對采用基于傳統魯棒孤子分布的編碼與BP譯碼算法時性能欠佳的問題，提出了一種基于譯碼開銷的度分布選擇優化方法。首先，在譯碼算法確定為BP譯碼、編譯碼效率由度分布決定的前提下，分析了各類常用度分布的數學表達形式與特點。其次，設計了一種不同碼長下的度分布選擇優化算法，將度分布函數與碼長相互匹配。最后，通過仿真實驗證明了在不增加編譯碼復雜度的前提下，該方法可以準確適配碼長，并有效提升編譯碼效率。

關鍵詞：LT碼；度分布函數；選擇優化；短碼長

中圖分類號：TN911.22 文獻標識碼：A 文章編號：1007-9416（2018）07-0063-02

數字噴泉碼是一種新的信道編碼技術，它的提出主要是為了解決大規模數據傳輸和廣播/多播等業務的可靠性問題。Luby M.等人于1998首先提出了數字噴泉碼的概念，但當時并沒有給出可行的噴泉碼設計方案。直到2002年，第一種具有現實意義的通用噴泉碼——LT碼[1]才被提出。與傳統前向糾錯編碼（FEC）技術相比，噴泉碼的優勢在于：首先，噴泉碼作為一種無碼率碼，方案設計不受信道環境影響，僅僅取決于原始數據分組的大小，接收端接收到一定數量的編碼分組就能恢復全部原始數據分組。其次，噴泉碼能夠匹配不同的信道條件，這是因為發送端可以產生任意數量的編碼分組，不同用戶根據信道條件接收一定的編碼分組即可恢復全部原始數據，用戶之間互不影響。

噴泉碼適用于大規模數據傳輸廣播/多播、深空通信、分布式數據存儲、軍用抗干擾傳輸等方面。目前，相關研究工作主要集中于度分布函數設計[2]、編譯碼方式設計[3，4]等方面。值得注意的是，在碼長較短的條件下，由于編碼分組的數量較小，其分布不能夠逼近常用的、以極限性能為目標的魯棒孤子度分布，從而導致其譯碼性能欠佳，譯碼冗余開銷偏離理論值。因此，在碼長較小時，應進一步優化選擇度分布函數。

基于以上背景，本文針對短碼長LT碼提出了一種度分布優化選擇方法。在簡單介紹LT碼的編譯碼過程之后，給出并分析了各類常用度分布函數的數學表達形式與特點；根據分析結果，提出了一種以降低譯碼冗余為目標的度分布函數的優化選擇方法，從而在不增加編譯碼復雜度的前提下，實現譯碼性能的優化。

1 常用度分布

眾所周知，由LT碼的編譯碼過程可知，度分布函數以及譯碼算法的選擇是影響編碼性能的兩個主要因素。因此，在譯碼算法確定的前提下，度分布函數成為決定LT碼性能的關鍵。常用的度分布函數，即魯棒孤子分布如下[1]：

如公式（1）所示，歸一化參數，，是一個常數，表示譯碼失敗概率的上界。當接收到個編碼分組后，能夠保證成功譯碼概率的下界是。

在碼長較短的前提下，魯棒孤子度分布的所需譯碼開銷與碼長相比較大。取參數，分別取0.05，0.005和0.0005，即對應譯碼成功概率下界分別為95%，99.5%和99.95%，可計算出不同碼長下的譯碼所需符號相對冗余余值。隨著碼長的增加，譯碼所需要的編碼符號相對冗余逐漸減小，但是在短碼長條件下，冗余值維持在較高水平。因此，在短碼長條件下，需要通過對度分布的優化，提升冗余性能。

2 優化設計

根據碼長不同，首先需要分析各種度分布函數可行參數，然后通過理論分析或者仿真確定各類度分布參數，最后比較各種度分布函數在相對較好的參數下的性能，從而最終確定選擇的度分布函數及其參數。接下來以碼長為例，詳細說明度分布選擇優化算法的流程。

2.1 步驟1：各類度分布函數可行參數范圍分析

（1）對于理想孤子度分布，因為其度分布函數沒有截短，各度的函數值只與碼長有關，因此不需要分析參數的可行性。（2）對于魯棒孤子度分布，是魯棒性參數，是譯碼失敗概率上界參數，這兩個參數決定了中間參數，并將影響以的下界成功譯碼所需的編碼包長度。（3）對于消減魯棒孤子度分布，由于需要計算，因此需要滿足的約束，當時，取不同的常用參數和時，的取值如表1中所示。當時，參數和是可行的。（4）對于截短度分布，截短位置，需要滿足，可以推出。對于不同的值，可行范圍不同。（5）對于開關度分布，開關點參數可以根據需要調整。

2.2 步驟2：確定各類度分布參數

根據步驟1中的分析，通過實驗參數。

2.3 步驟3：仿真比較不同度分布函數的性能

按表2中的參數進行設置，進行蒙特卡洛仿真次數為10000的仿真，傳輸過程丟包率設置為20%。理想孤子度分布性能最差；魯棒孤子度分布與消減魯棒孤子度分布性能優于理想孤子度分布；截短度分布與開關度分布可以獲得比較理想的性能，綜合譯碼開銷性能與誤包率性能的比較之后，截短度分布的性能更好。

2.4 步驟4：確定選擇的度分布函數及其參數

根據步驟3的推導和實驗，可以確定在時應選擇截短度分布函數，其參數設置為0.67。

3 仿真實驗

為在不同碼長條件下得到適用的度分布函數，本章節通過蒙特卡洛仿真驗證不同度分布函數的性能，針對不同的碼長，重復前述度分布優化選擇方法。蒙特卡洛仿真次數設定為10000，譯碼算法為BP算法。圖1與圖2、分別顯示了與時譯碼性能曲線。其中每張圖的（a）子圖展示的是系統誤包率性能與譯碼開銷的關系；（b）子圖則展示了系統成功譯碼概率與譯碼開銷的關系。

由圖1可知，當時，截短度分布與開關度分布的性能幾乎一致，再結合圖2，能夠得到如下結論：在碼長小于20時，LT編碼時應選擇截短度分布，從而獲得相對更好的成功譯碼概率與誤包率性能。

4 結語

短碼長LT碼的度分布設計與選擇問題是業界研究的重點。本文分析比較常用的度分布函數，并根據不同碼長，設計了一種度分布函數選擇優化方法。本文提出的度分布選擇優化方法在不增加編譯碼復雜度的前提下，能夠有效提升譯碼效率，減小譯碼冗余，能夠對LT碼的實際工程應用有一定的指導意義。

參考文獻

[1]LUBY M. LT codes [C]// Proc of the 43rd Annual IEEE Symposium on Foundations of Computer Science，2002，pp：271-282.

[2]敖珺，盧亞軍，馬春波.基于短碼長的噴泉碼度分布設計[J].計算機與數字工程，2015，43（12）：2101-2105.

[3]時琳川，徐松毅，杜文舉. 窄帶通信中基于Jordan 標準型矩陣的噴泉碼研究[J].無線電通信技術，2017，43（1）：19-22.

[4]馮欣，張艷，賈志成.噴泉碼中LT碼的二次譯碼算法[J]. 計算機工程，2012，38（6）：291-293.