吳 軍，廖 鑫，張小紅

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

一種改進的LDPC碼低復雜度最小和算法

吳 軍，廖 鑫，張小紅

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

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

低密度奇偶校驗碼；最小和算法；單最小值；估算參數；信道自適應

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

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

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

1 最小和算法

1.1 傳統(tǒng)MS算法

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

縱向更新公式為

(1)

橫向更新公式為

(2)

每當消息經過第i次完整的傳遞后，譯碼器便進行軟判決為

(3)

當軟判決輸出的碼字全部滿足奇偶校驗方程或者達到預設的最大迭代次數時，譯碼器停止迭代譯碼并輸出碼字Zn。

1.2 SMMS算法

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

(4)

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

2 自適應可配置最小和算法

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

(5)

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

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

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

(6)

(7)

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

wk=w1+dw·(k-1)

(8)

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

(9)

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

3 仿真結果及分析

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

3.1 估算參數對性能的影響

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

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

從圖中可知，當dw=0.75時，ACMS算法在高信噪區(qū)取得了最佳的誤碼性能。

3.2 信道自適應修正系數對性能的影響

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

圖3 ε對譯碼性能的影響

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

圖4 自適應修正因子對譯碼性能的影響

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

3.3 譯碼性能比較

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

表1 各算法參數配置

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

圖5 各算法譯碼性能比較

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

3.4 復雜度分析

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

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

4 小結

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

[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]馬匯淼, 馬林華, 張嵩, 等. 基于整數運算的 LDPC 碼改進最小和譯碼算法[J]. 電視技術, 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)國. 一種可配置的 LDPC 碼最小和譯碼算法[J]. 中國科學技術大學學報, 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— )，副教授，主研無線通信、嵌入式系統(tǒng)；

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

張小紅(1966— )，女，教授，主研信息安全、細胞神經網絡、廣義混沌同步。

責任編輯：薛 京

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

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