譯碼迭代次數(shù)約束下累積無率碼的優(yōu)化設(shè)計

雷維嘉, 陳勝男

(重慶郵電大學(xué)移動通信技術(shù)重慶市重點實驗室, 重慶 400065)

?

譯碼迭代次數(shù)約束下累積無率碼的優(yōu)化設(shè)計

雷維嘉, 陳勝男

(重慶郵電大學(xué)移動通信技術(shù)重慶市重點實驗室, 重慶 400065)

以最大化碼率為目標設(shè)計的無率編碼通常能夠?qū)崿F(xiàn)逼近容量的性能,但是這種編碼在譯碼時需要進行非常多次(理論上是無窮多次)的迭代才能達到預(yù)期的誤比特率性能?；谕獠啃畔⑥D(zhuǎn)移圖的漸近收斂分析,提出一種在有限譯碼迭代次數(shù)約束下的非系統(tǒng)累積無率碼編碼度分布的優(yōu)化設(shè)計方法,給出此優(yōu)化問題的數(shù)學(xué)模型。通過求解該優(yōu)化問題可得到滿足要求的編碼度分布函數(shù)。仿真結(jié)果表明,與以最大化碼率為目標設(shè)計的編碼相比,在有限的譯碼迭代次數(shù)下,所提出的方法設(shè)計的編碼能獲得更好的糾錯性能,且譯碼迭代次數(shù)越小,性能優(yōu)勢越明顯。

累積無率碼; 迭代譯碼; 外部信息轉(zhuǎn)移圖; 迭代次數(shù)約束

0　引　言

數(shù)字噴泉碼[1]最初是為了實現(xiàn)刪除信道中高效可靠的傳輸而提出的。與傳統(tǒng)的固定碼率的編碼不同,它在發(fā)送端編碼時不需要事先固定碼率,而是可以不斷產(chǎn)生編碼符號,直到接收端譯碼成功并反饋確認(acknowledge, ACK)信息給發(fā)送端后停止編碼和發(fā)送。由于碼率并不固定,因此是一種無率編碼(rateless codes,RC)。無率碼非常適合用于時變信道中信息的傳輸。

Luby傳輸(Luby transform, LT)碼[2]是Luby在2002年提出的第一種實用的噴泉碼,其在刪除信道下有很好的性能。LT碼的基本結(jié)構(gòu)和非規(guī)則非系統(tǒng)的低密度生成矩陣(low density generator matrix, LDGM)碼[3]類似,也可以用于噪聲信道。但在噪聲信道下,正如文獻[4]中所指出,LDGM碼存在高錯誤平層,且不會隨著分組長度的增加而有所改善。文獻[5]的研究也發(fā)現(xiàn)LT碼在二進制對稱信道(binary symmetric channel, BSC)和二進制輸入加性高斯白噪聲(binary input additive white Gaussian noise, BIAWGN)信道中存在明顯的錯誤平層。Raptor碼[6]通過級聯(lián)一個高碼率的預(yù)編碼,有效地改善了錯誤平層的問題,但同時也增加了編碼和譯碼復(fù)雜度。為了進一步降低Raptor碼級聯(lián)預(yù)編碼帶來的高復(fù)雜度,文獻[7]提出了累積無率(accumulate rateless, AR)碼的概念,它由在LDGM無率碼編碼器后級聯(lián)一個累加器構(gòu)成。這種碼在高斯白噪聲(additive white Gaussian noise, AWGN)信道下與Raptor碼有著相當?shù)男阅?但編譯碼的復(fù)雜度更低。

無率編碼在AWGN信道下的譯碼一般采用置信傳播(belief propagation, BP)譯碼算法[8]。這種算法通過在變量節(jié)點和校驗節(jié)點間迭代地傳遞消息進行譯碼。在無率碼設(shè)計的相關(guān)文獻中,多以最大化碼率為目標設(shè)計優(yōu)化的校驗節(jié)點度分布以獲得逼近容量的性能。這種碼設(shè)計中優(yōu)化的方向是獲得逼近信道容量的最大碼率,它的錯誤概率會隨著碼長和譯碼迭代次數(shù)的增加而減小。這種編碼在設(shè)計時沒有考慮譯碼迭代時的收斂速度,在BP譯碼時需要進行非常多次(理論上是無窮多次)的迭代才能獲得預(yù)期的性能,這無疑帶來了很大的譯碼復(fù)雜度。如果通過減小最大譯碼迭代次數(shù)從而減小平均譯碼迭代次數(shù),該碼的糾錯能力又會有較大的下降。

實現(xiàn)譯碼復(fù)雜度和碼率折中的編碼的設(shè)計已成為近年來無率碼設(shè)計中的研究問題之一。文獻[9]針對碼率固定的非規(guī)則重復(fù)累積(irregular repeat accumulate, IRA)碼在刪除信道下的譯碼復(fù)雜度和碼率折中問題進行了研究。文獻[10]給出了給定目標錯誤概率時,BIAWGN信道下譯碼迭代次數(shù)最小的非規(guī)則低密度奇偶校驗(low-density parity-check, LDPC)碼的設(shè)計。文獻[11]從信息論的角度分析了無率碼的性能和復(fù)雜度折中。文獻[12-13]則給出了LT碼的低復(fù)雜度譯碼算法。

在本文中,我們考慮BIAWGN信道下非系統(tǒng)AR碼的譯碼復(fù)雜度-碼率折中,從另一個角度出發(fā),基于外部信息轉(zhuǎn)移(extrinsic information transfer, EXIT)圖[14]的漸近收斂分析,設(shè)計一種有限譯碼迭代次數(shù)約束下性能最好的非系統(tǒng)AR碼。這通過在給定最大譯碼迭代次數(shù)時,以最大化譯碼器間傳遞的信息為目標來實現(xiàn),通過求解凸優(yōu)化問題可得到最優(yōu)非系統(tǒng)AR碼的校驗節(jié)點度分布。仿真表明,與以最大化碼率為目標設(shè)計的非系統(tǒng)AR碼相比,在有限的譯碼迭代次數(shù)下,本文提出的編碼方案能夠獲得更好的糾錯性能,且譯碼迭代次數(shù)越小,所提方案的性能優(yōu)勢越明顯。

1　AR碼

1.1編碼

圖1　AR碼的Tanner圖

文獻[15]指出采用優(yōu)先選擇度值最小的信息節(jié)點來產(chǎn)生校驗節(jié)點的方法,使得各個信息節(jié)點的度數(shù)基本一致(記為ds),能夠有效地改善LT碼的錯誤平層。這樣信息節(jié)點度分布為λ(x)=xds-1,即絕大多數(shù)信息節(jié)點的度都為ds(可能會存在極少數(shù)的信息節(jié)點度為ds+1或ds-1)。本文的仿真中涉及到的LT碼的編碼都采用該編碼方法。

AR碼的編碼過程如下:

(1) 根據(jù)校驗節(jié)點度分布ρ(x)隨機選擇一個度值d;

(2) 通過優(yōu)先選擇度值最小的信息節(jié)點選擇d個信息節(jié)點;

(3) 將這d個信息節(jié)點進行模2加產(chǎn)生中間比特bk(k=1,2,…);

(4) 編碼比特ck由當前中間比特bk和前一編碼比特ck-1模2加得到,設(shè)c0=0,則

(1)

(2)

1.2譯碼及EXIT圖

AR碼采用BP譯碼算法,譯碼器包括3個部分:變量節(jié)點譯碼器(variablenodedecoder,VND),校驗節(jié)點譯碼器(checknodedecoder,CND)和累加器譯碼器(accumulatordecoder,AD)。AD能夠獲得信道中的觀測值。通常,將AD和CND作為一個譯碼單元,即AD&CND。非系統(tǒng)AR碼的譯碼器結(jié)構(gòu)如圖2所示。圖2中，互信息I的下標中的“A”為輸入,“E”為輸出。

圖2　非系統(tǒng)AR碼的譯碼器結(jié)構(gòu)

(3)

接收符號的對數(shù)似然比值(logarithmlikelihoodratios,LLRs)定義為

(4)

式中，p(y|x)表示輸入信號Pr(x=±1)=1/2的條件下,AWGN信道的輸出信號y的條件概率密度函數(shù)。接收符號LLRs的方差為

(5)

AR碼的譯碼器有VND、AD&CND兩個分量譯碼器,所以有兩類EXIT曲線,IE,VND～IA,VND和IE,AD&CND～IA,AD&CND曲線。類似文獻[16]中的分析方法,可以得到非系統(tǒng)AR碼的兩條EXIT曲線對應(yīng)的函數(shù)的表達式:

(6)

(7)

式中,IE,VND表示VND的輸出互信息;IA,VND表示其先驗輸入互信息;IE,AD&CND表示合并的AD和CND的輸出互信息;IA,CND表示CND的先驗輸入互信息;AD的輸出互信息和先驗輸入互信息分別由IE,AD和IA,AD表示。J(·)為傳輸?shù)腂PSK符號與接收符號LLRs之間的互信息:

(8)

J(σ)是單調(diào)遞增函數(shù),存在唯一的反函數(shù)σ=J-1(I)。為了簡便起見,使用文獻[17]中給出的近似表達式來計算J(·)和J-1(·):

(9)

(10)

式中,H1=0.307 3,H2=0.893 5,H3=1.106 4。

圖3為非系統(tǒng)AR碼的EXIT圖。x軸表示VND的輸出互信息IE,VND以及AD&CND的先驗輸入互信息IA,AD&CND。y軸表示VND的先驗輸入互信息IA,VND以及AD&CND的輸出互信息IE,AD&CND。定義AD&CND的EXIT函數(shù)為y=f(x),VND的EXIT函數(shù)為x=g(y),其中x=IE,VND=IA,AD&CND,y=IA,VND=IE,AD&CND,兩者的具體表達式可由式(6)和式(7)得到。

圖3　非系統(tǒng)AR碼的EXIT圖

2　編碼度分布的設(shè)計

(11)

其中,第一個約束條件為保證譯碼成功的充分條件,即譯碼器本次迭代所傳遞的信息必須大于上次迭代傳遞的信息。第二個約束條件為非系統(tǒng)AR碼的譯碼開始條件,即必須有度為1的校驗節(jié)點存在。通過對一系列離散的信息節(jié)點度值ds求解問題(11)可以得到優(yōu)化的校驗節(jié)點度分布,即使得碼率最大的ds和校驗節(jié)點度分布ρ(x)作為最優(yōu)解。

這種度分布優(yōu)化問題在設(shè)計過程中并未考慮譯碼復(fù)雜度,為在最優(yōu)碼率下實現(xiàn)預(yù)期的誤比特率(bit error rate,BER)性能,在BP譯碼時需要進行非常多次(理論上是無窮多次)的迭代,在實際情況下,譯碼的迭代次數(shù)卻是有限的。

本文考慮設(shè)計一種有限譯碼迭代次數(shù)約束下性能最好的碼,從而實現(xiàn)譯碼復(fù)雜度-碼率的折中。非系統(tǒng)AR碼譯碼時,在進行L次迭代后的平均BER[7]如下:

(12)

式中,Q(·)定義為

(13)

在L一定時,只需要將問題(11)中的目標函數(shù)換為非系統(tǒng)AR碼的平均誤比特率Pe,就可以使得其經(jīng)過一定的譯碼迭代次數(shù)后錯誤概率最小。由于J-1(·)是一個連續(xù)單調(diào)遞增函數(shù),而Q(·)是一個連續(xù)單調(diào)遞減函數(shù),最小化Pe等價于在L次迭代后使譯碼器間傳遞的信息y(L)最大化。

(14)

(15)

式中，h(y)=f(g(y))。經(jīng)過足夠多的迭代次數(shù)后,譯碼器會收斂于一個固定點y=f(g(y))=h(y),對于性能良好的碼,這個點通常在y值接近于1時出現(xiàn)。

據(jù)此,優(yōu)化問題轉(zhuǎn)換為固定譯碼迭代次數(shù)下,最大化譯碼器間傳遞的信息:

(16)

式中,所有的約束條件關(guān)于ρj都是線性的。因此,如果目標函數(shù)y(L)是凹的,那么上述問題將是一個凸優(yōu)化問題[18]。AD&CND的EXIT函數(shù)f(x)可以用式(17)表示

(17)

式中,fj表示度為j的AD&CND的轉(zhuǎn)移函數(shù)。那么

(18)

可見,y是關(guān)于校驗節(jié)點度ρj的線性函數(shù)。那么問題(16)中,目標函數(shù)和約束條件都是線性的,因此這是一個線性規(guī)劃。文獻[18]中指出,任何線性規(guī)劃都是凸優(yōu)化問題,該凸優(yōu)化問題可用相關(guān)的優(yōu)化工具求解。

對任意L值,都可以通過求解上式得到優(yōu)化的校驗節(jié)點度分布。觀察式(16),可以看到,約束條件與最大迭代次數(shù)L都是相互獨立的,且此優(yōu)化問題只需知道f(x)和g(y)的表達式,而這對許多編碼都是可得的。

由于式(16)是以最大化譯碼器間傳遞的信息為優(yōu)化目標,因此將該方案稱為最大化譯碼器間信息傳遞的方案,簡稱為最大化信息方案。

3　性能仿真和分析

在本節(jié)的仿真中,信息比特長度為K=10 000,采用BPSK調(diào)制方式,符號能量Es=1。凸優(yōu)化問題式(16)通過Matlab的CVX工具箱求解。通過仿真不同信道容量下誤比特率隨碼率的變化情況來驗證編碼的性能。為更好地反映本文方法設(shè)計的編碼的性能,我們將其與以最大化碼率為目標優(yōu)化的編碼進行性能比較。

圖4給出信道容量C=3/4 bit/symbol (噪聲標準差σn=0.677 0)的BIAWGN信道下的LT碼、Raptor碼和非系統(tǒng)AR碼的BER性能,最大譯碼迭代次數(shù)設(shè)定為150。圖中的橫坐標為碼率的倒數(shù)。其中,LT碼采用文獻[19]中的度分布,Raptor碼的預(yù)編碼為碼率為0.95的(3,60)的規(guī)則LDPC碼,非系統(tǒng)AR碼的度分布通過求解本文提出的最大化譯碼器間傳遞信息的優(yōu)化問題式(16)得到。從圖4中可以看到,非系統(tǒng)AR碼和Raptor碼有著相當?shù)腂ER性能,甚至優(yōu)于Raptor碼。LT碼雖然在碼率較大時有更好的性能,但是存在較高的錯誤平層,BER并不能隨碼率的下降而迅速下降,而非系統(tǒng)AR碼和Raptor碼則在仿真中沒有出現(xiàn)錯誤平層。這是由于Raptor碼通過在LT碼編碼器前級聯(lián)一個預(yù)編碼構(gòu)成,在譯碼時,Raptor碼先在內(nèi)層進行LT譯碼,再在外層進行LDPC譯碼。一些在LT譯碼時沒有糾正的錯誤可在LDPC碼的譯碼中糾正,解決了LT碼的高錯誤平層問題,大大改善了LT碼在噪聲信道中的性能。而AR碼則是通過在LT編碼器后級聯(lián)一個累加器構(gòu)成,解決了LT碼的Tanner圖中編碼節(jié)點度值恒為1的問題,有效地改善了LT碼的錯誤平層。與Raptor碼級聯(lián)一個預(yù)編碼器相比,AR碼僅需級聯(lián)一個累加器,大大降低了編譯碼的復(fù)雜度,更便于實現(xiàn)。

圖4　LT碼、Raptor碼和非系統(tǒng)AR碼的BER性能

表1為信道容量C=3/4 bit/symbol (σn=0.677 0),C=2/3 bit/symbol (σn=0.766 6)和C=1/2 bit/symbol (σn=0.978 6)的BIAWGN信道下,采用本文提出的最大化信息傳遞的設(shè)計方法得到的不同譯碼迭代次數(shù)限制下的最優(yōu)非系統(tǒng)AR碼的校驗節(jié)點度分布。圖5～圖7分別給出3種不同信道下,固定最大譯碼迭代次數(shù)L=20、80、150時,以最大化碼率[7]和本文的以最大化譯碼器間傳遞信息為目標優(yōu)化的非系統(tǒng)AR碼的BER性能仿真結(jié)果。最大化碼率的度分布通過求解式(11)得到,該優(yōu)化結(jié)果與譯碼時限制的最大迭代次數(shù)L無關(guān);而通過求解優(yōu)化問題(16)可以得到在某一固定的L條件下,譯碼器間傳遞信息最大化的校驗節(jié)點度分布。

表1　不同信道條件下的最優(yōu)校驗節(jié)點度分布

圖5　不同譯碼迭代次數(shù)限制下的BER性能(C=3/4 bit/symbol)

仿真結(jié)果表明,在譯碼迭代次數(shù)限制的約束條件下,本文提出的最大化譯碼器間傳遞信息的設(shè)計方法設(shè)計的編碼性能優(yōu)于以最大化碼率為目標的設(shè)計方法設(shè)計的編碼。從圖中可以看出,在迭代限制次數(shù)較小時,本文設(shè)計的編碼的性能優(yōu)勢較為明顯。隨著迭代限制次數(shù)的增大,該性能優(yōu)勢逐漸減小。如在C=2/3 bit/symbol,迭代次數(shù)限制為L=20、80、150時,在獲得10-5的誤比特率時,與以最大化碼率為目標設(shè)計的編碼相比,本文設(shè)計的編碼需要接收的碼長縮短了0.3%、0.21%、0.09%,換算為減少的信噪比要求分別為0.025 7 dB、0.017 9 dB、0.007 2 dB。注意到以最大化碼率為目標設(shè)計的編碼在L=20、BER為10-5時,距離香農(nóng)極限也僅為0.947 4 dB,本文方案0.025 7 dB的性能改善已經(jīng)相當可觀。在迭代次數(shù)足夠大時,以最大化碼率為目標設(shè)計的編碼的性能已接近設(shè)計目標性能,因此與本文方案設(shè)計的編碼性能相近。

圖6　不同譯碼迭代次數(shù)限制下的BER性能(C=2/3 bit/symbol)

圖7　不同譯碼迭代次數(shù)限制下的BER性能(C=1/2 bit/symbol)

4　結(jié)　論

以最大化碼率為目標的編碼設(shè)計方法通常能夠?qū)崿F(xiàn)逼近容量的性能,但是這種設(shè)計過程中并未考慮譯碼復(fù)雜度的問題,在BP譯碼時需要進行非常多次的迭代才能達到預(yù)期的BER性能。本文研究了BIAWGN信道中有限譯碼迭代次數(shù)約束下非系統(tǒng)AR碼的優(yōu)化設(shè)計。通過對EXIT圖的漸近收斂分析,給出了編碼校驗節(jié)點度分布優(yōu)化問題的數(shù)學(xué)模型,通過求解該優(yōu)化問題可以得到任一譯碼迭代次數(shù)約束下糾錯性能最好的非系統(tǒng)AR碼。這種方法在編碼設(shè)計時考慮了譯碼迭代次數(shù),在譯碼復(fù)雜度和譯碼時延受限的實際應(yīng)用中有著重要的意義。通過仿真比較了所提方法和以最大化碼率為目標的設(shè)計方法所設(shè)計的非系統(tǒng)AR碼的BER性能,結(jié)果表明,在有限的譯碼迭代次數(shù)約束下,本文所提出的方案設(shè)計的編碼具有更好的誤碼性能,而譯碼迭代的限制次數(shù)越小,性能優(yōu)勢越明顯。

[1] Byers J W, Luby M, Mitzenmacher M. A digital fountain approach to asynchronous reliable multicast[J].IEEEJournalonSelectedAreasinCommunications, 2002, 20(8): 1528-1540.

[2] Luby M. LT codes[C]∥Proc.oftheIEEESymposiumonFoundationsofComputerScience, 2002: 271-280.

[3] Garcia-Frias J, Zhong W. Approaching Shannon performance by iterative decoding of linear codes with low-density generator matrix[J].IEEECommunicationsLetters, 2003, 7(6): 266-268.

[4] Mackay D J C. Good error-correcting codes based on very sparse matrices[J].IEEETrans.onInformationTheory, 2002, 45(2): 399-431.

[5] Palanki R, Yedidia J S. Rateless codes on noisy channels[C]∥Proc.oftheInternationalSymposiumonInformationTheory, 2004: 37-42.

[6] Shokrollahi A. Raptor codes[J].IEEETrans.onInformationTheory, 2006, 52(6): 2551-2567.

[7] Chen S L, Zhang Z Y, Zhu L L, et al. Accumulate rateless codes and their performances over additive white Gaussian noise channel[J].IETCommunications, 2013, 7(4): 372-381.

[8] Jenkac H, Mayer T, Stockhammer T, et al. Soft decoding of LT-codes for wireless broadcast[C]∥Proc.oftheISTMobileSummit,2005：369-374.

[9] Grant A, Land I, and Wang G, Iteration-constrained design of IRA codes[C]∥Proc.oftheInternationalZurichSeminaronCommunications, 2012: 67-70.

[10] Smith B, Ardakani M, Yu W, et al. Design of irregular LDPC codes with optimized performance-complexity tradeoff[J].IEEETrans.onCommunications,2010,58(2):489-499.

[11] Dohyung P, Chung S Y. Performance complexity tradeoffs of rateless codes[C]∥Proc.oftheIEEEInternationalSympo-siumonInformationTheory, 2008: 2056-2060.

[12] Hussian I, Xiao M, Rasmussen L K. Reduced-complexity decoding of LT codes over noisy channels[C]∥Proc.oftheIEEEWirelessCommunicationandNetworkingConference, 2013: 3856-3860.

[13] Hussian I, Land I, Chan T H, et al. A new design framework for LT codes over noisy channels[C]∥Proc.oftheInternationalSymposiumonInformationTheory, 2014: 2162-2166.

[14] Ashikhmin A, Kramer G, Ten B S. Extrinsic information transfer functions: model and erasure channel properties[J].IEEETrans.onInformationTheory, 2004, 50(11): 2657-2673.

[15] Hussain I, Xiao M, Rasmussen L K. Error floor analysis of LT codes over the additive white Gaussian noise channel[C]∥Proc.oftheIEEEGlobalTelecommunicationsConference, 2011: 1-5.

[16] Ten B S, Kramer G. Design of repeat-accumulate codes for iterative detection and decoding[J].IEEETrans.onSignalProcessing, 2003, 51(11):2764-2772.

[17] Brannstrom F, Rasmussen L K, Grant A J. Convergence analysis and optimal scheduling for multiple concatenated codes[J].IEEETrans.onInformationTheory, 2005,51(9): 3354-3364.

[18] Boyd S, Vandenberghe L.Convexoptimization[M]. Cambridge university press, 2004：668-680.

[19] Venkiah A, Poulliat C, Declercq D. Jointly decoded raptor codes: analysis and design for the BIAWGN channel[J].EURASIPJournalonWirelessCommunicationsandNetworking, 2009,16(1): 1-11.

Optimized design for accumulate rateless codes with iterative decoding number constraint

LEI Wei-jia, CHEN Sheng-nan

(Chongqing Key Lab of Mobile Communications Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, China)

The rateless codes designed by the methods which aim to maximize the coding rate can usually approach capacity. However a large number of iterations (theoretically infinite) are needed in the process of iterative decoding to achieve the desired bit error rate performance. Based on the asymptotic convergence analysis of extrinsic information transfer charts, an optimization design method for the degree distributions of non-systematic accumulate rateless codes with a fixed number of decoding iterations is proposed and the mathematical model for optimization is formulated. The degree distributions satisfying the requirements can be obtained by solving the mathematical problem. Simulations show that, compared with the codes designed by the traditional maximizing coding rate method, for a given number of decoding iterations, the proposed design scheme can achieve better error correcting performance. What’s more, the less the number of iterations, the more obvious the advantage is.

accumulate rateless code; iterative decoding; extrinsic information transfer chart; iterative decoding number constraint

2015-08-10；

2016-01-16；網(wǎng)絡(luò)優(yōu)先出版日期：2016-03-04。

國家自然科學(xué)基金(61271259，61301123，61471076)；重慶市基礎(chǔ)與前沿研究計劃(cstc2015jcyjA40047)；長江學(xué)者和創(chuàng)新團隊發(fā)展計劃項目(IRT1299)；重慶市科委重點實驗室專項項目資助課題

TN 919.3

A

10.3969/j.issn.1001-506X.2016.08.32

雷維嘉(1969-),男,教授,博士,主要研究方向為無線和移動通信技術(shù)。

E-mail: leiwj@cqupt.edu.cn

陳勝男(1993-),女,碩士研究生,主要研究方向為無率碼編碼。

E-mail: csn_cqupt@163.com

網(wǎng)絡(luò)優(yōu)先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20160304.1300.002.html