黃 勝，季瑞軍，楊曉非

（重慶郵電大學(xué)光通信與網(wǎng)絡(luò)技術(shù)重點實驗室，重慶 400065）

基于盧比變換碼的分解重組編碼算法

黃 勝，季瑞軍，楊曉非

（重慶郵電大學(xué)光通信與網(wǎng)絡(luò)技術(shù)重點實驗室，重慶 400065）

LT（盧比變換）碼是第一個能夠?qū)嶋H應(yīng)用的數(shù)字噴泉碼。盡管采用BP（置信）譯碼算法的LT碼的編譯碼復(fù)雜度已接近線性，但依然會增加較大的時延。文章提出了一種DRE（分解重組編碼）算法，對所有信息包分解后重新組合，分成多組并行編碼，有效地降低了編碼時間和譯碼的操作數(shù)，減少了數(shù)據(jù)傳輸時延。該編碼方法可適用于不同度分布函數(shù)。仿真結(jié)果表明，當(dāng)信息包數(shù)量K=1 000和2 000時，采用同樣的度分布可以達到NRE（非重復(fù)編碼）的性能，并能夠減少約75%的編碼時間和大量的譯碼操作數(shù)。

盧比變換碼；置信譯碼；度分布

0　引 言

在現(xiàn)代通信網(wǎng)中，傳統(tǒng)的糾錯方法，例如自動重傳請求，存在較大的缺點，需要增加一條額外的反饋信道，浪費了寶貴的信道資源，且會產(chǎn)生較大的時延，而前向糾錯技術(shù)卻不需要額外的信道。數(shù)字噴泉碼是一種新型的前向糾刪碼，而LT（盧比變換）碼是首個實際應(yīng)用的數(shù)字噴泉碼［1］，在衛(wèi)星通信、移動通信和多媒體傳輸中都有深入的研究［2-3］。與經(jīng)典的糾刪碼相比，LT碼性能好，編譯碼復(fù)雜度接近線性，對于較大的數(shù)據(jù)也能以較小的代價進行糾錯，節(jié)約了硬件成本，編譯碼的運算時間也大大減少，降低了傳輸時延。噴泉碼無碼率的特性使其能適應(yīng)任何復(fù)雜的信道，例如衛(wèi)星通信復(fù)雜多變的信道和廣播通信的多路徑傳輸?shù)龋?］。

本文對LT碼的編碼方法進行優(yōu)化，將原始信息包分解重組后并行編碼，縮短了進行編碼的信息包長度，減少了編碼時間。從二分圖來看，編碼包與信息包的連邊因為參與編碼的包長減少而縮減，通過降低邊的數(shù)量及譯碼的消邊操作間接減少了譯碼時間。仿真結(jié)果表明，相較于文獻［5］的NRE（非重復(fù)編碼）和原始LT碼，同樣開銷下，采用文獻［5］的度分布，DRE（分解重組編碼）算法能夠達到與其相似的譯碼成功率且產(chǎn)生的邊數(shù)大量減少。

1　LT碼編譯碼原理

1.1編碼

LT碼作為一種無碼率的碼字，可以在產(chǎn)生足夠多的編碼包后執(zhí)行譯碼。假設(shè)信息包數(shù)量為K，編碼過程為：在K個信息包中隨機選擇d個由其異或得到編碼后的包，其中d為編碼包的度，由度分布函數(shù)得到。編碼中的重要部分是度分布，常見的度式中，d的范圍是｛1，K｝；ρ（d）表示度數(shù)為d的概率，

（1）理想孤波分布

理想孤波分布假設(shè)每次譯碼迭代后都會有一個度為1的編碼包產(chǎn)生，使得BP（置信）譯碼算法可以繼續(xù)執(zhí)行，初始化第一次譯碼有且只有1個度為1的編碼包，剩下的編碼包隨著度數(shù)的增加，其占總編碼包的比例依次減少：

（2）RSD

Luby等人發(fā)現(xiàn)，在使用理想孤波分布時，譯碼后的效果并不理想，尤其是在信息包數(shù)量較小的情況下［1］。基數(shù)很小時，每次譯碼迭代后很難保證度1編碼包一直存在，尤其是在譯碼初期的迭代過程中最容易造成譯碼中斷。為了改善該問題，提出了RSD：分布有理想孤波分布和RSD（魯棒孤波分布）［1］。

式中，

1.2譯碼

LT碼采用的是BP譯碼算法，譯碼的開始需要一個度1編碼包，通過不停迭代直到恢復(fù)完所有的信息包，具體步驟如下：

（1）從所有的編碼包中查找度1的編碼包是否存在，如果存在則轉(zhuǎn)至步驟（2），不存在則譯碼失??；

（2）令度1編碼包等于與其相連的信息包（即恢復(fù)出該信息包）；

（3）更新與此信息包相連的所有編碼包，更新結(jié)果為它們的異或結(jié)果，更新后消除這些邊；

（4）重復(fù)執(zhí)行步驟（1）～（3）直至譯碼失敗或信息包全部恢復(fù)。

圖1所示為3個信息包和3個編碼包時LT碼的譯碼過程。圖中，圓表示信息包，橢圓表示編碼包，深色圓表示譯碼完成的信息包，深色橢圓表示選中的度1編碼包。（a）～（c）對應(yīng)步驟（1）～（3），（d）～（f）對應(yīng)步驟（4），即重復(fù)前面3步迭代譯碼直到成功譯碼或失敗。

圖1　LT碼的譯碼過程

2　分解重組編碼策略

針對低傳輸時延的需求，本文基于LT碼提出了一種DRE算法，以減少編碼和譯碼的時間。DRE算法的主要步驟如下：

（1）對信息包分塊，使每一塊具有相等數(shù)量的編碼包；

（2）對分塊后的信息包重新組合，重組后的這組信息包長度不超過總的信息包的長度；

（3）按照步驟（2）分成多組信息包，使均等分的塊在各組中出現(xiàn)的總次數(shù)相同；

（4）各組采用相同的度分布獨立編碼。

按照編碼算法步驟進行分析，對于K個信息包，在編碼時將它們n等分，每一份的數(shù)量用Ki表示：

完成分塊后，將各個塊重新分成n-j組，其中j∈0，1，2，…，n-1，每組擁有n-P個塊，其中P為降低每個分組的碼塊數(shù)量，P∈0，1，2，…，n-1。重新分組后進行編碼，分組后的每組編碼包長度為

編碼后的信息包長被虛擬擴展，長度用K′表示：

可以由不同的度分布得到編碼包的度數(shù)進行編碼，由公式（2）～（6）得出每個分組的RSD為

為了達到只產(chǎn)生適當(dāng)冗余的目的，每個分組產(chǎn)生的編碼包數(shù)量必須要減少，數(shù)量控制為Ni，即

圖2　DRE過程

圖中，分塊數(shù)n取4，標(biāo)記為1～4。j=0，即分組數(shù)為4。P=1可以清楚地看到每個分組由3個塊組成，且每個塊在該分組中重復(fù)出現(xiàn)3次，即在編碼過程中這些塊重復(fù)參與3次，增加了編碼包與信息包的相關(guān)性。編碼可以采用任意度分布。

在分組時，如果分組后每組的塊的數(shù)量小于總的塊數(shù)，就可以達到降低譯碼時間的目的。圖2所示的4個分組并行編碼，這種情況下產(chǎn)生相同數(shù)量的編碼包所需時間僅為普通編碼的1/4。假如圖2的分組只有3組，這樣就無法均等處理每個分好的塊，導(dǎo)致不等差錯保護。為了避免這種情況發(fā)生，必須控制分組數(shù)和分塊數(shù)的關(guān)系。由式（7）可以得知，需滿足等式

經(jīng)過DRE后，得到多組小于原信息包長的分組包，因此在編碼時降低了編碼包與信息包的邊的數(shù)量。用e表示減少后的邊的數(shù)量，由式（10）可知：

3　仿真分析

仿真參數(shù)如下：信息包數(shù)量K取1 000和2 000，信道模型為二進制刪除信道，信道的刪除概率P=0.1。LT碼中度分布函數(shù)的參數(shù)為c=0.02，δ=0.2。仿真以開銷和譯碼成功率來分析DRE算法的性能，開銷ε可表示為ε=［（N-K）/K］·100。對比NRE算法和傳統(tǒng)的LT碼，對它們產(chǎn)生的邊數(shù)進行比較。

圖3所示為3種算法的譯碼成功率比較。DRE算法的取值與圖2一致。仿真次數(shù)分別為1 000和2 000。由圖可知，DRE算法可通過重組后并行編碼，能節(jié)約大量的編碼時間，在相同數(shù)量編碼包的情況下可減少約75%的譯碼時間，而NRE算法和傳統(tǒng)的LT碼在編碼時間上沒有改變。

圖3 3種算法的譯碼成功率比較

圖4所示為仿真次數(shù)分別為1 000和2 000時3種算法的生成邊數(shù)對比。可以看到生成邊數(shù)隨開銷線性增長，這也側(cè)面反映了BP譯碼算法的線性復(fù)雜度，且DRE算法能夠有效地降低生成的邊數(shù)。

圖4　3種算法的生成邊數(shù)對比

4　結(jié)束語

本文提出了一種基于LT碼的DRE算法，通過分解原始信息包并重新組合，多組并行編碼，有效地降低了編碼時間。分組后的信息包長度相對原始信息包有一定的縮減，使得編碼包與信息包連邊減少，因此減少了譯碼操作數(shù)并降低了譯碼時間。DRE算法與NRE算法和傳統(tǒng)LT碼算法相比，在同開銷和度分布的情況下，有相似的譯碼成功率且能夠有效降低傳輸時延。

［1］ Luby M.LT codes［C］//Foundations of Computer Science，2002.Vancouver，Canada：IEEE，2002：271-280.

［2］ Yao W D，Hui L I，Chen L J，et al.Study on the fountain codes technology in deep space communications［J］.Systems Engineering&Electronics，2009，31（1）：40-44.

［3］ Ahmad S，Hamzaoui R，Al-Akaidi M M.Unequal error protection using fountain codes with applications to video communication［J］.IEEE Trans Multimedia，2011，13（1）：92-101.

［4］ Wang N，Zhang Z.The impact of application layer Raptor FEC on the coverage of MBMS［C］//2008 IEEE Radio and Wireless Symposium.Orlando，F(xiàn)L，USA：IEEE，2008：223-226.

［5］ Yen K K，Liao Y C，Chen C L，et al.Non-Repetitive Encoding with Increased Degree-1 Encoding Symbols for LT Codes［C］//APCCAS 2012.Kaohsiung，China：IEEE，2012：655-658.

Decomposition and Restructuring Encoding Algorithm for LT Codes

HUANGSheng，JI Rui-jun，YANG Xiao-fei
（Key Laboratory of Optical Fiber Communication and Network Technology，Chongqing University of Posts and Telecommunications，Chongqing 400065，China）

LT codes are the first realization of the digital Fountain codes.LT codes using BP decoding algorithm which means the complexity is close to that of linear algorithm.However it still suffers from great delay.In order to solve this problem，we propose a decomposition and restructuring encoding algorithm.The algorithm first decomposes and regroups K information packets，and then divides the packets into a plurality of sets for parallel encoding.The algorithm can effectively reduce the encoding time and operation of decoding with reduced data transmission delay.The encoding method can be applied to various modifications distribution.In the case of K=1 000 and K=2 000 and the same degree distribution，the simulation results show that it can achieve Non-Repetitive Encoding（NRE）algorithm performance with 75%encoding time reduction and less decoding operands.

LT codes；BP decoding；degree distribution

TN911.22

A

1005-8788（2016）04-0012-04

10.13756/j.gtxyj.2016.04.004

2016-04-04

國家自然科學(xué)基金資助項目（61371096，61171158）；重慶市自然科學(xué)基金資助項目（cstc2013jcyj A40052）；重慶市教委科學(xué)技術(shù)研究項目（KJ130515）

黃勝（1974-），男，湖北英山人。教授，博士，主要研究方向為光互聯(lián)網(wǎng)、未來網(wǎng)。

季瑞軍，碩士研究生。E-mail：1120330180@qq.com