LT碼的增強型BP譯碼算法

楊曉非，季瑞軍，黃　勝，張春明

(重慶郵電大學 光通信與網絡重點實驗室，重慶 400065)

LT碼的增強型BP譯碼算法

楊曉非，季瑞軍，黃勝，張春明

(重慶郵電大學 光通信與網絡重點實驗室，重慶 400065)

摘要:傳統的LT碼采用的BP譯碼算法，當不存在度1編碼分組時會導致BP譯碼算法失敗，不能繼續譯碼。為了提高譯碼的成功率，分析了剩余編碼分組的結構，提出LT碼的再次譯碼算法(Again Belief Propagation decoding algorithm，ABP)。算法主要思想是BP譯碼失敗后，查找滿足條件的可譯結構，繼續譯碼，直到譯碼成功或再次失敗，如果失敗重復上面步驟直到譯碼成功或可譯結構不存在，從理論上分析了可譯結構存在的概率。仿真結果顯示譯碼成功率得到提高。

關鍵詞:LT碼；BP譯碼；譯碼效率；增強型譯碼算法

數字噴泉碼在1998年被提出[1]。LT碼是由M.Luby等人針對刪除信道設計出的第一個實用的數字噴泉碼[2]，之后數學家Shokrollahi針對LT碼的缺點改進后提出了性能更好的Raptar碼[3]，數字噴泉碼在廣播通信[4]，針對數據擁有不同優先等級的視頻傳輸[5]，復雜信道環境的深空通信[6]，當前熱門的數據安全存儲[7]等領域具有廣泛的應用前景。LT碼譯碼算法采用BP(置信傳播)譯碼算法，然而，譯碼很可能因為查找不到度1的編碼分組而導致失敗，影響了數據傳輸質量。由于傳輸質量的要求，通常需要接收多于原始信息分組數量的編碼分組才能成功恢復原始信息分組，把多接收的編碼分組與信息分組的長度之比稱為譯碼開銷。

文獻[8]就如何提高LT碼等無碼率編碼算法的譯碼效率問題進行了討論，從減少開銷得到的復雜度出發，文章中提出了一種提前結束譯碼的算法。文獻[9]對BEC上的Raptor碼譯碼方案進行了討論，提出一種可以在不損失性能的情況下有效地減小譯碼時間的方案即增量高斯消去的譯碼方案，相對于高斯消除算法，該算法在譯碼矩陣中增加一些行，這可以保證矩陣的三角化成功。文獻[10]對無碼率碼的生成方式進行了改進，討論了無碼率碼在迭代譯碼時的一些獨有特性。筆者分別在相等、不等差錯保護和有限長碼字情況下，分析了LT碼和Raptor碼在進行最大似然譯碼算法譯碼時的錯誤碼元概率的上下界，進行LT解碼時，接收端可以根據接收到的編碼分組的個數來譯出原始信息的不同部分。

深入分析譯碼的整個過程可以知道，譯碼過程可以轉換為解一次多元方程組的過程，譯碼即是求解變量元素，這里的變量元素就是信息分組，只要方程組系數矩陣(譯碼矩陣)滿秩，方程組有解，理論上譯碼是可以完成的。由于BP譯碼算法只是查找度數為1的編碼分組，BP譯碼算法失敗時并不意味著系數矩陣不滿秩，即剩余的編碼分組仍然具有可譯性。對于這種方程組可解但BP譯碼由于檢測不到度1編碼分組而失敗的情況，本文提出一種更加完善的BP譯碼算法，經過仿真驗證可以看出確實改善了譯碼的效果，譯碼成功率得到了提高。

1LT碼編譯碼原理

LT碼：其編碼是由K個符號分組生成任意數量的編碼分組，接收端只需要接收到任意個編碼分組，即可以以一定概率成功解碼全部信息分組。這里，N略大于K，這樣會帶來一定的譯碼開銷。

1.1編碼過程

LT碼的編碼過程如下[2]：

1)根據度分布函數ρ(d)隨機選取整數d作為編碼分組的度數。這里1

2)從K個信息分組等概隨機選取d個并異或得到編碼分組。

重復上面的步驟，直到接收端接收到N個編碼分組為止。編碼過程如圖1所示。

圖1　編碼分組的生成示例

1.2譯碼過程

根據LT碼的定義，接收端接收到個編碼分組即可以開始譯碼，具體過程如下[2]：

1)根據接收到的編碼分組和信息分組的對應關系建立二分圖。

2)遍歷所有的編碼分組，如果存在度1的編碼分組，則可以譯出與之相連的信息分組，若不存在，則譯碼結束。

3)將已經譯出的信息分組的值異或到與之相連的編碼分組中，去掉二分圖中與這個信息分組相連的邊。

4)重復步驟2)和3)直到譯碼停止。若所有的信息分組全部譯出則成功譯碼，否則譯碼失敗。

1.3LT碼的度分布

M.Luby等人提出來兩種編碼分組的度分布，首先是ISD(IdealSolitonDistribution)函數[2]表示為

(1)

在理想情況下，該度分布每次譯碼迭代后恰好有一個度1的編碼包留下，但是實際情況卻是度1的編碼包太少，很有可能在某次迭代后消失，尤其是短碼長的數據很容易在譯碼前期就迭代失敗。

RSD[2]如式(2)～(3)所示

(2)

(3)

在傳統LT碼譯碼迭代會因為沒有度1的編碼分組導致譯碼失敗。實際上剩下的編碼分組是存在可譯性的。本文針對BP譯碼算法的這種漏洞，提出了增強型的BP譯碼算法，在BP譯碼失敗之后查找二分圖中的特殊結構，根據特殊結構譯出其中的一個信息分組，這使BP譯碼算法可以繼續執行。

2增強型BP譯碼算法

圖2是ABP可譯結構示意圖，編碼分組tm的度為i-1，編碼分組tn的度為i，其中3

ABP可譯結構查找算法：遍歷剩余生成矩陣G的任意兩列，異或遍歷迭代中被選中的兩列(對應位置元素異或)，當結果中只有一個元素為1，其余元素為0時，即查找到圖2所示結構。

圖2　結構圖示

圖中編碼分組tm的度為i-1，編碼分組tn的度為i，3

圖3示出了ABP可譯結構查找算法示例。圖3a為BP譯碼算法失敗后的譯碼矩陣G，遍歷矩陣G中的任意兩列，只有圖3a橢圓陰影圈住的兩列符合ABP可譯結構，對矩陣中的這兩列進行異或，得到結果如圖3b所示，然后用該結果去替換ABP可譯結構中度數大的那一列，并且用兩個編碼分組異或的值去替換度數較大的編碼分組，如圖3c所示。

圖3　ABP可譯結構查找算法示例

本算法可以擴展為對3個或3個以上的不同剩余的編碼分組進行的操作，異或3個不同剩余的編碼分組，觀察是否可以產生度為1的編碼分組。但因為有3個編碼分組組成的這種結構的概率低譯碼查找復雜度大，這里不做理論分析和實驗驗證。

2.1ABP譯碼算法具體操作步驟

步驟1：在信息分組未完全恢復的情況下，編碼分組tn中沒有度1的分組則譯碼迭代停止，轉到步驟4。

步驟2：令信息分組sK=tn，更新與tn相連的編碼分組，更新的結果為當前編碼包與tn異或的結果，最后刪掉tn。

步驟3：若信息分組全部恢復則譯碼成功，否則重復步驟1。

步驟4：查找滿足ABP的可譯結構。即遍歷剩余生成矩陣G的任意兩列，異或遍歷迭代中被選中的兩列(對應位置元素異或)，當結果中只有一個元素為1，其余元素為0時，即找到ABP可譯結構，則根據sj=tm⊕tn恢復出結構中的信息分組sj，更新二分圖，重復步驟1；查找不到則譯碼失敗。

圖4是算法流程圖。

圖4　算法流程圖

當檢測到BP譯碼算法失敗時，會進入可譯結構的檢測，更新二分圖也就是生成矩陣，繼續跳回BP譯碼。本算法不但提高譯碼的成功率，而且也減譯碼開銷。

2.2ABP結構存在的概率

這種結構存在的概率可以看作成從箱子中取小球的問題，每個小球取出的概率是相等的。這里裝有N-L小球的箱子，tn可以看成從中取i個小球，取出后放回，tm可以看成從中取出i-1個小球。

對于任意兩個編碼分組符合這種結構的概率為

(4)

對于未處理的編碼分組共有c(N-L,2)個兩兩組合，于是，未處理編碼分組中存在度為i和度為i-1的比編碼符號符合這種結構的總數

(5)

對于不同的度M的取值為

…

(6)

符合度3的編碼分組包含度2的編碼分組的這種ABP可譯結構的個數最多，不受未處理編碼分組數的影響。其他度數的這種結構的個數隨著未處理編碼分組數的減少而增加。由此可知，未處理的編碼分組會以一定的概率符合這種條件。

3仿真分析

仿真與傳統的BP譯碼算法作為對比。選擇理想孤子分布作為編碼的度分布，這里主要考察兩個性能指標，一個是譯碼成功率，當所有的信息符號全部正確譯出時代表譯碼成功；另一個性能指標是成功譯出分組比例，及每次譯碼結束時，成功譯出信息分組占總的信息分組的比例。對信息分組數為1 000和2 000進行1 000次實驗。

圖5是譯碼成功率的仿真圖，橫坐標為譯碼開銷。仿真用的BEC信道，其刪除概率為0.02。由圖可以看出，使用改進算法的譯碼成功率大幅度增加，并且隨著譯碼開銷的增加，改進算法提升的幅度增大。由傳統的LT的編碼特性可知，隨著信息分組數的增加，編碼的度分布函數更加接近于理想孤波分布，所以信息分組數越大，譯碼性能越好。如圖中虛線所示，信息分組數為2 000的LT碼譯碼成功率要大于信息分組數為1 000的LT碼。由圖中實線可以看出，改進算法譯碼額有這樣的趨勢，即信息分組數為2 000的LT碼譯碼成功率要大于信息分組數為1 000的LT碼。

圖5　譯碼成功率仿真圖

圖6是成功譯出分組比例隨譯碼開銷變化的仿真圖。信道模型為二進制刪除信道，刪除概率為0.02。可以看出，成功譯出分組比例與譯碼成功率有相同的趨勢，改進算法成功譯出分組比例要高于傳統的BP譯碼算法。信息分組數為2 000的LT碼成功率譯出分組比例同樣大于信息分組數為1 000的LT碼。

圖6　成功譯出分組比例仿真圖

圖7是譯碼成功率隨譯碼負載變化的仿真圖。信道模型為二進制刪除信道，刪除概率為0.05。由圖可以看出，在相同的譯碼開銷下LT碼的再次譯碼算法的性能優于BP譯碼算法的性能。

圖7　譯碼成功率仿真圖

圖8是成功譯出分組比例隨譯碼負載變化的仿真圖。信道模型為二進制刪除信道，刪除概率為0.05。由圖可以看出，在相同的譯碼開銷下LT碼的再次譯碼算法的性能優于BP譯碼算法的性能。

圖8　成功譯出分組比例仿真圖

4小結

本文針對BP譯碼失敗時其余編碼分組仍然具有可譯性的特點，通過查找編碼分組是否滿足ABP可譯結構，提出LT碼的再次譯碼算法。通過對文中提出的結構進行處理后的到可以滿足BP譯碼算法特點的生成矩陣，重新進入譯碼迭代。仿真結果表明，該算法確實改善了原來BP譯碼的缺點，可以看出譯碼的成功率也得到了提高。本文提出的算法不僅可以用在LT碼中，同樣也可用于其他采用BP譯碼算法解碼的編碼方法。

參考文獻：

[1]BYER J W，LUBY M，MITZERMACHER M，et al. A digital fountain approach to reliable distribution of bulk data[C]//Proc.ACM Sigcomm’ 98 Conference.[S.l.]：IEEE Press，1998.

[2]LUBY M. LT codes[C] //Proc.43rd Annual IEEE Symposium on Foundations of Computer Science. USA：IEEE Press，2002：271-280.

[3]SHOKROLLAHI A. Raptor codes[J]. IEEE Transactions on information theory，2006， 52(6)：2551-2567.

[4]鄧善征，杜興民，楊軍，等.LT 碼在移動多媒體廣播系統中的應用[J].電視技術，2007，31(3)：37-39.

[5]YU J， ZHONG J， ZHAO M， et al. Novel LT coding scheme with limited feedback in broadcast systems[C]//Proc.2012 International Conference on.Wireless Communications & Signal Processing (WCSP). [S.l.]：IEEE Press，2012： 1-5.

[6]ZHANG Q， ZHANG S， ZHOU W. Enhanced LT decoding scheme in satellite communication [C]//Proc.2014 Sixth International Conference on Wireless Communications and Signal Processing (WCSP). [S.l.]：IEEE Press，2014：1-6.

[7]BALDI M， MATURO N， MONTALI E， et al. AONT-LT： a data protection scheme for cloud and cooperative storage systems [C]//Proc. International Conference on High Performance Computing & Simulation. [S.l.]：IEEE Press，2014：566-571.

[8]HARRISON C， JAMIESON K. Power-aware rateless codes in mobile wireless communication[C]//Proc.the 11th ACM Workshop on Hot Topics in Networks. [S.l.]：ACM Press，2012：25-30.

[9]KIM S， KO K， CHUNG S Y. Incremental Gaussian elimination decoding of raptor codes over BEC[J]. IEEE communications letters，2008，12(4)：307-309.

[10]RAHNAVARD N， VELLAMBI B N， FEKRI F. Rateless codes with unequal error protection property[J]. IEEE transactions on information theory，2007，53(4)：1521-1532.

[11]KOKAL J，FILIPOVIC S， SPASOJEVIC P， et al. Doped fountain coding for minimum delay data collection in circular networks[J]. IEEE journal on selected areas in communications，2009，27(5)：673-684.

楊曉非，博士，副教授，從事電路、信號與系統專業相關的教學和科研工作；

季瑞軍，碩士生，主要研究方向為數字噴泉碼在未來網中的應用；

黃勝，博士，教授，主要研究方向為光互聯網，未來網；

張春明，碩士生，主要研究方向為糾刪碼及糾刪碼在未來網中的應用。

責任編輯：閆雯雯

EnhancedLTcodesBPdecodingalgorithm

YANGXiaofei，JIRuijun，HUANGSheng，ZHANGChunming

(Key Laboratory of Optical Fiber Communication and Network Technology ， Chongqing University of Posts and Telecommunications， Chongqing 400065， China)

Abstract:BP decoding algorithm used by general LT code， when degree-1 encoding packet can not be found， BP decoding algorithm failure， however， the original BP algorithm can’t keep decoding. In order to improve the success rate of decoding， the structure of the remaining coded packet is analyzed， this thesis presents a again belief propagation decoding algorithm. When BP decoding fails， the proposed search algorithm can be used to find ABP translatable structure according to the proposed algorithm， maintaining decoding until the decryption succeeds or fails. If decoding fails ， repeat the above steps until the decryption succeeds or translatable structure can’t be found. Through simulation， the decoding success rate has been greatly improved.

Key words:LT codes；BP decoding；decoding efficiency；enhanced BP decoding algorithm

中圖分類號:TN911.22

文獻標志碼：A

DOI：10.16280/j.videoe.2016.03.020

基金項目：國家自然科學基金項目(61371096；61171158)；重慶市自然科學基金項目(cstc2013jcyjA40052);重慶市教委科學技術研究項目(KJ130515)

作者簡介：

收稿日期：2015-07-21

文獻引用格式：楊曉非，季瑞軍，黃勝，等.LT碼的增強型BP譯碼算法[J]. 電視技術，2016，40(3)：93-97.YANGXF，JIRJ，HUANGS，etal.EnhancedLTcodesBPdecodingalgorithm[J].Videoengineering， 2016，40(3)：93-97.