無線信道下基于可譯集的噴泉碼增量譯碼算法

張瑞丹 徐大專 鄧大椿

（南京航空航天大學(xué)電子信息工程學(xué)院，南京，211106）

引 言

為解決大規(guī)模數(shù)據(jù)分發(fā)和可靠廣播等問題，1998年Luby等首次提出數(shù)字噴泉碼(Digital fountain,DF)的概念[1]，它具有無碼率特性、無需反饋、不限用戶以及實(shí)時(shí)性好等優(yōu)良特性。此后第一種實(shí)用噴泉碼LT碼[2]和具有優(yōu)良性能的Raptor碼[3]的提出使得噴泉碼逐漸受到業(yè)界的廣泛關(guān)注[4-6]。

噴泉碼的譯碼多采用BP(Belief propagation)譯碼算法，該算法思路簡(jiǎn)單，但復(fù)雜度較高。已有大量文獻(xiàn)對(duì)降低BP譯碼算法的復(fù)雜度進(jìn)行研究。文獻(xiàn)[7-8]提出了一種最小和算法，將迭代過程中的乘法運(yùn)算轉(zhuǎn)化成加法，避免了非線性函數(shù)的復(fù)雜運(yùn)算，降低了復(fù)雜度，但由于近似計(jì)算導(dǎo)致性能變差。文獻(xiàn)[9-10]對(duì)LDPC碼中的最小和算法進(jìn)行了改進(jìn)，改善了其收斂特性和譯碼性能。文獻(xiàn)[11-13]通過對(duì)信息節(jié)點(diǎn)進(jìn)行可靠性分析，加快了其收斂速度。Frey等還曾提出過“及早判決”的概念[14]，將迭代過程中似然比超過某個(gè)門限值的節(jié)點(diǎn)及時(shí)譯出，不再繼續(xù)更新，以減少計(jì)算量，但并未給出門限值的具體計(jì)算方法。利用“及早判決”的思想，文獻(xiàn)[15-17]對(duì)Turbo碼和LDPC碼的譯碼算法進(jìn)行了改進(jìn)，給出了門限值選取的一些理論依據(jù)。

雖有以上研究對(duì)傳統(tǒng)BP算法進(jìn)行了改進(jìn)，但應(yīng)用于噴泉碼時(shí)，復(fù)雜度依然較高。譯碼需接收到一定數(shù)量的碼字后開始譯碼，迭代至預(yù)設(shè)最大次數(shù)后再對(duì)變量節(jié)點(diǎn)進(jìn)行硬判決。若譯碼失敗，需繼續(xù)接收更多數(shù)量的碼字重新迭代，使得之前迭代的信息沒有得到有效利用，復(fù)雜度依然較大。利用“及早判決”的思想，為提高BP譯碼算法應(yīng)用于噴泉碼時(shí)的效率，本文分析了二進(jìn)制加性高斯白噪聲（Binary input additive white Gaussian noise，BIAWGN）信道下LT碼的BP算法原理,根據(jù)理想誤碼率與信噪比及似然比之間的關(guān)系，推導(dǎo)出了變量節(jié)點(diǎn)加入可譯集成功譯碼時(shí)似然比所需達(dá)到的門限值Tre。將迭代過程中似然比達(dá)到門限值的變量節(jié)點(diǎn)加入可譯集提前譯出，不再繼續(xù)參與迭代，一方面減少了迭代過程中的計(jì)算量；另一方面，即使譯碼失敗，開銷增加時(shí)也可利用已經(jīng)達(dá)到門限值成功譯出的部分變量節(jié)點(diǎn)簡(jiǎn)化Tanner圖，只對(duì)未達(dá)到譯碼門限的變量節(jié)點(diǎn)進(jìn)行迭代，進(jìn)一步減少計(jì)算量。仿真實(shí)驗(yàn)表明，該算法與傳統(tǒng)的BP譯碼算法性能相同，但計(jì)算量大大減少，效率顯著提高。

1 傳統(tǒng)BP譯碼算法原理

無線信道中，噴泉碼常用的譯碼算法為對(duì)數(shù)域BP算法，也稱和積譯碼算法（Sum-product,SP）。本文討論BIAWGN信道中LT碼的BP譯碼算法。假設(shè)噴泉的原始信息比特序列為x=(x1,x2,…,xk),噴泉編碼后生成的序列為y=(y1,y2,…,yn)，生成矩陣為G,則y=x*G。 對(duì)編碼序列y進(jìn)行BPSK（Binary phase shift keying）調(diào)制，得到序列y'。經(jīng)BIAWGN信道傳輸后，接收端收到的信息序列為r=(r1,r2,…,rn)，其關(guān)系為

式中：z為信道噪聲，服從N(0,σ2)分布。利用生成矩陣Tanner圖中的聯(lián)系，在變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)之間不斷地相互傳遞似然比信息來逐漸收斂到可靠值，節(jié)點(diǎn)的對(duì)數(shù)似然比定義為

則變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)的似然比迭代公式為[18]

BP譯碼步驟為

(1)初始化。由于沒有先驗(yàn)信息，變量節(jié)點(diǎn)是0和1的概率相同，因此變量節(jié)點(diǎn)的初始似然比為零，即=0。

(2)校驗(yàn)節(jié)點(diǎn)信息更新。如圖1所示，根據(jù)式(4)計(jì)算校驗(yàn)節(jié)點(diǎn)的似然比信息并更新。

(3)變量節(jié)點(diǎn)信息更新。在校驗(yàn)節(jié)點(diǎn)已更新的基礎(chǔ)上，根據(jù)式(4)計(jì)算變量節(jié)點(diǎn)的似然比信息并更新，如圖2所示。

圖1 校驗(yàn)節(jié)點(diǎn)似然比更新Fig.1 Likelihood ratio update of check nodes

圖2 變量節(jié)點(diǎn)似然比更新Fig.2 Likelihood ratio update of variable nodes

(4)判決。步驟(2)和(3)重復(fù)進(jìn)行迭代，達(dá)到規(guī)定次數(shù)后進(jìn)行硬判決，此時(shí)變量節(jié)點(diǎn)似然比信息計(jì)算公式為

判決準(zhǔn)則為

應(yīng)用于噴泉碼進(jìn)行譯碼時(shí)，需接收到一定數(shù)量的數(shù)據(jù)包之后開始譯碼。若譯碼失敗，需增加開銷，繼續(xù)接收更多數(shù)量的數(shù)據(jù)包重新開始迭代，直到完全譯碼成功。

2 可譯門限值Tre的估計(jì)

為減少傳統(tǒng)BP譯碼算法迭代過程中的計(jì)算量，并利用到低開銷譯碼中的有用信息，定義了無線信道中可譯集的概念，將似然比達(dá)到門限值Tre的變量節(jié)點(diǎn)加入可譯集提前譯出。關(guān)于門限值Tre的取值，若太小，則不能保證已加入到可譯集中變量節(jié)點(diǎn)的正確性，可能造成錯(cuò)誤傳播；若太大，則不能保證將正確節(jié)點(diǎn)盡快譯出以減少計(jì)算量。本文根據(jù)理想誤碼率與信噪比和似然比的關(guān)系，推導(dǎo)出了門限值Tre的合適取值，過程如下。

已知在BIAWGN信道中，BPSK調(diào)制模式下，誤碼率BER和信噪比SNR的關(guān)系為

根據(jù)式(3)有

因此在期望達(dá)到誤碼率BER時(shí)，需滿足

可將條件放大至

因此似然比需滿足

將式(9)代入式(13)即可得譯碼門限值Tre為

式中SNR可由式(8)求得。

3 基于可譯集的增量譯碼算法

上面已推導(dǎo)出變量節(jié)點(diǎn)可正確譯碼時(shí)似然比所需達(dá)到的門限值Tre，將該門限值作為變量節(jié)點(diǎn)加入可譯集的判定依據(jù)，利用可譯集從兩方面減少傳統(tǒng)BP譯碼算法中的計(jì)算量。

（1）如圖3所示，在開銷固定的一次譯碼過程中，該算法在每次迭代結(jié)束后對(duì)變量節(jié)點(diǎn)的似然比進(jìn)行一次判定，將似然比Lxi≥Tre的變量節(jié)點(diǎn)xi利用式(6)提前進(jìn)行硬判決，并刪除xi在Tanner圖中的連接。圖中，若x2，x4的似然比達(dá)到譯碼門限值，則加入可譯集并刪去與其相連的邊，不再繼續(xù)參與迭代，以減少計(jì)算量。

為保證縮小后的Tanner圖可繼續(xù)正確迭代，需對(duì)刪除后的信道似然比加以修正：

(a)若變量節(jié)點(diǎn)xi判決為0，則無需修正；(b)若變量節(jié)點(diǎn)xi判決為1，需對(duì)所有與其相連的校驗(yàn)節(jié)點(diǎn)所在的信道似然比進(jìn)行修正：

圖3 利用可譯集簡(jiǎn)化Tanner圖Fig.3 Simplify Tanner graphs using translatable sets

令S表示所有已經(jīng)譯出的所有變量節(jié)點(diǎn)集合，將xi加入集合S，則提前譯出部分節(jié)點(diǎn)后的似然比迭代公式變?yōu)?/p>

繼續(xù)迭代，直至所有變量節(jié)點(diǎn)全部譯出或達(dá)到預(yù)設(shè)最大迭代次數(shù)。若迭代次數(shù)達(dá)到lmax后變量節(jié)點(diǎn)未能全部譯出，則根據(jù)迭代結(jié)束后的最終似然比對(duì)剩余變量節(jié)點(diǎn)進(jìn)行硬判決，判決公式同式(6)。

（2）進(jìn)行增量譯碼時(shí)，在固定開銷下利用上面的迭代算法進(jìn)行迭代及提前譯出。若當(dāng)前開銷下未能成功譯碼，需增大開銷接收更多數(shù)據(jù)包，先利用可譯集簡(jiǎn)化Tanner圖，再對(duì)未譯出節(jié)點(diǎn)進(jìn)行譯碼。如圖4，傳統(tǒng)BP算法在開銷增大時(shí)需進(jìn)行譯碼的Tanner圖為圖4(a)。而圖4(b)中基于可譯集的增量譯碼算法可利用集合S中已經(jīng)成功譯出的部分變量節(jié)點(diǎn)x2,x4簡(jiǎn)化Tanner圖，只對(duì)未譯出的變量節(jié)點(diǎn)按照步驟(1)中固定開銷的情況進(jìn)行迭代及提前譯出，進(jìn)一步減少計(jì)算量。

圖4 增加開銷y6y7y8時(shí)兩種算法Tanner圖比較Fig.4 Tanner map comparison when increasing overhead

4 仿真分析

利用Matlab為工具對(duì)提出的基于可譯集的增量譯碼算法和傳統(tǒng)BP譯碼算法進(jìn)行了仿真比較。考慮LT碼在BIAWGN信道中，BPSK調(diào)制下，取不同碼長(zhǎng)時(shí)的性能和時(shí)間效率比較。仿真次數(shù)取1 000次，最大迭代次數(shù)lmax=30，實(shí)際信道的信噪比SNR'取3dB，期望誤碼率取BER=10-6，本文中用接收到的校驗(yàn)節(jié)點(diǎn)數(shù)目n與變量節(jié)點(diǎn)數(shù)目K的商表示開銷，利用式(14)計(jì)算得到的譯碼門限值Tre=23.57。

圖5和圖6分別仿真了碼長(zhǎng)為2 000和5 000時(shí)兩種算法的誤碼率曲線?？梢钥闯觯绿岢龅淖g碼算法與傳統(tǒng)BP譯碼算法性能幾乎相同，改進(jìn)的算法并沒有造成性能的下降。

5 復(fù)雜度分析

當(dāng)碼長(zhǎng)趨于無窮時(shí)，若信道是二元對(duì)稱信道，則BP譯碼迭代過程中節(jié)點(diǎn)的似然比服從對(duì)稱高斯分布。可利用高斯近似法[19]分析追蹤每次迭代結(jié)束后的高斯均值，即可知此時(shí)的節(jié)點(diǎn)似然比分布。定義度分布函數(shù)

圖5 K=2 000時(shí)兩種譯碼算法的性能比較Fig.5 Decoding performance comparison when K＝2 000

圖6 K=5 000時(shí)兩種譯碼算法的性能比較Fig.6 Decoding performance comparison when K＝5 000

式中：Ωd表示變量節(jié)點(diǎn)度為d的概率。同時(shí)邊角度的輸入度分布函數(shù)λ(x)和輸出度分布函數(shù)ω(x)分別定義為

式中：λd表示與某條邊相連的輸入節(jié)點(diǎn)的度為d的概率，ωd表示與某條邊相連的輸出節(jié)點(diǎn)的度為d的概率，則輸入節(jié)點(diǎn)的似然比均值迭代公式為

式中φ(x)定義為

定義PTre為碼長(zhǎng)無窮時(shí)，似然比達(dá)到門限值的變量節(jié)點(diǎn)所占比例，即

計(jì)算得理想狀態(tài)下增量譯碼算法在不同開銷下，對(duì)應(yīng)的仍需參與迭代的變量節(jié)點(diǎn)所占比例為圖7所示。

由圖7可知，理想狀態(tài)下90%以上的變量節(jié)點(diǎn)在譯碼過程中已達(dá)到門限值可提前譯出，并釋放存儲(chǔ)空間。而傳統(tǒng)BP算法仍需完全迭代所有變量節(jié)點(diǎn)，即完全譯碼成功前參與迭代的變量節(jié)點(diǎn)比例一直為1。因此，基于可譯集的增量譯碼算法在理想情況下在時(shí)間和空間上均可減少90%的復(fù)雜度。

但在實(shí)際應(yīng)用中，碼長(zhǎng)一般為有限值，因此圖8仿真了碼長(zhǎng)為2 000時(shí)兩種算法計(jì)算量的比較。設(shè)Tanner圖中每條邊進(jìn)行一次信息相互傳遞的計(jì)算量為1，取最大迭代次數(shù)lmax=30，開銷取0～1.4變化。因?yàn)閭鹘y(tǒng)BP算法參與迭代的變量節(jié)點(diǎn)固定為最大值不變，因此計(jì)算量隨著開銷的增大而線性遞增。而利用可譯集的增量譯碼算法在開銷較小時(shí)并沒有節(jié)點(diǎn)的似然比達(dá)到門限值，所以和傳統(tǒng)BP算法的計(jì)算量相同。但隨著開銷的增大，達(dá)到門限可譯出并刪去的節(jié)點(diǎn)越來越多，計(jì)算量反而逐漸減少，直到開銷為1時(shí)節(jié)點(diǎn)全部譯出。雖不能達(dá)到理想情況下減少90%的復(fù)雜度，但相比傳統(tǒng)BP算法計(jì)算量已大大減少。

圖7 碼長(zhǎng)無窮時(shí)Tre-BP算法未達(dá)到門限值的比例Fig.7 Ratio of no-decoding infinite length codes with Tre-BP decoding

圖8 碼長(zhǎng)K=1 000時(shí)兩種算法在不同開銷下計(jì)算量Fig.8 Computation complexity comparison in different overhead when K=1 000

表1給出了相同仿真條件下基于可譯集的增量譯碼算法和傳統(tǒng)BP譯碼算法的執(zhí)行時(shí)間?？梢钥闯龌诳勺g集的增量譯碼算法執(zhí)行效率大大提高，約為傳統(tǒng)BP算法的5倍。

表1 不同碼長(zhǎng)下兩種譯碼算法的運(yùn)行時(shí)間比較Tab.1 Time comparison of different code lengths

6 結(jié)束語

本文針對(duì)無線信道中傳統(tǒng)BP譯碼算法應(yīng)用于數(shù)字噴泉碼時(shí)復(fù)雜度較高、效率低下的問題，提出了一種基于可譯集的增量譯碼算法。該算法首先提出了無線信道中可譯集的概念，并給出了合適門限值Tre選取的理論依據(jù)。一方面，在開銷固定時(shí)將譯碼過程中似然比高于門限值Tre的變量節(jié)點(diǎn)歸入可譯集，提前譯出并停止參與迭代，減少了迭代過程中的計(jì)算量。另一方面，利用可譯集的概念，即使在低開銷譯碼失敗時(shí)，也可利用其中已經(jīng)達(dá)到門限值成功譯出的部分變量節(jié)點(diǎn)先簡(jiǎn)化Tanner圖，增加開銷時(shí)只對(duì)未達(dá)到譯碼門限的變量節(jié)點(diǎn)進(jìn)行迭代譯碼，進(jìn)一步減少了計(jì)算量。此外，利用高斯近似法對(duì)改進(jìn)后的譯碼算法進(jìn)行復(fù)雜度理論分析，在碼長(zhǎng)趨于無窮的理想狀態(tài)下分析得出90%以上的變量節(jié)點(diǎn)在譯碼過程中已達(dá)到門限值可提前譯出，并釋放存儲(chǔ)空間，在時(shí)間和空間上均可減少90%的復(fù)雜度。最后又通過仿真實(shí)驗(yàn)表明，在碼長(zhǎng)有限的實(shí)際情況中，該算法與傳統(tǒng)BP譯碼算法相比，擁有相同的譯碼性能，但大大減少了計(jì)算量，譯碼效率顯著提高。