基于多/單比特切換機制的LDPC碼兩級WBF算法

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

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

0 引 言

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

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

1 基于LDPC碼的BF譯碼算法

1.1 基本定義

用(N,K)(dv,dc)表示有固定行重dc、列重dv和碼率為R=K/N的規則二進制LDPC碼，其中，N為碼長，K為信息位，其對應的奇偶校驗矩陣記為H=[hmn]，H為M行N列矩陣。用集合N(m)={n∶hmn=1}表示H第m行中所有“1”的位置，即與校驗節點m相連的變量節點集合；用集合M(n)={m∶hmn=1}表示H第n列中所有“1”的位置，即與變量節點n相連的校驗節點集合。設發送碼字c={c1,c2,…,cn}經過二進制相移鍵控(Binary Phase Shift Keying, BPSK)調制后得到雙極性碼字序列{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)的高斯白噪聲。根據硬判決規則得到二進制碼字序z={z1,z2,…,zn},其中：

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

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

1.2 SMWBF譯碼算法

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

(3)

SMWBF算法對應的翻轉函數為

式中，α為權重因子，用來修正變量節點對判決帶來的過度影響。

SMWBF算法步驟詳述如下：

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

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

步驟3 計算伴隨式：

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

步驟4 由式(4)計算各個變量節點的翻轉函數。

步驟5 翻轉最大En值所對應的比特：

步驟6k=k+1,轉至步驟3。

步驟7 輸出zk，譯碼結束。

1.3 VSMWBF譯碼算法

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

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

步驟6k=k+1，算法轉至步驟2。

2 本文算法描述

圖1 多/單BF切換機制

2.1 第一級譯碼器

圖2 第一次出現時的殘留錯誤比特

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

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

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

2.2 第二級譯碼器

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

表1 第一級譯碼器陷入循環的概率

2.3 本文算法步驟及流程圖

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

圖4 算法流程

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

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

步驟3 計算伴隨式：

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

步驟4 由式(4)計算各個變量節點的翻轉函數En。

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

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

步驟8 譯碼結束，輸出zk。

3 仿真分析

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

3.1 閾值參數γ的選取

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

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

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

3.2 加權因子α和擴大倍數β的選取

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

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

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

3.3 譯碼性能分析

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

圖7 譯碼性能比較

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

3.4 譯碼平均迭代次數與譯碼時間分析

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

圖9 平均迭代次數比較

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

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

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

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

4 結束語

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

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