譯碼迭代次數約束下累積無率碼的優化設計

雷維嘉, 陳勝男

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

?

譯碼迭代次數約束下累積無率碼的優化設計

雷維嘉, 陳勝男

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

以最大化碼率為目標設計的無率編碼通常能夠實現逼近容量的性能,但是這種編碼在譯碼時需要進行非常多次(理論上是無窮多次)的迭代才能達到預期的誤比特率性能。基于外部信息轉移圖的漸近收斂分析,提出一種在有限譯碼迭代次數約束下的非系統累積無率碼編碼度分布的優化設計方法,給出此優化問題的數學模型。通過求解該優化問題可得到滿足要求的編碼度分布函數。仿真結果表明,與以最大化碼率為目標設計的編碼相比,在有限的譯碼迭代次數下,所提出的方法設計的編碼能獲得更好的糾錯性能,且譯碼迭代次數越小,性能優勢越明顯。

累積無率碼; 迭代譯碼; 外部信息轉移圖; 迭代次數約束

0　引　言

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

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

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

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

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

1　AR碼

1.1編碼

圖1　AR碼的Tanner圖

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

AR碼的編碼過程如下:

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

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

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

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

(1)

(2)

1.2譯碼及EXIT圖

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

圖2　非系統AR碼的譯碼器結構

(3)

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

(4)

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

(5)

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

(6)

(7)

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

(8)

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

(9)

(10)

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

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

圖3　非系統AR碼的EXIT圖

2　編碼度分布的設計

(11)

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

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

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

(12)

式中,Q(·)定義為

(13)

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

(14)

(15)

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

據此,優化問題轉換為固定譯碼迭代次數下,最大化譯碼器間傳遞的信息:

(16)

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

(17)

式中,fj表示度為j的AD&CND的轉移函數。那么

(18)

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

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

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

3　性能仿真和分析

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

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

圖4　LT碼、Raptor碼和非系統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信道下,采用本文提出的最大化信息傳遞的設計方法得到的不同譯碼迭代次數限制下的最優非系統AR碼的校驗節點度分布。圖5～圖7分別給出3種不同信道下,固定最大譯碼迭代次數L=20、80、150時,以最大化碼率[7]和本文的以最大化譯碼器間傳遞信息為目標優化的非系統AR碼的BER性能仿真結果。最大化碼率的度分布通過求解式(11)得到,該優化結果與譯碼時限制的最大迭代次數L無關;而通過求解優化問題(16)可以得到在某一固定的L條件下,譯碼器間傳遞信息最大化的校驗節點度分布。

表1　不同信道條件下的最優校驗節點度分布

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

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

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

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

4　結　論

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

[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；網絡優先出版日期：2016-03-04。

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

TN 919.3

A

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

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

E-mail: leiwj@cqupt.edu.cn

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

E-mail: csn_cqupt@163.com

網絡優先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20160304.1300.002.html