吳 瓊，梅進(jìn)杰

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

0 引言

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

1 Min-sum算法及其改進(jìn)

1.1 LDPC碼

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

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

圖1 矩陣H對(duì)應(yīng)的Tanner圖

1.2 Min-sum算法

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

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

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

①似然信息初始化

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

②水平迭代(校驗(yàn)節(jié)點(diǎn)的信息處理)

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

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

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

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

④譯碼判決

對(duì)所有變量節(jié)點(diǎn)結(jié)算硬判決消息

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

⑤停止

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

1.3 改進(jìn)的Min-sum算法

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

Normalized BP-based算法是通過(guò)將原來(lái)的幅度除以一個(gè)尺度因子α得到的，其中α＞1，稱其為校正因子，此時(shí)校驗(yàn)節(jié)點(diǎn)的輸出信息L(γ)(rji)更新為:

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

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

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

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

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

解得:

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

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

2 仿真實(shí)驗(yàn)與結(jié)果分析

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

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

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

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

3 結(jié)束語(yǔ)

該文對(duì)LDPC碼常用的譯碼算法進(jìn)行了研究，并提出一種改進(jìn)型Min-sum算法，該算法的創(chuàng)新之處在于結(jié)合了Normalized BP-based算法和Offset BP-based的優(yōu)點(diǎn)，并通過(guò)均方誤差準(zhǔn)則來(lái)選擇參數(shù)，進(jìn)一步降低了校驗(yàn)節(jié)點(diǎn)之間信息的相關(guān)性，提高了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.