LDPC碼中一種基于節(jié)點(diǎn)殘余的BP譯碼算法*

王興成，王中訓(xùn)，郭 棟，于心喬

（煙臺(tái)大學(xué) 光電信息科學(xué)技術(shù)學(xué)院，山東 煙臺(tái) 264005）

1 引言

低密度奇偶校驗(yàn)（LDPC）碼[1-3]是性能接近香農(nóng)極限的糾錯(cuò)編碼，因而得到廣泛關(guān)注，對(duì)于無(wú)線通信有著至關(guān)重要的作用。在LDPC碼譯碼時(shí)，校驗(yàn)節(jié)點(diǎn)與變量節(jié)點(diǎn)之間有大量的信息傳送，因此降低LDPC碼譯碼復(fù)雜度與譯碼器的功率消耗，關(guān)鍵在于減少信息傳送的運(yùn)算量。

在眾多優(yōu)秀的譯碼算法中，殘余信息的LDPC碼BP譯碼算法（RBP）[4]是一種有效動(dòng)態(tài)調(diào)度的譯碼算法，在迭代次數(shù)較少情況下與無(wú)調(diào)度的譯碼算法相比譯碼速度較快，但誤碼率和復(fù)雜度較高。筆者研究的VC-RBP譯碼算法與RBP譯碼算法相比，具有優(yōu)良的誤碼率性能，復(fù)雜度較低，同樣具有快速譯碼的性能，不同之處在于殘留信息的計(jì)算。RBP算法的殘余信息的計(jì)算在校驗(yàn)節(jié)點(diǎn)傳向變量節(jié)點(diǎn)信息更新前后，而VC-RBP算法的殘余信息的計(jì)算在變量節(jié)點(diǎn)傳向校驗(yàn)節(jié)點(diǎn)信息更新前后。

2 LDPC碼中的BP譯碼算法及其改進(jìn)

2.1 BP譯碼算法[5]

消息傳遞算法的信道輸出符號(hào)集和譯碼過(guò)程中發(fā)送信息的符號(hào)集相同，都是實(shí)數(shù)集，也就是說(shuō)采用連續(xù)性的消息時(shí)，適當(dāng)?shù)剡x擇信息映射函數(shù)，就能把人工智能中的置信傳播（BP）算法運(yùn)用于LDPC碼，從而形成LDPC碼的現(xiàn)代譯碼方案。

該算法的主要思想在于利用接收到的軟信息在變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)之間進(jìn)行迭代運(yùn)算，從而獲得最大的編碼增益，因此具有很好的性能。BP譯碼算法的迭代過(guò)程分為校驗(yàn)節(jié)點(diǎn)的信息更新和變量節(jié)點(diǎn)的信息更新。如圖1所示，H為校驗(yàn)矩陣，t為迭代次數(shù)，完成一次迭代過(guò)程時(shí)，按照“若校驗(yàn)節(jié)點(diǎn)傳遞到變量節(jié)點(diǎn)的信息mc→v>0，則c＾=1，否則c＾=0”的規(guī)則進(jìn)行譯碼判決。 在此迭代過(guò)程中，如果譯碼成功，譯碼過(guò)程立即結(jié)束而不是進(jìn)行固定次數(shù)的迭代，有效地減少了算法的迭代次數(shù)，降低了運(yùn)算復(fù)雜度。而且如果算法在預(yù)先限定的最大迭代次數(shù)tmax到達(dá)后仍未找到有效的譯碼結(jié)果，譯碼器將報(bào)錯(cuò)，這時(shí)的譯碼錯(cuò)誤為“可檢測(cè)的”。同時(shí)由于BP算法是一種并行算法，在硬件中的并行實(shí)現(xiàn)能夠極大地提高譯碼速度。

2.2 RBP譯碼算法[6]

圖1 BP譯碼算法流程圖

LDPC譯碼的置信傳播算法是通過(guò)變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)之間的消息迭代來(lái)實(shí)現(xiàn)的。設(shè)一個(gè)碼長(zhǎng)為N的LDPC 碼，碼字 V={v1，v2，v3，…，vN}表示一組信息節(jié)點(diǎn){vj:j=1，2，3，…，N}，{ci:i=1，2，3，…，M}表示一組校驗(yàn)節(jié)點(diǎn)，節(jié)點(diǎn)間傳遞的信息為m，mk為傳遞的第k個(gè)信息。任意的校驗(yàn)節(jié)點(diǎn)ci與其相鄰的變量節(jié)點(diǎn)vj傳遞信息的方程為

式中：CvJ=ln（p（yj|vj=1）/p（yj|vj=0）），為變量節(jié)點(diǎn) vj的對(duì)數(shù)似然比，yi是信號(hào)譯碼器的接收序列。

RBP譯碼算法是一種動(dòng)態(tài)調(diào)度的譯碼算法[7]，節(jié)點(diǎn)開(kāi)始迭代時(shí)的最大殘余隨著迭代次數(shù)的增加逐漸減小至零，因此殘余的值越大說(shuō)明此消息還未被收斂，先處理這樣的消息會(huì)加速譯碼。對(duì)于消息mk來(lái)說(shuō)，其殘余為

式中：fk（m）為變量節(jié)點(diǎn)k在更新后的對(duì)數(shù)似然比。

RBP算法可以概括為以下3個(gè)步驟：1）假設(shè)mci→vj的殘余最大，則首先對(duì)mci→vj進(jìn)行更新，此時(shí)設(shè)置該信息殘余為零。 2）計(jì)算 mvj→ca的殘余 r（mvj→ca），此時(shí) ca∈N（vj）ci。3）計(jì)算 mca→vb的殘余 r（mca→vb），此時(shí) vb∈N（ca）vj，然后根據(jù)校驗(yàn)節(jié)點(diǎn)傳向變量節(jié)點(diǎn)的信息更新前后的差異對(duì)將要更新的信息進(jìn)行排序。

盡管RBP算法是一種有效的動(dòng)態(tài)調(diào)度方案，由Vila casado等人應(yīng)用到LDPC碼上，但在誤碼率性能和復(fù)雜度方面不甚理想。RBP算法因其貪婪特性[5]會(huì)產(chǎn)生新的錯(cuò)誤，這在非動(dòng)態(tài)的譯碼方案中不會(huì)出現(xiàn)。在復(fù)雜度方面，當(dāng)一個(gè)校驗(yàn)節(jié)點(diǎn)到變量節(jié)點(diǎn)更新時(shí)，mc→v不必重新計(jì)算信息量，因?yàn)樵趓（mc→v）確定時(shí)其值已經(jīng)確定。另外，在譯碼算法最后，每個(gè)邊緣殘余被計(jì)算時(shí)，殘余信息序列Q都會(huì)被重新排序，這樣就增加了譯碼復(fù)雜度。

因此，RBP 譯碼算法流程為：1）初始化 1，mc→v=0；2）初始化 2，mvn→c=Cn；3）計(jì)算 r（mc→v）和生成 Q；4）mci→vj為Q 的首次傳遞信息；5）得到mci→vj迭代傳遞；6）令 r（mvj→ci）=0，重新排序Q；7）獲得與變量節(jié)點(diǎn)j相連的除去i節(jié)點(diǎn)的校驗(yàn)節(jié)點(diǎn)的集合 ca∈N（vj）ci；8）得到 mvj→ca迭代傳遞；9）獲得校驗(yàn)節(jié)點(diǎn)j相連的除去i節(jié)點(diǎn)的變量節(jié)點(diǎn)集合vb∈N（ca）vj；10）計(jì)算 r（mca→vb），重新排序 Q；11）若c＾·HT≠0，返回步驟4）。

2.3 VC-RBP譯碼算法[6]

VC-RBP譯碼算法在貪婪特性方面要優(yōu)于RBP譯碼算法，主要區(qū)別在于VC-RBP的殘余是根據(jù)變量節(jié)點(diǎn)傳向校驗(yàn)節(jié)點(diǎn)更新信息前后的差異計(jì)算出來(lái)。與RBP譯碼算法相比，VC-RBP譯碼算法的程序少了一步。第一步，VC-RBP 選擇相應(yīng)的邊緣最大值r（mvi→cj）并設(shè)置為零，然后更新所選邊緣連接的校驗(yàn)節(jié)點(diǎn)。第二步，先更新mcj→va，va∈N（cj）vi；接著更新mva→cb，cb∈N（Va）cj，根據(jù)更新信息的差異計(jì)算出 r（mva→cb），與RBP相比可減少譯碼復(fù)雜度。

因此，VC-RBP 譯碼算法流程為：1）初始化 1，mc→v=0；2）初始化 2，mvn→c=Cn；3）確認(rèn) r（mc→v）最大值；4）確認(rèn)mvi→cj節(jié)點(diǎn)；5）設(shè)置 r（mvi→cj）=0；6）獲得 va∈N（cj）vi；7）得到mcj→va迭代傳遞；8）獲得 cb∈N（va）cj；9）得到 mva→cb迭代傳遞；10）計(jì)算 r（mva→cb）；11）若c＾·HT≠0，返回步驟 3）。

在糾錯(cuò)性能方面，VC-RBP要優(yōu)于RBP。RBP首先把信息傳遞給不太可靠的變量節(jié)點(diǎn)，因?yàn)榘畲髿堄嗟男畔H僅基于一個(gè)校驗(yàn)方程，這樣的貪婪特性會(huì)產(chǎn)生新的錯(cuò)誤，而糾錯(cuò)需要大量的信息更新。VC-RBP首先傳遞包含最大殘余的信息時(shí)是基于全部校驗(yàn)方程的，通過(guò)更新以表示校驗(yàn)方程的校驗(yàn)節(jié)點(diǎn)和變量節(jié)點(diǎn)的信息，從而有效地解決了更新校驗(yàn)節(jié)點(diǎn)時(shí)的差錯(cuò)平底。

3 仿真結(jié)果

采用Matlab工具對(duì)提出的LDPC改進(jìn)譯碼算法的性能進(jìn)行了仿真驗(yàn)證，采用IEEE802.16e標(biāo)準(zhǔn)設(shè)計(jì)的QCLDPC碼，在AWGN信道下碼長(zhǎng)為1024，碼率為1/2，迭代次數(shù)為10的仿真結(jié)果如圖2所示。隨著信噪比的增大，RBP譯碼算法和VC-RBP譯碼算法均比傳統(tǒng)的BP譯碼算法性能優(yōu)越。迭代次數(shù)為10的VC-RBP在誤碼率為10-4時(shí)，與RBP相比有0.28 dB的增益。

4 小結(jié)

研究了VC-RBP與RBP和一般的BP譯碼算法相比具有的優(yōu)越性能。在同一信噪比的情況下，VC-RBP譯碼算法性能最優(yōu)，使LDPC譯碼算法收斂得更快。

[1]GALLAGER R G.Low-density-parity-check codes[EB/OL].[2010-03-05].http：//www.rle.mit.edu/rgallager/documents/ldpc.pdf.

[2]IEEE802.16e-2005，IEEE standard for Local and me2tropolitan area networks，part 16：air interface for fixed and mobile broadband wireless access systems[S].2006.

[3]楊知行，林之初，王軍，等.準(zhǔn)循環(huán)LDPC碼的半并行譯碼器設(shè)計(jì)[J].電視技術(shù)，2006，30（2）：24-26.

[4]ELIDAN G，MCGRAW I，KOLLER D.Residual belief propagation:informed scheduling for asynchronous message passing[C]//Proc.22 Conf.Uncertainty in Artificial Intelligence.Cambridge：[s.n.]，2006：165-173.

[5]MACKAY D J C，NEAL R M.Near Shannon limit performance of low density parity check codes[J].Electronics Letters，1996，32（18）：1645-1646.

[6]CASADO A I V，GRIOT M，WESEL R D.Improving LDPC decoders via informed dynamic scheduling[EB/OL].[2010-03-06].http：//www.ee.ucla.edu/～csl/files/publications/Improving_LDPC_Decoders_IT-W2007.pdf.

[7]CASADO A I V，GRIOT M，WESEL R D.Informed dynamic scheduling for belief-propagation decoding of LDPC codes[C]//Proc.IEEE ICC 2007.Glasgow，Scotland：IEEE Press，2007：208-213.