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

鄭娟毅 孫宇 張帆

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

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

中圖分類(lèi)號(hào)： TN911.22?34 ? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼： A ? ? ? ? ? ? ? ? ? ? ? ?文章編號(hào)： 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 ?引 ?言

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

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

1 ?LLR BP譯碼算法

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

通過(guò)將一個(gè)二值隨機(jī)變量[x]引入LLR BP譯碼，其對(duì)數(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） 似后驗(yàn)概率更新：[vl=v0l+m∈M（l）uml];

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

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

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

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

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

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

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

對(duì)二維[H（n，k）]的估計(jì)是固定[n]或[k]中的一個(gè)變量，這樣就可以先估計(jì)一維[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]來(lái)表示，即相鄰兩個(gè)接收信號(hào)的比值和對(duì)應(yīng)的發(fā)送信號(hào)的比值之差為[di=yi+1yi-xi+1xi]，[xi]是發(fā)送信號(hào)，[yi]是接收信號(hào)，推導(dǎo)得：

2.2 ?LLR BP譯碼改進(jìn)算法

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

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

3 ?仿真過(guò)程

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

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

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

圖3 ?改進(jìn)算法與LLR BP譯碼算法性能對(duì)比

3.2 ?結(jié)果分析

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

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

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

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

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

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

參考文獻(xiàn)

[1] 徐俊，許進(jìn)，胡留軍.一種應(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] 杜樂(lè)，鄭娟毅，李永，等.一種適用于高速移動(dòng)環(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] 洪銀芳，李暉，王新梅.一種改進(jìn)的Polar碼的BP譯碼算法[J].西安電子科技大學(xué)學(xué)報(bào)，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] 姚順銓?zhuān)芪鋾D.一種新穎的TS?LDPC譯碼算法[J].計(jì)算機(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].計(jì)算機(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.