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

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

0 引 言

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

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

1 基于LDPC碼的BF譯碼算法

1.1 基本定義

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

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

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

1.2 SMWBF譯碼算法

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

(3)

SMWBF算法對應的翻轉(zhuǎn)函數(shù)為

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

SMWBF算法步驟詳述如下：

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

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

步驟3 計算伴隨式：

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

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

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

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

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

1.3 VSMWBF譯碼算法

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

步驟5 翻轉(zhuǎn)最大En值所對應的比特，同時將其幅值擴大β倍。

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

2 本文算法描述

圖1 多/單BF切換機制

2.1 第一級譯碼器

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

如圖3所示，若對殘留錯誤比特依舊進行多BF譯碼會導致譯碼性能不佳，而使用單BF譯碼來接替譯碼任務，相較于此時停止譯碼，性能會得到進一步提升，故本文提出了多BF向單BF切換的兩級WBF譯碼機制。

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

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

2.2 第二級譯碼器

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

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

2.3 本文算法步驟及流程圖

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

圖4 算法流程

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

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

步驟3 計算伴隨式：

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

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

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

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

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

3 仿真分析

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

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

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

圖5 γ取值對譯碼性能的影響

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

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

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

圖6 α和β的取值對譯碼性能的影響

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

3.3 譯碼性能分析

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

圖7 譯碼性能比較

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

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

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

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

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

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

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

表3 碼1在不同SNR下各WBF算法對20萬隨機碼字完成譯碼所需時間

4 結(jié)束語

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

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