一種改進(jìn)的LLR BP譯碼算法研究*

高 杰, 龍 華, 邵玉斌, 張 強(qiáng)

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

?

一種改進(jìn)的LLR BP譯碼算法研究*

高 杰, 龍 華, 邵玉斌, 張 強(qiáng)

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

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

LLR BP算法； 低密度奇偶校驗(yàn)碼； 泰勒級(jí)數(shù)； 分段線性近似

0 引 言

低密度奇偶校驗(yàn)(low density parity check,LDPC)碼具有結(jié)構(gòu)簡(jiǎn)單、在高斯信道下接近香農(nóng)限和超越主流Turbo碼的譯碼性能[1]，已成為當(dāng)今通信領(lǐng)域的研究熱點(diǎn)。

影響碼的編碼性能和發(fā)展(尤其是長(zhǎng)碼)最重要的一個(gè)因素是譯碼算法。當(dāng)今國(guó)內(nèi)外學(xué)者對(duì)降低LDPC碼譯碼算法復(fù)雜度和促進(jìn)LDPC碼的發(fā)展作出了大量貢獻(xiàn)，相繼提出了一些簡(jiǎn)化的譯碼算法[2,3]。LDPC碼的譯碼算法主要分為基于軟判決的置信迭代譯碼和基于硬判決的比特翻轉(zhuǎn)譯碼兩大類。基于軟判決譯碼，碼性能可逼近香農(nóng)限，譯碼性能較好，但實(shí)現(xiàn)復(fù)雜度高;基于硬判決譯碼，譯碼性能較差但實(shí)現(xiàn)復(fù)雜度低[4～6]。LLR BP是基于軟判決的置信迭代譯碼算法，譯碼性能好，但其運(yùn)算復(fù)雜限制了在實(shí)際中的應(yīng)用，因此，本文提出了一種改進(jìn)的LLR BP譯碼算法。

1 LLR BP譯碼算法

BP譯碼的核心思想是在變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)之間對(duì)信道接收的信息反復(fù)進(jìn)行迭代運(yùn)算譯碼，其涉及大量的乘法和加法運(yùn)算。LLR BP 譯碼算法是將BP譯碼算法中的運(yùn)算域變換到對(duì)數(shù)域中，將大量的乘法變換成加法運(yùn)算，大大減少了運(yùn)算量[7,8]。

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

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

1)信道初始化

信道傳遞給變量節(jié)點(diǎn)的信息概率的似然比為

(1)

2)迭代處理過(guò)程

雙曲正切函數(shù)

=p0-p1=1-2p1

(2)

校驗(yàn)節(jié)點(diǎn)消息處理

(3)

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

變量節(jié)點(diǎn)消息處理

(4)

譯碼判決,即變量節(jié)點(diǎn)利用收集到的所有信息進(jìn)行判決

(5)

3)停止

LLR BP 算法充分利用了信息節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)性質(zhì)以及接收序列的所有信息，從而可以得到逼近香農(nóng)極限的譯碼性能。但由于譯碼時(shí)迭代次數(shù)過(guò)多和每次循環(huán)時(shí)校驗(yàn)節(jié)點(diǎn)的計(jì)算復(fù)雜度高，導(dǎo)致譯碼復(fù)雜。

2 LLR BP譯碼算法優(yōu)化

提出采用泰勒級(jí)數(shù)對(duì)LLR BP 算法中運(yùn)算復(fù)雜的雅克比修正項(xiàng)進(jìn)行分段線性近似，對(duì)校驗(yàn)節(jié)點(diǎn)進(jìn)行更新。根據(jù)文獻(xiàn)[10]中的方法對(duì)式(3)中tanh(x)進(jìn)行變換處理得到

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)

校驗(yàn)節(jié)點(diǎn)傳遞的外部消息

(7)

式中M,N為獨(dú)立的二進(jìn)制隨機(jī)變量；L(M),L(N)為M和N的似然比；fi,bi分別為一組輔助的二進(jìn)制隨機(jī)變量；dc為L(zhǎng)DPC碼的檢驗(yàn)度；⊕為邏輯模運(yùn)算。

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

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

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

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

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

3 性能仿真

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

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

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

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

[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] 田 進(jìn)，王毓玲，馬正新.一種衛(wèi)星突發(fā)通信中抗相位模糊LDPC譯碼算法[J].傳感器與微系統(tǒng)，2012，31(12):140-142.

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

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

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

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

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

[8] 盧建波.硬判決LDPC 譯碼算法在衛(wèi)星導(dǎo)航中的應(yīng)用[J]. 無(wú)線電工程，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] 胡樹楷 ，王新梅.一種簡(jiǎn)化的GF(q)-LDPC碼譯碼算法[J].西安電子科技大學(xué)學(xué)報(bào) ，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云南省科技廳基金資助項(xiàng)目(2014RA051);2013云南省科技廳基金資助項(xiàng)目(2013FZ010)

TP 212

A

1000—9787(2017)07—0070—03

高 杰(1991-)，男，碩士研究生，主要研究方向?yàn)樾畔⑻幚?，E—mail:gaojie_swfu@163.com。

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