張高遠(yuǎn)，周 亮，文 紅

(電子科技大學(xué)通信與抗干擾技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室 成都 611731)

簡(jiǎn)單高效的LDPC碼加權(quán)比特翻轉(zhuǎn)譯碼算法

張高遠(yuǎn)，周 亮，文 紅

(電子科技大學(xué)通信與抗干擾技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室 成都 611731)

現(xiàn)有的兩種低密度奇偶校驗(yàn)(LDPC)碼加權(quán)比特翻轉(zhuǎn)(WBF)譯碼算法雖然具有較低的實(shí)現(xiàn)復(fù)雜度，但糾錯(cuò)性能并不理想。該文基于對(duì)兩種WBF算法的物理意義和它們之間內(nèi)在聯(lián)系的詳細(xì)理論分析，提出一種可靠度外信息修正(ERA)方案。該方案顯著提高了現(xiàn)有兩種低復(fù)雜度譯碼算法校驗(yàn)方程可靠度的準(zhǔn)確性，進(jìn)而提高了翻轉(zhuǎn)效率。仿真結(jié)果表明，在AWGN信道條件下，ERA方案能顯著提高現(xiàn)有兩種WBF算法的譯碼性能，獲得顯著譯碼增益，從而實(shí)現(xiàn)了譯碼復(fù)雜度和性能間的良好折中。

比特翻轉(zhuǎn); 可靠度外信息修正; LDPC碼; 最大后驗(yàn)概率

低密度奇偶校驗(yàn)(LDPC)碼[1]是一種逼近香農(nóng)限的好碼，在深空通信、光通信和磁盤存儲(chǔ)等眾多領(lǐng)域得到廣泛應(yīng)用[2]。在其眾多譯碼算法中，置信傳播(belief-propagation，BP)[3]算法、歸一化和偏移BP算法[4]性能優(yōu)異，但實(shí)現(xiàn)復(fù)雜度較高。APP-Based(a posteriori probability-based)算法和最小和(min-sum, MS)算法[3]是對(duì)BP算法的簡(jiǎn)化近似，文獻(xiàn)[5-6]提出的歸一化APP-Based (normalized APP-based)、歸一化最小和(normalized MS，NMS)與偏移最小和(offset MS，OMS)算法在性能和實(shí)現(xiàn)復(fù)雜度上得到一定的折中。比特翻轉(zhuǎn)(bit flipping, BF)譯碼算法實(shí)現(xiàn)最為簡(jiǎn)單，適用于要求簡(jiǎn)單編譯碼裝置的場(chǎng)合。加權(quán)BF(weighted BF, WBF)算法則將校驗(yàn)節(jié)點(diǎn)鄰接的信息節(jié)點(diǎn)的最小幅度作為雙極性校驗(yàn)子的權(quán)重[7]。文獻(xiàn)[8]通過(guò)引入加權(quán)因子，使改進(jìn)的WBF(modified WBF，MWBF)算法中的翻轉(zhuǎn)函數(shù)更加有效。與MWBF算法相比，文獻(xiàn)[9]提出的IMWBF(improved modified WBF)算法，取得了一定的增益。很多學(xué)者對(duì)上述WBF算法的結(jié)構(gòu)進(jìn)行修正，提出了一些改進(jìn)的算法[10-15]。對(duì)于上述WBF算法而言，信息節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)之間傳遞的僅僅是二進(jìn)制信息(即校驗(yàn)式信息和翻轉(zhuǎn)比特信息)，屬于二進(jìn)制置信傳播算法[16]，實(shí)現(xiàn)復(fù)雜度大大降低。

文獻(xiàn)[17]的IMWBF算法是基于歸一化最小和(normalized MS-based，NMS-Based)算法的最優(yōu)WBF算法，且WBF算法和MWBF算法是IMWBF算法的簡(jiǎn)化形式。但并沒(méi)有對(duì)IMWBF算法翻轉(zhuǎn)函數(shù)的物理意義做詳細(xì)的分析說(shuō)明，更沒(méi)有從理論上得出如何簡(jiǎn)化IMWBF算法才能得出WBF算法和MWBF算法。本文從全新的角度出發(fā)，首先推導(dǎo)出IMWBF算法，得出其翻轉(zhuǎn)函數(shù)中各項(xiàng)所代表的嚴(yán)格的物理意義；其次，根據(jù)這種全新的理解方式，推導(dǎo)得出MWBF算法和WBF算法，并闡明3種算法間的內(nèi)在聯(lián)系；最后提出一種可靠度外信息修正(extrinsic reliability adjustment，ERA)方案對(duì)WBF和MWBF算法進(jìn)行改進(jìn)。

1 基本定義和算法描述

碼長(zhǎng)為N、信息位長(zhǎng)為K的二元LDPC碼，可由M行N列的校驗(yàn)矩陣H=[hmn]決定。對(duì)于規(guī)則LDPC碼，H的第m行中1的數(shù)量用dr表示，第n列中1的數(shù)量用dc表示。H的第m行中1的位置可表示為A(m)={n:hmn=1}；第n列中1的位置可表示為B(n)={m:hmn=1}。為碼字序列，經(jīng)BPSK調(diào)制后得到進(jìn)入加性高斯白噪聲信道后得到接收序列是均值為零、方差為σ2高斯白噪聲。為硬判決輸出序列，判決規(guī)則為表示錯(cuò)誤圖樣，如果xn錯(cuò)誤，則en=1；否則en=0。定義對(duì)數(shù)似然比為：

1.1 MS-Based WBF算法的推導(dǎo)

記比特xn發(fā)生錯(cuò)誤的先驗(yàn)概率為qn，比特xn發(fā)生錯(cuò)誤的后驗(yàn)概率為則對(duì)于AWGN信道有[3,18]：從而得到由APP-Based算法可得[3]：

其中，

而

式中，rmn為{xi|Xm′xn}中有奇數(shù)個(gè)錯(cuò)誤的概率。利用近似關(guān)系[3]：

則有：

從而有：

將式(6)代入式(3)得到：

將式(7)代入式(2)得到：

式中，ωmn為歸一化ERI(normalized ERI，NERI)的幅度，即為文獻(xiàn)[16]中的MS-based WBF算法。(2sm?1)ωmn為第m個(gè)校驗(yàn)方程提供的NERI，由sm和ωmn決定；校驗(yàn)方程提供的NERI，由smn和決定；為歸一化IRI(NIRI)，即xn的可靠度先驗(yàn)信息；En為歸一化PRI(NPRI)。

同時(shí)可以得出以下結(jié)論：1) 可以對(duì)滿足{xn|n= argEn>0}的比特都進(jìn)行翻轉(zhuǎn)，但性能并不理想[16]。 MS-based WBF算法只對(duì)滿足比特翻轉(zhuǎn)，即對(duì)發(fā)生錯(cuò)誤后驗(yàn)概率最大的比特翻轉(zhuǎn)。2) 文獻(xiàn)[18]已證明利用Max-log MAP(MLP)算法譯碼的推導(dǎo)方式同樣可以得到式(6)的結(jié)果，從而得到式(8)的結(jié)果。故MS-Based WBF算法是基于MLP準(zhǔn)則的算法。

1.2 IMWBF算法的推導(dǎo)

顯然式(9)中的ωmn也是MS算法中校驗(yàn)節(jié)點(diǎn)傳遞給信息節(jié)點(diǎn)的信息的幅度，考慮到ωmn大于BP算法中校驗(yàn)節(jié)點(diǎn)傳遞給信息節(jié)點(diǎn)的信息的幅度[6]，可對(duì)MS-Based WBF算法中的NERI進(jìn)行歸一化，便得到歸一化MS-based WBF[18]，其翻轉(zhuǎn)函數(shù)為：

對(duì)式(10)進(jìn)行變換后得到：

式中，α可以看做是α′的倒數(shù)[16]。式(11)即是IMWBF算法的翻轉(zhuǎn)函數(shù)，故IMWBF算法是基于歸一化MLP(normalized MLP，NMLP)準(zhǔn)則的算法[6]。式(11)中各項(xiàng)所代表的嚴(yán)格的物理意義與2.1節(jié)中定義的相同。

2 基于ERA方案的WBF算法

2.1 MWBF算法和WBF算法的推導(dǎo)

如果對(duì)式(4)采用以下近似計(jì)算：

對(duì)式(13)做歸一化處理，則可得到xn參加的第m個(gè)校驗(yàn)方程向其提供的NERI：同時(shí)考慮到NIRI便得到MWBF算法的翻轉(zhuǎn)函數(shù)為：

由此得到文獻(xiàn)[7]中的WBF算法?？梢?jiàn)，通過(guò)對(duì)IMWBF算法的NERI進(jìn)行近似可得到MWBF算法，WBF算法則是在MWBF算法的基礎(chǔ)上，認(rèn)為xn差錯(cuò)與否先驗(yàn)等概，因此二者在性能上必然會(huì)有不同程度的損失。

2.2 ERA方案

相比于IMWBF算法，MWBF算法由于涉及式(12)的近似計(jì)算，從而引入某種相關(guān)性[5]。具體的，MWBF算法中第m個(gè)校驗(yàn)方程向{xn|n∈A(m)}提供的NERI的幅度都為ωm。然而得到的NERI幅度應(yīng)該為序列{yn,n∈A(m)}的次小值，即xi得到的外信息的可靠度降低，需要修正。傳統(tǒng)意義上講，要實(shí)現(xiàn)這種操作，首先要在中找到滿足的信息節(jié)點(diǎn)，然后增加其可靠度[19]。顯然傳統(tǒng)方法是進(jìn)行“先查找，后增加”的操作。由于WBF算法不涉及可靠度信息的更新傳遞，故增加校驗(yàn)方程中某個(gè)信息節(jié)點(diǎn)的可靠度等價(jià)于增加與其對(duì)應(yīng)的yn的幅度，即可得到一種比傳統(tǒng)實(shí)現(xiàn)方法更加簡(jiǎn)單的方法，具體步驟如下：

1) 對(duì)y的幅度進(jìn)行預(yù)處理：

以下為基于ERA的MWBF譯碼算法步驟。

初始化：初始化迭代次數(shù)k=1，設(shè)定最大迭代次數(shù)Kmax。

1) 計(jì)算伴隨式S，若S全為0，停止迭代，輸出x；否則計(jì)算第m個(gè)校驗(yàn)方程的權(quán)重

2) 計(jì)算翻轉(zhuǎn)函數(shù)為：

3) 比特翻轉(zhuǎn)為：

4) 用更新過(guò)的x計(jì)算伴隨式，如果S全零，則終止迭代；如果不為全零，但迭代次數(shù)達(dá)到最大次數(shù)限制，也終止迭代。否則k=k+1，跳至步驟2)。

由上述分析可知，新的實(shí)現(xiàn)方法只需進(jìn)行“加法”的操作。需特別指出的是，傳統(tǒng)實(shí)現(xiàn)方法最多只需增加M個(gè)信息節(jié)點(diǎn)的可靠度，而新的實(shí)現(xiàn)方案對(duì)校驗(yàn)方程中每個(gè)信息節(jié)點(diǎn)的可靠度都增加。而仿真結(jié)果表明，新的實(shí)現(xiàn)方案同樣能有效地削弱近似計(jì)算帶來(lái)的相關(guān)性，提高譯碼性能。為分析方便，認(rèn)為1次比較運(yùn)算等同于1次加法運(yùn)算，則傳統(tǒng)實(shí)現(xiàn)方法共需要M(dr?1)次加法運(yùn)算。同時(shí)，由式(15)可知，新的實(shí)現(xiàn)方案僅需要增加N次加法運(yùn)算和N個(gè)存儲(chǔ)單元。顯然ERA方案可同時(shí)運(yùn)用于WBF算法，而理論上得出最優(yōu)化的修正因子γ仍然具有一定難度，可考慮通過(guò)仿真得到。

3 仿真結(jié)果和統(tǒng)計(jì)分析

本節(jié)仿真參數(shù)如下：采用列重為3的(504,252) PEG-LDPC碼(記為碼A)和(1 008,504) PEG-LDPC碼(記為碼B)[14]，迭代次數(shù)分別設(shè)定為50和100；在AWGN信道條件下，采用BPSK調(diào)制，在每個(gè)信噪比下至少采集1 000個(gè)比特錯(cuò)誤。

3.1 尋找最佳的修正因子γ

文獻(xiàn)[8]通過(guò)蒙特卡洛仿真得出了MWBF算法的最優(yōu)加權(quán)因子。類似地，文獻(xiàn)[14]通過(guò)仿真得出了基于幅度和的WBF算法的最優(yōu)加權(quán)因子?？梢?jiàn)，當(dāng)通過(guò)理論分析得到算法所需的最優(yōu)因子較為困難時(shí)，蒙特卡洛仿真是首選的有效方法。由于目前通過(guò)理論分析得出修正因子γ較為困難，本文仍采用蒙特卡洛仿真。

圖1 碼A條件下，不同信噪比下γ對(duì)ERA-WBF算法性能的影響

圖1為不同信噪比下，ERA-WBF算法在碼A條件下受不同γ影響時(shí)的誤比特率性能。由圖1可知，對(duì)所有的Eb/N0可以選擇一個(gè)固定不變且最優(yōu)的γ，此時(shí)的性能損失可忽略不計(jì)，且保持較低的實(shí)現(xiàn)復(fù)雜度。6.0～6.5 dB時(shí)的最優(yōu)化γ為0.3，而6.75 dB時(shí)最優(yōu)化的γ為0.25，但考慮到6.75 dB時(shí)γ=0.25和γ=0.3時(shí)性能損失可忽略不計(jì)，故本文仿真中ERA-WBF算法在碼A條件下最優(yōu)化的γ設(shè)定為0.3。

3.2 算法性能和實(shí)現(xiàn)復(fù)雜度比較

圖2為最優(yōu)參數(shù)下，碼A和碼B在各算法下性能比較。MWBF算法的最優(yōu)加權(quán)系數(shù)分別設(shè)定為0.2和0.3[14]，IMWBF算法的最優(yōu)加權(quán)系數(shù)都設(shè)定為0.2[9]，ERA-WBF的最優(yōu)γ分別設(shè)定為0.3和0.2，ERA-MWBF的最優(yōu)γ都設(shè)定為0.45。圖3給出碼B在各譯碼算法下平均迭代次數(shù)比較。圖4給出碼A在IMWBF和MS-Based WBF算法下誤比特性能。

圖2 碼A和碼B在各譯碼算法下性能比較

圖3 碼B在各算法下平均迭代次數(shù)統(tǒng)計(jì)

圖4 碼A在IMWBF和MS-Based WBF算法下性能圖

表1 BER=10?5，各算法在碼A和碼B下性能統(tǒng)計(jì)

表1給出BER=10?5時(shí)，各算法的性能比較。由表1可知，在碼A條件下，ERA-MWBF算法與IMWBF算法的性能基本一致。在BER=10?5時(shí)，相對(duì)于MWBF算法，ERA-MWBF算法可獲得0.45 dB的增益；ERA-WBF算法相對(duì)于WBF算法可獲得0.30 dB的增益。在碼B條件下，當(dāng)Eb/N0大于4.25 dB時(shí)，ERA-MWBF的性能甚至好于IMWBF算法。在Eb/N0大于5.0 dB時(shí)，ERA-WBF算法的性能也要好于MWBF算法。從圖3可知，修正后WBF算法和MWBF算法的平均迭代次數(shù)大大降低。為分析方便，認(rèn)為一次比較運(yùn)算等同于一次加法運(yùn)算。當(dāng)Eb/N0=4.5 dB時(shí)，由圖3得出，ERA-MWBF算法的平均迭代次數(shù)比傳統(tǒng)算法降低20次，加法運(yùn)算次數(shù)平均降低20(N?1+dcdr)=20520次[14]，總體上平均加法運(yùn)算次數(shù)降低了20520?N=19512次。類似的，Eb/N0=4.0 dB和5.0 dB時(shí)，總體上平均加法運(yùn)算次數(shù)都減低14 382次。從圖4可知，IMWBF和MS-Based WBF算法分別是基于NMLP準(zhǔn)則和MLP準(zhǔn)則得出的，因此前者性能必然優(yōu)于后者。

4 結(jié) 束 語(yǔ)

本文從一個(gè)新的角度得出IMWBF算法的物理意義，分析了IMWBF算法與WBF算法和MWBF算法的內(nèi)在聯(lián)系。以此為基礎(chǔ)提出一種ERA方案對(duì)WBF算法和MWBF算法進(jìn)行改進(jìn)。仿真結(jié)果表明，AWGN信道下，誤比特率為10?5時(shí)，與傳統(tǒng)算法相比，基于ERA方案的WBF和MWBF算法可分別獲得約0.70 dB和0.76 dB的增益，同時(shí)實(shí)現(xiàn)復(fù)雜度有所降低，從而在糾錯(cuò)性能和實(shí)現(xiàn)復(fù)雜度之間達(dá)到了很好的平衡匹配。文獻(xiàn)[7-15]和本文提出的改進(jìn)方案都以單比特翻轉(zhuǎn)模式為出發(fā)點(diǎn)，即每次迭代過(guò)程中對(duì)發(fā)生錯(cuò)誤概率最大的比特執(zhí)行翻轉(zhuǎn)操作，隸屬于串行算法。多比特翻轉(zhuǎn)模式下的算法仍有待深入研究。此外，本文提出的改進(jìn)方案適用于行重和列重相對(duì)較小的LDPC碼。仿真結(jié)果表明，此改進(jìn)方案對(duì)于行重和列重較大的LDPC碼則不太適用。針對(duì)行重和列重較大的LDPC碼，多比特翻轉(zhuǎn)模式下的改進(jìn)方案值得進(jìn)一步的深入研究。

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

[2] 施玉晨, 白寶明. 基于多元LDPC碼的多用戶協(xié)作方案[J].電子科技大學(xué)學(xué)報(bào), 2013, 42(8): 205-208. SHI Yu-chen, BAI Bao-ming. Multiuser cooperative scheme based on nonbinary LDPC codes[J]. Journal of University of Electronic Science and Technology of China, 2013, 42(8): 205-208.

[3] FOSSORIER M, MIHALJEVIC M, IMAI H. Reduced complexity iterative decoding low density parity-check codes based on belief propagation[J]. IEEE Transactions on Information Theory, 1999, 47(5): 673-680.

[4] YAZDANI M, HEMATI S , BANIHASHEMI A. Improving belief propagation on graphs with cycles[J]. IEEE Communications Letters, 2004, 8(1): 57-59.

[5] CHEN Jing-hu, FOSSORIER M. Decoding low-density parity check codes with normalized APP-based Algorithm[C]//Global Telecommunication Conference. San Antonio, TX, USA: IEEE, 2001(2): 1026-1030.

[6] CHEN Jing-hu, DHOLAKIA A, ELEFTHERIOU E, et al. Reduced-complexity decoding of LDPC codes[J]. IEEE Transactions on Communications, 2005, 53(8): 1288-1299.

[7] KOU Y, LIN Shu, FOSSORIER M. Low-density parity-check codes based on finite geometries: a rediscovery and new results[J]. IEEE Transactions on Information Theory, 2001, 47(7): 2711-2736.

[8] ZHANG Jun-tan, FOSSORIER M. A modified weighted bit-flipping decoding of low-density parity-check codes[J]. IEEE Communications Letters, 2004, 8(3): 165-167.

[9] JIANG Ming, ZHAO Chun-ming, SHI Zhi-hua, et al. An improvement on the modified weighted bit flipping decoding algorithm for LDPC codes[J]. IEEE Communications Letters, 2005, 9(9): 814-816.

[10] GUO F, HANZO L. Reliability ratio based weighted bit-flipping decoding for low-density parity-check codes[J]. Electronics Letters, 2004, 40(21): 1356-1358.

[11] 劉原華, 張美玲. LDPC碼的改進(jìn)迭代比特翻轉(zhuǎn)譯碼算法[J]. 電訊技術(shù), 2012, 52(4): 488-491. LIU Yuan-hua, ZHANG Mei-ling. An improved iterative bit-flipping decoding algorithm for low-density parity-check codes[J]. Telecommunications Engineering, 2012, 52(4): 488-491.

[12] CHEN T. An efficient bit-flipping decoding algorithm for LDPC codes[C]//International Conference on Cross Strait Quad-Regional Radio Science and Wireless Technology. New Taipei City, Taiwan, China: IEEE, 2012: 109-112.

[13] 劉原華, 張美玲. 結(jié)構(gòu)化LDPC碼的改進(jìn)比特翻轉(zhuǎn)譯碼算法[J]. 北京郵電大學(xué)學(xué)報(bào), 2012, 35(4): 116-119. LIU Yuan-hua, ZHANG Mei-ling. Improved bit-flipping method for decoding structured low-density parity-check codes[J]. Journal of Beijing University of Posts and Telecommunications, 2012, 35(4): 116-119.

[14] 張高遠(yuǎn), 周亮, 蘇偉偉,等. 基于平均幅度的LDPC碼加權(quán)比特翻轉(zhuǎn)譯碼算法[J]. 電子與信息學(xué)報(bào), 2013, 35(11): 2572-2578. ZHANG Gao-yuan, ZHOU Liang, SU Wei-wei, et al. Average magnitude based weighted bit-flipping decoding algorithm for LDPC codes[J]. Journal of Electronics & Information Technology, 2013, 35(11): 2572-2578.

[15] CHEN T. Channel-independent weighted bit-flipping decoding algorithm for low-density parity-check codes[J]. IET Communications, 2012, 6(17): 2968-2973.

[16] NASTARAN M. New iterative decoding algorithms for low-density parity-check (LDPC) codes[D]. Ottawa, Canada: Carleton University, 2011.

[17] WU Xiao-fu, LING C, JING Ming, et al. New insights into weighted bit-flipping decoding[J]. IEEE Transactions on Communications, 2009, 57(8): 2177-2181.

[18] 張立軍, 劉明華, 盧萌. 低密度奇偶校驗(yàn)碼加權(quán)大數(shù)邏輯譯碼研究[J]. 西安交通大學(xué)學(xué)報(bào), 2013, 47(4): 35-38. ZHANG Li-jun, LIU Ming-hua, LU Meng. A research on weighted majority-logic decoding for LDPC codes[J]. Journal of Xi’an Jiaotong University, 2013, 47(4): 35-38.

[20] DARABIHA A, CARUSONE A C, KSCHISCHANG F R. A bit-serial approximate min-sum LDPC decoder and FPGA implementation[C]//IEEE International Symposium on Circuits and Systems. Island of Kos, Greece: IEEE, 2006: 149-152.

編輯張 俊

Simple and Efficient Weighted Bit-Flipping Decoding Algorithm for LDPC Codes

ZHANG Gao-yuan, ZHOU Liang, and WEN Hong
(National Key Laboratory of Science and Technology on Communications, University of Electronic Science and Technology of China Chengdu 611731)

An extrinsic reliability adjustment (ERA) scheme of low-density parity-check (LDPC) codes is proposed in this paper based on theoretical analysis of the physical significance for two previous weighted bit-flipping (WBF) algorithms, which have less complexity with poor error correcting performance. The novel scheme significantly improves the check-node realiability accuracy of the two previous WBF algorithms. Therefore, the flipping efficiency of the novel decoding algorithm is increased. The extensive simulations prove that the ERA scheme can obviously improves the performance of the two previous WBF algorithms and a great decoding gain is obtained over an AWGN channel, which achieves an appealing tradeoff between performance and complexity.

bit flipping; extrinsic reliability adjustment; LDPC codes; MAP

TP911.22

A doi:10.3969/j.issn.1001-0548.2015.04.008

2013 ? 10 ? 25；

2015 ? 01 ? 12

國(guó)家自然科學(xué)基金(61032003, 61271172, 61261021)；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金(A03008023901004)；高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金(20120185110030，20130185130002)

張高遠(yuǎn)(1984 ? )，男，博士生，主要從事信道編譯碼技術(shù)方面的研究.