一種基于短LT碼的級聯(lián)編譯碼算法

黃曉可 劉洛琨 郭 虹

（解放軍信息工程大學(xué)信息系統(tǒng)工程學(xué)院，鄭州，450002）

引 言

數(shù)字噴泉碼［1］是一種新穎的基于圖的糾刪編碼技術(shù)，具有優(yōu)良的抗刪除特性，在刪除信道中有著比其他碼更好的應(yīng)用前景。M.Luby于1998年提出了噴泉碼的概念，并在2002年提出了第一種高效可行的噴泉碼，即LT（Luby transform）碼［2］。之后，Shokrollahi等人提出 Raptor碼［3］，其中一種系統(tǒng)Raptor碼已被3GPP的多媒體廣播多播業(yè)務(wù)采用［10］。

LT碼等最早都是為刪除信道設(shè)計(jì)的，如今已經(jīng)從有線走向了無線，并被推廣到越來越多的領(lǐng)域，比如無線多媒體廣播和深空通信［4－7］等。通常噴泉碼碼長需要達(dá)到103或更高量級才能取得良好的性能［8－9］，但是碼長較長將導(dǎo)致譯碼時(shí)延和接收緩存較大。針對多媒體廣播的實(shí)時(shí)性需求和深空通信中設(shè)備小型化與資源受限的特點(diǎn)，短碼長噴泉碼的研究具有重要現(xiàn)實(shí)意義［10－12］。

本文提出了一種碼長在102量級的短LT碼與傳統(tǒng)糾錯(cuò)碼的級聯(lián)方案，利用Reed Solomon碼與卷積碼的強(qiáng)糾錯(cuò)檢錯(cuò)能力，構(gòu)造等效刪除信道。針對方案所用LT碼碼長較短的特點(diǎn)，本文將置信傳播（Belief propagation，BP）算法與高斯消元（Gauss elimination，GE）算法合并作為譯碼方法，同時(shí)分析比較了幾類現(xiàn)有度分布對短LT碼的適用性，最后對級聯(lián)方案的糾錯(cuò)能力進(jìn)行了仿真驗(yàn)證。理論分析和仿真證明了該方案的有效性，級聯(lián)系統(tǒng)在等效包刪除概率不超過0.01時(shí)，譯碼開銷約為0.12。

1 短LT碼與RS－CC碼級聯(lián)方案

級聯(lián)系統(tǒng)的原理框圖如圖1所示，對于實(shí)時(shí)性要求較高的傳輸系統(tǒng)可選用短LT碼，圖1中二進(jìn)制信源被等長度分組，每個(gè)原始數(shù)據(jù)分組的長度設(shè)為l，l的大小按RS編碼需求長度設(shè)計(jì)。LT碼以數(shù)據(jù)分組為單位，每k個(gè)原始數(shù)據(jù)分組進(jìn)行一次LT編碼，即每次LT編碼前數(shù)據(jù)長度為k×l比特，編碼后分組個(gè)數(shù)為K，數(shù)據(jù)長度為K×l比特，K值大小由等效信道的刪除概率決定。

圖1 LT碼與RS碼級聯(lián)系統(tǒng)Fig.1 Concatenated system diagram of LT codes and RS codes

LT編碼后，各數(shù)據(jù)分組分別進(jìn)行RS－卷積（Reed solomon－convolution coding，RS－CC）編碼。RS－CC碼是一類傳統(tǒng)的前向糾錯(cuò)編碼方法。它由Reed Solomon碼、交織編碼和卷積碼級聯(lián)而成。卷積碼有較強(qiáng)的糾隨機(jī)錯(cuò)誤能力，但是如果在解碼過程中發(fā)生錯(cuò)誤，解碼器的Viterbi譯碼可能導(dǎo)致突發(fā)錯(cuò)誤，為了降低出現(xiàn)突發(fā)錯(cuò)誤長度超出RS碼糾錯(cuò)范圍的概率，在RS碼與卷積碼之間加入了塊交織，交織編碼的優(yōu)點(diǎn)是不增加附加的監(jiān)督碼元且提高了抗突發(fā)誤碼的能力。

RS碼同時(shí)具有檢錯(cuò)和糾錯(cuò)的能力，在誤比特率超出RS碼糾錯(cuò)范圍時(shí)，仍可被RS碼較大概率地檢測出來。文獻(xiàn)［4］對RS－CC級聯(lián)碼的譯碼差錯(cuò)概率作了詳細(xì)分析，硬判決后的Viterbi譯碼的比特差錯(cuò)概率上邊界為

式中：dfree為卷積碼的自由距離上邊界；P2（d）為成對差錯(cuò)概率，因調(diào)制解調(diào)技術(shù)的不同而不同。在只有隨機(jī)錯(cuò)誤的情況下，有m個(gè)錯(cuò)誤的概率為

對于RS（n，l）碼，信息符號長度為l，編碼符號長度n≤2m－1，則其可糾錯(cuò)長度為即如果在一個(gè)編碼符號內(nèi)出現(xiàn)的錯(cuò)誤數(shù)少于t個(gè)，則RS碼可正確糾錯(cuò)，那么出現(xiàn)RS碼不可糾的錯(cuò)誤概率為

由于RS碼可以檢測出個(gè)數(shù)低于2t的錯(cuò)誤，即出現(xiàn)RS碼不可檢的錯(cuò)誤概率極低，因此可以將經(jīng)過RS－CC級聯(lián)碼譯碼后的數(shù)據(jù)分為正確接收和檢測出錯(cuò)誤兩類。RS－CC譯碼器檢測并刪除錯(cuò)誤數(shù)據(jù)分組，只把正確數(shù)據(jù)分組傳遞給LT譯碼器，這樣就將信道等效為刪除信道，刪除概率p＝Ppe，其中0≤p≤1。

K個(gè)編碼數(shù)據(jù)分組經(jīng)過刪除概率為p的等效信道后，LT譯碼器收到K′＝K（1－p）個(gè)數(shù)據(jù)分組，然后運(yùn)用適當(dāng)?shù)淖g碼方法重構(gòu)出k（k≤K′）個(gè)原始數(shù)據(jù)分組?？梢?，設(shè)計(jì)一種低復(fù)雜度且譯碼成功率高的LT碼編譯碼算法是本方案的關(guān)鍵。級聯(lián)方案確定后，通過改變噴泉碼的輸出分組個(gè)數(shù)k，若接收端接收到足夠多正確的LT編碼數(shù)據(jù)分組，可達(dá)到極低的誤碼率。

2 短LT碼編譯碼算法與度分布函數(shù)設(shè)計(jì)

2.1 LT碼編譯碼原理與算法

2.1.1 LT碼編碼

文獻(xiàn)［2］對LT編碼方法進(jìn)行了詳細(xì)的介紹分析，本文沿用了其中的一些定義與表示符號，假定原始數(shù)據(jù)長度為N，將其分為k組，則每個(gè)分組長度為l＝N／k，這些分組稱為原始數(shù)據(jù)分組。由原始數(shù)據(jù)分組通過編碼運(yùn)算產(chǎn)生編碼分組。LT碼每個(gè)編碼分組的產(chǎn)生過程如下：

（1）從給定度分布ρ（·）中隨機(jī)產(chǎn)生一個(gè)度d。

（2）從k個(gè)原始分組中等概隨機(jī)選取d個(gè)分組。

（3）將選取的d個(gè)分組進(jìn)行異或運(yùn)算，即得到一個(gè)編碼分組。

（4）重復(fù)以上步驟即可源源不斷地產(chǎn)生編碼分組。

2.1.2 LT碼譯碼

LT譯碼是對接收到的K′個(gè)編碼分組進(jìn)行處理來恢復(fù)出k個(gè)原始數(shù)據(jù)分組，一般要求K′略大于k。在刪除信道中，對線性碼的最大似然譯碼等同于解線性方程組，因此可以使用高斯消元算法來求解。對于給定的k個(gè)原始數(shù)據(jù)分組可用向量x＝ （x1，x2，…，xk）T表示，接收到的K′個(gè)編碼分組可用向量y＝ （y1，y2，…，yK′）T表示。則整個(gè)譯碼過程可以視為用K′個(gè)方程聯(lián)合求解k個(gè)未知數(shù)的一個(gè)線性方程組

式中：H為經(jīng)過刪除信道后的生成矩陣；hm為矩陣H第m列構(gòu)成的列矢量，加法均為模2加運(yùn)算。

但是，GE算法類似于矩陣求逆，在原始分組數(shù)k較大時(shí)運(yùn)算量過大。因此，噴泉編碼常采用置信傳播迭代譯碼算法。

根據(jù)模2加的性質(zhì)，則式（4）可以改寫為

BP算法即是從矩陣H中找出一個(gè)重量為1的行，假設(shè)為第i行且該行唯一元素在第j列，則可直接得到y(tǒng)i＝xj，即xj被譯出。則式（5）可寫為

即

式中：編碼分組集y更新為y′＝y(tǒng)＋hj·xj，矩陣H的第j列元素更新為全零，設(shè)為H′。因此，只要矩陣H′存在重量為1的行，以上過程就可以循環(huán)迭代進(jìn)行。

2.1.3 譯碼算法分析與改進(jìn)

GE算法譯碼運(yùn)算量O（Kk2）隨著原始數(shù)據(jù)分組個(gè)數(shù)的增加快速增長，而BP譯碼算法復(fù)雜度僅為O（klogk），實(shí)現(xiàn)簡單。但BP算法的迭代過程容易因某一步?jīng)]有解出新的數(shù)據(jù)就提前中止，導(dǎo)致無法完整譯碼。因此，采用BP算法時(shí)需要接收更多的編碼分組以保證譯碼成功，而對于碼長較短的噴泉碼，BP算法的譯碼開銷更大。對此，文獻(xiàn)［8］提出了增強(qiáng)型高斯消元算法，但復(fù)雜度仍較高。文獻(xiàn)［9，11］提出BP算法譯碼失敗時(shí)可用其他算法求出一個(gè)新解繼續(xù)進(jìn)行迭代。

由于本文碼長較短，將文獻(xiàn)［9］的思想簡化，提出置信傳播高斯消元（Belief propagation Gauss elimination，BPGE）譯碼算法，即在BP譯碼失敗時(shí)即對剩余未解出的分組全部采用GE譯碼，可以在保證與GE算法有相同譯碼成功率的條件下降低譯碼復(fù)雜度。

譯碼器首先采用BP算法譯碼，假設(shè)由于隨機(jī)性的存在，在某次迭代之后矩陣H′中找不到重量為1的行，BP算法將被迫中止，此時(shí)剩余的方程即式（7）可寫為

式中：x′為尚未譯出的初始分組集合。

如果矩陣H列滿秩即rank（H）＝k，即方程（5）有唯一解，則對應(yīng)式（8）仍存在唯一解，此時(shí)，再采用高斯消元法求解式（8）。但是，如果rank（H）＜k，則說明譯碼失敗，采用GE算法譯碼也無法求解，需要繼續(xù)接收編碼分組?？梢?，相對于直接用GE算法求解式（4），本文所提算法降低了復(fù)雜度且與GE算法有相同譯碼成功率。

2.2 度分布函數(shù)設(shè)計(jì)

在編碼過程中，度分布函數(shù)的設(shè)計(jì)至關(guān)重要，好的度分布設(shè)計(jì)可以使得接收端用盡可能少的接收符號和盡可能小的復(fù)雜度恢復(fù)出原始信息。

2.2.1 常用度分布函數(shù)

文獻(xiàn)［2］中給出了Ideal Soliton分布函數(shù)定義

在此基礎(chǔ)上，Robust Soliton分布引入了兩個(gè)調(diào)節(jié)參數(shù)c和δ，其中，c為一大于零的可調(diào)常數(shù)，δ則與譯碼錯(cuò)誤概率有關(guān)。定義

除了以上兩種經(jīng)典分布外，較著名的已被3GPP組織的多媒體廣播多播業(yè)務(wù)標(biāo)準(zhǔn)采用的度分布［10］，其度分布函數(shù)如下

還有其他一些關(guān)于度分布優(yōu)化方法的設(shè)計(jì)，比如用重要抽樣法優(yōu)化得到的短碼長噴泉碼的稀疏度分布函數(shù)［6］

這兩個(gè)度分布函數(shù)都是將Robust Soliton分布函數(shù)弱化，以在接收到K′＝k個(gè)編碼分組時(shí)的譯碼成功率為目標(biāo)函數(shù)，采用BP迭代譯碼算法，通過提高此時(shí)的譯碼成功率來優(yōu)化得到的度分布。

2.2.2 短LT碼度分布

針對短碼長LT碼，如果譯碼時(shí)采用BPGE譯碼算法，當(dāng)經(jīng)過刪除信道后的生成矩陣H列滿秩（rank（H）＝k）時(shí)，就可以成功譯碼。因此，優(yōu)化度分布的目標(biāo)即是滿足rank（H）＝k的條件下盡可能降低所需接收編碼分組數(shù)。文獻(xiàn)［6］定義此優(yōu)化目標(biāo)函數(shù)為全部分組都譯碼成功時(shí)所需接收的平均編碼分組數(shù)，記為MinAvg。

文獻(xiàn)［2］在最初設(shè)計(jì)LT碼時(shí)，得到度分布服從Ideal Soliton函數(shù)時(shí)LT碼性能漸進(jìn)最優(yōu)，但實(shí)際應(yīng)用中由于存在抽樣誤差，無法達(dá)到精準(zhǔn)理論分布。其改進(jìn)型Robust Soliton分布通過引入?yún)?shù)c和δ來調(diào)節(jié)性能，有較大實(shí)際應(yīng)用價(jià)值。而削弱之后的度分布，如式（12）和（13），雖然降低了一定的編碼復(fù)雜度，但對于碼長較短的短LT碼，其編碼分組的度選擇范圍受到限制時(shí)，容易產(chǎn)生相同的編碼分組，即引起短環(huán)，致使其成功譯碼時(shí)所需的MinAvg高于Robust Soliton分布。

因此，本方案采用優(yōu)化參數(shù)后的Robust Soliton分布，并將在第3節(jié)仿真對比采用BPGE譯碼時(shí)各度分布的性能。

3 仿真分析

為了評估所提短LT碼級聯(lián)方案的性能，本節(jié)首先仿真對比了幾類短碼長LT碼，驗(yàn)證相同接收包數(shù)下本文所提短LT碼的譯碼成功率更高。然后對本文設(shè)計(jì)的級聯(lián)方案在無線信道中的應(yīng)用進(jìn)行仿真，驗(yàn)證此級聯(lián)方案的有效性，并給出了不同等效信道刪除概率下的譯碼開銷。

3.1 短LT碼設(shè)計(jì)方法對比

本節(jié)構(gòu)造了碼長k＝100的短LT碼，編碼度分布服從參數(shù)為δ＝0.05，c＝0.03的 Robust Soliton函數(shù)，譯碼采用本文提出的BPGE算法。文獻(xiàn)［6］中的短LT碼采用式（13）度分布，譯碼采用BP算法。首先對這兩種設(shè)計(jì)方案作性能對比。為了比較各類度分布的性能，在譯碼都采用BPGE算法時(shí)，本文也仿真了編碼采用文獻(xiàn)［6，10］中的度分布。

對以上4種設(shè)計(jì)方法分別進(jìn)行104次蒙特卡洛仿真，每次仿真發(fā)送原始分組包數(shù)為k＝100，發(fā)送端按給定度分布持續(xù)產(chǎn)生并發(fā)送編碼分組包，直至接收端正確譯碼，記錄此時(shí)接收的分組包數(shù)。對記錄結(jié)果進(jìn)行統(tǒng)計(jì)，以成功譯碼時(shí)接收的分組包數(shù)為橫軸，將包數(shù)對應(yīng)的譯碼成功次數(shù)換算成占總實(shí)驗(yàn)數(shù)的比例作為縱軸，繪出柱狀圖如圖2～5所示。

圖2 本文方案：RS度分布，BPGE譯碼Fig.2 This Scheme：RS degree distribution，BPGE decoding

圖3 式（13）度分布，BP譯碼Fig.3 Formula 13degree distribution，BP decoding

圖4 式（13）度分布，BPGE譯碼Fig.4 Formula 13degree distribution，BPGE decoding

圖5 式（12）度分布，BPGE譯碼Fig.5 Formula 12degree distribution，BP decoding

對比圖3和圖4可以看出，在采用相同度分布時(shí)，BP譯碼算法成功譯碼的分組數(shù)集中在115至135之間，在120處峰值比例為0.11；而BPGE譯碼算法成功譯碼的分組數(shù)集中在105至120之間，在110處到達(dá)峰值，峰值比例約為0.15。因此采用BPGE譯碼算法降低了譯碼成功所需接收的平均分組數(shù)MinAvg。

然后對比圖2，4和5，本文設(shè)計(jì)方案的成功譯碼分組數(shù)集中在110以內(nèi)，峰值比例為0.35；而按其他兩類削弱的度分布編碼時(shí)，譯碼都已采用BPGE算法時(shí)，但成功譯碼的分組數(shù)大多集中在100至120之間，峰值比例相對較低。因此在采用BPGE譯碼時(shí)，Robust Soliton度分布的 MinAvg最低，性能最優(yōu)。

3.2 短LT碼級聯(lián)方案性能分析

在仿真中采用傳統(tǒng)的RS－CC級聯(lián)碼構(gòu)造等效刪除信道，即RS（255，223）碼與（7，1／2）卷積碼級聯(lián)，在二者之間加入交織編碼，調(diào)制方式選用QPSK。接收端卷積碼采用軟判決Viterbi譯碼，RS譯碼檢測出接收編碼分組包有不可糾錯(cuò)誤時(shí)刪去此包，這樣就可以把RS編碼之前和RS譯碼之后的整個(gè)子系統(tǒng)等效為刪除信道。不同的刪除概率對應(yīng)AWGN信道不同信噪比下的RS－CC碼的不可糾錯(cuò)誤概率。

仿真時(shí)，LT碼的原始數(shù)據(jù)分組個(gè)數(shù)，數(shù)據(jù)分組長度為l＝1 784bit＝8×223bit，編碼時(shí)選用δ＝0.05，c＝0.03的Robust Soliton度分布，設(shè)定每次仿真產(chǎn)生的編碼分組個(gè)數(shù)為有限值K＝120，LT譯碼采用BPGE譯碼算法。仿真實(shí)驗(yàn)時(shí)信源產(chǎn)生的數(shù)據(jù)在同一指定的Eb／N0值上重復(fù)發(fā)送105次，求出平均譯碼成功概率。

經(jīng)RS－CC編碼后的誤碼率如圖6所示，在Eb／N0為3dB左右時(shí)已達(dá)到10－5量級。因此，選取了Eb／N0在2～3.5dB這一區(qū)間測試級聯(lián)LT碼的性能。

圖6同時(shí)給出了RS－CC碼與LT碼級聯(lián)前后的誤包率，其中，RS－CC碼的誤包率即是RS譯碼時(shí)的不可糾錯(cuò)誤包概率，即等效刪除信道的刪除概率。從圖中可以看出，在Eb／N0值大于2.5dB后，即等效信道的刪除概率低于0.1之后，級聯(lián)LT碼的誤包率迅速降低。當(dāng)誤包率在10－3附近時(shí)，級聯(lián)短LT碼后的編碼增益約0.75dB。對于無碼率的LT碼，隨著Eb／N0值的增加或等效包刪除概率的降低，發(fā)送編碼分組包的數(shù)量可適當(dāng)降低。

圖7顯示了等效包刪除概率p取0.01，0.1，0.2和0.4時(shí)，不同發(fā)送編碼包數(shù)對應(yīng)的成功譯碼概率，即在給定包刪除概率條件下成功恢復(fù)的原始信息包數(shù)與k的比值。譯碼開銷是在成功恢復(fù)出所有信息包時(shí)，發(fā)送端至少要發(fā)送的編碼包個(gè)數(shù)K與k的差值除以k。從圖7可以看出，在等效包刪除概率為0.1時(shí)，接收端成功譯碼需要發(fā)送編碼包個(gè)數(shù)為K＝126，因此譯碼開銷為（K－k）／k＝0.26。當(dāng)Eb／N0下降即等效包刪除概率降低時(shí)，譯碼開銷也迅速降低，如圖當(dāng)刪除概率為0.01時(shí)，譯碼開銷約為0.12。

圖6 LT碼級聯(lián)前后的誤比特率與誤包率Fig.6 BER and FER of LT concatenated coding

圖7 發(fā)送編碼包數(shù)與譯碼成功率Fig.7 Number of encoded frames and the success rate

4 結(jié)束語

該文通過分析噴泉碼編譯碼算法與度分布的設(shè)計(jì)，提出了一種短LT碼級聯(lián)方案，方案利用RS－CC碼的強(qiáng)糾錯(cuò)能力將無線信道構(gòu)造為等效刪除信道，再將文中設(shè)計(jì)的LT碼與之級聯(lián)，即可適應(yīng)有實(shí)時(shí)通信要求的無線信道。仿真結(jié)果表明，此方案中的LT譯碼器只需正確接收略大于原始數(shù)據(jù)包數(shù)的編碼包即可正確譯碼，當(dāng)刪除概率為0.01時(shí)譯碼開銷約為0.12。并且信道Eb／N0大于2.5 dB后，該級聯(lián)系統(tǒng)誤包率較傳統(tǒng)糾刪碼下降更迅速。但由于文中的LT碼非系統(tǒng)碼，在信噪比過低時(shí)系統(tǒng)性能反而惡化，因此短碼長系統(tǒng)噴泉碼是本文下一步的改進(jìn)方向。

［1］Mackay D J.Fountain codes［J］.IEE Proceedings Communications，2005，152（6）：1062－1068.

［2］Luby M.LT codes［C］∥Proc 43rd Ann IEEE Symposium on Foundations of Computer Science，Vancouver.Canada：IEEE，2002：271－282.

［3］Shokrollahi A.Raptor codes［J］.IEEE Transactions on Information Theory，2006，52（6）：2551－2567.

［4］Lin Y，Wu C，Zhang Q，et al.Application of the concatenation of the concatenation of RS and LT codes in deep communications［C］∥Third IEEE International Conference on Space Mission Challenges for Information Technology （SMC－IT）.Pasadena：IEEE，2009：29－33.

［5］卞銀兵，酆廣增.一種低復(fù)雜度的短LDPC碼級聯(lián)譯碼算法［J］.數(shù)據(jù)采集與處理，2010，25（2）：250－254.Bian Yinbing，F(xiàn)eng Guangzeng.Novel concatenation decoding algorithm for short LDPC codes with lower complexities［J］.Journal of Data Acquisition and Processing，2010，25（2）：250－254.

［6］Hyytia E，Tirronen T，Virtamo J.Optimizing the degree distribution of LT codes with an importance sampling approach［C］∥Proceedings of the 6th International Workshop on Rare Event Simulation（RESIM 2006），Bamberg，Germany：Tinbergen Institute，2006：64－73.

［7］焦健，張欽宇，李安國.面向深空通信的噴泉編碼技術(shù)［J］.宇航學(xué)報(bào)，2010，31（4）：1156－1161.Jiao Jian，Zhang Xinyu，Li Anguo.A method of concatenated fountain codes in deep space communication［J］.Journal of Astronautics，2010，31（4）：1156－1161.

［8］Kim S，Ko K，Chung S.Incremental Gaussian elimination decoding of raptor codes over BEC［J］.IEEE Communications Letters，2008，12：307－309.

［9］Shokrollahi A，Lassen S，Krap R.Systems and processes for decoding a chain reaction code through inactivation［P］.U.S Patent：7633413B2，2009－12－15.

［10］3rd Generation Partnership Project.3GPP－TS－26.364－V9.4.0，multi－media broadcast／multicast services（MBMS）protocols and codes（release 9）［S］.Valbonne，F(xiàn)rance：3GPP Organizational Partners，2010.

［11］Lu F，Chuan H F，Cai J，et al.LT codes decoding：design and analysis［C］∥The IEEE International Symposium on Information Theory.Seoul，Korea：IEEE，2009：2492－2496.

［12］林永照，吳成柯，劉薇.LT碼和q－LDPC碼級聯(lián)方案在深空通信中的應(yīng)用［J］.電子與信息學(xué)報(bào)，2010，32（8）：1898－1903.Lin Yongzhao，Wu Chengke，Liu Wei.Applications of the concatenation of q－LDPC and luby transform codes in deep communications［J］.Journal of Electronics ＆ Information Technology，2010，32（8）：1898－1903.