對數(shù)似然比置信傳播算法的改進

鄭娟毅 孫宇 張帆

摘 ?要： 改進對數(shù)似然比置信傳播（LLR BP）算法，以提高其對低密度奇偶校驗（LDPC）碼的譯碼性能。在變量節(jié)點間加入信道響應(yīng)相關(guān)性，并在算法中預(yù)設(shè)迭代次數(shù)，以使變量節(jié)點間傳遞的外部信息達到平衡，降低外部信息震蕩現(xiàn)象，并保障譯碼不會因所需迭代次數(shù)過大而終止。改進型LLR BP算法可降低誤碼率，并在信噪比（SNR）較小時降低譯碼迭代次數(shù)。

關(guān)鍵詞： 對數(shù)似然比; 響應(yīng)相關(guān)性; 信息震蕩; 迭代預(yù)設(shè); 譯碼性能; 改進型LLR BP算法

中圖分類號： TN911.22?34 ? ? ? ? ? ? ? ? ? ? ? ?文獻標(biāo)識碼： A ? ? ? ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2019）15?0005?03

Improvement of log?likelihood ratio belief propagation algorithm

ZHENG Juanyi， SUN Yu， ZHANG Fan

（School of Communications and Information Engineering， Xian University of Posts and Telecommunications， Xian 710121， China）

Abstract： Log?likelihood ratio belief propagation （LLR BP） algorithm is improved to enhance its decoding performance for low density parity check （LDPC） codes. The channel response correlation is added between variable nodes and the number of iterations is preset in the algorithm to balance the external information transmitted between the variable nodes， reduce the external information oscillation phenomenon， and ensure that the decoding is not terminated while the required number of iterations is too large. The improved algorithm can reduce the bit error rate and decrease the number of decoding iterations when the signal noise ratio is small.

Keywords： log?likelihood ratio; response correlation; information oscillation; iteration preset， decoding performance; improved LLR BP algorithm

0 ?引 ?言

隨著人們對高速率通信不斷追求，第五代（Fifth Generation，5G）移動通信技術(shù)將對人們的生活、學(xué)習(xí)、工作帶來更多的便捷和改變，到目前已確定低密度奇偶校驗（Low Density Parity Check，LDPC）碼是5G采用的信道編碼技術(shù)之一。LDPC碼作為5G信道編碼標(biāo)準(zhǔn)熱門候選技術(shù)之一[1]，對提高LDPC碼譯碼性能顯得尤為重要。

通常所采用對數(shù)似然比置信傳播（Log?likelihood Ratio Belief Propagation，LLR BP）算法對LDPC進行譯碼，相較于原始的置信傳播（Belief Propagation，BP）算法，LLR BP算法由累乘轉(zhuǎn)變?yōu)槔奂樱蟠蠼档土俗g碼復(fù)雜度。但在譯碼性能上還需要進一步的提升，改進的LLR BP譯碼算法是在LLR BP算法[2]基礎(chǔ)上加入響應(yīng)相關(guān)性并在算法中預(yù)設(shè)迭代次數(shù)，使得LLR BP算法得到進一步改進。

1 ?LLR BP譯碼算法

LLR BP與BP譯碼算法思想一致，LLR BP采用對數(shù)似然比描述BP算法。這樣就把乘法運算轉(zhuǎn)變成加法運算，LLR BP算法的優(yōu)點在于極大地減少運算量，使得譯碼復(fù)雜度得到了很大的降低。

通過將一個二值隨機變量[x]引入LLR BP譯碼，其對數(shù)似然比[L（x）]定義為：

推導(dǎo)得完整的LLR BP算法步驟[2?3]如下：

1） 初始化：[vml=v0l];

2） [sm]更新：[uml=2arctanl∈L（m）＼ltanhvml2];

3） [x1]更新：[vml=v0l+m∈M（l）uml];

4） 似后驗概率更新：[vl=v0l+m∈M（l）uml];

5） 比特判決：如果[vl>0]，則[xl=0]，否則，[xl=1（l=1，2，…，N）]。如果[HTx=0]或者迭代次數(shù)達到最大，則迭代終止，把[x]作為譯碼輸出，否則轉(zhuǎn)到步驟2）繼續(xù)迭代。

LLR BP譯碼算法的基本譯碼步驟如圖1所示。

圖1 ?LLR BP譯碼算法流程圖

2 ?基于相關(guān)性的LLR BP譯碼算法

2.1 ?相關(guān)性的介紹

[Xn，k]是經(jīng)過編碼后的發(fā)送信號，[Yn，k]是接收信號，[Nn，k]是均值為0，方差為[σ2]的高斯噪聲，[H（n，k）]是編碼的信道響應(yīng)，[Yn，k]在頻域內(nèi)可以表示為：

[H（n，k）]會因[n]和[k]的變化而產(chǎn)生變化，當(dāng)[n]變?yōu)閇n+1]，或[k]變成[k+1]時，[H（n，k）]與[H（n+1，k）]，[H（n，k+1）]，[H（n+1，k+1）]之間存在一些相關(guān)性，在LLR BP譯碼算法里加入這些相關(guān)性可以降低變量節(jié)點外部信息震蕩現(xiàn)象，譯碼就會更加準(zhǔn)確。這種相關(guān)性同樣在5G中也有可能得到應(yīng)用[4]。

對二維[H（n，k）]的估計是固定[n]或[k]中的一個變量，這樣就可以先估計一維[H（i）]。[H（n，k）]隨[n]或[k]的變化而變化，但[H（n，k+1）]與[H（n，k）]是緊密聯(lián)系著的。若[H（i）]位于頻率方向，即[k]為下標(biāo)，那么[H（n，k+1）]與[H（n，k）]總是近似。將相關(guān)性用[di]來表示，即相鄰兩個接收信號的比值和對應(yīng)的發(fā)送信號的比值之差為[di=yi+1yi-xi+1xi]，[xi]是發(fā)送信號，[yi]是接收信號，推導(dǎo)得：

2.2 ?LLR BP譯碼改進算法

在譯碼前需要計算出小于給定的差錯率[Ps（10-2）]的出錯次數(shù)，記作[DM]，由[DM]來給定[de]的值。每個待翻轉(zhuǎn)比特與其前后比特做對比，得出[di]值，若該比特的兩個[di]值都大于[de]（即發(fā)生兩次連續(xù)的跨越）[5]，則譯碼出錯，要對該比特進行翻轉(zhuǎn)。這樣就可以對不穩(wěn)定的比特進行翻轉(zhuǎn)，同時在已翻轉(zhuǎn)比特中再進行比較，如果再次出現(xiàn)跨越，則需要繼續(xù)進行比特翻轉(zhuǎn)，這樣可以使得所有比特都滿足條件。在這個改進的LLR BP譯碼迭代中[6]，軟信息在[sm]和[xl]間不斷地來回傳遞，最后得到正確的譯碼結(jié)果，操作流程見圖2。與LLR BP譯碼算法相比，計算過程中只增加了對加入的響應(yīng)相關(guān)性的計算，但通過增加相關(guān)性，就可以降低誤碼率和迭代次數(shù)，加快算法的收斂速度[7]。

圖2中預(yù)設(shè)迭代次數(shù)需要設(shè)置的盡可能大。通過提前測出不能被正確譯出的碼字，并將其進行翻轉(zhuǎn)[8]，這樣可以使得得出正確譯碼的概率增大。

3 ?仿真過程

3.1 ?參數(shù)設(shè)置

設(shè)校驗因子為1，在允許迭代譯碼輸出錯誤的條件下，進行8次連續(xù)迭代譯碼得到8個碼字，與誤碼比特相比，輸出碼字的比特個數(shù)小于等于1，則連續(xù)譯碼次數(shù)為8次。仿真過程中，二進制LDPC碼，其碼長取值為504，碼率為1/2，最大迭代次數(shù)設(shè)為30次，信噪比（Signal Noise Ratio，SNR）區(qū)間設(shè)為[-1.5，1.5] dB，步長[9]為0.5 dB。 采用Matlab對該算法進行仿真，并采用二進制相移鍵控進行調(diào)制，得到加入相關(guān)性改進后的譯碼算法和原始LLR BP譯碼算法的仿真對比圖，如圖3所示。

圖2 ?加入相關(guān)性的LLR BP譯碼算法

圖3 ?改進算法與LLR BP譯碼算法性能對比

3.2 ?結(jié)果分析

根據(jù)圖3可以看出，基于相關(guān)性的LLR BP譯碼算法相較于LLR BP譯碼，相同信噪比下其誤碼率顯著降低。

預(yù)設(shè)迭代次數(shù)是8次，當(dāng)?shù)螖?shù)大于8次時，系統(tǒng)會自動進入跨越，此時需要計算當(dāng)前信噪比系統(tǒng)中的誤碼率來判斷是否繼續(xù)進行迭代，如果誤碼率小于[Ps]，則迭代終止。因此基于相關(guān)性的LLR BP譯碼算法中預(yù)設(shè)迭代次數(shù)是很重要的一個步驟[11]。通過仿真可以看出，基于相關(guān)性的LLR BP譯碼算法在只增加了響應(yīng)相關(guān)性微小的計算量的情況下，在信噪比相同的條件下，大大降低迭代次數(shù)，并且降低誤碼率，使得譯碼性能有顯著提升。

根據(jù)表1中兩種譯碼算法的對比可以看出，當(dāng)信噪比小于1.5 dB時，基于相關(guān)性的LLR BP譯碼算法可以很大地減小譯碼迭代的次數(shù);當(dāng)信噪比大于1.5 dB時，基于相關(guān)性的LLR BP譯碼算法迭代次數(shù)接近LLR BP算法迭代次數(shù)，這是因為在信噪比的值較高時不是依據(jù)檢驗因子是否處于穩(wěn)定狀態(tài)來確定輸出結(jié)果是否正確[3，10]。

表1 ?兩種譯碼算法的迭代次數(shù)對比

4 ?結(jié) ?語

通過Matlab對基于相關(guān)性的LLR BP譯碼算法和傳統(tǒng)LLR BP算法同時進行仿真，得出兩種譯碼的對比圖。由對比圖很容易看出，與原始LLR BP譯碼算法相比，加入響應(yīng)相關(guān)性的LLR BP譯碼算法在相同信噪比的條件下，迭代次數(shù)和誤碼率都有很大的降低，提高了譯碼效率。

參考文獻

[1] 徐俊，許進，胡留軍.一種應(yīng)用于5G基于LDPC碼的物理層包編碼[J].中興通訊技術(shù)，2016（3）：26?30.

XU Jun， XU Jin， HU Liujun. A physical layer packet coding based on LDPC codes for 5G [J]. ZTE communication technology， 2016（3）： 26?30.

[2] 賀鶴云.LDPC碼基礎(chǔ)與應(yīng)用[M].北京：人民郵電出版社，2009.

HE Heyun. Basis and application of LDPC code [M]. Beijing： Posts and Telecom Press， 2009.

[3] 杜樂，鄭娟毅，李永，等.一種適用于高速移動環(huán)境的LDPC譯碼算法[J].光通信研究，2017，43（4）：66?69.

DU Le， ZHENG Juanyi， LI Yong. A LDPC Decoding algorithm for the mobile environment of high speed [J]. Study on optical communications， 2017， 43（4）： 66?69.

[4] 洪銀芳，李暉，王新梅.一種改進的Polar碼的BP譯碼算法[J].西安電子科技大學(xué)學(xué)報，2016，43（4）：39?44.

HONG Yinfang， LI Hui， WANG Xinmei. Improved BP deco?ding algorithm for Polar codes [J]. Journal of Xidian University， 2016， 43（4）： 39?44.

[5] 姚順銓，周武旸.一種新穎的TS?LDPC譯碼算法[J].計算機仿真，2008（4）：133?137.

YAO Shunquan， ZHOU Wuyang. A new decoding algorithm for TS?LDPC [J]. Computer simulation， 2008（4）： 133?137.

[6] CHEN P， CAI K， ZHENG S. Rate?adaptive protograph LDPC codes for Multi?Level?Cell （MLC） NAND FLASH memory [J]. IEEE communications letters， 2018， 22（6）： 1112?1115.

[7] SUN Z Y， LI H H. Improvement of LDPC codes decoding algorithm in the application of the rotational OFDM system [J]. Advanced materials research， 2014， 3190（934）： 111?118.

[8] YUAN J， LIU F， YE W， et al. A new coding scheme of QC?LDPC codes for optical transmission systems [J]. Optik?international journal for light and electron optics， 2014， 125（3）： 1016?1019.

[9] COTRONEI M， LAZZARO D， MONTEFUSCO L B， et al. Image compression through embedded multiwavelet transform co?ding [J]. IEEE transactions on image processing， 2000，9（2）：184?189.

[10] LI T， HUANG Q， WANG Z L， et al. Low?complexity enco?ding of binary quasi?cyclic codes based on Galois Fourier transform [C]// IEEE International Symposium on Information Theory. Istanbul： IEEE， 2013： 131?135.

[11] SONG H， CRUZ J R. Reduced?complexity decoding of Q?ary LDPC codes for magnetic recording [J]. IEEE transactions on magnetics， 2003， 39（2）： 1081?1087.

[12] 方承志，鞏雪艷，劉潔.OFDM系統(tǒng)中基于響應(yīng)相關(guān)性LDPC譯碼研究[J].計算機技術(shù)與發(fā)展，2016，26（8）：75?78.

FANG Chengzhi， GONG Xueyan， LIU Jie. Research on LDPC decoding based on response correlation in OFDM system [J]. Computer technology and development， 2016， 26（8）： 75?78.