一種改進(jìn)的LDPC碼低復(fù)雜度最小和算法

吳 軍，廖 鑫，張小紅

(江西理工大學(xué) 信息工程學(xué)院，江西 贛州 341000)

一種改進(jìn)的LDPC碼低復(fù)雜度最小和算法

吳 軍，廖 鑫，張小紅

(江西理工大學(xué) 信息工程學(xué)院，江西 贛州 341000)

研究了低密度奇偶校驗(yàn)(Low-Density Parity-Check，LDPC)碼的單最小值最小和(Single-Minimum Min-Sum，SMMS)算法，為了提高譯碼性能，在此基礎(chǔ)上提出一種信道自適應(yīng)可配置LDPC碼最小和譯碼(Adaptive Configurable Min-Sum，ACMS)算法。ACMS算法在BP譯碼時(shí)的橫向消息迭代更新過(guò)程中，LLR次小值用一個(gè)基于迭代次數(shù)的估算參數(shù)與最小值相加來(lái)取代，同時(shí)根據(jù)每次判決時(shí)的錯(cuò)誤比特個(gè)數(shù)對(duì)不同信噪比下的估算參數(shù)進(jìn)行動(dòng)態(tài)修正。仿真結(jié)果表明，ACMS算法整體上提高了譯碼性能而僅增加少量復(fù)雜度。

低密度奇偶校驗(yàn)碼；最小和算法；單最小值；估算參數(shù)；信道自適應(yīng)

低密度奇偶校驗(yàn)(Low-Density Parity Check，LDPC)碼是當(dāng)今性能最優(yōu)越的兩大信道糾錯(cuò)碼之一，Gallager對(duì)LDPC碼的研究最早可以追溯到1962年[1]，MacKay和Neal于1996年重新發(fā)明它之后，LDPC碼便成為了Turbo碼的強(qiáng)大競(jìng)爭(zhēng)對(duì)手，被廣泛運(yùn)用到衛(wèi)星廣播、深空通信、光纖網(wǎng)絡(luò)等多個(gè)領(lǐng)域中，在IEEE802多個(gè)規(guī)范中和多個(gè)國(guó)家的衛(wèi)星廣播標(biāo)準(zhǔn)中也得到正式采用。

人工智能領(lǐng)域內(nèi)著名的BP(Belief Propagation)算法是公認(rèn)的LDPC碼的最佳譯碼方法。近年來(lái)，在改善LDPC碼BP譯碼性能上取得了很多有價(jià)值的研究成果，如Casado等提出的消息傳遞動(dòng)態(tài)調(diào)度策略[2]、Wu等提出的自適應(yīng)迭代譯碼[3]等。這些改進(jìn)算法通過(guò)適當(dāng)配置都可以獲得非常好的譯碼性能，但這類算法通常消息更新策略較復(fù)雜，給硬件設(shè)計(jì)帶來(lái)一定困難，不適合對(duì)譯碼速率有較高要求的場(chǎng)合。為了降低BP譯碼復(fù)雜度使之實(shí)用化，F(xiàn)ossorier提出了最小和(Min-Sum, MS)算法[4]，大幅減少了BP譯碼每次迭代所需的計(jì)算量。文獻(xiàn)[5]對(duì)BP譯碼的接收信號(hào)進(jìn)行整數(shù)量化，提高了譯碼速率。為了進(jìn)一步減少計(jì)算復(fù)雜度，Darabiha等首次提出了基于單個(gè)最小值的最小和(Single-Minimum Min-Sum, SMMS)算法[6]。在MS算法的橫向迭代消息更新中，譯碼器需要搜索每個(gè)比特節(jié)點(diǎn)傳給校驗(yàn)節(jié)點(diǎn)的LLR(Log Likelihood Ratios)最小值和次小值，SMMS算法在校驗(yàn)節(jié)點(diǎn)消息更新時(shí)僅搜索第一個(gè)LLR最小值，次小值被表示為最小值加上一個(gè)固定的估算參數(shù)。

本文提出一種基于迭代次數(shù)的信道自適應(yīng)可配置最小和(Adaptive Configurable Min-Sum, ACMS)算法。算法在不同信噪比下自適應(yīng)修正估算參數(shù)的取值。仿真結(jié)果顯示，ACMS算法整體上取得了較好的譯碼性能，同時(shí)其復(fù)雜度相對(duì)MS算法大幅降低，不需要對(duì)信道條件進(jìn)行估計(jì)，具有一定應(yīng)用價(jià)值。

1 最小和算法

1.1 傳統(tǒng)MS算法

設(shè)一個(gè)信道采用BPSK調(diào)制，伴隨均值為0、方差為σ2加性高斯白噪聲ni的通信系統(tǒng)，若將待發(fā)送的碼長(zhǎng)為N的編碼序列表示為X=(x1,x2,…,xN)T，接收端收到的信號(hào)表示為Y=(y1,y2,…,yN)T，則編碼序列經(jīng)過(guò)AWGN信道后的過(guò)程可以用Yi=2·xi-1+ni來(lái)表示，其中i=1,2,…,N。BP算法本質(zhì)上是比特節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)的概率信息在Tanner圖上交互傳播的過(guò)程。為了簡(jiǎn)便起見(jiàn)，迭代過(guò)程中傳播的軟消息通常使用的是LLR值，它的絕對(duì)值表示該比特節(jié)點(diǎn)的可靠性大小，對(duì)二進(jìn)制的LDPC碼，其符號(hào)被映射為對(duì)應(yīng)比特的二進(jìn)制數(shù)碼。LDPC碼的MS算法每次都選擇可靠度最低的比特節(jié)點(diǎn)信息對(duì)校驗(yàn)節(jié)點(diǎn)進(jìn)行更新，其主要包括縱向消息傳遞和橫向消息傳遞兩大步驟，如式(1)和式(2)所示。

縱向更新公式為

(1)

橫向更新公式為

(2)

每當(dāng)消息經(jīng)過(guò)第i次完整的傳遞后，譯碼器便進(jìn)行軟判決為

(3)

當(dāng)軟判決輸出的碼字全部滿足奇偶校驗(yàn)方程或者達(dá)到預(yù)設(shè)的最大迭代次數(shù)時(shí)，譯碼器停止迭代譯碼并輸出碼字Zn。

1.2 SMMS算法

MS算法在橫向更新中實(shí)際用到了一個(gè)最小值和一個(gè)次小值，次小值用于更新和同一個(gè)校驗(yàn)節(jié)點(diǎn)相鄰的可靠度最低的比特節(jié)點(diǎn)信息，最小值則更新除此比特節(jié)點(diǎn)外，與該校驗(yàn)節(jié)點(diǎn)相鄰的其他比特節(jié)點(diǎn)信息。SMMS算法簡(jiǎn)化了MS算法中次小值的計(jì)算方法，其更新表達(dá)式為

(4)

最初的SMMS算法僅對(duì)最小值進(jìn)行加“1”運(yùn)算得到次小值，即式中ω=1，其實(shí)現(xiàn)簡(jiǎn)單，但高信噪比下消息收斂過(guò)慢，存在較為嚴(yán)重的誤碼平層。其后Zhang等在改進(jìn)的SMMS算法[7]中將NMS算法[8]中的偏移修正系數(shù)α引入SMMS算法，通過(guò)仿真獲取最佳的ω取值，在一定程度上改善了譯碼性能。文獻(xiàn)[9]提出的CMS算法為每個(gè)信噪比都配置了一個(gè)最佳估算參數(shù)，但譯碼器需要對(duì)信道條件進(jìn)行準(zhǔn)確估計(jì)，不利于實(shí)際應(yīng)用。

2 自適應(yīng)可配置最小和算法

在SMMS算法橫向更新過(guò)程中，LLR次小值的大小不但取決于信噪比，而且隨著迭代次數(shù)的增加發(fā)生變化。為了研究MS算法中次小值的變化趨勢(shì)，本文首先使用MS算法對(duì)不同信噪比、不同迭代次數(shù)時(shí)LLR最小值和次小值的差作均值估計(jì)，定義

(5)

圖1 MS算法中兩個(gè)LLR最小值的平均差值隨迭代次數(shù)的變化曲線

為了更加精確地估計(jì)LLR次小值，F(xiàn)abian等提出了VWMS(Variable Weight Min-Sum)算法[10]，該算法在不同迭代次數(shù)時(shí)使用不同的估算參數(shù)對(duì)次最小值進(jìn)行估計(jì)，VWMS算法改善了SMMS算法在高信噪比下的譯碼性能，并獲得了比NMS算法還低的誤碼平層。VWMS算法在中低信噪比區(qū)的譯碼性能不如MS算法，也沒(méi)有給出獲取最佳估算參數(shù)的確定性方法，為不同信道條件都單獨(dú)配置一組最優(yōu)ω(i)值的工作量非常大，不利于算法的實(shí)現(xiàn)。

為了解決上述問(wèn)題，本文提出信道自適應(yīng)可配置最小和(Adaptive Configurable Min-Sum, ACMS)算法，ACMS算法在不同迭代區(qū)間使用不同的估算參數(shù)，同時(shí)通過(guò)每次譯碼的判決情況動(dòng)態(tài)調(diào)整次小值所在比特節(jié)點(diǎn)的LLR值幅度，實(shí)現(xiàn)信道自適應(yīng)譯碼。改進(jìn)算法的校驗(yàn)節(jié)點(diǎn)消息更新公式為

(6)

(7)

Fabian指出不宜將迭代區(qū)間劃分得過(guò)多，這樣會(huì)增加譯碼復(fù)雜度，仿真結(jié)果亦表明過(guò)多的迭代區(qū)間劃分對(duì)譯碼性能幾乎沒(méi)有影響。因?yàn)樵谧g碼過(guò)程中絕大多數(shù)錯(cuò)誤碼字通常都在經(jīng)過(guò)若干次迭代后就得到了糾正，在之后的迭代過(guò)程中E(Dmin)值基本穩(wěn)定，故本文算法在之后的仿真分析中按照Fabian的方法將迭代區(qū)間的邊界固定為I=[5 10 15 30]。將不同迭代區(qū)間配置的估算參數(shù)用式(8)表示，通過(guò)仿真來(lái)獲得ω(i)的最佳配置。

wk=w1+dw·(k-1)

(8)

式中：dw為一固定常數(shù)，故wk實(shí)質(zhì)上是一組等差數(shù)列。在不同信噪比時(shí)不宜將同一組ω(i)配置進(jìn)ACMS算法，為了避免對(duì)ω(i)進(jìn)行多次配置，ACMS算法首先在高信噪比條件下通過(guò)仿真獲得最佳ω(i)后，將其乘以一個(gè)信道自適應(yīng)修正因子β來(lái)修正中低信噪比條件下軟消息的LLR值幅度。算法根據(jù)每次判決時(shí)錯(cuò)誤比特的個(gè)數(shù)來(lái)判斷是否使用β對(duì)次小值進(jìn)行修正，判斷條件為

(9)

式中：num(HT·Zn≠0)表示譯碼器每次判決時(shí)統(tǒng)計(jì)的錯(cuò)誤比特的個(gè)數(shù)；ε為預(yù)配置的一個(gè)固定整數(shù)。

3 仿真結(jié)果及分析

為了驗(yàn)證改進(jìn)算法的性能，分析不同參數(shù)配置對(duì)譯碼性能的影響，下文仿真均采用IEEE802.16e標(biāo)準(zhǔn)中碼長(zhǎng)為576、碼率為0.5的準(zhǔn)循環(huán)LDPC碼，在AWGN信道下采用BPSK調(diào)制，最大迭代次數(shù)設(shè)置為30，每組信噪比下統(tǒng)計(jì)10 000個(gè)數(shù)據(jù)幀。

3.1 估算參數(shù)對(duì)性能的影響

為了保證高信噪比區(qū)的譯碼性能，本文首先配置w1=1.25，這個(gè)值是在Eb/N0=3.2 dB時(shí)按照式(5)仿真得到，然后通過(guò)改變步進(jìn)間距dw的值來(lái)獲得不同的ω(i)配置組，為了方便使用文獻(xiàn)[5]中的方法對(duì)算法中接收到的信息進(jìn)行整數(shù)量化，本文將dw設(shè)置為0.25的整數(shù)倍。圖2是在高信噪比區(qū)，不同ω(i)配置對(duì)譯碼性能的影響。

圖2 ω(i)對(duì)譯碼性能的影響

從圖中可知，當(dāng)dw=0.75時(shí)，ACMS算法在高信噪?yún)^(qū)取得了最佳的誤碼性能。

3.2 信道自適應(yīng)修正系數(shù)對(duì)性能的影響

ε取值必須適當(dāng)，過(guò)高的ε在譯碼判決時(shí)將帶來(lái)更多的運(yùn)算復(fù)雜度，在中低信噪比區(qū)也不能有效抑制被高估的次小值。過(guò)低的ε值會(huì)使迭代次數(shù)增加，使算法在高信噪比區(qū)下難以收斂，給譯碼性能帶來(lái)一定影響。圖3是β值一定且Eb/N0=3 dB時(shí)，不同ε值對(duì)譯碼性能的影響。

圖3 ε對(duì)譯碼性能的影響

從圖3可知，ε=10時(shí)，ACMS算法取得了最佳的性能，故本文將ε設(shè)置為10。在前文所得的最佳ω(i)和ε配置下，圖4表示在不同β值對(duì)譯碼性能的影響。

圖4 自適應(yīng)修正因子對(duì)譯碼性能的影響

從圖中對(duì)比可知，在高信噪比區(qū)，當(dāng)β=0.8時(shí)，ACMS算法取得了最佳的譯碼性能，注意到在中低信噪比區(qū)β取值越低，性能改進(jìn)越明顯。為了保證高信噪比下最佳的譯碼性能，本文將β取為0.8。

3.3 譯碼性能比較

各算法的參數(shù)配置歸納如表1所示，表中的偏移修正系數(shù)α為使用NMS算法仿真得出的最佳值。

表1 各算法參數(shù)配置

圖5是MS、CMS、VWMS和ACMS算法的誤碼性能曲線。

圖5 各算法譯碼性能比較

從圖中可以看出，本文提出的ACMS算法整體上優(yōu)于VWMS算法。在誤碼率數(shù)量級(jí)為10-5時(shí)，相對(duì)VWMS算法有近0.1 dB的增益。VWMS算法在Eb/N0<2.6 dB時(shí)，其糾錯(cuò)性能不如MS算法，而本文提出的ACMS算法在Eb/N0>1.6 dB時(shí)，譯碼性能就超過(guò)了MS算法。這是因?yàn)樵谥械托旁氡葏^(qū)ACMS算法抑制了VWMS算法中被高估的LLR次小值的傳播。在高信噪比區(qū)，LDPC碼中的陷阱集[11]的存在使部分比特收斂到一個(gè)始終不滿足校驗(yàn)方程的錯(cuò)誤狀態(tài)。正確的比特接收到LLR值通常都很高，而錯(cuò)誤比特的LLR值通常比較低。BP譯碼器接收到的LLR軟判決信息隨著迭代次數(shù)而增加，使得正確比特的LLR幅度和錯(cuò)誤比特的LLR值都變得越來(lái)越大，這樣譯碼器就始終無(wú)法糾正這些錯(cuò)誤比特。MS算法在高信噪比下的快速收斂特性會(huì)使得比特軟消息幅值更快地陷入陷阱集，而ACMS算法根據(jù)每次迭代后的判決情況，通過(guò)對(duì)LLR值的控制，適當(dāng)?shù)販p緩了收斂速度，防止LLR值發(fā)生急劇變化，抑制了錯(cuò)誤消息的傳播，從而避免了比特快速收斂到一個(gè)錯(cuò)誤的狀態(tài)。

3.4 復(fù)雜度分析

對(duì)一個(gè)校驗(yàn)矩陣為H(M,N)且行重為r的規(guī)則LDPC碼，VWMS算法在處理LLR最小值時(shí)只需進(jìn)行M·(r-1)次比較運(yùn)算和M次加法運(yùn)算，基于兩個(gè)最小值的MS算法需要M·(r-2+logr)次比較運(yùn)算。雖然算法中引入的α系數(shù)增加了少量運(yùn)算復(fù)雜度，但對(duì)算法進(jìn)行FPGA的硬件設(shè)計(jì)時(shí)，其總體硬件開(kāi)支比MS算法要少[10,12]。

在VWMS算法復(fù)雜度的基礎(chǔ)上，本文提出的ACMS算法在硬件設(shè)計(jì)時(shí)需要增加若干存儲(chǔ)單元用于存放β·ω(i)和ε,這些參數(shù)都可以在譯碼開(kāi)始前配置好，在之后的校驗(yàn)節(jié)點(diǎn)和比特節(jié)點(diǎn)軟消息迭代更新過(guò)程中沒(méi)有增加任何運(yùn)算量。在每次硬判決時(shí)，ACMS算法相對(duì)VWMS算法多出的計(jì)算量為統(tǒng)計(jì)每次判決時(shí)的錯(cuò)誤比特個(gè)數(shù)，并做一次條件判斷。由此可知，ACMS算法相比VWMS僅增加少量運(yùn)算而改善了整體的譯碼性能，同時(shí)譯碼器不需對(duì)信道條件進(jìn)行估計(jì)。

4 小結(jié)

針對(duì)SMMS算法對(duì)信道條件敏感的問(wèn)題，本文提出了一種信道自適應(yīng)的可配置LDPC碼的最小和譯碼算法，在ACMS算法的橫向迭代過(guò)程中，在不同迭代次數(shù)時(shí)采用不同的估算參數(shù)，同時(shí)引入一個(gè)信道自適應(yīng)修正因子β對(duì)ω(i)的LLR值進(jìn)行動(dòng)態(tài)修正，這樣就省去了在不同信噪比下對(duì)ω(i)的多次配置。仿真結(jié)果表明，ACMS算法整體性能優(yōu)于VWMS算法, 在中高信噪比區(qū)的糾錯(cuò)性能也優(yōu)于基于2個(gè)最小值的MS算法。由于ACMS算法省去了次小值的計(jì)算，因此更適合硬件的快速實(shí)現(xiàn)。

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

[2]CASADO A I V, GRIOT M, WESEL R D. LDPC decoders with informed dynamic scheduling[J]. IEEE Trans. Communications, 2010, 58(12): 3470-3479.

[3]WU X, SONG Y, JIANG M, et al. Adaptive-normalized/offset min-sum algorithm[J]. IEEE Communications Letters, 2010, 14(7): 667-669.

[4]FOSSORIER M P C, MIHALJEVIC M, IMAI H. Reduced complexity iterative decoding of low-density parity check codes based on belief propagation[J]. IEEE Trans. Communications, 1999, 47(5): 673-680.

[5]馬匯淼, 馬林華, 張嵩, 等. 基于整數(shù)運(yùn)算的 LDPC 碼改進(jìn)最小和譯碼算法[J]. 電視技術(shù), 2013, 37(17): 197-199.

[6]DARABIHA A, CARUSONE A C, KSCHISCHANG F R. A bit-serial approximate min-sum LDPC decoder and FPGA implementation[C]//Proc. IEEE International Symposium on Circuits and Systems. Greece: IEEE Press, 2006:1-4.

[7]ZHANG C, WANG Z, SHA J, et al. Flexible LDPC decoder design for multigigabit-per-second applications[J]. IEEE Trans. Circuits and Systems I: Regular Papers, 2010, 57(1): 116-124.

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

[9]張光榮, 徐鷹, 衛(wèi)國(guó). 一種可配置的 LDPC 碼最小和譯碼算法[J]. 中國(guó)科學(xué)技術(shù)大學(xué)學(xué)報(bào), 2008, 38(7): 792-796.

[10]ANGARITA F, VALLS J, ALMENAR V, et al. Reduced-Complexity Min-Sum algorithm for decoding LDPC codes with low error-floor[J]. IEEE Trans. Circuits and Systems I: Regular Papers,2014(99):1-9.

[11]CHILAPPAGARI S K, NGUYEN D V, VASIC B, et al. On trapping sets and guaranteed error correction capability of LDPC codes and GLDPC codes[J]. IEEE Trans. Information Theory, 2010, 56(4): 1600-1611.

[12]WEY C L, SHIEH M D, LIN S Y. Algorithms of finding the first two minimum values and their hardware implementation[J]. IEEE Trans. Circuits and Systems I: Regular Papers, 2008, 55(11): 3430-3437.

吳 軍(1963— )，副教授，主研無(wú)線通信、嵌入式系統(tǒng)；

廖 鑫(1990— )，碩士生，主研LDPC碼譯碼；

張小紅(1966— )，女，教授，主研信息安全、細(xì)胞神經(jīng)網(wǎng)絡(luò)、廣義混沌同步。

責(zé)任編輯：薛 京

Improved Min-sum Algorithm with Low Complexity for Decoding LDPC Codes

WU Jun, LIAO Xin, ZHANG Xiaohong

(CollegeofInformationEngineering,JiangxiUniversityofScienceandTechnology,JiangxiGanzhou341000,China)

In order to reduce the performance loss of SMMS (Single-Minimum, Min-Sum) algorithm for decoding LDPC (Low-Density Parity-Check) codes, the ACMS (adaptive configurable Min-Sum) algorithm is proposed in this paper. Only the absolute minimum is used in this algorithm to update the check-node message and the second minimum is determined by a configurable estimation weight factor based on the iteration and a correction factor based on the number of error bits in each hard decision. Compared to the original SMMS and VWMS algorithm, the simulation result shows the proposed ACMS algorithm reduce the performance loss in general by introducing only a little additional complexity.

LDPC codes; min-sum algorithm; single-minimum; estimation weight; channel adaptive

TN911.22

A

10.16280/j.videoe.2015.01.022

2014-06-04

【本文獻(xiàn)信息】吳軍，廖鑫，張小紅.一種改進(jìn)的LDPC碼低復(fù)雜度最小和算法[J].電視技術(shù),2015，39(1).