基于OMS算法的LDPC譯碼算法改進?

吳少峰 楊春蘭 黎德文

（中國船舶集團有限公司第七二二研究所 武漢 430205）

1 引言

LDPC 碼是Gallager 于1962 年首先提出的［1］，Mackay 等人發現LDPC 碼在較低復雜度的情況下具有逼近容量限的性能，相較于Turbo 碼，LDPC 碼誤碼性能更好、錯誤平層更低、構造靈活、譯碼吞吐更高［2］，在無線通信系統中受到了廣泛的關注，如WiMAX、數字視頻廣播（DVB）、IEEE802.11［3］和ATSC［4］。特別是在增強移動寬帶（eMBB）場景中，3GPP選擇了它們作為第五代移動通信（5G）中數據傳輸的糾錯碼［5］。

如今主流的LDPC 編碼算法主要包括兩種，分別是根據生成矩陣G和根據具有特殊結構的校驗矩陣H 進行編碼。本文主要介紹其中的準循環碼編碼方法。準循環碼（QC-LDPC）具有存儲復雜度和編碼復雜度低的特點，因此3GPP決定在5G中使用兩種QC-LDPC 基矩陣，分別命名為BG1 和BG2，它們都支持速率兼容和數據擴展傳輸。5G 中使用基圖的具體結構如圖一所示。在本文中，我們以基圖BG1為基礎進行研究，因為BG1針對更大的塊長度和更高的速率，基圖BG1 有46 行，68 列，22 個信息位列。

LDPC碼譯碼方面，LDPC譯碼算法其根本的思想是變量節點和校驗節點進行不斷的迭代更新，每一次迭代更新過程就是變量節點和校驗節點之間信息交換的過程。當前誤碼性能最好的譯碼算法是基于后驗概率的BP 譯碼算法，但其計算復雜度高，實際情況難以應用。1998 年，Fossorier 等［6］提出最小和（MS）算法，通過比較出的最小值來更新校驗節點消息，有效降低了計算復雜度，同時也來帶了一定損失。為了進一步提高譯碼性能，許多學者又提出了一些改進算法：偏移最小和譯碼算法（OMS）［7～9］和歸一化最小和譯碼算法（NMS）［10～11］，兩種譯碼算法都是從LDPC 碼譯碼的迭代過程進行性能上的改進。

2 OMS算法改進

2.1 OMS算法

在介紹OMS 算法前我們首先對需要用到的變量進行一些注釋。

H(m),H(n)：相鄰的變量、校驗節點

βm,n,αm,n：校驗節點m 和變量節點n 節點之間的信息更新；

β1，β2，β3：BP、MS、OMS 算法中校驗節點m到變量節點n 的信息更新；

dc：校驗節點的度；

首先是校驗節點的迭代過程，在BP算法中：

可以看到BP算法中含有大量的雙曲正切函數的運算，運算復雜度非常高，譯碼過程相對復雜。因此，MS算法用近似值代替雙曲正切函數的運算，過程如下：

如果譯碼器解出了碼字或者達到了最大迭代次數后停止工作。在MS 譯碼算法中，校驗節點的近似處理會導致對校驗節點消息的過高估計，從而降低譯碼器的性能。為了克服這個問題，OMS算法和NMS算法應運而生。。

OMS 算法具體操作為在更新每個校驗節點時通過減去一個偏移因子β來改進性能：

其中

NMS 算法具體操作為在更新每個校驗節點時乘以一個小于1的歸一化常數α來提高性能：

從式（3～4）可知，目前不論是NMS 算法還是OMS算法，思路都是通過加入因子參與計算獲得更加精確的近似值，但不難發現在這兩種算法的迭代過程中加入因子的值是一個不隨迭代過程變化的固定值，這理論上會造成一定的近似偏差從而導致算法譯碼性能的損失。

2.2 改進的OMS算法

本文在OMS 算法的基礎上提出一種改進的OMS 算法，提升算法的譯碼性能，其本質就是要找到與BP 算法中雙曲正切函數更為接近的近似值，本文提出的改進之處主要體現在兩個方面，其一是加入參數γ作為乘性因子，目的是對每次迭代求偏移因子的范圍進行更加精確的控制，γ的取值參照文獻［12］設置為固定值；其二是通過密度進化理論求出每次迭代過程中的偏移因子值β，保存在儲存單元中，后續直接提取使用［13］。下面給出改進的OMS算法的校驗節點更新公式：

由式（2～3，5）可知，β1和β2有著相同的符號，即sgn(β1)=sgn(β2)且β1的數值小于β2，接下來我們先計算初次迭代時所需要的β值。

首先，根據β1和β2分別求出它們的均值E(|β1|)和E(|β2|)，初次迭代時的β值即為兩者之差。

其中，P（·）為γn對應的概率密度函數。

我們繼續計算第一次以后的迭代需要用到的β值，令式（5）中，可以得出X 的概率分布函數如公式（9）：

因此得出每個量化節點的概率密度函數：

故得出β3的均值：

最后得出后續每次迭代中β值：

3 改進的OMS算法仿真

本節包括對不同譯碼算法的譯碼性能仿真比較和不同算法的復雜度分析。在本節中，我們使用5G 標準下的基圖BG1 的LDPC 碼，碼率設置為0.5，碼長N=8448，其中信息位長度K=4224，移位因子Z為192，最大迭代次數設置為20次。

3.1 譯碼性能仿真比較

首先，我們探究偏移因子隨著迭代次數變化對改進OMS 算法譯碼性能的影響。上述仿真條件下，偏移因子β與迭代次數的關系如圖1所示。

圖1 偏移因子β 與迭代次數的關系

從圖1 我們可以看到，偏移因子值的大小隨著迭代次數的增加逐漸減小，在迭代次數到達第9 次時，偏移因子變為0。如式（8）和式（13），初次偏移因子值是MS 算法和BP 算法信息迭代過程中的均值之差，后續偏移因子值是OMS 算法和BP 算法信息迭代過程中的均值之差，隨著迭代過程的進行，兩者的差值逐漸變小，證明了迭代過程的正確性；另一方面，如圖1 可見，信噪比降低時，偏移因子有著更為明顯的下降趨勢。

其次，通過仿真得出我們需要的每次迭代過程中的最優偏移因子值后，我們將BP 算法、MS 算法、OMS 算法、NMS 算法以及改進后的OMS 算法的譯碼性能進行仿真，其中OMS 算法和NMS 算法的參數參照文獻［14］和文獻［15］設置，歸一化因子α=0.7，OMS算法中β=0.4，改進后OMS算法中固定參數γ=0.89，結果如圖2。

圖2 不同算法誤碼率性能比較

仿真結果表明，在誤碼率為10-5的情況下，本文提出的改進OMS 算法經過20 次譯碼迭代，譯碼性能相較于原OMS 算法提升了約0.13dB，較NMS算法提升了約0.15dB，其性能也更接近與BP算法。

最后，我們對不同譯碼算法的平均迭代次數進行仿真，結果如圖3。平均迭代次數是譯碼算法收斂能力的反映。從圖3 我們可以看到，MS 因其迭代過程中近似性不好，平均迭代次數更多，其算法復雜度更高。改進后的OMS 算法在相同條件下較原OMS 算法收斂速度更快，平均迭代次數更少，在相同迭代次數時也有更好的性能表現。

圖3 不同譯碼算法的平均迭代次數對比

3.2 復雜度分析

表1 和表2 分別表示了不同算法在FPGA 實現時譯碼過程中一次信息更新所需的硬件情況和不同運算的硬件需求情況，其中N 表示在（N，K）的LDPC 碼所對應的校驗矩陣中非零元素的個數，在FPGA硬件中異或操作和加法的完成方式是完全相同的。

表1 譯碼過程中信息一次更新所需運算情況

表2 不同運算的硬件需求情況

因此綜上仿真結果與數據分析，改進后的OMS算法相較于原OMS 算法，在消耗邏輯元器件提升14.2%和存儲位相同的情況下，在誤碼率為10-5量級有約0.13dB 的誤碼率性能提升；相較于NMS 算法，所消耗邏輯元器件增加了12.9%，消耗存儲位增加了6.2%，但譯碼性能在誤碼率為10-5量級時有0.15dB 的提升，在FPGA 實現時，此程度的復雜度提升是可以處理的，不會增加硬件成本。

4 結語

為了提高LDPC 碼在5G 移動通信中的糾錯性能，本文提出了一種改進的偏移最小和譯碼算法。在原OMS 算法的校驗節點更新環節中，首先加入一個乘性因子γ，其次通過密度進化理論計算出每次迭代的偏移因子，再運用于迭代過程中。仿真結果表明，本文提出的改進OMS 譯碼算法在相同的復雜度情況下對比現有的OMS 譯碼算法有約0.13dB 的增益，與NMS 算法相比在復雜度提升不到15%的條件下獲得約0.15dB的增益。