《電子技術(shù)應(yīng)用》
您所在的位置：首頁(yè) > 通信與網(wǎng)絡(luò) > 設(shè)計(jì)應(yīng)用 > LDPC碼節(jié)點(diǎn)剩余度置信傳播譯碼改進(jìn)
LDPC碼節(jié)點(diǎn)剩余度置信傳播譯碼改進(jìn)
2017年電子技術(shù)應(yīng)用第11期
周 華1，2，3，翁少輝1，3，馮 姣1，3
1.南京信息工程大學(xué)，江蘇 南京210044；2.江蘇省大氣環(huán)境與裝備技術(shù)協(xié)同創(chuàng)新中心，江蘇 南京210044； 3.江蘇省氣象探測(cè)與信息處理重點(diǎn)實(shí)驗(yàn)室，江蘇 南京210044
摘要： 低密度奇偶校驗(yàn)（LDPC）碼的剩余度置信傳播（RBP）和基于校驗(yàn)節(jié)點(diǎn)的剩余度置信傳播（NWRBP）譯碼算法是根據(jù)剩余度值的有序度量，動(dòng)態(tài)選擇最大剩余度值所在的邊或校驗(yàn)節(jié)點(diǎn)，對(duì)其依次進(jìn)行更新。對(duì)比依次同步更新所有校驗(yàn)節(jié)點(diǎn)和變量節(jié)點(diǎn)的flooding算法，NWRBP算法的收斂速度和譯碼性能有了很大的提高?；贜WRBP算法，提出一種改進(jìn)型NWRBP（ENWRBP）算法，即統(tǒng)計(jì)NWRBP譯碼過(guò)程中各變量節(jié)點(diǎn)的更新次數(shù)。如果NWRBP迭代譯碼失敗，則將更新次數(shù)最少的變量節(jié)點(diǎn)的初始化值設(shè)置為0，重新譯碼。仿真結(jié)果表明，與NWRBP相比，ENWRBP譯碼算法降低了誤碼率和誤幀率。
中圖分類號(hào)： TN92
文獻(xiàn)標(biāo)識(shí)碼： A
DOI：10.16157/j.issn.0258-7998.170678
中文引用格式： 周華，翁少輝，馮姣. LDPC碼節(jié)點(diǎn)剩余度置信傳播譯碼改進(jìn)[J].電子技術(shù)應(yīng)用，2017，43(11)：107-111.
英文引用格式： Zhou Hua，Weng Shaohui，F(xiàn)eng Jiao. Enhanced node-wise residual belief propagation for LDPC codes[J].Applica-
tion of Electronic Technique，2017，43(11)：107-111.
Enhanced node-wise residual belief propagation for LDPC codes
Zhou Hua1，2，3，Weng Shaohui1，3，F(xiàn)eng Jiao1，3
1.Nanjing University of Information Science and Technology，Nanjing 210044，China； 2.Jiangsu Collaborative Innovation Center on Atmospheric Environment and Equipment Technology，Nanjing 210044，China； 3.Jiangsu Key Laboratory of Meteorological Observation and Information Processing，Nanjing 210044，China
Abstract： Residual belief-propagation(RBP) and Node-wise residual belief-propagation(NWRBP) decoding algorithm based on low-density parity-check(LDPC) codes dynamically select the edge or check node where the maximum residual value is located to update, according to the order of the residual metric. Compared with the flooding algorithm of which simultaneously update all the check nodes and variable nodes in turn, the convergence speed and decoding performance of NWRBP algorithm have been greatly improved. Based on NWRBP algorithm, this paper presents an enhanced NWRBP（ENWRBP）algorithm, which counts the number of updates for each variable node during the NWRBP decoding process. If the decoding fails, it will set the initialized LLR value of the variable node with the least number of updates to zero and restart the decoding. Simulation results show that compared with NWRBP, ENWRBP improves the decoding performance with lower the bit error rate and frame error rate.
Key words : low density parity check code；belief-propagation；residual degree；iterative decoding

0 引言

    碼率為R=(N-M)/N的低密度奇偶校驗(yàn)(Low-Density Parity-Check，LDPC)碼是一種線性分組碼[1-2]。LDPC碼因其優(yōu)異的譯碼性能，已經(jīng)受到了越來(lái)越多的關(guān)注，并且日前在深空通信、光纖通信、衛(wèi)星數(shù)字視頻、音頻廣播等領(lǐng)域已經(jīng)得到了廣泛的應(yīng)用[3]。

    LDPC碼的傳統(tǒng)迭代譯碼算法flooding[4-6]，又稱為兩相的消息傳遞，是最簡(jiǎn)單的譯碼方式。flooding算法這種在一次迭代中順序更新所有節(jié)點(diǎn)的方式，導(dǎo)致其譯碼的收斂速度較慢，并且需要大量的迭代次數(shù)才能達(dá)到想要的譯碼效果。為了減少迭代的次數(shù)和收斂速度, 時(shí)序置信傳播譯碼算法[7-8]（Belief-Propagation，BP）被提出。在時(shí)序譯碼算法中，假設(shè)校驗(yàn)節(jié)點(diǎn)被分成p個(gè)子集，在一次迭代過(guò)程中，第一個(gè)子集中從變量節(jié)點(diǎn)到校驗(yàn)節(jié)點(diǎn)的信息被更新，然后從校驗(yàn)節(jié)點(diǎn)到相鄰的變量節(jié)點(diǎn)的信息要被更新并傳播，同樣其他p-1個(gè)校驗(yàn)節(jié)點(diǎn)的子集也同時(shí)相應(yīng)地被更新。很明顯，一次迭代過(guò)程也涉及到所有變量節(jié)點(diǎn)以及所有的校驗(yàn)節(jié)點(diǎn)的子集，因此，每次譯碼迭代，時(shí)序譯碼算法的計(jì)算復(fù)雜度和傳統(tǒng)flooding相同，但是其收斂速度對(duì)比f(wàn)looding算法，要快過(guò)兩倍。盡管置信傳播算法有很好的譯碼性能，但為了進(jìn)一步提高譯碼性能，其不是最好的選擇，最終，Casado等人將剩余度概念運(yùn)用到了置信傳播[9-10]，并提出了兩種時(shí)序算法：基于剩余度置信(Residual Belief Propagation，RBP)傳播譯碼算法、基于校驗(yàn)節(jié)點(diǎn)的剩余度置信傳播(Node-Wise RBP，NWRBP)譯碼算法[11-12]。

    RBP算法和NWRBP算法這種迭代機(jī)制會(huì)導(dǎo)致有的變量節(jié)點(diǎn)很少有機(jī)會(huì)去將它們本身的消息傳播到整個(gè)譯碼過(guò)程中，所以，其譯碼算法不會(huì)達(dá)到最好的譯碼效果。為了減少這種情況帶來(lái)的誤差，本文提出了一種改進(jìn)型NWRBP(Enhanced NWRBP，ENWRBP)算法，在迭代譯碼過(guò)程中，如果NWRBP算法譯碼沒(méi)有成功，則依次將更新最少次數(shù)的變量節(jié)點(diǎn)的初始化對(duì)比似然數(shù)值(Log-Likelihood Radio，LLR)設(shè)置為0，并重新譯碼，直到譯碼正確或達(dá)到最大測(cè)試次數(shù)。本算法最多測(cè)試T個(gè)變量節(jié)點(diǎn)。該算法改變了校驗(yàn)節(jié)點(diǎn)的更新順序，均衡了變量節(jié)點(diǎn)的更新次數(shù)，從而提高了LDPC碼的譯碼性能。

1 LDPC碼的RBP和NWRBP譯碼算法

    對(duì)于規(guī)則(N，J，K)LDPC碼，N表示碼長(zhǎng)，J和K分別表示校驗(yàn)矩陣H行和列的重量。LDPC碼可以用Tanner圖表示。Tanner圖由變量節(jié)點(diǎn)、校驗(yàn)節(jié)點(diǎn)以及連接變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)的邊組成。變量節(jié)點(diǎn)ci對(duì)應(yīng)矩陣H中的第i列，校驗(yàn)節(jié)點(diǎn)vj對(duì)應(yīng)矩陣H中的第j行。如果hij=1，表明Tanner圖中節(jié)點(diǎn)vj和ci由一條邊相連，否則不相連。圖1所示為規(guī)則(6，2，3)LDPC碼的Tanner圖，校驗(yàn)節(jié)點(diǎn)和變量節(jié)點(diǎn)分別用方框和圓表示。每個(gè)節(jié)點(diǎn)連接的邊的個(gè)數(shù)稱之為該節(jié)點(diǎn)的度，圖1所示LDPC碼的校驗(yàn)節(jié)點(diǎn)和變量節(jié)點(diǎn)的度分別為3和2[13]。

tx6-t1.gif

tx6-gs1.gif

其中，ni是服從均值為0、方差為δ2的高斯白噪聲(表示為ni～N(0，δ2))，且它們之間相互獨(dú)立。Eb/No表示信噪比(Signal-to-Noise Ratio，SNR)，Eb表示發(fā)送前每個(gè)信息比特的能量，No表示發(fā)送前噪聲功率譜密度以及δ2=No/2。在開(kāi)始進(jìn)行譯碼前，對(duì)于通過(guò)一個(gè)BPSK AWGN信道的碼字，最終接收序列的每個(gè)碼字的先驗(yàn)概率的對(duì)數(shù)似然比(LLR)初始化為：

tx6-gs2-4.gif

    式(3)和式(4)描述了譯碼過(guò)程中LDPC碼變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)之間的消息更新和傳遞規(guī)律。RBP和NWRBP算法是將剩余度值作為度量去調(diào)整更新順序的兩種主要算法機(jī)制。剩余度是消息更新之前和之后差值的絕對(duì)值。在LDPC譯碼中，剩余度值的定義值為：  

tx6-gs5.gif

    作為RBP的擴(kuò)展和延伸，RBP算法和NWRBP算法兩者的區(qū)別是：RBP動(dòng)態(tài)選擇最大剩余度所在的邊進(jìn)行更新，而NWRBP動(dòng)態(tài)選擇最大剩余度所在的校驗(yàn)節(jié)點(diǎn)進(jìn)行更新。NWRBP詳細(xì)步驟見(jiàn)算法1。

    算法1：LDPC碼的NWRBP算法譯碼流程

tx6-sf1.gif

2 ENWRBP算法機(jī)制描述

    由于RBP譯碼算法和NWRBP譯碼算法每次通過(guò)一條邊或是一個(gè)校驗(yàn)節(jié)點(diǎn)去更新傳播消息，這樣會(huì)形成一個(gè)個(gè)相對(duì)獨(dú)立彼此沒(méi)有影響的子集合，經(jīng)過(guò)數(shù)次迭代后，可能就會(huì)導(dǎo)致忽略掉已經(jīng)被正確修改的錯(cuò)誤比特節(jié)點(diǎn)，再一次出現(xiàn)錯(cuò)誤，所以，RBP算法和NWRBP算法都具有一定的貪婪性。而NWRBP譯碼算法根據(jù)節(jié)點(diǎn)更新消息，每個(gè)子集合范圍較大，其貪婪性相對(duì)較弱。因此，經(jīng)過(guò)大量的迭代譯碼后，NWRBP算法的譯碼性能會(huì)優(yōu)于RBP算法譯碼性能。然而，這兩種算法的性能受限于陷井集(trapping sets)的影響，導(dǎo)致一些錯(cuò)誤的變量節(jié)點(diǎn)(即誤碼)在迭代多次后很難被發(fā)現(xiàn)。經(jīng)研究發(fā)現(xiàn)，NWRBP在譯碼過(guò)程中，節(jié)點(diǎn)更新的次數(shù)并不均衡，存在某些節(jié)點(diǎn)更新次數(shù)少的現(xiàn)象，而相對(duì)于更新次數(shù)較多的變量節(jié)點(diǎn)，更新次數(shù)較少的變量節(jié)點(diǎn)不能為相鄰節(jié)點(diǎn)提供足夠的有用信息，亦或該節(jié)點(diǎn)無(wú)法從相鄰節(jié)點(diǎn)獲得有用信息，導(dǎo)致相鄰節(jié)點(diǎn)或其本身發(fā)生錯(cuò)誤的概率更大。本文正是利用此思想來(lái)減少帶來(lái)的誤差，在NWRBP譯碼算法的基礎(chǔ)上提出一種改進(jìn)算法Enhanced NWRBP(ENWRBP)。在NWRBP譯碼算法的一次譯碼過(guò)程中，如果達(dá)到最大的迭代次數(shù)仍然不滿足譯碼成功條件，那么就尋找到在迭代過(guò)程中更新最少次數(shù)的變量節(jié)點(diǎn)vmin，并且將最初經(jīng)高斯白噪聲信道接收到的序列對(duì)應(yīng)的初始對(duì)數(shù)似然數(shù)rmin設(shè)置為0。隨后，重新用NWRBP進(jìn)行譯碼，直到譯碼成功或連續(xù)重復(fù)T上述過(guò)程，即更新T次最少的變量節(jié)點(diǎn)。ENWRBP算法過(guò)程描述如圖2，詳細(xì)步驟見(jiàn)算法2。

tx6-t2.gif

    算法2：LDPC碼的ENWRBP算法譯碼流程

tx6-sf2.gif

tx6-sf2-x1.gif

3 仿真結(jié)果與討論

    本文中所有的仿真都是在二進(jìn)制輸入加性高斯白噪聲(BI-AWGN)信道進(jìn)行的。譯碼方式采用基于剩余度置信傳播(RBP)算法、基于校驗(yàn)節(jié)點(diǎn)的剩余度置信傳播(NWRBP)算法,以及本文提出的基于校驗(yàn)節(jié)點(diǎn)的改進(jìn)剩余度置信傳播(ENERBP)算法，最大迭代次數(shù)設(shè)為100，調(diào)制方式為BPSK，具體的仿真結(jié)果如圖3~圖6所示。

tx6-t3.gif

tx6-t4.gif

tx6-t5.gif

tx6-t6.gif

    圖3和圖4中T=10時(shí)，可以觀察到ENWRBP算法的譯碼性能要好于NWRBP和RBP算法。在SNR值較低時(shí)，圖3中SNR值為2.5～3 dB，圖4中為2.5～2.7 dB，誤碼率BER和誤幀率FER的曲線三者大致相同。隨著SNR值的增加，ENWRBP算法和NWRBP算法的譯碼曲線逐漸優(yōu)于RBP算法，圖3中NWRBP算法和ENWRBP算法依然大致相同，直到SNR值為4.0 dB時(shí)，ENWRBP算法開(kāi)始優(yōu)于NWRBP算法，圖4中ENWRBP算法在所示SNR范圍內(nèi)始終優(yōu)于RBP算法和NWRBP算法，并且這種優(yōu)勢(shì)隨著SNR值增大而逐漸擴(kuò)大。例如：如圖4所示，在FER=2×10-4時(shí)，相比RBP和NWRBP，ENWRBP的FER分別得到0.3 dB和0.18 dB的譯碼增益；同樣，在BER=2×10-5時(shí)，相比RBP和NWRBP，ENWRBP的BER分別得到0.28 dB和0.16 dB的譯碼增益。

    通過(guò)圖5和圖6 ENWRBP譯碼性能的比較，可以觀察到，T=10時(shí)的曲線要低于T=5時(shí)的曲線，并且這種趨勢(shì)隨著SNR值的增大而增大。例如：如圖6所示，在FER=1×10-4時(shí)，相比T=5，T=10得到0.8 dB的譯碼增益；同樣，在BER=1×10-5時(shí)，相比T=5，T=10得到1.2 dB的譯碼增益。由此可見(jiàn)，通過(guò)增大變量節(jié)點(diǎn)初始LLR值置0嘗試次數(shù)，可進(jìn)一步提高ENWRBP譯碼性能。

4 結(jié)論

    本文在NWRBP算法的基礎(chǔ)上介紹了一種增強(qiáng)譯碼算法ENWRBP(Enhanced NWRBP)。相比較NWRBP算法，該算法的譯碼性能優(yōu)于NWRBP，特別是SNR值稍大時(shí)尤為明顯。仿真表明，NWRBP在每次迭代過(guò)程中，更新次數(shù)少的變量節(jié)點(diǎn)，其本身或相鄰節(jié)點(diǎn)發(fā)生誤碼的概率高于其他的變量節(jié)點(diǎn)。ENWRBP譯碼算法針對(duì)這一點(diǎn)，多次找到更新次數(shù)最少的變量節(jié)點(diǎn)，然后對(duì)該節(jié)點(diǎn)的初始化值置0，并重新譯碼，從而提高了NWRBP算法譯碼性能。另外，本文提出的基于節(jié)點(diǎn)更新次數(shù)最小、置零初始化值的思路也可以運(yùn)用于其他LDPC譯碼算法中。

參考文獻(xiàn)

[1] Li Hua，Zheng Linhua.Efficient puncturing scheme for irregular LDPC codes based on serial schedules[J].IEEE Communications Letters，2015，19(9)：1508-1511.

[2] 白寶明，孫成，陳佩瑤，等.信道編碼技術(shù)新進(jìn)展[J].無(wú)線電通信技術(shù)，2016，42(6)：1-8.

[3] MACKAY D J C，NEAL R.Near Shannon limit performance of low density parity check codes[J].IEEE Electronics Letters，1998，33(6)：457-458.

[4] 鄭偉，馬曉越，趙成晨.一種改進(jìn)的LDPC碼BP譯碼算法[J].河北大學(xué)學(xué)報(bào)(自然科學(xué)版)，2016，36(5)：547-553.

[5] 張福星，許生旺.一種改進(jìn)的多元LDPC碼譯碼算法[J].無(wú)線通訊技術(shù)，2016，42(6)：56-81.

[6] GOLOV O，AMRANI O.Edge-based scheduled BP in LDPC codes[C].IEEE International Symposium on Information Theory，2007：2376-2380.

[7] SAEJOON K，KARAM K.Two-staged informed dynamic scheduling for sequential belief propagation decoding of LDPC codes[J].IEEE Communication Letters，2009，13(3)：193-195.

[8] LEE H C，UENG Y L，YEH S M，et al.Two informed dynamic scheduling strategies for iterative LDPC decoders[J].IEEE Transactions on Communications，2013，61(3)：886-896.

[9] CASADO A I V，GRIOT M，WESEL R D.LDPC decoders with informed dynamic scheduling[J].IEEE Transactions on Communications，2010，58(12)：3470-3479.

[10] Song Lingyan，Hou Shujuan.Improved decoding of LDPC codes by variable-to-check residual belief propagation[C].International Conference on Communications & Networking in China，2015：163-166.

[11] Liu Xingcheng，Zhang Yuanbin，Cui Ru.Variable-node-based dynamic scheduling strategy for belief-propagation decoding of LDPC codes[J].IEEE Communications Letters，2015，19(2)：147-150.

[12] Han Guojun，Liu Xingcheng.An efficient dynamic schedule for layered belief-propagation decoding of LDPC codes[J].IEEE Communications Letters，2009，13(13)：193-195.

[13] KSCHISCHANG F R，F(xiàn)REY B J，LOELIGER H A.Factor graphs and the sum-product algorithm[J].IEEE Transactions on Information Theory，2001，47(2)：498-519.



作者信息：

周  華1，2，3，翁少輝1，3，馮  姣1，3

(1.南京信息工程大學(xué)，江蘇 南京210044；2.江蘇省大氣環(huán)境與裝備技術(shù)協(xié)同創(chuàng)新中心，江蘇 南京210044；

3.江蘇省氣象探測(cè)與信息處理重點(diǎn)實(shí)驗(yàn)室，江蘇 南京210044)

此內(nèi)容為AET網(wǎng)站原創(chuàng)，未經(jīng)授權(quán)禁止轉(zhuǎn)載。