基于高斯近似的LDPC碼TDMP算法分析

王秀敏,曹維林,單 良,洪 波,李勁松

(中國計量大學(xué) 信息工程學(xué)院,浙江 杭州 310018)

基于高斯近似的LDPC碼TDMP算法分析

王秀敏,曹維林,單 良,洪 波,李勁松

(中國計量大學(xué) 信息工程學(xué)院,浙江 杭州 310018)

針對目前缺少對LDPC碼TDMP算法理論分析的問題,提出了TDMP算法的高斯近似.基于BP算法和對稱條件,得到結(jié)果收斂的TDMP算法的高斯近似.利用高斯近似來分析TDMP算法的譯碼收斂性,為論證TDMP算法的優(yōu)越性能提供了理論依據(jù).基于Wimax標準,分別對BP算法和TDMP算法的高斯近似進行仿真.仿真結(jié)果表明,在相同情況下,TDMP算法譯碼收斂速度更快,需要的迭代次數(shù)更少.同時，給出了TDMP算法分別采用高斯近似和密度進化時的門限值,它們的差別僅為0.03～0.08 dB.

LDPC碼;高斯近似;TDMP算法;收斂速度;門限值

LDPC碼[1-2]是Gallager在1962年首次提出來的.1996年,D MacKay,M Neal等人[3]LDPC碼重新進行了研究,發(fā)現(xiàn)LDPC碼具有逼近Shannon極限且實現(xiàn)復(fù)雜度低的優(yōu)異性能,并在Gallager的概率迭代譯碼算法的基礎(chǔ)上,提出了BP算法[4],使得LDPC碼的研究跨入了一個新的階段,成為了信道編碼理論的研究熱點.

Richardson等人基于Gallager的思想,引入了密度進化[4]的概念,密度進化可以用來計算LDPC碼消息傳遞譯碼時的容量,即信道參數(shù)的門限值[6-7].也就是說,會存在一個噪聲功率σ*,當噪聲功率大于σ*時,無論迭代多少次,誤碼率一定大于某一個正常數(shù);當噪聲功率小于σ*時,只要迭代次數(shù)足夠多,誤碼率最終會趨向無窮小.于是，這個噪聲功率σ*就是門限值.對于Binary input additive white gaussian noise(BIAWGN)信道,可以用高斯近似[8]代替密度進化,以簡化譯碼算法的分析.BP算法是LDPC碼譯碼的基本算法,雖然該算法能夠獲得接近Shannon限的誤碼率性能,但是迭代過程中的校驗節(jié)點需要處理多次非線性運算,所以BP算法的實現(xiàn)復(fù)雜度較高.隨著對譯碼算法研究的進一步深入,Mansour和Shanbhag提出了TDMP的分層譯碼算法[8-10].TDMP的分層譯碼算法在獲得高吞吐率的同時可以加快迭代譯碼的收斂速度,最好的情況下,可以比BP算法減少一半的平均迭代次數(shù).

Mansour在文獻[10]中,利用EXIT圖分析了TDMP算法的譯碼收斂性.而本文是在研究BP算法高斯近似的基礎(chǔ)上,提出了TDMP算法的高斯近似,從高斯近似的角度來分析TDMP算法的譯碼收斂性,從而為論證TDMP算法的優(yōu)越性能提供更多的理論依據(jù);并在Wimax標準下,對LDPC碼進行仿真,得到BP算法和TDMP算法高斯近似的性能曲線,從而驗證了TDMP算法收斂速度更快.

1 BP算法的高斯近似

對于(dv,dc)規(guī)則LDPC碼,校驗節(jié)點消息和變量節(jié)點消息的迭代表示[5]分別如式(1)和(2):

(1)

(2)

已知均值為m,方差為σ2的高斯分布,在對稱條件下可簡化為σ2=2m[5],又由于高斯分布可以完全由其均值和方差決定,所以在迭代的過程中,只需考慮均值m.

(3)

(4)

其中,φ(x)的表達式如式(5)[8]:φ(x)=

(5)

規(guī)則和非規(guī)則LDPC碼的誤碼率的計算都如式(6)[8]:

(6)

2 TDMP算法的高斯近似分析

TDMP算法的核心是對每個分層依次譯碼.在進行迭代譯碼時,下一層消息的更新可以直接使用上一層更新后的消息,這加快了譯碼的收斂速度.但是,這種分層譯碼算法的本質(zhì)是優(yōu)化消息傳遞的流程,并沒有改變每一層水平消息更新算法的具體實現(xiàn)方式,因此BP算法也是適用于分層譯碼的.接下來對TDMP算法高斯近似的分析就是基于BP算法的.每一層水平消息更新的分析同BP算法校驗節(jié)點消息的更新,而BP算法校驗節(jié)點消息更新這部分內(nèi)容在第1節(jié)中已經(jīng)介紹過了,所以,接下來重點在于變量節(jié)點消息更新這部分內(nèi)容.

(7)

(8)

根據(jù)對稱性條件中的校驗節(jié)點對稱,式(8)右邊可寫成式(9)形式[13]:

(9)

(10)

對式(7)和式(10)左右兩邊同時取期望,得:

(11)

(12)

3 仿真結(jié)果分析

圖1 BP算法時6種碼率的誤碼率性能Figure 1 BER of BP algorithm at 6 code rates

Wimax標準定義了1/2、2/3A、2/3B、3/4A、3/4B和5/6共6種不同碼率的LDPC碼.在BIAWGN信道下,對這6種碼率的LDPC碼進行了仿真計算,BP算法時,最大迭代次數(shù)設(shè)為20,TDMP算法時,最大迭代次數(shù)設(shè)為10.

圖1和圖2分別為BP算法和TDMP算法在6種碼率下的LDPC碼高斯近似的性能曲線圖,其中1/2碼率信噪比取值區(qū)間為0～2.5 dB,2/3A和2/3B碼率信噪比取值區(qū)間為0.5～3.0 dB,3/4A和3/4B碼率信噪比取值區(qū)間為1.0～3.5 dB,5/6碼率信噪比取值區(qū)間為1.5～4.0 dB.

圖2 TDMP算法時6種碼率的誤碼率性能Figure 2 BER of TDMP algorithm at 6 code rates

選擇碼率為1/2,信噪比為1.5 dB時進行詳細討論,此時BP算法和TDMP算法誤碼率與迭代次數(shù)的關(guān)系如圖3.從圖3中可以看出,TDMP算法的收斂速度比BP算法快,并且誤碼率都低于某一個誤碼率,例如10-5時,BP算法大約需要迭代8次,而TDMP算法只需4次.

圖3 誤碼率與迭代次數(shù)的關(guān)系Figure 3 Relationship between BER and iterations

圖4表示碼率為1/2時,在不同信噪比下,達到期望誤碼率(設(shè)為10-5)時,BP算法和TDMP算法各需要的迭代次數(shù).從圖4中可以看出,當信噪比分別為0和0.5 dB時,在最大迭代次數(shù)內(nèi),BP算法和TDMP算法都達不到設(shè)定的期望誤碼率.當信噪比大于0.5 dB時,TDMP算法所需的迭代次數(shù)都比BP算法少,最好情況下,TDMP算法所需的迭代次數(shù)比BP算法少一半.

圖4 不同信噪比下達到期望誤碼率時所需的迭代次數(shù)Figure 4 Iterations for reaching to excepted BER under different SNR

圖3和圖4的仿真結(jié)果表明,我們可以從高斯近似的角度證明TDMP算法比BP算法譯碼收斂速度更快,平均迭代次數(shù)更少.

4 門限值分析

信道參數(shù)具有一個門限值,門限值一般是指噪聲功率.給定LDPC碼度的分布、期望誤碼率、迭代次數(shù),找到一個最大的噪聲功率σ*,當噪聲功率超過σ*時,在設(shè)定的迭帶次數(shù)內(nèi),誤碼率無法達到期望誤碼率;當噪聲功率小于σ*時,在設(shè)定迭帶次數(shù)內(nèi),誤碼率都小于σ*.門限值也稱為碼容量,表示LDPC碼能容忍的信道環(huán)境的惡劣程度,它是評價LDPC碼的一個重要標準.

門限值計算流程圖如圖5[7],其中M表示設(shè)定的最大迭代次數(shù),Pe表示設(shè)定的期望誤碼率,nstep1和nstep2分別表示噪聲功率增加和減少的步長,nstart表示設(shè)定的初始噪聲功率,n表示當前噪聲功率,l表示當前的迭代次數(shù),Pl表示第l次迭代時的誤碼率.

圖5 門限值計算流程圖Figure 5 Flow chart of calculating thresholds

Wimax標準下6種碼率的LDPC碼在BIAWGN信道下,TDMP算法分別采用密度進化和高斯近似時的門限值如表1.其中r為碼率,σ1表示密度進化時TDMP算法的門限值,σ2表示高斯近似時TDMP算法的門限值,Δs表示σ1和σ2之間的距離,Δs的計算公式如式(13)[7]:

(13)

采用高斯近似,可將高維校驗節(jié)點消息和變量節(jié)點消息的密度進化簡化為一維的均值進化,可以很大地降低計算量.并且從表1可以看出,采用高斯近似計算出的門限值與采用密度進化計算出的門限值只有0.03～0.08 dB的差距.從而說明,在性能損失非常小的前提下,采用高斯近似可以更加容易地分析和計算信道參數(shù)的門限值.

表1 TDMP算法高斯近似和密度進化門限值

5 結(jié) 語

本文在研究BP算法高斯近似的基礎(chǔ)上,提出了TDMP算法的高斯近似,并基于Wimax標準,對LDPC碼的BP算法和TDMP算法進行仿真,從高斯近似的角度,證明了TDMP算法比BP算法譯碼收斂速度更快,平均迭代次數(shù)更少.同時,采用高斯近似的方法,可以更加方便地分析和計算信道參數(shù)的門限值.從而也給出了TDMP算法高斯近似和密度進化的門限值,它們的差別僅為0.03～0.08 dB.本文提出的TDMP算法的高斯近似也適用于其他標準.

[1] GALLAGER R. Low-density parity-check codes[J].IRE Transactions on Information Theory,1962,8(1):21-28.

[2] 王秀敏,洪芳菲,單良,等.LDPC/Turbo雙模譯碼器技術(shù)發(fā)展與前景綜述[J].中國計量學(xué)院學(xué)報,2016,27(1):63-67. WANG X M, HONG F F, SHAN L, et al. The advance overview on LDCP/Turbo dual-mode decoders[J].Journal of China University of Metrology,2016,27(1):63-67.

[3] MACKAY D J C, NEAL R M. Near Shannon limit performance of low density parity check codes[J].Electric Lett,1996,32:1645-1646.

[4] MACKAY D J C. Good error-correcting codes based on very sparse matrices[J].IEEE Trans on Information Theory,1999,45(2):399-431.

[5] RICHARDSON T J, URBANKE R L. The capacity of low-density parity-check codes under message-passing decoding[J].IEEE Transaction on Information Theory,2001,47:599-618.

[6] 肖娟,王琳,鄧禮釗.不規(guī)則LDPC碼的密度進化方法及其門限值確定[J].電子與信息學(xué)報,2005,27(4):617-620. XIAO J, WANG L, DENG L Z. Density evolution method and threshold decision for irregular LDPC codes[J].Journal of Electronics and Information Technology,2005,27(4):617-620.

[7] 袁東風,張海剛.LDPC碼理論與研究[M].北京:人民郵電出版社,2008:122-123.

[8] CHUNG S Y, RICHARDSON T J, URBANKE R L. Analysis of sum-product decoding of low-density parity-check codes using a gaussian approximation[J].IEEE Transaction on Information Theory,2001,47:657-670.

[9] HOCEVAR D E. A reduced complexity decoder architecture via layered decoding of LDPC codes[C]//IEEE Workshop on Signal Processing Systems. Austin: IEEE,2004:107-112.

[10] MANSOUR M M. A Turbo-decoding message-passing algorithm for sparse parity-check matrix codes[J].IEEE Transaction on Signal Processing,2006,54(11):4376-4392.

[11] SUN Y, CAVALLARO J R. A flexible LDPC/Turbo decoder architecture[J].Journal of Signal Processing Systems,2011,64(1):1-16.

[12] ZEINEDDINE H, MANSOUR M M. A reconfigurable TDMP decoder for raptor codes[J].Journal of Signal Processing Systems,2012,69(3):293-304.

[13] 洪芳菲.基于DDE理論的LDPC雙模譯碼器研究[D].杭州:中國計量大學(xué),2016. HONG F F. The Research of dual-mode LDPC decoder based on DDE[D].Hangzhou: China Jiliang University,2016.

Analysis of TDMP algorithm of LDPC codes based on GA

WANG Xiumin, CAO Weilin, SHAN Liang, HONG Bo, LI Jinsong
(College of Information Engineering, China Jiliang University, Hangzhou 310018, China)

To solve the problem of lacking of a theoretical analysis of TDMP algorithm of LDPC codes, the Gaussian Approximation(GA) of TDMP algorithm was proposed. Based on BP algorithm and symmetry conditions, the convergent GA of TDMP algorithm could be obtained. When using GA to analyze the decoding convergence of TDMP algorithm, the theoretical basis for proving the superiority of TDMP algorithm could be provided. GAs of BP algorithm and TDMP algorithm were simulated based on the Wimax standard respectively. Simulation results show that the decoding convergence speed of TDMP algorithm is faster and its number of iterations is fewer compared with BP algorithm under the same condition. Meanwhile, the thresholds of GA and Density Evolution(DE) of TDMP algorithm were presented respectively. The gap of thresholds between GA and DE was 0.03～0.08 dB.

LDPC codes; Gaussian approximation; TDMP algorithm; convergence speed; threshold

2096-2835(2017)01-0076-05

10.3969/j.issn.2096-2835.2017.01.013

2016-12-21 《中國計量大學(xué)學(xué)報》網(wǎng)址：zgjl.cbpt.cnki.net

國家自然科學(xué)基金資助項目(No.61379027),國家自然科學(xué)青年基金資助項目(No.51404223),浙江省自然科學(xué)青年基金資助項目(No.LQ14E060003).

王秀敏(1963- )，女，遼寧省錦州人，教授，主要研究方向為電子信息與通信.E-mail:wxm6341@163.com

TN91

A