一種改進的LLR-SPA譯碼新算法*

王 巖，王中訓，唐田田，劉為云，高興龍

(煙臺大學 光電信息科學技術學院，山東 煙臺 264005)

0 引言

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

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

LLR-SPA算法雖然極大地降低了BP算法的復雜度，但是其譯碼復雜度仍然較高，限制了LDPC碼的進一步應用。目前，專家學者為LDPC碼的實際應用做了諸多貢獻。參考文獻[7]提出了一種基于LLR-SPA算法的改進的MS(min-sum)譯碼算法，該算法雖然降低了LLR-SPA譯碼算法的復雜度，但其譯碼性能相對較差，難以滿足對譯碼性能要求較高的應用。參考文獻[8-9]提出了一種基于LLR-SPA算法的改進的OMS(offset min-sum)譯碼算法和 NMS(normalized min-sum)譯碼算法，這兩種算法雖然能夠提供較高的譯碼精度，但是要根據實際情況設置相關的偏移參數和校正因子，增加了譯碼復雜度，而且也不利于硬件實現。參考文獻[10-11]分別提出了一種基于一階邁克勞林級數和一階泰勒級數簡化的譯碼算法，這兩種算法雖然能有效地降低譯碼復雜度，但是犧牲了譯碼精度。基于此，本文提出一種基于泰勒級數分段線性近似的簡化算法，該算法是將LLR-SPA譯碼算法中復雜度較高的雅克比修正項采用泰勒級數進行分段線性近似，在譯碼復雜度相當的情況下，大大提高了譯碼精度。

1 LDPC碼的譯碼算法

1.1 LLR-SPA譯碼算法

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

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

(1)初始化，變量節點傳向校驗節點的初始信息和校驗節點傳向變量節點的初始信息，其計算公式分別如式(1)、式(2)所示：

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

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

1.2 基于泰勒級數的簡化譯碼算法

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

從校驗節點獲得外部信息：

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

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

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

圖1 兩種線性近似曲線

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

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

該算法與LLR-SPA算法相比，在譯碼性能基本沒有變化的情況下，避免了查表操作和非線性的對數運算，降低了算法的復雜度。與兩種修正的MS譯碼算法相比無需設置偏移參數和校正因子，更利于實際應用。

2 仿真結果

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

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

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

圖 2 規則 LDPC碼（504，3，6）的譯碼性能，迭代次數為 40

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

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

圖 3 規則 LDPC碼（6 000，3，6）的譯碼性能，迭代次數為 80

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

3 結論

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

參考文獻

[1]沈雪梅.下一代無線局域網中LDPC譯碼算法研究[J].科技通報，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].電子技術應用，2012，38（5）：122-124.

[4]李成福，盧選民，楊杰，等.基于LDPC碼和物理層網絡編碼的聯合信道編碼技術[J].微型機與應用，2013，32(17)：41-43.

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

[6]梁偉，劉亮，沈旭，等.采用動態量化的低存儲空間 LDPC譯碼研究[J].計算機工程與應用，2011，47(10)：106-109.

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

[8]陳旭燦，劉冬培.改進的 LPDC譯碼算法研究[J].電子科技大學學報，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]胡樹楷，王新梅.一種簡化的GF(q)-LDPC碼譯碼算法[J].西安電子科技大學學報，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.