一種改進的LLR BP譯碼算法研究*

高 杰, 龍 華, 邵玉斌, 張 強

(昆明理工大學 信息工程與自動化學院，云南 昆明 650500)

?

一種改進的LLR BP譯碼算法研究*

高 杰, 龍 華, 邵玉斌, 張 強

(昆明理工大學 信息工程與自動化學院，云南 昆明 650500)

運用LLR BP經典算法對低密度奇偶校驗 (LDPC) 碼譯碼時，由于譯碼時迭代次數過多和每次循環時校驗節點的計算復雜度過高，導致譯碼復雜度非常高。提出了一種改進型LLR BP譯碼算法，采用泰勒級數將LLR BP算法中復雜度高的雅克比修正項進行分段線性近似。仿真表明:該算法在譯碼性能損失不大的情況下可大幅降低 LDPC 碼的譯碼復雜度。

LLR BP算法； 低密度奇偶校驗碼； 泰勒級數； 分段線性近似

0 引 言

低密度奇偶校驗(low density parity check,LDPC)碼具有結構簡單、在高斯信道下接近香農限和超越主流Turbo碼的譯碼性能[1]，已成為當今通信領域的研究熱點。

影響碼的編碼性能和發展(尤其是長碼)最重要的一個因素是譯碼算法。當今國內外學者對降低LDPC碼譯碼算法復雜度和促進LDPC碼的發展作出了大量貢獻，相繼提出了一些簡化的譯碼算法[2,3]。LDPC碼的譯碼算法主要分為基于軟判決的置信迭代譯碼和基于硬判決的比特翻轉譯碼兩大類?；谲浥袥Q譯碼，碼性能可逼近香農限，譯碼性能較好，但實現復雜度高;基于硬判決譯碼，譯碼性能較差但實現復雜度低[4～6]。LLR BP是基于軟判決的置信迭代譯碼算法，譯碼性能好，但其運算復雜限制了在實際中的應用，因此，本文提出了一種改進的LLR BP譯碼算法。

1 LLR BP譯碼算法

BP譯碼的核心思想是在變量節點和校驗節點之間對信道接收的信息反復進行迭代運算譯碼，其涉及大量的乘法和加法運算。LLR BP 譯碼算法是將BP譯碼算法中的運算域變換到對數域中，將大量的乘法變換成加法運算，大大減少了運算量[7,8]。

簡單起見，定義如下參數:編碼后的信息碼元c=(c1,c2,…,cn)；接收的碼元y=(y1,y2,…,yn)；變量節點i傳遞給校驗節點j的信息qij(b),b=0,1；變量節點i接收到校驗節點j傳遞的信息為rji(b),b=0,1；與變量節點i相連的校驗節點j的集合C(j)；與校驗節點j相連的變量節點i的集合R(j)。

LLR BP算法的譯碼基本步驟如下[9]:

1)信道初始化

信道傳遞給變量節點的信息概率的似然比為

(1)

2)迭代處理過程

雙曲正切函數

=p0-p1=1-2p1

(2)

校驗節點消息處理

(3)

式中 ?i′j=sign(L(Pi)),βi′j=|L(Pi)|

變量節點消息處理

(4)

譯碼判決,即變量節點利用收集到的所有信息進行判決

(5)

3)停止

LLR BP 算法充分利用了信息節點和校驗節點性質以及接收序列的所有信息，從而可以得到逼近香農極限的譯碼性能。但由于譯碼時迭代次數過多和每次循環時校驗節點的計算復雜度高，導致譯碼復雜。

2 LLR BP譯碼算法優化

提出采用泰勒級數對LLR BP 算法中運算復雜的雅克比修正項進行分段線性近似，對校驗節點進行更新。根據文獻[10]中的方法對式(3)中tanh(x)進行變換處理得到

L(M⊕N)=sign(L(M))sign(L(N))min(|L(M)|, |L(N)|)+log(1+exp(-|L(M)+L(N)|))- log(1+exp(-|L(M)-L(N)|))

(6)

校驗節點傳遞的外部消息

(7)

式中M,N為獨立的二進制隨機變量；L(M),L(N)為M和N的似然比；fi,bi分別為一組輔助的二進制隨機變量；dc為LDPC碼的檢驗度；⊕為邏輯模運算。

分別對fi,bi利用傳送的碼元x={x1,x2,…,xn}和式(6)進行遞歸操作，得到L(fi)和L(bi)；通過(xn1⊕xn2⊕…⊕xnd)=0得到xni=(fi-1⊕bi+1)，i∈{2,3,…，dc-1}；利用前后向的遞歸運算來完成校驗節點更新。

本文提出的線性分段近似算法:用函數I(x)=log(1+e-|x|)表示式(6)的修正項，以函數I(x)的切點x0對曲線I(x)在泰勒級數近似的基礎上進行線性分段近似，分段步長為0.85，具體如表1所示。

表1 曲線I(x)=log(1+e-|x|)分段近似函數

文獻[11]使用泰勒級數中的修正項進行修正，該文獻中泰勒級數近似于原曲線的最大誤差為30.586 9，而本文提出的線性分段近似于原曲線的最大誤差只有0.128 1，有效降低了譯碼時產生的誤碼率。

提出的線性分段近似譯碼算法與經典的LLR BP算法相比，將曲線近似分段成直線，避免了非線性的對數運算，降低了運算復雜度，其譯碼性能與LLR BP 譯碼算法基本一致，且更利于實際應用中的操作。

3 性能仿真

使用Matlab進行仿真驗證。仿真中信道采用AWGN信道，調制方式為BPSK，LDPC碼元分別為(5 00,3,6)和(5000,3,6)，碼率為1/2，迭代次數分別設為40次和80次。仿真結果如圖1所示。由圖1、圖2可知，無論是在長碼還是短碼的情況下，在低信噪比小于1.0 dB條件下，LLR BP和優化的LLR BP算法譯碼性能幾乎一樣，當誤碼比特率為10-2時本文提出的優化算法要優于經典LLR BP算法。

圖1 2種迭代次數下(5 000,3,6)LDPC譯碼性能

4 結束語

與LLR BP 譯碼算法相比，采用泰勒級數對LLR BP 算法中復雜度高的雅克必修正項進行分段線性近似，避免了查表操作和復雜的非線性對數函數的計算。在沒有改變譯碼性能的前提下，大大降低了譯碼運算復雜度。

[1] Wang Kaiyao，Xiao Yang，Kim K.Construction of time frequency codes based on protograph LDPC codes in OFDM communication systems[J].Journal of Systems Engineering and Electronics，2012，23 (3):335-341.

[2] 田 進，王毓玲，馬正新.一種衛星突發通信中抗相位模糊LDPC譯碼算法[J].傳感器與微系統，2012，31(12):140-142.

[3] 陳允鋒，董繼剛.LDPC碼在基于FH-FSK的AUV水聲通信系統中的應用[J].傳感器與微系統，2015，34(12):156-160.

[4] 沈雪梅.下一代無線局域網中LDPC譯碼算法研究[J].科技通報,2013，29(2):127-129.

[5] 喬曉峰，劉躍敏，寧永海.RS碼與QC-LDPC碼的級聯碼在淺海信道中的性能研究[J].電子技術應用，2012，38(5):122-124.

[6] 楊志良，李晉華.LDPC編碼在無線傳感器網絡中的應用[J].傳感器與微系統，2013，32(10):139-141.

[7] 袁東風，張海剛.LDPC碼理論與應用[J].北京:人民郵電出版社，2008.

[8] 盧建波.硬判決LDPC 譯碼算法在衛星導航中的應用[J]. 無線電工程，2012，42(9):38-40,64

[9] Kschischangf R J，Loeligerh A.Factor graphs and the sum-product algorithm[J].IEEE Transaction on Information Theory，2009，47(2):498-519 .

[10] 胡樹楷 ，王新梅.一種簡化的GF(q)-LDPC碼譯碼算法[J].西安電子科技大學學報 ，2011，38(2):8-12.

[11] Chen Jinghu，Dholakia A，Eleftheriou E，et al.Reduced-complexity decoding of LDPC codes[J].IEEE Transaction on Communications，2005，53(8):1288-1299.

Research on improved LLR BP decoding algorithm*

GAO Jie, LONG Hua, SHAO Yu-bin, ZHANG Qiang

(Faculty of Information Engineering and Automation，Kunming University of Science and Technology，Kunming 650500，China)

When classical log likelihood rate belief propagation(LLR BP)is applied to decode low density parity check(LDPC) code, it becomes very complex because of excessive number of iterations and high computation check complexity of parity check nodes at each iteration. To solve this problem, a modified LLR BP decoding algorithm is proposed, which approximating the highly complex Jacobi correction term in LLR BP algorithm segmentally and linearly by Taylor series.Simulation shows that it becomes less complex than LDPC decoding in case of not too much loss of decoding performance.

log likelihood rate belief propagation(LLR BP)algorithm;low density parity check(LDPC) code;Taylor series;piece wise linear approximation

10.13873/J.1000—9787(2017)07—0070—03

2016—06—21

2014云南省科技廳基金資助項目(2014RA051);2013云南省科技廳基金資助項目(2013FZ010)

TP 212

A

1000—9787(2017)07—0070—03

高 杰(1991-)，男，碩士研究生，主要研究方向為信息處理，E—mail:gaojie_swfu@163.com。

龍 華(1963-)，女，通訊作者，教授，碩士生導師，主要從事信息處理方向研究工作，E—mail:1228627124@qq.com。