一種改進(jìn)的LLR-SPA譯碼新算法*

王 巖，王中訓(xùn)，唐田田，劉為云，高興龍

(煙臺(tái)大學(xué) 光電信息科學(xué)技術(shù)學(xué)院，山東 煙臺(tái) 264005)

0 引言

低密度奇偶校驗(yàn)碼(Low Density Parity-Check，LDPC)是一種誤碼性能逼近香農(nóng)極限的實(shí)用碼，并且能夠做到完全的并行譯碼，一直以來(lái)備受研究者的關(guān)注。近年來(lái)隨著其編碼和譯碼算法的不斷改進(jìn)與完善，該碼在深空、水下、移動(dòng)通信等領(lǐng)域得到了較為廣泛的應(yīng)用[1-4]。

LDPC碼的譯碼算法是建立在無(wú)環(huán)Tanner圖上的置信傳播(Belief Propagation，BP)算法。基于概率域的BP譯碼算法涉及大量的加法和乘法運(yùn)算，其又被稱(chēng)作和積(Sum-Product Algorithm，SPA)算法。該算法中的乘法運(yùn)算不僅會(huì)消耗大量運(yùn)算時(shí)間，而且不利于量化實(shí)現(xiàn)[5-6]。針對(duì)此問(wèn)題，研究者提出使用似然比表示概率消息，用加法運(yùn)算代替大量乘法運(yùn)算，基于此方法提出的譯碼算法被稱(chēng)為 LLR-SPA（Sum-Product Algorithm in Log-Likelihood-domain)算法，LLR-SPA算法的提出為 LDPC碼的實(shí)際應(yīng)用打下了堅(jiān)實(shí)的基礎(chǔ)。

LLR-SPA算法雖然極大地降低了BP算法的復(fù)雜度，但是其譯碼復(fù)雜度仍然較高，限制了LDPC碼的進(jìn)一步應(yīng)用。目前，專(zhuān)家學(xué)者為L(zhǎng)DPC碼的實(shí)際應(yīng)用做了諸多貢獻(xiàn)。參考文獻(xiàn)[7]提出了一種基于LLR-SPA算法的改進(jìn)的MS(min-sum)譯碼算法，該算法雖然降低了LLR-SPA譯碼算法的復(fù)雜度，但其譯碼性能相對(duì)較差，難以滿足對(duì)譯碼性能要求較高的應(yīng)用。參考文獻(xiàn)[8-9]提出了一種基于LLR-SPA算法的改進(jìn)的OMS(offset min-sum)譯碼算法和 NMS(normalized min-sum)譯碼算法，這兩種算法雖然能夠提供較高的譯碼精度，但是要根據(jù)實(shí)際情況設(shè)置相關(guān)的偏移參數(shù)和校正因子，增加了譯碼復(fù)雜度，而且也不利于硬件實(shí)現(xiàn)。參考文獻(xiàn)[10-11]分別提出了一種基于一階邁克勞林級(jí)數(shù)和一階泰勒級(jí)數(shù)簡(jiǎn)化的譯碼算法，這兩種算法雖然能有效地降低譯碼復(fù)雜度，但是犧牲了譯碼精度?；诖耍疚奶岢鲆环N基于泰勒級(jí)數(shù)分段線性近似的簡(jiǎn)化算法，該算法是將LLR-SPA譯碼算法中復(fù)雜度較高的雅克比修正項(xiàng)采用泰勒級(jí)數(shù)進(jìn)行分段線性近似，在譯碼復(fù)雜度相當(dāng)?shù)那闆r下，大大提高了譯碼精度。

1 LDPC碼的譯碼算法

1.1 LLR-SPA譯碼算法

LDPC 碼根據(jù)檢驗(yàn)矩陣 Hm×n傳送的碼字 x={x1，x2，…，xn}和接收的碼字 y={y1，y2，…，yn}進(jìn)行譯碼。

信息經(jīng)過(guò)編碼，采用BPSK調(diào)制，通過(guò)AWGN信道傳輸，其信道的噪聲方差為σ2，每個(gè)變量節(jié)點(diǎn)的先驗(yàn)似然比是 L(xn)=log{P(xn=0|yn)/P(xn=1|yn)}，則 LLR-SPA算法的譯碼過(guò)程如下：

(1)初始化，變量節(jié)點(diǎn)傳向校驗(yàn)節(jié)點(diǎn)的初始信息和校驗(yàn)節(jié)點(diǎn)傳向變量節(jié)點(diǎn)的初始信息，其計(jì)算公式分別如式(1)、式(2)所示：

(2)校驗(yàn)節(jié)點(diǎn)的更新，對(duì)于每一行 m，n∈N(m)，N(m)表示與校驗(yàn)節(jié)點(diǎn)m相連的所有變量節(jié)點(diǎn)的集合，n′=N(m) ，N(m) 表示N(m)中去掉變量節(jié)點(diǎn)n。計(jì)算公式為：

(3)變量節(jié)點(diǎn)的更新，對(duì)于每一列 n，m∈M(n)，M(n)表示與變量節(jié)點(diǎn)n相連的所有校驗(yàn)節(jié)點(diǎn)的集合，m′=M(n)m，M(n)m表示M(n)中去掉校驗(yàn)節(jié)點(diǎn)m。計(jì)算公式為：

1.2 基于泰勒級(jí)數(shù)的簡(jiǎn)化譯碼算法

本文提出的算法是針對(duì)LLR-SPA算法中復(fù)雜度較高的雅克比修正項(xiàng)采用泰勒級(jí)數(shù)進(jìn)行分段線性近似，主要是對(duì)其校驗(yàn)節(jié)點(diǎn)進(jìn)行更新，對(duì)于式(3)中的tanh運(yùn)算采用參考文獻(xiàn)[12]中的核心操作對(duì)式(3)重新處理得到式(7)。其中式(7)中的兩個(gè)非線性的對(duì)數(shù)函數(shù)是雅可比修正項(xiàng)。

從校驗(yàn)節(jié)點(diǎn)獲得外部信息：

其中，U、V表示統(tǒng)計(jì)獨(dú)立的二進(jìn)制隨機(jī)變量，L(U)、L(V)是 U、V的似然比值，fi、bi分別表示一組輔助的二進(jìn)制隨機(jī)變量，i=1，2，…，dc，dc表示 LDPC 碼的校驗(yàn)度，⊕表示模二操作。

利用式(7)和傳送的碼 字 x={x1，x2，…，xn}對(duì)輔助的二進(jìn)制隨機(jī)變量 fi、bi分別作遞歸處理，得到 L(fi)和 L(bi)。利用公式(xn1⊕xn2⊕…⊕xnd)=0，得到 xni=(fi-1⊕bi+1)，其c中i∈{2，3，…，dc-1}。通過(guò)這種前向后向遞歸運(yùn)算完成校驗(yàn)節(jié)點(diǎn)的更新。

[11]使用一階泰勒級(jí)數(shù)對(duì)式(7)中的修正項(xiàng)進(jìn)行處理。本文提出的算法與該算法與原曲線的最大誤差對(duì)比結(jié)果如表1所示，本文提出的算法與參考文獻(xiàn)[11]提出的算法近似曲線的對(duì)比結(jié)果如圖1所示。本文采用泰勒級(jí)數(shù)對(duì)式(7)中的修正項(xiàng)進(jìn)行分段線性近似。使用函數(shù)g(x)=log(1+e-|x|)表示式(7)中的修正項(xiàng)，在一階泰勒級(jí)數(shù)近似的基礎(chǔ)上對(duì)曲線g(x)進(jìn)行分段線性近似，并以g(x)函數(shù)切點(diǎn)x0為分段節(jié)點(diǎn)進(jìn)行分段，分段步長(zhǎng)為0.75，分段函數(shù)如表2所示。

圖1 兩種線性近似曲線

表1 兩種線性近似方式與原曲線的最大誤差

從圖1可以看出本文提出的算法有效地解決了參考文獻(xiàn)[11]提出的使用一階泰勒級(jí)數(shù)近似時(shí)在x=0和g(x)=0處造成誤差的問(wèn)題。

該算法與LLR-SPA算法相比，在譯碼性能基本沒(méi)有變化的情況下，避免了查表操作和非線性的對(duì)數(shù)運(yùn)算，降低了算法的復(fù)雜度。與兩種修正的MS譯碼算法相比無(wú)需設(shè)置偏移參數(shù)和校正因子，更利于實(shí)際應(yīng)用。

2 仿真結(jié)果

實(shí)驗(yàn)使用MATLAB從以下幾個(gè)方面進(jìn)行驗(yàn)證：與原曲線的最大誤差；信噪比和誤比特率。實(shí)驗(yàn)環(huán)境如下：信道采用AWGN信道，調(diào)制方式為BPSK，規(guī)則的LDPC碼(504，3，6)和(6 000，3，6)，迭代次數(shù)分別設(shè)為 40 和 80。

從表1數(shù)據(jù)可以看出，本文提出的算法相比于文獻(xiàn)[11]提出的算法與原曲線的最大誤差小，更接近原曲線。

在迭代次數(shù)為 40，使用規(guī)則 LDPC碼(504，3，6)的情況下，本文提出的算法與LLR-SPA算法、最小和譯碼算法、一階泰勒級(jí)數(shù)近似算法在信噪比和誤比特率方面對(duì)比結(jié)果如圖2所示。

圖 2 規(guī)則 LDPC碼（504，3，6）的譯碼性能，迭代次數(shù)為 40

從圖2可以看出，當(dāng)誤碼比特率為10-4時(shí)，本文提出的算法在譯碼性能上優(yōu)于一階泰勒級(jí)數(shù)算法和最小和算法分別約為0.15 dB，0.35 dB。相比于最優(yōu)的LLRSPA算法，僅有0.05 dB的性能損失。

在迭代次數(shù)為 80，使用規(guī)則 LDPC碼(6 000，3，6)的情況下，本文提出的算法與LLR-SPA算法、最小和譯碼算法、一階泰勒級(jí)數(shù)近似算法在信噪比和誤比特率方面對(duì)比結(jié)果如圖3所示。

圖 3 規(guī)則 LDPC碼（6 000，3，6）的譯碼性能，迭代次數(shù)為 80

從圖3可以看出，當(dāng)誤碼比特率為10-4時(shí)，本文提出的算法分別優(yōu)于一階泰勒級(jí)數(shù)算法和最小和算法分別約為 0.2 dB，0.55 dB；當(dāng)誤碼比特率為 10-5時(shí)，本文提出的算法分別優(yōu)于一階泰勒級(jí)數(shù)算法和最小和算法分別約為0.22 dB，0.6 dB。從圖中還可以看出本文提出的算法與最優(yōu)的LLR-SPA算法相比，幾乎沒(méi)有性能損失。

3 結(jié)論

本文旨在提出一種提高譯碼精度的新算法，該算法將LLR-SPA譯碼算法中復(fù)雜度較高的雅克比修正項(xiàng)采用泰勒級(jí)數(shù)進(jìn)行分段線性近似。該算法與一階泰勒級(jí)數(shù)近似相比在譯碼復(fù)雜度基本不變的情況下，極大地提高了譯碼算法的性能；與LLR-SPA譯碼算法相比，不僅避免了查表操作和復(fù)雜的非線性對(duì)數(shù)函數(shù)的計(jì)算，而且在性能上逼近最優(yōu)的LLR-SPA譯碼算法，具有有效性和實(shí)用性。

參考文獻(xiàn)

[1]沈雪梅.下一代無(wú)線局域網(wǎng)中LDPC譯碼算法研究[J].科技通報(bào)，2013，29(2)：127-129.

[2]Wang Kaiyao，Xiao Yang，KIM K.Construction of timefrequency codes based on protograph LDPC codes in OFDM communication systems[J].Journal of Systems Engineering and Electronics，2012，3(23)：335-341.

[3]喬曉峰，劉躍敏，寧永海.RS碼與QC-LDPC碼的級(jí)聯(lián)碼在淺海信道中的性能研究[J].電子技術(shù)應(yīng)用，2012，38（5）：122-124.

[4]李成福，盧選民，楊杰，等.基于LDPC碼和物理層網(wǎng)絡(luò)編碼的聯(lián)合信道編碼技術(shù)[J].微型機(jī)與應(yīng)用，2013，32(17)：41-43.

[5]吳斌，楊波，葉明.LDPC硬件實(shí)現(xiàn)中的數(shù)據(jù)量化位數(shù)選擇及其性能仿真[J].信息通信，2012，118(2)：26-28.

[6]梁偉，劉亮，沈旭，等.采用動(dòng)態(tài)量化的低存儲(chǔ)空間 LDPC譯碼研究[J].計(jì)算機(jī)工程與應(yīng)用，2011，47(10)：106-109.

[7]吳瓊，梅進(jìn)杰.改進(jìn)Min-sum的 LDPC譯碼研究[J].無(wú)線電通信技術(shù)，2012，38(2)：27-29.

[8]陳旭燦，劉冬培.改進(jìn)的 LPDC譯碼算法研究[J].電子科技大學(xué)學(xué)報(bào)，2010，39(2)：219-222.

[9]Hu Xiaoyu，ELEFTHERIOU E，ARNOLD D M，et al.Efficient implementations of the sum-product algorithm for decoding LDPC codes[C].Global Telecommunications Conference，IEEE GLOBECOM(2)，2001：1036-1036E.

[10]PAPAHARALABOS P，MATHIOPOULOS P T.Simplified sum-product algorithm for decoding LDPC codes with optimal performance[J].Electronics Letters，2009，45(2)：116-117.

[11]胡樹(shù)楷，王新梅.一種簡(jiǎn)化的GF(q)-LDPC碼譯碼算法[J].西安電子科技大學(xué)學(xué)報(bào)，2011，38(2)：8-12.

[12]Chen Jinghu，DHOLAKIA A，ELEFTHERIOU E，et al.Reduced-complexity decoding of LDPC codes[J].IEEE Transactions on Communications，2005，53(8)：1288-1299.