LT碼的增強(qiáng)型BP譯碼算法

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

(重慶郵電大學(xué) 光通信與網(wǎng)絡(luò)重點(diǎn)實(shí)驗(yàn)室，重慶 400065)

LT碼的增強(qiáng)型BP譯碼算法

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

(重慶郵電大學(xué) 光通信與網(wǎng)絡(luò)重點(diǎn)實(shí)驗(yàn)室，重慶 400065)

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

關(guān)鍵詞:LT碼；BP譯碼；譯碼效率；增強(qiáng)型譯碼算法

數(shù)字噴泉碼在1998年被提出[1]。LT碼是由M.Luby等人針對刪除信道設(shè)計(jì)出的第一個(gè)實(shí)用的數(shù)字噴泉碼[2]，之后數(shù)學(xué)家Shokrollahi針對LT碼的缺點(diǎn)改進(jìn)后提出了性能更好的Raptar碼[3]，數(shù)字噴泉碼在廣播通信[4]，針對數(shù)據(jù)擁有不同優(yōu)先等級的視頻傳輸[5]，復(fù)雜信道環(huán)境的深空通信[6]，當(dāng)前熱門的數(shù)據(jù)安全存儲[7]等領(lǐng)域具有廣泛的應(yīng)用前景。LT碼譯碼算法采用BP(置信傳播)譯碼算法，然而，譯碼很可能因?yàn)椴檎也坏蕉?的編碼分組而導(dǎo)致失敗，影響了數(shù)據(jù)傳輸質(zhì)量。由于傳輸質(zhì)量的要求，通常需要接收多于原始信息分組數(shù)量的編碼分組才能成功恢復(fù)原始信息分組，把多接收的編碼分組與信息分組的長度之比稱為譯碼開銷。

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

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

1LT碼編譯碼原理

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

1.1編碼過程

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

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

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

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

圖1　編碼分組的生成示例

1.2譯碼過程

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

1)根據(jù)接收到的編碼分組和信息分組的對應(yīng)關(guān)系建立二分圖。

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

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

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

1.3LT碼的度分布

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

(1)

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

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

(2)

(3)

在傳統(tǒng)LT碼譯碼迭代會因?yàn)闆]有度1的編碼分組導(dǎo)致譯碼失敗。實(shí)際上剩下的編碼分組是存在可譯性的。本文針對BP譯碼算法的這種漏洞，提出了增強(qiáng)型的BP譯碼算法，在BP譯碼失敗之后查找二分圖中的特殊結(jié)構(gòu)，根據(jù)特殊結(jié)構(gòu)譯出其中的一個(gè)信息分組，這使BP譯碼算法可以繼續(xù)執(zhí)行。

2增強(qiáng)型BP譯碼算法

圖2是ABP可譯結(jié)構(gòu)示意圖，編碼分組tm的度為i-1，編碼分組tn的度為i，其中3

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

圖2　結(jié)構(gòu)圖示

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

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

圖3　ABP可譯結(jié)構(gòu)查找算法示例

本算法可以擴(kuò)展為對3個(gè)或3個(gè)以上的不同剩余的編碼分組進(jìn)行的操作，異或3個(gè)不同剩余的編碼分組，觀察是否可以產(chǎn)生度為1的編碼分組。但因?yàn)橛?個(gè)編碼分組組成的這種結(jié)構(gòu)的概率低譯碼查找復(fù)雜度大，這里不做理論分析和實(shí)驗(yàn)驗(yàn)證。

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

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

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

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

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

圖4是算法流程圖。

圖4　算法流程圖

當(dāng)檢測到BP譯碼算法失敗時(shí)，會進(jìn)入可譯結(jié)構(gòu)的檢測，更新二分圖也就是生成矩陣，繼續(xù)跳回BP譯碼。本算法不但提高譯碼的成功率，而且也減譯碼開銷。

2.2ABP結(jié)構(gòu)存在的概率

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

對于任意兩個(gè)編碼分組符合這種結(jié)構(gòu)的概率為

(4)

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

(5)

對于不同的度M的取值為

…

(6)

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

3仿真分析

仿真與傳統(tǒng)的BP譯碼算法作為對比。選擇理想孤子分布作為編碼的度分布，這里主要考察兩個(gè)性能指標(biāo)，一個(gè)是譯碼成功率，當(dāng)所有的信息符號全部正確譯出時(shí)代表譯碼成功；另一個(gè)性能指標(biāo)是成功譯出分組比例，及每次譯碼結(jié)束時(shí)，成功譯出信息分組占總的信息分組的比例。對信息分組數(shù)為1 000和2 000進(jìn)行1 000次實(shí)驗(yàn)。

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

圖5　譯碼成功率仿真圖

圖6是成功譯出分組比例隨譯碼開銷變化的仿真圖。信道模型為二進(jìn)制刪除信道，刪除概率為0.02?？梢钥闯?，成功譯出分組比例與譯碼成功率有相同的趨勢，改進(jìn)算法成功譯出分組比例要高于傳統(tǒng)的BP譯碼算法。信息分組數(shù)為2 000的LT碼成功率譯出分組比例同樣大于信息分組數(shù)為1 000的LT碼。

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

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

圖7　譯碼成功率仿真圖

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

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

4小結(jié)

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

參考文獻(xiàn)：

[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 碼在移動(dòng)多媒體廣播系統(tǒng)中的應(yīng)用[J].電視技術(shù)，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，F(xiàn)ILIPOVIC 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.

楊曉非，博士，副教授，從事電路、信號與系統(tǒng)專業(yè)相關(guān)的教學(xué)和科研工作；

季瑞軍，碩士生，主要研究方向?yàn)閿?shù)字噴泉碼在未來網(wǎng)中的應(yīng)用；

黃勝，博士，教授，主要研究方向?yàn)楣饣ヂ?lián)網(wǎng)，未來網(wǎng)；

張春明，碩士生，主要研究方向?yàn)榧m刪碼及糾刪碼在未來網(wǎng)中的應(yīng)用。

責(zé)任編輯：閆雯雯

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

文獻(xiàn)標(biāo)志碼：A

DOI：10.16280/j.videoe.2016.03.020

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

作者簡介：

收稿日期：2015-07-21

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