改進Min-sum的LDPC譯碼算法研究

吳 瓊，梅進杰

(1.空軍雷達學院研究生管理大隊，湖北武漢430019;2.空軍雷達學院，湖北武漢430019)

0 引言

低密度奇偶校驗碼(Low-density Parity Codes，LDPC)是由Gallager于1962年提出的一種基于稀疏校驗矩陣的線性糾錯碼［1］。由于LDPC碼具有較強的糾錯能力、較大的靈活性和比較低的譯碼復雜度，在高斯白噪聲AWGN信道下的譯碼性能可以逼近Shannon信道容量的極限，使它成為近年來糾錯編碼領域的研究熱點之一。該文提出一種改進的Min-sum算法，利用最小差準則來計算該算法中的各個參數(shù)，有效提高了Min-sum算法中的性能。

1 Min-sum算法及其改進

1.1 LDPC碼

LDPC碼是由稀疏奇偶校驗矩陣H(N－K)×N定義的線性分組碼，其中碼長為N，信息位為K，校驗位為M=N－K，碼率為R=K/N。則該碼的校驗矩陣H是一個M×N的矩陣，如果校驗矩H中每一行有“ρ”個1，且每一列有“λ”個1，即H矩陣每行的行重相同，且每列的列重也相同，這種碼稱為規(guī)則(regular)LDPC 碼［2］，記為 (N，λ，ρ)，否則稱為非規(guī)則(irregular)LDPC碼［3］。雖然非規(guī)則LDPC碼的性能優(yōu)于同等參數(shù)條件下的規(guī)則LDPC碼，但是因為非規(guī)則碼的實現(xiàn)復雜度很高，所以目前主要的研究對象還是規(guī)則LDPC碼。式(1)給出了某個(8，2，4)LDPC碼的校驗矩陣H:

LDPC 碼通常由雙向圖(也稱 Tanner圖［4］)表示，它是由變量節(jié)點(Variable node，矩陣的每行代表1個校驗方程，每列代表1個碼字)和校驗節(jié)點組成的。其中變量節(jié)點分別與校驗矩陣的各列相對應，校驗節(jié)點分別與校驗矩陣中的各行對應。如果1個碼字比特包含在相應的校驗方程中，就用1條連線將所涉及的比特節(jié)點和校驗節(jié)點連起來，所以Tanner圖中的連線數(shù)與校驗矩陣中的1的個數(shù)相同。圖1所示為式(1)所對應的Tanner圖，其中X1－X8為變量節(jié)點，C1－C4為校驗節(jié)點。

圖1 矩陣H對應的Tanner圖

1.2 Min-sum算法

對數(shù)域BP算法(LLR-BP)譯碼算法是最經(jīng)典的LDPC解碼算法之一，其核心思想就是利用Tanner圖中的變量節(jié)點和校驗節(jié)點之間的約束關系，在2種節(jié)點之間來回傳遞并更新置信度信息，最終實現(xiàn)解碼。在每次迭代過程中，所有校驗節(jié)點從相鄰的變量節(jié)點接收信息，將這一信息處理后反饋給相鄰的變量節(jié)點，然后變量節(jié)點再從校驗節(jié)點反饋給相鄰的變量節(jié)點，最后根據(jù)變量節(jié)點的信息進行判決。

LLR-BP譯碼算法是用LLR值作為迭代譯碼過程中傳遞的置信值的一種置信傳播譯碼算法。與概率域BP算法相比，它將大量的乘法運算轉(zhuǎn)化為加法運算，大大降低了譯碼算法的復雜度，并有效地減小了系統(tǒng)的時延。但是LLR-BP算法在迭代譯碼前需要估算信道噪聲功率，并且在對校驗節(jié)點進行信息處理時，非線性運算實現(xiàn)復雜度較高。

設編碼器輸出碼字為 c=(c1，c2，…，cn)，采用BPSK調(diào)制方式后變?yōu)閤i=2ci－1，通過AWGN信道后，譯碼器的輸入序列為 k=(k1，k2，…，kn)，其中ki=2ci－1+mi，mi是均值為0、方差為σ2的高斯白噪聲，譯碼得到的序列為c^=(c^1，c^2，…c^n)。Rj={I∶Hji=1}表示與校驗節(jié)點j相連的變量節(jié)點的集合，Rj/i表示除去第i個節(jié)點以外其他與校驗節(jié)點j相連的校驗節(jié)點的集合，Ci={j∶hji=1}表示與變量節(jié)點i相連的校驗節(jié)點的集合，Ci/j表示除去第j個校驗節(jié)點以外其他與變量節(jié)點i相連的校驗節(jié)點的集合，qij(b)表示變量節(jié)點i傳遞給校驗節(jié)點j的外部概率信息;rji(b)表示校驗節(jié)點傳遞給變量節(jié)點的外部概率信息;Pi(b)=P(ci=b|yi)表示接收到y(tǒng)i以后判斷變量節(jié)點ci=b的概率。最小和算法的具體譯碼過程如下:

①似然信息初始化

計算信道傳遞給變量節(jié)點的初始概率似然比信息 L(pi)，i=1，2，…，n，對于變量節(jié)點 i以及與其相鄰的校驗節(jié)點j而言，在AWGN信道中變量節(jié)點傳遞給校驗節(jié)點的初始信息為:

②水平迭代(校驗節(jié)點的信息處理)

對所有的校驗節(jié)點j和其相鄰的變量節(jié)點i∈R(j)，第r次迭代時，計算變量節(jié)點傳向校驗節(jié)點的消息:

最小和算法對校驗節(jié)點的信息更新公式做了如下近似簡化:

③垂直迭代(變量節(jié)點的信息處理)

對所有的變量節(jié)點i和其相鄰的校驗節(jié)點j∈C(i)，第r次迭代時，計算校驗節(jié)點傳向變量節(jié)點的消息:

④譯碼判決

對所有變量節(jié)點結(jié)算硬判決消息

L(l)(qi)＞0，則c^i=0;否則為1。

⑤停止

判斷Hc^iT=0是否成立，若成立則停止迭代，譯碼輸出為c^i;否則返回步驟①繼續(xù)迭代，直到達到最大迭代次數(shù)，同時給出譯碼失敗標志。

1.3 改進的Min-sum算法

由于Min-sum算法與LLR-BP算法相比過高的估計了輸出校驗消息的幅度，如果采取措施降低消息的幅度，則可以接近甚至超過LLR-BP算法的性能，由此產(chǎn)生了Normalized BP-based算法和Offset BP-based算法。為了敘述方便，將式(4)中的L(r)(rji)記為L1，式(5)中的L(r)(rji)記為L2。

Normalized BP-based算法是通過將原來的幅度除以一個尺度因子α得到的，其中α＞1，稱其為校正因子，此時校驗節(jié)點的輸出信息L(γ)(rji)更新為:

Offset BP-based算法是將原來的校驗消息幅度減去一個數(shù)值β來降低，β稱其為偏移因子，此時校驗節(jié)點的輸出信息L(r)(rji)更新為:

從式(9)和式(10)可以看出，由于Normalized BP-based算法和Offset BP-based算法分別通過引入單一的乘性因子和加性因子，從而只能一定程度上減小變量節(jié)點之間信息的相關性，對LLR BP算法的譯碼性能提升有限。如果能夠同時引入乘性因子和加性因子，那么必然能夠使得LLR BP算法的譯碼性能得到進一步提升。

該文對Min-sum算法進一步改進，通過同時引入α、β和γ，使得式(5)中不但含有乘性因子而且還有加性因子，從而進一步減小變量節(jié)點之間信息的相關性，提高Min-Sum算法的譯碼性能。

為了確定γ和β的值，使得m(γ，β)達到最小值，分別對式(10)中的γ和β求偏導數(shù)，得出:

將式(10)代入式(11)可得:

解得:

綜上所述，改進的Min-sum算法校驗節(jié)點的信息更新公式可以用下式進行描述:

式中，γ和β的值由式(13)求得。

2 仿真實驗與結(jié)果分析

在Matlab軟件中，選取碼長256、行重為6、列重為3、碼率為1/2的規(guī)則LDPC碼，經(jīng)過BPSK調(diào)制后，經(jīng)過高斯信道。LDPC的最大迭代次數(shù)設為50次，根據(jù)蒙特卡羅算法可以求出式(13)中的數(shù)學期望E［·］，通過仿真得到γ =0.97，β=53。根據(jù)文獻［5］可知當 α =1.1時，Normalized BP-based算法具有最好的譯碼性能，故在改進的Min-sum算法中，令α=1.1，γ=0.97，β=53。

Min-sum算 法、NormalizedBP-based(α =1.1)、Offset BP-based(β=0.1)及改進的Min-sum算法的譯碼性能曲線如圖2所示。從圖中可以看出，對于(256，6，3)LDPC 碼來說，在相同誤碼率BER=10－3的情況下，β =0.1的Offset BP-based算法比Min-sum算法的誤碼性能了約0.3 dB提高，而α=1.1的Normalized BP-based算法比Offset BP-based譯碼算法性大約有0.1 dB的增益，但實現(xiàn)復雜度稍微高些。

α=1.1，γ=0.97，β=53的改進型Min-sum算法又比α=1.1的Normalized BP-based算法的譯碼性能有0.1～0.2 dB的提高，相比Min-sum算法有0.5 dB的增益，其譯碼性能接近于LLR-BP算法。改進型的Min-sum算法的硬件復雜度相對于Normalized BP-based算法而言只增加了一個加法器，相對于Offset BP-based而言只增加了一個乘法器，因此該算法能在較低復雜度的情況下提高譯碼性能。LLR-BP算法雖然具有最好的譯碼性能，但是Min-sum算法及其改進的算法在校驗節(jié)點的消息處理時采用了簡化處理，提高了譯碼效率，其硬件實現(xiàn)的復雜度上要降低很多。

圖2 不同譯碼算法的誤碼性能

3 結(jié)束語

該文對LDPC碼常用的譯碼算法進行了研究，并提出一種改進型Min-sum算法，該算法的創(chuàng)新之處在于結(jié)合了Normalized BP-based算法和Offset BP-based的優(yōu)點，并通過均方誤差準則來選擇參數(shù)，進一步降低了校驗節(jié)點之間信息的相關性，提高了Min-Sum算法的譯碼性能。

［1］GALLAGER R G.Low Density Parity Check Codes［J］.IEEE Trans Information Theory，1962，8(3)：208 －220.

［2］ZHANG H T，MOURA J M F.The Design of Structured Regular LDPC Codes With Large Girth［C］∥IEEE Global Telecommunications Conference，2003(3)：4022 －4024.

［3］TIAN T，JONES C，VILLASENOR J D，et al.Construction of Irregular LDPC Codes with Low Eroor Floors［J］.IEEE Intl.Conf.Comm，2003，6：3125 －3129.

［4］TANNER R M.A Recursive Approach to Low Complexity Codes［J］.IEEE Trans.Inf.Theory，1981，27(5)：533 －547.

［5］CHEN J H，F(xiàn)OSSORIER M P C.Density Evolution for BP-based Decoding Algorithm of LDPC Codes and Their Quantize Versions［J］.Global Teleconference，2002，6(2)：1378 －1382.