基于循環(huán)檢測(cè)的LDPC比特翻轉(zhuǎn)譯碼算法研究

朱方強(qiáng)，王中訓(xùn)，劉 麗，王 娟

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

0 引言

低密度奇偶校驗(yàn)碼（Low-Density Parity-Check，LD?PC）是Gallager[1]于1962年提出的一種基于稀疏校驗(yàn)矩陣的線性分組碼，但由于當(dāng)時(shí)計(jì)算機(jī)能力有限，而且級(jí)聯(lián)碼被認(rèn)為具有更好的性能，在很長(zhǎng)的一段時(shí)間內(nèi)，LDPC碼并未受到重視，直到Mackay和Neal[2]在90年代重新發(fā)現(xiàn)并證明LDPC碼是一種逼近香農(nóng)限的好碼[3]，使用迭代軟信息譯碼的LDPC碼性能甚至超過了Turbo碼，由此對(duì)LDPC的研究成為通信領(lǐng)域編譯碼研究的一個(gè)熱點(diǎn)。

LDPC碼的譯碼算法基本可分為基于軟判決的譯碼和基于硬判決的譯碼。這些譯碼算法包括基于消息傳遞（Message Passing）的置信傳播（Belief Propagation，BP）算法[3]，改進(jìn)的BP算法（迭代APP算法、最小和算法等），Gallager提出的比特翻轉(zhuǎn)（Bit Fliping）算法[1]以及在此基礎(chǔ)上改進(jìn)的一系列軟硬混合判決算法，如加權(quán)比特翻轉(zhuǎn)算法[4]（WBF）、改進(jìn)的加權(quán)比特翻轉(zhuǎn)算法[5]（IWBF）、LP加權(quán)比特翻轉(zhuǎn)算法[6]（LP-WBF）等。軟判決算法性能良好但譯碼復(fù)雜度高，硬判決算法性能稍差易于硬件實(shí)現(xiàn)，有較高的實(shí)用性。

本文提出基于比特翻轉(zhuǎn)的一種改進(jìn)譯碼算法，對(duì)于低密度奇偶校驗(yàn)矩陣，伴隨式權(quán)重會(huì)隨著平均錯(cuò)誤增多而增加，直到錯(cuò)誤權(quán)重大于最小距離的1/2[7]，因此在每次迭代中選擇一個(gè)伴隨式權(quán)重降低的比特翻轉(zhuǎn)。同時(shí)在比特翻轉(zhuǎn)算法中存在著多次迭代后算法陷入死循環(huán)的問題，本文借鑒文獻(xiàn)[7-8]的循環(huán)檢測(cè)（Loop Detection，LD）方法有效解決了這個(gè)問題。這種改進(jìn)的基于對(duì)接收符號(hào)可靠性軟判決的算法在運(yùn)算復(fù)雜度增加不大的情況下使譯碼性能改善顯著。

1 譯碼算法

1.1 LDPC碼基本定義

LDPC碼由校驗(yàn)矩陣H定義，碼長(zhǎng)為n，信息長(zhǎng)度為k，H 的維數(shù)是m×n，即m行n列（m=n-k）。對(duì)于規(guī)則LDPC碼有恒定的列重wc和行重wr，非規(guī)則碼行重和列重不再固定，但校驗(yàn)矩陣仍滿足稀疏性[2]。

首先定義譯碼算法中出現(xiàn)的符號(hào)。設(shè)發(fā)送碼字c=(c0,c1,…,cN-1)按照xi=2ci-1準(zhǔn)則變?yōu)殡p極性發(fā)送序列x=(x0,x1,…,xN-1)，接收序列為y=(y0,y1,…,yN-1)，其中yi=xi+ni，0 ≤i

在每次迭代時(shí)可計(jì)算伴隨式s=Z·HT來判斷校驗(yàn)式和，若所有校驗(yàn)式都滿足特征子空間為0，則停止譯碼，其中s=(s0,s1,…,sM-1)。對(duì)于軟輸出序列 y=(y0,y1,…,yN-1)定義對(duì)數(shù)似然比為

1.2 本文算法1

BF算法核心思想[1]是根據(jù)伴隨式譯碼方案，如果某比特參與的校驗(yàn)式大多有錯(cuò)，則認(rèn)為此比特錯(cuò)誤概率很大，翻轉(zhuǎn)比特?；贐F算法提出的算法1的譯碼流程為：1）初始化。設(shè)置迭代次數(shù)k=0，計(jì)算z(0)和s(0)=wt(z(0)·HT)。

2）如果s(k)=0，則進(jìn)行步驟8）。

3）k← k+1（k+1后，重新賦于k），如果k>kmax將進(jìn)行步驟9），其中，kmax是最大迭代次數(shù)。

6）如果 j(k)=j(k-1)，則進(jìn)行步驟9）。

7）計(jì)算 z(k)=z(k-1)+uj(k)和 s(k)=wt(z(k)·HT)后跳到步驟2）。

8）停止譯碼并返回z(k)。

9）宣布譯碼失敗并返回z(k-1)。

算法1在每次迭代只翻轉(zhuǎn)1 bit，翻轉(zhuǎn)的依據(jù)是伴隨式權(quán)重隨著錯(cuò)誤權(quán)重增多而增加，由于引入計(jì)算漢明重使得算法又不同于BF算法。這種判決準(zhǔn)則有可能在譯碼中選擇錯(cuò)誤的位置j翻轉(zhuǎn)，引進(jìn)了一個(gè)新的錯(cuò)誤，接著在隨后的迭代譯碼中這個(gè)錯(cuò)誤又有很大可能被糾正。

1.3 本文算法2（算法1的改進(jìn)）

對(duì)算法1可以在幾乎不增加運(yùn)算復(fù)雜度的前提下進(jìn)行改進(jìn)并達(dá)到更好的性能。借鑒文獻(xiàn)[5]對(duì)WBF算法的改進(jìn)，算法2增加對(duì)接收符號(hào)的可靠性度量以提高算法性能。

1）|Li|越大說明硬判決結(jié)果zi可靠性越高。

2）如果在校驗(yàn)矩陣H的不同列沒有非零元素重疊，則每列對(duì)伴隨式權(quán)重的貢獻(xiàn)值為wc。

3）在不同的信噪比下，|Li|的值一般不一樣，所以存在最優(yōu)權(quán)重因子α。對(duì)于特定的LDPC碼在某一信噪比下，最優(yōu)的權(quán)重因子選擇譯碼時(shí)比特錯(cuò)誤最小對(duì)應(yīng)的α值，一般需要計(jì)算機(jī)仿真得到。

當(dāng)α=0時(shí)，算法2就變?yōu)樗惴?。對(duì)于這兩種算法，譯碼的最大迭代次數(shù)kmax是自定的，對(duì)于譯碼的停止規(guī)則在算法中已表明：獲得步驟2）的結(jié)果，迭代次數(shù)為k次，宣布譯碼成功；達(dá)到最大迭代次數(shù)獲得步驟6）的結(jié)果，宣布譯碼失敗，這些都在仿真中可以看到。

1.4 基于循環(huán)檢測(cè)的算法2（LD）

用j(k)表示在第k次迭代時(shí)被翻轉(zhuǎn)的比特位置，如果j(k)=j(k-1)，則z(k)=z(k-2)，z(k+ρ)=z(k-2+ρ)，其中 ρ為大于 0的實(shí)數(shù)，這樣算法在第k次迭代時(shí)會(huì)陷入一個(gè)死循環(huán)。為了解決上述問題，文獻(xiàn)[6]提出了簡(jiǎn)化的破環(huán)路算法，即LD算法，通過選擇在第k次迭代時(shí)s(k)i的次小值代替最小值來打破這種死循環(huán)。

式中：1≤k′

1）初始化。設(shè)置迭代次數(shù)k=0，計(jì)算z(0)和s(0)=wt(z(0)·HT)，設(shè)置清除比特位置集合B，使其為空集（原步驟1））。

3）計(jì)算n(k′)和w(k′)，1 ≤ k′

2 算法運(yùn)算復(fù)雜度分析

1）算法2的運(yùn)算復(fù)雜度分析

在每次迭代中，通過Nwcwr次異或運(yùn)算和加法運(yùn)算來計(jì)算伴隨式權(quán)重，N-1次比較運(yùn)算來選擇比特翻轉(zhuǎn)位?？煽啃猿叨纫蜃觓wc| |Li只需在算法的第一次迭代前計(jì)算一次，由于比較運(yùn)算可當(dāng)做加法運(yùn)算處理，因此每次迭代需要2N-1次加法運(yùn)算和Nwcwr次異或運(yùn)算。

2）基于循環(huán)檢測(cè)的算法2（LD）運(yùn)算復(fù)雜度分析

一般循環(huán)檢測(cè)操作的次數(shù)與分組碼字長(zhǎng)度N沒有關(guān)系，只與執(zhí)行迭代次數(shù)有關(guān)。在實(shí)際仿真中最大迭代次數(shù)kmax一般遠(yuǎn)小于碼長(zhǎng)N，并且譯碼收斂的平均迭代次數(shù)小于最大迭代次數(shù)kmax。因此，用于循環(huán)檢測(cè)的運(yùn)算量與原算法2的2N-1次加法運(yùn)算和Nwcwr次異或運(yùn)算量相比可忽略不計(jì)，可認(rèn)為算法2（LD）運(yùn)算復(fù)雜度基本沒有增加。

3）比較幾種算法每次迭代的運(yùn)算量

BP算法[2-3]需要11Nωc-9N 次乘法，N(ωc+1)次除法以及N(3ωc+1)次加法運(yùn)算，WBF算法[4]需要N-1+wcwr次加法運(yùn)算，LP-WBF算法[6]需要N-1+wcwr次加法運(yùn)算，本文算法2需要2N-1次加法運(yùn)算和Nwcwr次異或運(yùn)算。通過比較發(fā)現(xiàn)，基于比特翻轉(zhuǎn)的改進(jìn)算法每次迭代計(jì)算量要比軟判決的BP算法少得多，只有加法運(yùn)算沒有了乘除運(yùn)算，更易于硬件實(shí)現(xiàn)，而本文的算法2及改進(jìn)的算法2和同類比特翻轉(zhuǎn)類算法相比運(yùn)算復(fù)雜度增加不大。

3 仿真試驗(yàn)及結(jié)果分析

基于Matlab仿真平臺(tái)對(duì)本文算法進(jìn)行仿真，并與標(biāo)準(zhǔn)BF算法、WBF算法、IWBF算法、LP-WBF算法和BP算法在誤碼率上進(jìn)行比較。仿真采用BPSK調(diào)制，經(jīng)過噪聲均值為0，方差為N02的加性高斯白噪聲信道。

3.1 算法1與BF算法比較

圖1為列重為3的（504，252）LDPC碼的比特翻轉(zhuǎn)算法BF與本文算法1誤碼率BER圖像對(duì)比，設(shè)最大迭代次數(shù)kmax為150。由于算法1與BF算法均是單一的硬判決算法，所以在這里單獨(dú)比較兩種算法的性能。由圖1可知，在誤碼率為10-3時(shí)，算法1與BF算法相比有大約0.5 dB的增益，同一信噪比下，算法1性能改善約一個(gè)數(shù)量級(jí)。由于伴隨式漢明重的引入，算法1的譯碼復(fù)雜度要比BF算法大。

3.2 算法2最優(yōu)α因子的選取

對(duì)于給定列重wc的LDPC碼，在給定信噪比下，α因子不同，則算法性能也不一樣。最優(yōu)α因子的值一般與LDPC碼和具體的碼結(jié)構(gòu)有關(guān)。選擇wc為3的（273，191）Gallager碼[9]仿真α因子對(duì)比特錯(cuò)誤概率BER的影響，最大迭代次數(shù)kmax為200。圖2和圖3仿真了在不同信噪比下，最優(yōu)α因子對(duì)誤碼率和平均迭代次數(shù)的影響。基于最優(yōu)α因子的定義，由圖2可知，在較低的信噪比下，α因子對(duì)比特錯(cuò)誤概率影響并不明顯。隨著信噪比的增加，最優(yōu)α因子變化不是很大。圖2和圖3可得到當(dāng)α大約為1.2時(shí)，誤碼率最低，譯碼需要的平均迭代次數(shù)最少，即α=1.2為此碼最優(yōu)權(quán)重因子。

3.3 算法2與其他算法性能比較

由圖2和圖3得到，wc為3的（273，191）Gallager碼[9]的最優(yōu)α因子為1.2。圖4對(duì)比了WBF算法、IWBF算法、LP-WBF算法、BP算法、本文算法2以及算法2的改進(jìn)，即基于循環(huán)檢測(cè)的算法2（LD）的誤碼率性能。其中，IWBF算法中的權(quán)重因子優(yōu)化為α=0.4，LP-WBF算法是改進(jìn)的基于循環(huán)檢測(cè)的算法。除BP算法最大迭代次數(shù)為40，其他算法最大迭代次數(shù)為200。當(dāng)信噪比較低時(shí)，比特翻轉(zhuǎn)類算法性能改善較小，軟判決的BP算法性能改善明顯，隨著信噪比增大，本文算法性能改善優(yōu)于同類基于軟硬混合判決的比特翻轉(zhuǎn)算法。由圖4可知，基于接收符號(hào)可靠性判斷的算法2性能遠(yuǎn)優(yōu)于WBF算法和IWBF算法；不帶循環(huán)檢測(cè)的算法2譯碼性能比LP-WBF算法稍差一些，當(dāng)BER為10-5時(shí)，LP-WBF算法比算法2多獲得0.2 dB增益；基于循環(huán)檢測(cè)的算法2（LD）性能要優(yōu)于 LP-WBF算法，在 BER為10-6時(shí)，算法 2（LD）比LP-WBF算法可獲得0.3 dB增益。在BER為10-5時(shí)，改進(jìn)的算法2（LD）比算法2獲得大約0.5 dB增益，與BP算法相比相差大約0.9 dB。

4 小結(jié)

本文在比特翻轉(zhuǎn)算法基礎(chǔ)上提出了基于循環(huán)檢測(cè)和對(duì)接收符號(hào)可靠性信息軟判決的譯碼算法。仿真結(jié)果表明，硬判決算法1與標(biāo)準(zhǔn)的BF算法相比獲得大約0.5 dB的增益，基于軟硬混合判斷的算法2（LD）性能優(yōu)于同類的LP-WBF算法約0.3 dB，與軟判決BP算法相比相差大約0.9 dB，這種改進(jìn)的算法在譯碼復(fù)雜度增加不大的情況下顯著改善了譯碼性能，達(dá)到了譯碼復(fù)雜度和性能的折中。本文只對(duì)兩種隨機(jī)碼進(jìn)行了仿真，同樣改進(jìn)的算法也適用于其他LDPC碼，如RS-LDPC碼、PEG-LD?PC碼等[9]。

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

[2] MACKAY D J C，NEAL R M.Near Shannon limit performance of low density parity check codes[J].IEEE Trans.Electronics Letters，1997，33（6）：457-458.

[3] MACKAY D J C.Good error-correcting codes based on very sparse matrices[EB/OL].[2010-10-18].http：//citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.136.1309&rep=rep1&type=pdf.

[4] KOU Y L，F(xiàn)OSSORIER M P C.Low-density parity-check codes based on finite geometries：a rediscovery and new results[J].IEEE Trans.Information Theory，2001，47（7）：2711-2736.

[5] ZHANG Juntan，F(xiàn)OSSORIER M P C.A modified weighted bit-flipping decoding of low-density parity-check codes[J].IEEE Trans.Communications Letters，2004，8（3）：165-167.

[6] LIU Zhenyu，PADOS D A.A decoding algorithm for finite-geomety LDPC codes[J].IEEE Trans.Communications，2005，53（3）：415-421.

[7] BOSSERT M.Channel coding for telecommunications[M].New York：Wiley，1999.

[8] BOSSERT M，HERGERT F.Hard and soft-decision decoding beyond the half minimum distance：an algorithm for linear codes[J].IEEE Trans.Information Theory，1986，32（5）：709-714.

[9] 吳黎麗，趙新建.不規(guī)則LDPC碼面向4G的性能改進(jìn)[J].電視技術(shù)，2009，33（S2）：184-185.