基于隨機置換展開與停止集的LT碼聯合編譯碼算法

焦健，楊志華，顧術實，周潔，張欽宇

（哈爾濱工業大學 深圳研究生院，廣東 深圳 518055）

1 引言

近年來，LT碼作為一種能夠以任意概率逼近香農極限的無碼率糾刪碼，受到分組通信業務的廣泛關注[1]。它將帶有檢錯機制的分組交換信道等效為刪除信道，將傳統糾刪編碼的處理對象拓展到了數據分組，形成了一種無需反饋鏈路、高效可靠的前向糾刪機制。尤其是碼長較短的LT碼(103數量級)，適用于節點運算能力受限的容遲網絡場景的信息糾錯(如物聯網、深空探測等)。LT碼的編譯碼算法的漸近性能取決于輸出度分布的選擇[2,3]，度的平均值是衡量編碼冗余與編譯碼復雜度的關鍵參數，目前采用的經典輸出度分布是魯棒孤波分布及其優化解。Luby設計了一種低復雜度的消息傳遞(BP,belief propagation)譯碼算法，譯碼的復雜度與編碼Tanner圖的關聯邊數成正比，當輸入節點數量較大時，BP譯碼算法對符合泊松分布輸入度分布的譯碼性能最優[4,5]。但是，LT碼的隨機編碼方式以及生成矩陣的稀疏特性，使其在碼長較短時無法保證對輸入節點的全選覆蓋，需要較大的編碼冗余才能保證恢復所有的輸入節點。

針對這個問題，通過引入修正的期望可譯集(ERS)可得到短碼長LT碼的離散密度進化度分布[6]，但該分布只能保證恢復出盡量多的原始數據分組，而不是恢復出整個原始文件。Hyytia引入馬爾科夫過程進行建模，通過較高復雜度的算法設計，給出了極短碼長條件下(小于 100)LT碼的最優解[7]。Zhu提出了一種度分布優化算法[8]，該算法給出了中短碼長的次優LT碼度分布。而Huang等人利用混沌算法和Logistic映射改進短碼長LT碼的編碼算法，在編碼冗余較大時(0.37～0.45)獲得了性能優化[9,10]。Gong提出了LT碼的Tanner圖展開PEG(progressive edge-growth)算法[11]，盡可能選擇具有最小度數的未被覆蓋的信息節點與輸出節點相連，并試圖獲得輸入節點的泊松分布，該算法對于構造實用短碼長的LT碼提供了有益的探索。在LT碼譯碼研究方面，許多研究把 Turbo、LDPC碼的似然譯碼技術引入到噴泉碼的譯碼算法中，以解決BP譯碼算法效率不高的問題。Sarwate提出了類似最大似然的譯碼算法[12]，充分利用信道狀態信息等軟信息設計了似然譯碼算法。Heo提出了一些改進算法降低了譯碼復雜度[13]，但實現起來較為困難。Kim提出了Raptor碼的漸增高斯譯碼算法[14]，通過設計類似高斯譯碼矩陣求逆的方式進行譯碼，獲得譯碼性能與譯碼算法復雜度較好的折衷，為噴泉碼的改進提供了一種可借鑒的思路。以上分析表明，隨機編碼方式使得短碼長LT碼需要較高的編碼冗余才能保證接收端能夠恢復所有的原始信息。而目前普遍采用的BP譯碼算法啟動門限較高，需要收到絕大部分的編碼分組才能進入譯碼瀑布區。本文綜合考慮上述短碼長LT碼的優化設計問題，提出了基于隨機置換展開與停止集的聯合編譯碼算法，限制編碼過程中節點的隨機連接性，充分利用 BP譯碼過程的剩余信息，有效地提高了短碼長 LT碼的編譯碼性能。

本文第2節針對編碼Tanner圖，設計了針對短碼長LT碼的隨機置換展開(RPEG, random permute edge-growth)算法，給出了算法的可譯碼概率與所需的編碼冗余理論表達式。第3節針對BP譯碼算法效率不高的問題，設計了停止集高斯譯碼(SSGE,stopping set gaussian elimination)算法。第4節針對所設計的聯合編譯碼算法進行了仿真分析和結果討論。最后給出了本文的結論。

2 基于隨機置換展開的編碼算法

給定 LT碼的輸入分組數據向量 S: S={S1,S2,… ,Sk}，輸出數據向量D:D ={ D1, D2,… ,Dn,…}和輸出度分布生成函數Ω(x):Ω(x) =，?i為重量為 i的輸出分組在全體輸出中的歸一化比例，則LT碼的編碼過程可表示為

其中，G為表征編碼關系的k×n階生成矩陣。根據式(1)及矩陣理論可知，當且僅當矩陣 G行滿秩，接收端才可能譯碼成功，即輸入節點全選是其必要條件。

定義隨機編碼方式的LT碼參數(k, n, ?)，輸入節點個數為k，輸出編碼分組數為n，以概率?i產生一個重量為i的輸出分組(即Tanner圖中與該輸出分組連接的邊數量為i)，則一個輸出分組的平均關聯邊數量為=Ω'(1)，因此 Tanner圖共有nΩ' (1)條連接邊。而一個特定輸入節點在一次隨機編碼過程中未被選中的概率為(1- 1 k)，則影響LT碼可譯碼性能的輸入節點漏選概率 P可由下式計算

以具有稀疏特性的魯棒孤波分布(RSD, robust soliton distribution)為例，設不可譯概率參數δ，譯碼算法可靠性參數 c，定義R =(k δ)，則度分布生成函數?(x)為[15]

將式(3)代入式(2)可計算出保證 LT碼可譯碼概率達到 10?4時，編碼端的輸入節點數量與對應的最少編碼分組個數，表1給出了碼長為1000以下的計算結果(取c=0.03，δ=0.05)。由表1可以看出，對于103及更小碼長的LT碼，使用隨機編碼方式的LT碼不可避免地需要增加編碼冗余以保證譯碼可靠性。

表1 魯棒孤波度分布譯碼失敗概率10?4所需編碼分組數量

針對此問題，本文提出基于隨機置換展開(RPEG)編碼算法，該算法通過限制LT碼隨機編碼方式的隨機性，提高碼字距離，以較小的編碼冗余達到輸入節點的全選覆蓋。設 RSD度分布的重量為?w，定義LT編碼分組Di,j，其中，i≤N表示編碼分組的數量，j表示第j個RPEG的置換展開區間；{Di,j}表示 Di,j中包含的原始分組；在第 j個RPEG置換展開區間的編碼向量選擇空間為Sj，且累計的原始編碼分組個數為Wj，具體算法流程如圖1所示。

Tanner圖如圖2所示，由算法步驟及圖2(a)可知，Tanner圖的輸入節點是近似于均勻分布的，而輸出節點度分布仍維持所選取的魯棒孤波分布，RPEG算法在沒有改變度分布和編碼復雜度的前提下，提高了碼字距離，保證了編碼分組對原始信息的隨機均勻覆蓋，圖2(b)直觀地體現了其優化效果。Tanner圖中小環的存在嚴重影響LT碼的譯碼性能，本文提出的RPEG編碼算法盡力抑制編碼過程中小環的產生。但在抑制小環的同時，需要注重保留碼字之間的一定相關性，避免BP譯碼過程提前終止，以保證對完全無環的Tanner圖的譯碼可靠性。

通過小環產生概率的推導給出對此問題的分析。給定隨機編碼方式的LT碼參數(k, n, ?)，則k×n階編碼生成矩陣G中度為i的列向量生成概率為

圖1 隨機置換展開編碼算法流程

而生成矩陣G中存在環長為4即存在另一列與該列在2個相同的行位置為1，設該列的度為j，顯然有i, j＞1，則這兩列具有4環的概率Pgirth4(i,j)為

圖2 隨機置換展開編碼算法的Tanner圖

則對于k×n階編碼生成矩陣G存在4環的概率Pgirth4為

由RPEG編碼算法可知，構造的k×n階編碼生成矩陣GRPEG近似地分為nΩ'(1)k個隨機置換展開區間，通過設置可在同區間內完全避免4環的產生。設α=k Ω'(1)，根據式(6)可近似地推導出RPEG編碼的4環生成概率Pgirth4_RPEG為

由式(7)可以看出，控制參數α可以實現性能改進，即通過降低輸出節點的平均度'(1)Ω來降低環的生成概率，并且不會對式(2)計算漏選概率產生影響。以編碼復雜度為常數的弱魯棒分布(WRSD)為例，其生成函數為[3]

3 面向隨機置換展開編碼算法的BP譯碼算法改進

針對隨機置換展開編碼的LT碼，本文采用具有較低計算復雜度的BP譯碼算法進行譯碼。如果想要保證BP算法的譯碼過程順利進行，必須滿足每一步譯碼之后譯出新的度為 1的分組，否則 BP譯碼中止。因此，譯碼過程中每一步的失敗概率是衡量BP譯碼算法的重要性能指標。

定義1 LT碼的BP譯碼狀態為(u, r, c)，u為此刻未譯碼的輸入節點數量(u≤k)，r為該時刻BP譯碼傳遞波紋算子(即譯碼緩存中度為 1的包)，c為該狀態下緩存中度大于1的分組。則譯碼器對于一個度為i的輸出分組Di進行譯碼，在該譯碼狀態下能夠成功恢復出一個新的輸入節點的概率p(i, u)為[2]

在式(9)中，度為i的編碼分組Di所連接的輸入節點包括:1) 1個輸入節點，是第(k?u)次BP譯碼中即將譯出的輸入節點；2) 1個輸入節點，包含在u個未譯碼的輸入節點集中；3) (i?2)個輸入節點，包含在已被譯碼的(k?u?1)個輸入節點集中。結合LT碼的度分布?，可獲得此狀態下譯碼器能夠譯出一個新的輸入節點的概率。

式(10)僅包含了此狀態下被譯碼的編碼分組，其所連接的輸入節點的一種組成情況。

對于度為i的編碼分組Di所連接的另外一種輸入節點組成:1) 1個輸入節點，在第(k?u)次BP譯碼時即將被譯出的輸入節點；2) (i?1)個輸入節點，包含在已被譯碼的(k?u)個輸入節點集中，概率為

同時，還存在著編碼分組Di所連接的第3種輸入節點組成，即該編碼分組中所有的輸入節點都已經在第(k?u)次BP譯碼之前被譯出的情況

聯立式(10)～式(12)即可獲得 BP譯碼的狀態轉移概率pu[15]

給定譯碼器的狀態轉移概率pu，可以推出譯碼器各個狀態轉移到BP譯碼停止狀態(u＞0, r=0, c＞0)的概率，此概率即為BP譯碼在每一步譯碼過程中可能的失敗概率。

針對BP譯碼過程的提前中止問題，本文充分利用BP譯碼過程中的剩余信息，采用高斯消去(GE,gaussian elimination)譯碼算法重新啟動譯碼過程，保證譯碼的順利完成，該算法既解決了BP譯碼停止問題，也降低了全局采用GE譯碼的譯碼復雜度。

圖3 RSD分布隨機編碼的BP停止集

圖4 RSD分布RPEG編碼的BP停止集

圖5 WRSD分布RPEG編碼的BP停止集

定義2 給定編碼冗余下，BP譯碼提前終止時剩余的所有度大于1的編碼節點集合稱之為停止集H。圖3～圖5給出了原始分組數量分別100, 300, 500,800, 1000條件下，運行10000次BP譯碼(迭代20次)在不同編碼冗余下的歸一化停止集大小。可以看出，1000以下的短碼長LT碼運用BP譯碼算法，譯碼停止集在編碼冗余接近0.25之后才逐漸消失，在編碼冗余為0.1～0.2區間里，歸一化的停止集接近0.2左右，采用停止集高斯譯碼算法(SSGE)，存在很大的可利用空間。

基于BP譯碼的停止集，下面給出具體的算法模型，設接收端正確收到的編碼分組構成的生成矩陣為G，則流程如圖6所示。

圖6 停止集高斯譯碼算法流程

相對于采用全局高斯譯碼算法，本算法的譯碼開銷與前半段BP譯碼過程能恢復的原始節點數量有關。由圖3可知，隨著BP譯碼能恢復絕大部分的原始節點，譯碼失敗時G中剩余的停止集H較小，所帶來后續高斯譯碼的譯碼開銷相對較小。若歸一化停止集比例設為η，對于采用 RSD分布編碼的SSGE譯碼開銷為O( nlog(k)+(η k)3)，而采用WRSD分布的 SSGE譯碼開銷為O( n log(+(ηk)3)，對于特定的編碼冗余(如0.25)，則增加的譯碼復雜度幾乎可忽略。

4 仿真結果討論

本文中把譯碼失敗次數占總仿真次數的比例，即譯碼失敗概率(decoding failure rate)作為衡量LT碼性能的重要指標，通過仿真對比分析提出的RPEG編碼算法，SSGE譯碼算法以及采用聯合編譯碼算法的性能，表2給出仿真參數配置。

表2 蒙特卡洛仿真參數配置

4.1 RPEG編碼方案對于BP譯碼算法可譯碼性能的改善

圖7給出了RPEG編碼方式下RSD和WRSD 2種度分布在原始數據數量為 k=100, 300, 500,800, 1000時，隨著編碼冗余變化所對應的譯碼失敗概率曲線。結果表明，碼長為1000和800的LT碼采用RPEG編碼算法后，以增加一個可選輸入節點緩存空間的代價，只需0.3的編碼冗余即可達到10?4的譯碼失敗概率。與表1中所需編碼冗余比較，明顯提高了103及以下碼長的BP譯碼性能。因此，RPEG編碼方案可以充分保證輸出編碼數據的可解性，對于編譯碼緩存空間受限和實時性要求較高的可靠傳輸業務具有廣泛的應用前景。

RSD的編碼開銷為O(nlog(k))，WRSD的編碼開銷為O(nlog(1/ε))，表3進一步給出了對應碼長的RSD與WRSD的平均度，其中，WRSD的平均度由參數ε唯一確定，而RSD的平均度隨著輸入節點 k的增加以log(k)增加。而圖7(a)的WRSD與圖5(b)RSD的BP譯碼性能非常接近，甚至在某些編碼冗余點上較 RSD的譯碼性能稍好，驗證了式(7)描述:通過降低LT編碼分組的平均度，能增大RPEG編碼過程中置換展開的空間，從而降低小環產生的機率，獲得BP譯碼性能的提升。

圖7 RPEG編碼的BP譯碼性能

表3 RSD與WRSD不同碼長的平均度

4.2 RPEG編碼算法在不同信道條件下的譯碼性能

給定發送端輸出n=2k數量的LT編碼分組，以隨機刪除信道的分組丟失率作為信道參數，接收端能接收的分組數量從 k增加到 1.6k，圖 8給出了RPEG編碼的LT碼在不同信道參數條件下(分組丟失率變化)的譯碼性能。可以看出，在信道逐漸變差時，RPEG算法的編碼輸出分組仍然能保持LT碼接收到一定數量編碼分組后，以較高的概率恢復全部原始信息。這是RPEG編碼算法與類LDPC編碼結構或PEG技術相比，其優勢所在。后2種類似固定編碼結構的算法在高分組丟失率的環境下，無法應付信道中的突發差錯，譯碼性能急劇下降。而RPEG編碼算法具有隨機編碼特點，在面臨信道條件變差時性能上更趨穩定[16,17]。進一步對比圖8(a)與圖 8(b)可發現，WRSD在分組丟失率大于0.25時，已無法達到10?4的譯碼失敗概率，而相同條件下 RSD可對抗 0.325左右的分組丟失率。這是由于RSD的平均度較高，比WRSD分布通過RPEG編碼置換展開的區間更多，因此發生分組丟失時，仍有相當數量的展開區間維持完整以保護譯碼性能的頑健性。

圖8 隨分組丟失率變化的RPEG編碼BP譯碼性能

4.3 隨機編碼方式下SSGE譯碼算法的性能比較

圖7對比了在碼長k≤1000的LT碼采用RSD隨機編碼方案下，不同譯碼算法的譯碼失敗概率。從圖9(a)可以看出，BP譯碼算法需要0.5以上的編碼冗余，才能達到10?4的譯碼失敗概率。隨著碼長降低，所需的冗余進一步加大。而圖9(b)的GE譯碼算法，在相同的編碼冗余下能達到稍低的譯碼失敗概率，相比于BP算法更接近可譯碼極限。圖9(c)的SSGE譯碼性能曲線與圖9(b)幾乎一致，證明第3節給出的SSGE算法在BP譯碼算法的基礎上通過增加有限的譯碼復雜度，使得LT碼的譯碼性能逼近最大似然譯碼的性能。

圖9 RSD分布隨機編碼的BP、GE、SSGE的譯碼性能比較

4.4 RPEG編碼算法與 SSGE譯碼算法的聯合編譯碼性能

在以上實驗的基礎上，聯合采用RPEG編碼算法與SSGE譯碼算法，分析其對短碼長LT碼性能的改善作用。圖10給出了短碼長LT碼采用RPEG編碼與SSGE譯碼算法后的譯碼失敗概率。對比圖10與圖7、圖9可以看出，聯合編譯碼算法在沒有改變度分布的前提下，通過對Tanner圖連接邊過程的隨機性進行部分限制，提高了碼字距離，獲得對原始信息的隨機均勻覆蓋，提高了短碼長下生成矩陣G的行滿秩概率。聯合算法隨著輸入節點的增加迅速地提高了LT碼的譯碼性能，對于800和1000的碼長只需要不超過0.1的編碼冗余，就能達到10?4的譯碼成功概率。而對于500和300碼長也降低了20%的編碼冗余開銷，算法的計算復雜度與直接使用GE相比降為O(η3)。

圖10 RPEG編碼與SSGE譯碼的聯合算法

5 結束語

針對短碼長(103以下)LT碼設計中，在保證較穩定的譯碼恢復概率時，需要增加編碼冗余的問題，本文設計了RPEG算法以限制編碼矩陣Tanner圖連接邊的部分隨機性，使得輸入節點變為近似均勻的度分布，提高了碼長為103以下短碼長噴泉碼的可譯碼性能。在此基礎上，充分利用了BP譯碼算法的剩余信息，設計了基于停止集的SSGE譯碼算法，實現了在接收編碼冗余0.2以上的條件下，以約等于GE譯碼開銷O(η3)的計算復雜度獲得最大似然的譯碼性能。仿真結果表明，在保留LT碼無碼率特點的情況下，采用上述聯合編譯碼算法，相對于傳統的 LT碼編譯碼算法具有較大的性能優勢，實現了短碼長LT碼設計中編碼冗余與譯碼性能之間的折衷。未來將從理論分析角度深入研究LT碼字中小環與BP譯碼的關系，以探明LT碼BP可譯的充分條件，并進一步提高RPEG算法編碼性能。

[1]慕建君,焦曉鵬,曹訓志.數字噴泉碼及其應用的研究進展與展望[J].電子學報, 2009, 37(7):1571-1577.MU J J, JIAO X P, CAO X Z.A survey of digital fountain code s and its application[J].ACTA Electronica Sinica, 2009, 37(7):1571-1577.

[2]LUBY M.LT codes[A].43rd Annual IEEE Symposium on Foundations of Computer Science[C].Vancouver, BC, Canada, 2002.271-282.

[3]SHOKROLLAHI A.Raptor codes[J].IEEE Transactions on Information Theory, 2006, 52(6):2251-2567.

[4]MACKAY D J.Fountain codes[J].Proceedings of IEEE Communication.2005, 152(6):1062-1068.

[5]SHOKROLLAHI A.New sequences of linear time erasure codes approaching the channel capacity[A].Proceedings of 13th Conference on Applied Algebra, Error Correcting Codes, and Cryptography[C].Springer Verlag,1999.65-76.

[6]ZHU H J, ZHANG C, LU J H.Designing of fountain codes with short code-length[A].IWSDA 2007[C].2007.65-68.

[7]HYYTIA E, TIRRONEN T, VIRTANO J.Optimal degree distribution for LT codes with small message length[A].Infocom 2007[C].2007.2576-2580.

[8]朱宏鵬,張更新,李廣俠.衛星數據廣播分發系統中的LT的研究[J].通信學報.2010, 31(7):122-128.ZHU H P, ZHANG G X, LI G X.Research of LT code in satellite data broadcasting system[J].Journal on Communications, 2010, 31(7):122-128.

[9]黃誠,易本順.基于拋物線映射的混沌LT編碼算法[J].電子與信息學報.2009, 31(10):2527-2530.HUANG C, YI B S.Chaotic LT encoding algorithm based on parabolic map[J].Journal of Electronics & Information Technology, 2009,31(10):2527-2530.

[10]黃誠,易本順.噴泉碼的 Logistic映射實現[J].北京郵電大學學報,2009, 32 (1):103-106.HUANG C, YI B S.Implementation of fountain codes using Logistic map[J].Journal of Beijing University of Post and Telecommunications,2009, 32 (1):103-106.

[11]龔茂康.中短長度 LT碼的展開圖構造方法[J].電子與信息學報.2009, 31(4):885-888.GONG M K.Unfolding graphs for constructing of short and moderate-length LT codes[J].Journal of Electronics and Information Technology, 2009, 31(4):885-888.

[12]SARWATE A.Rateless coding with partial CSI at the decoder[A].IEEE Information Theory Workshop[C].2008.378-383.

[13]HEO J, KIM S.Low complexity decoding for raptor codes for hybrid-ARQ systems[J].IEEE Transactions on Consumer Electronics,2008, 54(2):390-395.

[14]KIM S, KO C.Incremental gaussian elimination decoding of raptor codes over BEC[J].IEEE Communication Letters, 2008, 12(4):307-309.

[15]MAATYOUK E, SHOKROLLAHI A.Analysis of the second moment of the LT decoder[A].ISIT2009[C].Seoul, Korea, 2009.2326-2330.

[16]林廣榮,林新榮,依娜等.基于 LDPC碼的數字噴泉編碼[J].電子與信息學報.2008, 30(4):822-825.LIN G R, LIN X R, YI N, et al.Digital fountain base on LDPC code[J].Journal of Electronics and Information Technology, 2008,30(4):822-825.

[17]林廣榮,依娜,董明科等.基于停止集的噴泉編碼有限長性能估計[J].電子與信息學報, 2008, 30(11):2634-2637.LIN G R, YI N, DONG M K, et al.Finite length analysis of fountain codes based on stopping set[J].Journal of Electronics and Information Technology, 2008, 30(11):2634-2637.