一種短碼長LT碼的度分布選擇優(yōu)化方法

梁桃紅 何麗 張洪革

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

關(guān)鍵詞：LT碼；度分布函數(shù)；選擇優(yōu)化；短碼長

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

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

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

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

1 常用度分布

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

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

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

2 優(yōu)化設(shè)計

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

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

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

2.2 步驟2：確定各類度分布參數(shù)

根據(jù)步驟1中的分析，通過實驗參數(shù)。

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

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

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

根據(jù)步驟3的推導和實驗，可以確定在時應(yīng)選擇截短度分布函數(shù)，其參數(shù)設(shè)置為0.67。

3 仿真實驗

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

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

4 結(jié)語

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

參考文獻

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

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

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

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