張高遠，周 亮，文 紅

(電子科技大學(xué)通信與抗干擾技術(shù)國家重點實驗室 成都 611731)

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

張高遠，周 亮，文 紅

(電子科技大學(xué)通信與抗干擾技術(shù)國家重點實驗室 成都 611731)

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

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

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

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

1 基本定義和算法描述

碼長為N、信息位長為K的二元LDPC碼，可由M行N列的校驗矩陣H=[hmn]決定。對于規(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)制后得到進入加性高斯白噪聲信道后得到接收序列是均值為零、方差為σ2高斯白噪聲。為硬判決輸出序列，判決規(guī)則為表示錯誤圖樣，如果xn錯誤，則en=1；否則en=0。定義對數(shù)似然比為：

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

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

其中，

而

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

則有：

從而有：

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

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

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

同時可以得出以下結(jié)論：1) 可以對滿足{xn|n= argEn>0}的比特都進行翻轉(zhuǎn)，但性能并不理想[16]。 MS-based WBF算法只對滿足比特翻轉(zhuǎn)，即對發(fā)生錯誤后驗概率最大的比特翻轉(zhuǎn)。2) 文獻[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算法中校驗節(jié)點傳遞給信息節(jié)點的信息的幅度，考慮到ωmn大于BP算法中校驗節(jié)點傳遞給信息節(jié)點的信息的幅度[6]，可對MS-Based WBF算法中的NERI進行歸一化，便得到歸一化MS-based WBF[18]，其翻轉(zhuǎn)函數(shù)為：

對式(10)進行變換后得到：

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

2 基于ERA方案的WBF算法

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

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

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

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

2.2 ERA方案

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

1) 對y的幅度進行預(yù)處理：

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

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

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

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

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

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

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

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

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

3.1 尋找最佳的修正因子γ

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

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

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

3.2 算法性能和實現(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)計

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

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

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

4 結(jié) 束 語

本文從一個新的角度得出IMWBF算法的物理意義，分析了IMWBF算法與WBF算法和MWBF算法的內(nèi)在聯(lián)系。以此為基礎(chǔ)提出一種ERA方案對WBF算法和MWBF算法進行改進。仿真結(jié)果表明，AWGN信道下，誤比特率為10?5時，與傳統(tǒng)算法相比，基于ERA方案的WBF和MWBF算法可分別獲得約0.70 dB和0.76 dB的增益，同時實現(xiàn)復(fù)雜度有所降低，從而在糾錯性能和實現(xiàn)復(fù)雜度之間達到了很好的平衡匹配。文獻[7-15]和本文提出的改進方案都以單比特翻轉(zhuǎn)模式為出發(fā)點，即每次迭代過程中對發(fā)生錯誤概率最大的比特執(zhí)行翻轉(zhuǎn)操作，隸屬于串行算法。多比特翻轉(zhuǎn)模式下的算法仍有待深入研究。此外，本文提出的改進方案適用于行重和列重相對較小的LDPC碼。仿真結(jié)果表明，此改進方案對于行重和列重較大的LDPC碼則不太適用。針對行重和列重較大的LDPC碼，多比特翻轉(zhuǎ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é)報, 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碼的改進迭代比特翻轉(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碼的改進比特翻轉(zhuǎn)譯碼算法[J]. 北京郵電大學(xué)學(xué)報, 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] 張高遠, 周亮, 蘇偉偉,等. 基于平均幅度的LDPC碼加權(quán)比特翻轉(zhuǎn)譯碼算法[J]. 電子與信息學(xué)報, 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] 張立軍, 劉明華, 盧萌. 低密度奇偶校驗碼加權(quán)大數(shù)邏輯譯碼研究[J]. 西安交通大學(xué)學(xué)報, 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

國家自然科學(xué)基金(61032003, 61271172, 61261021)；中央高校基本科研業(yè)務(wù)費專項資金(A03008023901004)；高等學(xué)校博士學(xué)科點專項科研基金(20120185110030，20130185130002)

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