基于多/單比特切換機(jī)制的LDPC碼兩級(jí)WBF算法

周 華，張 銳，葛旗偉，史傳勝

(南京信息工程大學(xué) 電子與信息工程學(xué)院，南京 210044)

0 引 言

低密度奇偶校驗(yàn)(Low Density Parity Check, LDPC)碼[1]是一種逼近香農(nóng)極限的好碼，其譯碼算法可分為硬判決譯碼和軟判決譯碼算法。軟判決譯碼算法通過(guò)校驗(yàn)節(jié)點(diǎn)和變量節(jié)點(diǎn)之間的軟信息傳遞更新，常用算法有置信傳播(Belief Propagation, BP)算法[2]、最小和算法[3]和基于上述算法提出的一些改進(jìn)算法[4-5]；硬判決譯碼算法每次迭代時(shí)翻轉(zhuǎn)不滿(mǎn)足校驗(yàn)方程個(gè)數(shù)最多的比特，主要代表算法為比特翻轉(zhuǎn)(Bit-Flipping, BF)算法[1]。由于硬判決譯碼算法并沒(méi)有對(duì)可靠度軟信息進(jìn)行考量，故其具有復(fù)雜度低和運(yùn)算量小等特點(diǎn)，但譯碼性能不如軟判決譯碼算法。為了改善BF算法的譯碼性能，在此基礎(chǔ)上提出了加權(quán)比特翻轉(zhuǎn)(Weighted Bit Flipping,WBF)譯碼算法[6],該算法首次將可靠度軟信息引入到BF算法中;文獻(xiàn)[7-10]對(duì)WBF譯碼算法翻轉(zhuǎn)函數(shù)和權(quán)重計(jì)算進(jìn)行改進(jìn)，取得了一定的譯碼性能提升;文獻(xiàn)[11]提出的基于幅度和的WBF(Sum of the Magnitude based WBF,SMWBF)譯碼算法提出了一種新的權(quán)重計(jì)算來(lái)衡量比特的可靠性;文獻(xiàn)[12]在SMWBF譯碼算法基礎(chǔ)上提出了基于變量節(jié)點(diǎn)更新的SMWBF(Variable Node Updating based SMWBF,VSMWBF)譯碼算法，使性能獲得了進(jìn)一步的提升。

但以上算法在每次迭代中只能翻轉(zhuǎn)一個(gè)比特且VSMWBF譯碼算法由于比特幅值發(fā)生變化，需要重新計(jì)算權(quán)重，使得譯碼時(shí)間較長(zhǎng)，迭代收斂速度較慢。為了提高算法的譯碼速度，本文在SMWBF和VSMWBF譯碼算法基礎(chǔ)上提出了一種具有全新跳轉(zhuǎn)條件的多/單BF切換機(jī)制的兩級(jí)譯碼算法。仿真表明，與單獨(dú)采用SMWBF或VSMWBF譯碼算法相比，本文所提算法在提升譯碼性能和降低平均迭代次數(shù)方面都取得了一定成效。

1 基于LDPC碼的BF譯碼算法

1.1 基本定義

用(N,K)(dv,dc)表示有固定行重dc、列重dv和碼率為R=K/N的規(guī)則二進(jìn)制LDPC碼，其中，N為碼長(zhǎng)，K為信息位，其對(duì)應(yīng)的奇偶校驗(yàn)矩陣記為H=[hmn]，H為M行N列矩陣。用集合N(m)={n∶hmn=1}表示H第m行中所有“1”的位置，即與校驗(yàn)節(jié)點(diǎn)m相連的變量節(jié)點(diǎn)集合；用集合M(n)={m∶hmn=1}表示H第n列中所有“1”的位置，即與變量節(jié)點(diǎn)n相連的校驗(yàn)節(jié)點(diǎn)集合。設(shè)發(fā)送碼字c={c1,c2,…,cn}經(jīng)過(guò)二進(jìn)制相移鍵控(Binary Phase Shift Keying, BPSK)調(diào)制后得到雙極性碼字序列{2c1-1,2c2-1,…,2cn-1},通過(guò)加性高斯白噪聲(Additive White Gaussian Noise, AWGN)信道得到接收碼字y={y1,y2,…,yn} ，其中yi=(2ci-1)+vi，vi為均值為0、功率譜密度為N0/2 (即方差σ2=N0/2)的高斯白噪聲。根據(jù)硬判決規(guī)則得到二進(jìn)制碼字序z={z1,z2,…,zn},其中：

接收序列的伴隨式為s=[s1,s2,…,sn]=zHT，譯碼算法成功的標(biāo)志為伴隨式為全零矩陣。定義接收序列中各碼元信道觀(guān)測(cè)值的初始化對(duì)數(shù)似然比Li為

式中：P()為概率函數(shù)；Eb/N0為信息位信噪比(Signal Noise Ratio ,SNR)。由上式可知，比特i可靠度軟信息的|Li|與其幅值(信道觀(guān)測(cè)值)|yi|成正比例關(guān)系，因此下述幾種改進(jìn)的WBF譯碼算法均用幅值|yi|代替|Li|作為可靠度軟信息。

1.2 SMWBF譯碼算法

修正加權(quán)比特翻轉(zhuǎn)(Modified WBF, MWBF)[7]和改進(jìn)的修正加權(quán)比特翻轉(zhuǎn) (Improved Modified WBF, IMWBF)[8]譯碼算法在計(jì)算權(quán)重時(shí)認(rèn)為，參與某個(gè)校驗(yàn)方程的所有變量節(jié)點(diǎn)中具有最小幅值的節(jié)點(diǎn)對(duì)此校驗(yàn)方程的影響最大，而SMWBF譯碼算法[11]則認(rèn)為參與每一個(gè)校驗(yàn)方程的所有變量節(jié)點(diǎn)的幅值大小均會(huì)對(duì)結(jié)果造成不同程度的影響。其在計(jì)算比特n的權(quán)重時(shí)，將除了自身外其他變量節(jié)點(diǎn)幅值的和作為權(quán)重，故SMWBF譯碼算法的權(quán)重計(jì)算公式為

(3)

SMWBF算法對(duì)應(yīng)的翻轉(zhuǎn)函數(shù)為

式中，α為權(quán)重因子，用來(lái)修正變量節(jié)點(diǎn)對(duì)判決帶來(lái)的過(guò)度影響。

SMWBF算法步驟詳述如下：

步驟1 初始化：設(shè)置初始迭代次數(shù)k=1,并設(shè)定上限kmax，zk和sk為第k次迭代譯碼的輸出序列及其伴隨式。

步驟2 通過(guò)式(3)計(jì)算權(quán)重ωmn。

步驟3 計(jì)算伴隨式：

若sk為全零矩陣或達(dá)到預(yù)設(shè)的最大迭代次數(shù)，則跳至步驟7；反之，進(jìn)行步驟4。

步驟4 由式(4)計(jì)算各個(gè)變量節(jié)點(diǎn)的翻轉(zhuǎn)函數(shù)。

步驟5 翻轉(zhuǎn)最大En值所對(duì)應(yīng)的比特：

步驟6k=k+1,轉(zhuǎn)至步驟3。

步驟7 輸出zk，譯碼結(jié)束。

1.3 VSMWBF譯碼算法

由于SMWBF等WBF譯碼算法在一次迭代過(guò)程中，變量節(jié)點(diǎn)自身的可靠度信息并未更新，通過(guò)考慮軟判決譯碼算法的變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)軟信息交替更新的思想，VSMWBF[12]譯碼算法對(duì)SMWBF譯碼算法步驟5和6進(jìn)行修正，即在每次迭代過(guò)程中，人為擴(kuò)大被翻轉(zhuǎn)變量節(jié)點(diǎn)的幅值，并在下一次迭代中重新計(jì)算權(quán)重，以此來(lái)體現(xiàn)這種可靠度的增加，在每次迭代后變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)都實(shí)現(xiàn)更新。從而使翻轉(zhuǎn)函數(shù)En的計(jì)算更加精確，故譯碼性能取得進(jìn)一步改善。將SMWBF譯碼算法的步驟5和6做如下調(diào)整，即可得到VSMWBF算法的譯碼步驟。

步驟5 翻轉(zhuǎn)最大En值所對(duì)應(yīng)的比特，同時(shí)將其幅值擴(kuò)大β倍。

步驟6k=k+1，算法轉(zhuǎn)至步驟2。

2 本文算法描述

圖1 多/單BF切換機(jī)制

2.1 第一級(jí)譯碼器

圖2 第一次出現(xiàn)時(shí)的殘留錯(cuò)誤比特

如圖3所示，若對(duì)殘留錯(cuò)誤比特依舊進(jìn)行多BF譯碼會(huì)導(dǎo)致譯碼性能不佳，而使用單BF譯碼來(lái)接替譯碼任務(wù)，相較于此時(shí)停止譯碼，性能會(huì)得到進(jìn)一步提升，故本文提出了多BF向單BF切換的兩級(jí)WBF譯碼機(jī)制。

圖3 出現(xiàn)之后進(jìn)行不同的譯碼選擇對(duì)譯碼性能的影響

第一級(jí)多BF譯碼器對(duì)SMWBF譯碼算法步驟5調(diào)整如下：

2.2 第二級(jí)譯碼器

表1所示為第一級(jí)譯碼器陷入循環(huán)的概率表，由表可知，若第k次與第k+1次譯碼時(shí)所翻轉(zhuǎn)的比特位一致，則在后續(xù)迭代中，此變量節(jié)點(diǎn)將被無(wú)限循環(huán)翻轉(zhuǎn)。為避免這種情況，本文在第一級(jí)譯碼器中引入了循環(huán)檢測(cè)裝置，當(dāng)檢測(cè)到連續(xù)兩次迭代的翻轉(zhuǎn)比特位置相同時(shí)，跳到第二級(jí)譯碼器中，從而避免了無(wú)限循環(huán)，而VSMWBF譯碼算法在每次迭代后都會(huì)更新變量節(jié)點(diǎn)的幅值，故該算法不會(huì)出現(xiàn)無(wú)限循環(huán)翻轉(zhuǎn)現(xiàn)象，從而消除了整個(gè)譯碼器的無(wú)限循環(huán)翻轉(zhuǎn)。由此，本文算法選擇VSMWBF譯碼算法作為第二級(jí)單BF譯碼器的譯碼算法。

表1 第一級(jí)譯碼器陷入循環(huán)的概率

2.3 本文算法步驟及流程圖

綜上，如圖4所示，本文算法步驟如下：

圖4 算法流程

步驟1 初始化：設(shè)置初始迭代次數(shù)k=1,并設(shè)定上限kmax，通過(guò)仿真確定參數(shù)α、β和γ。

步驟2 通過(guò)式(3)計(jì)算權(quán)重ωmn。

步驟3 計(jì)算伴隨式：

若sk為全零向量，或達(dá)到預(yù)設(shè)的最大迭代次數(shù)，則進(jìn)行步驟8；反之，進(jìn)行步驟4。

步驟4 由式(4)計(jì)算各個(gè)變量節(jié)點(diǎn)的翻轉(zhuǎn)函數(shù)En。

步驟6 啟動(dòng)第一級(jí)譯碼器對(duì)zk進(jìn)行譯碼，同時(shí)記錄第k次翻轉(zhuǎn)位置，并與第k-1次翻轉(zhuǎn)位置進(jìn)行比較，若翻轉(zhuǎn)位置完全相同，取消翻轉(zhuǎn)并跳至步驟7；否則k=k+1，返回步驟3。

步驟7 啟動(dòng)第二級(jí)譯碼器對(duì)zk進(jìn)行譯碼，并更新伴隨式sk，若sk為全零矩陣或達(dá)到預(yù)設(shè)的最大迭代次數(shù)，則進(jìn)行步驟8；否則k=k+1，重復(fù)步驟7。

步驟8 譯碼結(jié)束，輸出zk。

3 仿真分析

本文仿真采用碼率為1/2、列重為4和行重為8的(504，252)Gallager-LDPC規(guī)則碼(碼1)以及碼率為1/2、列重為3的(1008，504)P漸進(jìn)邊增長(zhǎng)(Progressive-edge-growth，PEG)-LDPC碼(碼2)。由于本文算法涉及3個(gè)不同的參數(shù)即加權(quán)因子α、擴(kuò)大倍數(shù)β和閾值參數(shù)γ，故啟動(dòng)譯碼器前先通過(guò)仿真找出最佳的參數(shù)值。

3.1 閾值參數(shù)γ的選取

加權(quán)因子α為第一級(jí)和第二級(jí)譯碼器翻轉(zhuǎn)函數(shù)的一部分，擴(kuò)大倍數(shù)β為第二級(jí)譯碼器中可靠度的增加幅度，其取值會(huì)對(duì)翻轉(zhuǎn)函數(shù)En和幅值|yn|造成影響，而閾值參數(shù)γ的取值只會(huì)影響翻轉(zhuǎn)比特的個(gè)數(shù)，對(duì)En和|yn|并無(wú)影響，因此α和β的取值并不會(huì)影響γ，γ獨(dú)立于α和β，故在對(duì)γ進(jìn)行仿真時(shí)，固定α和β的取值。圖5所示為碼1和碼2在γ取不同值時(shí)對(duì)譯碼性能的影響，最大迭代次數(shù)分別為50和100。

圖5 γ取值對(duì)譯碼性能的影響

在譯碼性能方面，如圖5所示，γ取值越小，譯碼性能越差。造成此現(xiàn)象的原因是，若γ取值太小，則會(huì)導(dǎo)致每次迭代中翻轉(zhuǎn)過(guò)多的比特，使翻轉(zhuǎn)正確比特的概率增大，從而影響譯碼性能；若γ取值過(guò)大，則每次迭代翻轉(zhuǎn)的比特?cái)?shù)較少，不能有效降低迭代的收斂速度。本文選取γ=0.8為碼1的最優(yōu)閾值參數(shù)，γ=0.7為碼2的最優(yōu)閾值參數(shù)。

3.2 加權(quán)因子α和擴(kuò)大倍數(shù)β的選取

文獻(xiàn)[8]和[12]指出，不同SNR的最優(yōu)α和β可通過(guò)仿真找到，但為了便于分析，本文借鑒文獻(xiàn)[12]中對(duì)α和β聯(lián)合仿真的方法，選擇一個(gè)不變的α和β。由上節(jié)可知，閾值參數(shù)γ獨(dú)立于α和β，在分別對(duì)碼1和碼2做在不同SNR下α和β對(duì)譯碼性能影響的聯(lián)合仿真時(shí)，固定γ，聯(lián)合仿真圖如圖6所示。

圖6 α和β的取值對(duì)譯碼性能的影響

由圖可知，碼1的α和β選為11和0.7時(shí)性能較好，碼2的α和β選為11和0.4時(shí)性能較好。

3.3 譯碼性能分析

圖7(a)為碼1在最大迭代次數(shù)為50次時(shí)各WBF譯碼算法下的譯碼性能比較，兩種碼字的參數(shù)分別設(shè)定為3.1和3.2節(jié)仿真得到的對(duì)應(yīng)參數(shù)值，由圖可知，本文算法相較于VSMWBF譯碼算法有進(jìn)一步提升，在誤比特率為10-4處能獲得約0.2 dB的增益；而在最大迭代為25次時(shí)，如圖8(a)所示，在誤比特率為10-4處相較于VSMWBF譯碼算法能獲得約1 dB增益,在SNR=5 dB時(shí)，誤比特率由10-3數(shù)量級(jí)提高到10-4，由此可知，在降低最大迭代次數(shù)時(shí)，改進(jìn)算法譯碼性能相較于其他算法受影響較小，優(yōu)勢(shì)更為顯著。通過(guò)觀(guān)察圖7(b)和圖8(b)，碼2可獲得類(lèi)似結(jié)論。

圖7 譯碼性能比較

圖8 降低最大迭代次數(shù)時(shí)的譯碼性能比較

3.4 譯碼平均迭代次數(shù)與譯碼時(shí)間分析

如圖9(a)所示，本文算法在平均迭代次數(shù)上相較于其他WBF譯碼算法有明顯改善，碼1在SNR=4.5 dB時(shí)，IMWBF-2SBF[14]、VSMWBF和SMWBF譯碼算法均需要平均迭代25次以上才可完成譯碼，本文算法平均需迭代約13次即可完成譯碼，降低比例約50%。通過(guò)觀(guān)察圖9(b)，碼2可獲得類(lèi)似改進(jìn)。

圖9 平均迭代次數(shù)比較

表2所示為SMWBF、VSMWBF和本文算法在SNR=4.5、5.0和5.5 dB時(shí)平均迭代次數(shù)對(duì)比情況。表3所示為3種算法在Matlab仿真平臺(tái)分別在SNR=4.5、5.0和5.5 dB時(shí)模擬對(duì)20萬(wàn)個(gè)碼字完成譯碼所需時(shí)間對(duì)比情況。碼1的參數(shù)分別設(shè)定為3.1和3.2節(jié)仿真得到的對(duì)應(yīng)參數(shù)值，實(shí)驗(yàn)所用計(jì)算機(jī)的配置為內(nèi)存16 GB，CPU為Intel Core i7-10875H 2.30 GHz的臺(tái)式計(jì)算機(jī)。

如表2所示，本文所提算法相較于SMWBF譯碼算法，平均迭代次數(shù)在3種SNR情況下分別降低至48.7%、43.7%和43.4%，大幅降低了迭代收斂速度。如表3所示,相比于VSMWBF譯碼算法，譯碼所需時(shí)間降低至28.2%、24.2%和26.1%，顯著縮短了算法的譯碼時(shí)間。

表2 碼1在不同SNR下各WBF譯碼算法的平均迭代次數(shù)

表3 碼1在不同SNR下各WBF算法對(duì)20萬(wàn)隨機(jī)碼字完成譯碼所需時(shí)間

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

本文通過(guò)發(fā)現(xiàn)多BF譯碼出現(xiàn)最大翻轉(zhuǎn)函數(shù)值小于零時(shí)，采用單BF接替譯碼會(huì)提升譯碼性能，提出了一種全新的多/單比特切換條件將一種提前終止的判決門(mén)限多BF機(jī)制和單BF譯碼串聯(lián)，形成了一種多/單比特切換的兩級(jí)譯碼機(jī)制。該機(jī)制融合了多BF譯碼收斂速度快和單BF譯碼算法低誤比特率的兩個(gè)優(yōu)點(diǎn)。仿真表明，該方法在加快譯碼時(shí)間和收斂速度的同時(shí)，譯碼性能較SMWBF和VSMWBF等譯碼算法有所提升，并在最大迭代次數(shù)設(shè)定較小時(shí)優(yōu)勢(shì)更為顯著。

為了消除整個(gè)譯碼器的循環(huán)翻轉(zhuǎn)現(xiàn)象，本文算法選擇了VSMWBF譯碼算法作為第二級(jí)譯碼器，代價(jià)是增加了額外的參數(shù)擴(kuò)大倍數(shù)β，因此在譯碼開(kāi)始時(shí)需對(duì)3個(gè)參數(shù)進(jìn)行仿真選取，增加了額外的工作量。在以后的研究中，是否有更簡(jiǎn)捷的方式來(lái)確定參數(shù)或者基于本文提出的機(jī)制可以選擇其他優(yōu)秀的單比特譯碼算法作為第二級(jí)譯碼器，需要繼續(xù)加以探究。