LDPC碼的分層類擬合修正最小和譯碼算法

寧曉燕，孫晶晶，孫志國，宋禹良

(哈爾濱工程大學(xué) 信息與通信工程學(xué)院，哈爾濱 150001)

1962年Gallager[1]提出了低密度奇偶校驗碼(low density parity check, LDPC)，但是因為其譯碼效果不理想而被“休眠”。直到30 a后，又一次將目光聚焦在LDPC碼上。文獻[2]證明了LDPC碼的誤碼性能能夠接近理論香農(nóng)限。目前，LDPC碼已被應(yīng)用到深空通信、無人機數(shù)據(jù)鏈等場景下，并作為一種中長碼的編碼方式，應(yīng)用在5G數(shù)據(jù)信道中。

置信度傳播(belief propagation, BP)算法是LDPC碼的基礎(chǔ)譯碼算法，LDPC碼的譯碼算法大多是在BP譯碼算法的基礎(chǔ)上改進而來。將BP譯碼算法中的軟信息取對數(shù)進行計算，得到了對數(shù)似然比(log likelihood ratio, LLR)BP譯碼算法。為了使LLR BP譯碼算法的計算更加簡便，文獻[3]在校驗節(jié)點的更新過程中取近似運算，提出了最小和(minimum sum, MS)譯碼算法，以誤碼性能下降為代價換取了復(fù)雜度的降低；在MS算法基礎(chǔ)上，文獻[4-5]提出了偏移最小和(offset minimum sum, OMS)譯碼算法和歸一化最小和(normalized minimum sum, NMS)譯碼算法，分別通過減法和乘法運算使結(jié)果更加準(zhǔn)確；文獻[6]根據(jù)置信傳播算法與最小和譯碼算法的校驗節(jié)點信息，推導(dǎo)出一種新的近似因子用來修正MS算法；文獻[7-9]分別將最小和譯碼算法中的取一個最小值的方法，改進為綜合分析多個最小值進行計算；文獻[10-12]在迭代更新的過程中對不可靠信息做出處理；文獻[13]中用不同的偏移因子去修正最小值和次小值，并用次序統(tǒng)計量進行分析；文獻[14]通過在最小和譯碼算法的最小值上增加一個可變因子，來達到近似修正的目的，這些算法都對MS算法中存在的性能損失做出了彌補，提升了誤碼性能；文獻[15-16]介紹了一種基于分層的LDPC碼譯碼算法，改變了算法的調(diào)度方式，提升了譯碼效果。

在一定程度上，這些算法都對MS算法中存在的性能損失做了補償，提升了誤碼性能。OMS算法和NMS算法中，雖然算法本身的復(fù)雜度增加不多，但是偏移系數(shù)以及歸一化系數(shù)的計算勢必會帶來工作量的增加，且固定的系數(shù)必然無法準(zhǔn)確的對MS算法中存在的誤差進行修正，以及改進MS算法由于取值的個數(shù)增加導(dǎo)致復(fù)雜度提升等問題。

基于此，本文提出一種類擬合修正最小和(class fitting modified minimum sum, CFMMS)譯碼算法，該算法首先根據(jù)校驗節(jié)點更新中的非線性函數(shù)構(gòu)造了一個類擬合函數(shù)，來根據(jù)變量節(jié)點信息最小值所在閾值的不同而做出不同的處理，因此能夠更加準(zhǔn)確的對MS算法中存在的誤差進行修正；在此基礎(chǔ)上，將類擬合修正最小和譯碼算法與分層譯碼的思想相結(jié)合，提出一種分層類擬合修正最小和(layered class fitting modified minimum sum, LCFMMS)譯碼算法，改變了傳統(tǒng)譯碼算法的調(diào)度方式，將更新順序由整體更新變成了分層進行更新，加快了譯碼收斂速度，提升了誤碼性能。同時，不再需要儲存所有的校驗節(jié)點信息，壓縮了算法所需的儲存空間。

1 LDPC譯碼算法

LDPC碼有基于硬判決和基于軟判決的兩類譯碼方式[7]，前者雖然較為簡單，但是譯碼效果差；后者雖誤碼性能較好，但復(fù)雜度較大。因此，對于BP譯碼算法的研究，不僅要關(guān)注譯碼效果，也要關(guān)注對復(fù)雜度的影響。

1.1 LLR BP譯碼算法

LDPC碼的譯碼算法是在Tanner圖的基礎(chǔ)上進行的[12]，以(6，2)LDPC碼為例，其校驗矩陣及校驗方程見式(1)，Tanner圖見圖1。

圖1 校驗矩陣對應(yīng)的Tanner圖Fig.1 Tanner diagram corresponding to check matrix

(1)

假設(shè)發(fā)送端預(yù)傳輸?shù)男畔⑿蛄薪?jīng)LDPC編碼器后得到的編碼序列為c=(c1,c2,…,cn)，編碼序列經(jīng)BPSK調(diào)制后得到的傳輸序列為x=(x1,x2,…,xn)，傳輸序列經(jīng)高斯白噪聲信道傳輸后，接收端的接收序列為r=(r1,r2,…,rn)，最后經(jīng)過LDPC譯碼器后得到的譯碼序列為y=(y1,y2,…,yn)。

在LLR BP[17]譯碼算法中，首先接收端接收到來自信道的概率信息，并計算初始對數(shù)似然比為

(2)

式中σ2為噪聲方差。

隨后更新校驗節(jié)點信息及變量節(jié)點信息分別為

(3)

(4)

式中：J(i)為第i行對應(yīng)的變量節(jié)點的集合，J(i)j為第i行對應(yīng)的變量節(jié)點的集合(不包含第j個變量節(jié)點)，I(j)為第j列對應(yīng)的校驗節(jié)點的集合，I(j)i為第j列對應(yīng)的校驗節(jié)點的集合(不包含第i個校驗節(jié)點)。

最后根據(jù)得到的信息進行判決。與概率域BP譯碼算法相比，LLR BP譯碼算法完成了運算方式由乘法到加法的轉(zhuǎn)化，復(fù)雜度有所降低。

1.2 最小和譯碼算法及其改進算法

雖然，將概率域BP譯碼算法放在對數(shù)域運算會降低一定程度的復(fù)雜度，但是算法內(nèi)卻存在非線性函數(shù)，復(fù)雜度依然較高。因此，出現(xiàn)了MS算法，MS算法是在LLR BP譯碼算法中采取了近似運算，將乘法運算轉(zhuǎn)化為比較運算[17]。

由于雙曲正切函數(shù)和反雙曲正切函數(shù)都是奇函數(shù)，式(3)可繼續(xù)推導(dǎo)為

(5)

對于任意的實數(shù)x，都有tanh(|x|)∈(0,1)，式(5)取近似運算可轉(zhuǎn)換為

(6)

由此，MS算法中校驗節(jié)點的更新公式可簡化為

(7)

MS算法的大致思想是將ωc-1個xi相乘近似為xi中的最小值(其中ωc為列重，xi∈(0,1)，i=1,2,…,ωc-1)，這樣得到的結(jié)果要比實際值偏大。因此，對MS算法的改進過程便是使得到的結(jié)果更接近于置信傳播算法的過程。

對于MS算法以部分誤碼性能換取低復(fù)雜度的問題，出現(xiàn)了各種各樣的改進算法，兩種比較經(jīng)典的改進算法，分別為NMS算法和OMS算法[4]，在式(7)的基礎(chǔ)上，得到兩種改進算法的校驗節(jié)點更新過程：

(8)

(9)

式中：α∈(0,1)，β>0。

顯然，這兩種算法都在一定程度上減小了得到的校驗節(jié)點信息數(shù)值，對MS算法中存在的誤差起到了一定的補償作用，使得到的結(jié)果更加接近置信傳播算法。

2 改進的LDPC譯碼算法

2.1 類擬合修正最小和譯碼算法

NMS算法和OMS算法的性能都在一定程度上優(yōu)于MS算法，但是算法中系數(shù)α和β的值是需要根據(jù)仿真得到的[10]，對于系數(shù)的計算，在一定程度上增加了算法的工作量。因此本節(jié)給出了另外一種修正方案，提出了類擬合修正最小和(CFMMS)譯碼算法，對MS算法再一次做近似處理。MS算法對LLR BP算法的近似是向上取近似，本文提出的算法，是在MS算法的基礎(chǔ)上向下取近似，達到減小誤差的目的。

根據(jù)MS算法可得校驗節(jié)點的更新過程為

(10)

首先，定義式(10)中的后半部分為類擬合函數(shù)，即為

效果分為顯效、有效以及無效3個等級，顯效是指患者治療后的臨床癥狀明顯改善，透析過程中無低血壓發(fā)生；有效是指患者的臨床癥狀有所緩解，收縮壓在透析的過程中基本正常；無效則為患者在治療的過程中臨床癥狀和體征無明顯好轉(zhuǎn)，并出現(xiàn)低血壓[5]。

CFF(v)=tanh-1[tanh(v)]

(11)

式中v為任意實數(shù)。

由式(10)可知，本文中v≥0，因此在函數(shù)y=tanh(x)和y=tanh-1(x)中只考慮x≥0(下文關(guān)于分段函數(shù)的段數(shù)問題均在該范圍內(nèi)討論)的部分即可。將兩個函數(shù)分別近似為一個含有3段的分段函數(shù)，對y=tanh(x)函數(shù)均勻的選擇的4個點分別為(0，0)、(1，0.76)、(2，0.96)、(3，1)，在y=artanh(x)中，考慮斜率的變化選擇的4個點分別為(0，0)、(0.4，0.42)、(0.8，1.1)、(1，2.5)，得到兩個非線性函數(shù)與其近似函數(shù)圖像見圖2。

圖2 近似線性函數(shù)Fig.2 Approximate linear function

將兩個分段函數(shù)分別代入類擬合函數(shù)中，為保證類擬合函數(shù)擁有較低的復(fù)雜度，同時考慮變量節(jié)點最小值的變化范圍，得到類擬合函數(shù)為

(12)

由類擬合函數(shù)可以看出，該函數(shù)會根據(jù)變量節(jié)點最小值所在閾值的不同，做出不同的處理，每一部分的計算都是為了得到與置信傳播算法更接近的結(jié)果。

綜上分析，CFMMS算法的校驗節(jié)點更新公式為

(13)

如果在MS算法中引入類擬合函數(shù)的概念，MS算法中類擬合函數(shù)的表達式應(yīng)為

(14)

很明顯，MS算法中存在的類擬合函數(shù)只是一個簡單的線性函數(shù)，且不會受變量節(jié)點信息的影響。而在式(12)中，類擬合函數(shù)會根據(jù)最小值的不同而采取不同的處理方式，得到的校驗節(jié)點信息會更加準(zhǔn)確。

此外，分段函數(shù)的段數(shù)也會影響其與原函數(shù)的近似程度。因此，對于分段函數(shù)段數(shù)的選取并不是隨意的，如果分段函數(shù)的段數(shù)過多，就會出現(xiàn)近似函數(shù)與原函數(shù)擬合程度過高，進而達不到修正的目的；反之，分段函數(shù)的段數(shù)過少，則會導(dǎo)致近似函數(shù)與原函數(shù)偏離程度過大，進而出現(xiàn)修正過度的現(xiàn)象。

2.2 基于分層的類擬合修正最小和譯碼算法

針對CFMMS算法增加了少量復(fù)雜度且譯碼收斂速度較慢的問題，將CFMMS算法與分層譯碼的思想相結(jié)合，提出了一種基于分層的類擬合修正最小和(LCFMMS)譯碼算法。

圖3 分層迭代譯碼算法處理流程圖Fig.3 Processing flow of layered iterative decoding algorithm

LCFMMS算法的迭代更新具體過程如下：

1)首先將校驗矩陣HM×N以行為單位分成D層(0

2)初始化信息

(15)

3)層內(nèi)變量節(jié)點更新

(16)

4)層內(nèi)校驗節(jié)點更新

(17)

5)后驗概率更新

(18)

6)判斷是否已到達最大層數(shù)，如果未到達最大層數(shù)，則返回步驟3繼續(xù)進行更新；如果已到達最大層數(shù)，則進入步驟7。

7)判決：如果Vi>0，則判yi=0；否則判yi=1。

8)最后，檢驗信息序列y是否滿足校驗方程H·yT=0，如果滿足校驗方程，則譯碼完成；否則，信息序列y將被作為初始對數(shù)似然比信息重新回到步驟3進行更新，直到滿足譯碼完成的條件，即可停止譯碼。

3 算法仿真及分析

3.1 算法復(fù)雜度分析

表1給出了MS算法、CFMMS算法、LCFMMS算法3種算法在一次迭代中節(jié)點更新所需要的各類運算(“+”、“×”、“<”)的次數(shù)，其中m為校驗矩陣H的行數(shù)，n為校驗矩陣H的列數(shù)，ωr為校驗矩陣H的行重，ωc為檢驗矩陣H的列重，D取值為m。

表1 算法復(fù)雜度Tab.1 Algorithm complexity

CFMMS算法相比較于MS算法來說，3種運算的次數(shù)均稍有增加；而LCFMMS算法在復(fù)雜度方面有了明顯的下降，不論行重大小如何，乘法運算、加法運算和比較運算次數(shù)都在一定程度上有所減少。由表1可以看出，不論何種譯碼算法，在碼率以及行重、列重固定的條件下，完成譯碼所需各種運算的次數(shù)與LDPC碼的碼長是成正比關(guān)系的，即各算法的運算復(fù)雜度會隨著碼長的增加而增加。

3.2 算法仿真結(jié)果

為驗證本文提出的CFMMS算法和LCFMMS算法的性能，在AWGN信道下，調(diào)制方式采用BPSK調(diào)制，最大迭代次數(shù)設(shè)為10次，碼率為1/2，碼長分別選取較短碼長128、中等碼長1 024和較長碼長2 048，根據(jù)以上條件對LDPC碼進行仿真分析。在文獻[4-5,18]中，關(guān)于改進的LDPC譯碼算法的性能分析，都以誤碼率作為指標(biāo)。因此，在本文中也分析其誤碼率曲線，其仿真結(jié)果及分析如下。

在圖4中，分別為在碼長2 048和碼長128下，MS算法、CFMMS算法和LCFMMS算法3種譯碼算法的誤碼率曲線?？梢钥闯觯徽摯a長如何，在前提條件相同的情況下，這3種譯碼算法的誤碼性能都是MS算法最差，CFMMS算法次之，LCFMMS算法最好。在碼長為2 048，誤碼率接近10-4時，CFMMS算法較MS算法、LCFMMS算法較CFMMS算法來說，誤碼性能分別提升了約0.4 dB；在碼長為128，誤碼率為10-5時，CFMMS算法較MS算法來說，誤碼性能提升了約0.5 dB，LCFMMS算法相比較于CFMMS算法來說，亦具有0.3 dB的性能增益。

圖4 各譯碼算法在不同碼長下誤碼性能對比Fig.4 Comparison of BER performance of decoding algorithms under different code lengths

圖5展示了在采用LCFMMS算法進行譯碼的前提下，碼長對于譯碼算法誤碼性能的影響。從圖中可以看出，隨著碼長的增加，譯碼算法的誤碼性能是越來越好的，即譯碼算法對于長碼長LDPC碼的誤碼性能要優(yōu)于短碼長LDPC碼的誤碼性能，這也是LDPC碼更適用于長碼的原因。但是，由分析可知，譯碼算法的算法復(fù)雜度與LDPC碼的碼長成正比關(guān)系。因此，在實際應(yīng)用中并不可一味的追求長碼長的優(yōu)異性能，還要綜合考慮復(fù)雜度的問題，這樣才能選出合適的碼長。

圖5 不同碼長下的誤碼性能對比Fig.5 Comparison of BER performance under different code lengths

圖6為在碼長分別為2 048和128，最大迭代次數(shù)為10次的情況下，3種不同的譯碼算法完成譯碼所需要的迭代次數(shù)。從圖中可以看出，不論碼長如何，CFMMS譯碼算法所需要的迭代次數(shù)要比MS算法稍少一些，但是差別不大；而LCFMMS算法由于應(yīng)用了分層調(diào)度的調(diào)度方式，提高了信息的可靠度，使得譯碼能夠快速收斂，因此所需要的迭代次數(shù)會在一定程度上有所下降。

圖6 不同算法所需迭代次數(shù)Fig.6 Number of iterations required by different algorithms

圖7為不同最大迭代次數(shù)下的誤碼率曲線，采用的譯碼算法為LCFMMS譯碼算法。由圖可知，在一定范圍內(nèi)，誤碼性能與最大迭代次數(shù)是呈正比關(guān)系的，尤其在最大迭代次數(shù)小于10次的情況下，誤碼性能的提升最為明顯；但是，當(dāng)最大迭代次數(shù)超過10次后，誤碼率曲線的變化趨勢會減?。磺易畲蟮螖?shù)超過20次后，誤碼率曲線不會再隨著迭代次數(shù)的增加而發(fā)生明顯的變化。在實際應(yīng)用中最大迭代次數(shù)的選取要經(jīng)過充分的考慮。如果數(shù)值選取過小會影響誤碼性能，選取過大會浪費資源。

圖7 不同最大迭代次數(shù)下的誤碼率曲線Fig.7 BER curves under different maximum iterations

4 結(jié) 論

本文首先基于MS算法提出了一種CFMMS算法，對MS算法中近似運算帶來校驗節(jié)點信息數(shù)值偏大的問題進行了修正，雖然計算復(fù)雜度較MS算法稍有增加，但是得到的校驗節(jié)點信息值更為準(zhǔn)確。在此基礎(chǔ)上，改變了CFMMS算法的調(diào)度方式，將原來的洪水式調(diào)度變?yōu)榉謱邮秸{(diào)度，對算法所需的儲存空間進行了壓縮，而且每層變量節(jié)點更新用到的都是上一層剛剛更新的節(jié)點信息，因此得到的信息更加具有實時性和可靠性。仿真結(jié)果與復(fù)雜度分析表明，本文所提出的CFMMS和LCFMMS算法，在誤碼性能方面都有所提升。而且，LCFMMS算法不僅提升了誤碼性能，還降低了算法的實現(xiàn)復(fù)雜度，加快了譯碼的收斂速度，帶來了更低的譯碼延時。