LDPC碼SPA算法的迭代加速

李韋健

北京交通大學 北京 100044

引言

1962年，Gallager率先提出了低密度奇偶校驗碼的概念[1]，其通過校驗矩陣的低密度特性盡可能降低了在與之相匹配的Tanner圖中出現環路的可能，因此在碼長較長的情況下其譯碼性能接近香農限，針對LDPC碼，和積算法（sum-product algorithm，SPA）是目前比較常用的譯碼方式。

SPA譯碼算法作為最經典的譯碼方式，其基本的譯碼思路是在校驗節點和變量節點之間不斷進行信息交互來完成譯碼[2-3]，在不斷迭代的過程中譯碼結果將符合所有校驗方程而得到碼字。

盡管SPA譯碼算法在譯碼性能方面極其優秀，但是同時也帶來了極高的計算復雜度，為了優化此問題，研究者們提出了LLR SPA算法[4]，將概率域SPA譯碼算法傳遞的概率信息轉換為對數似然比信息，從而由簡單的加法運算取代原來復雜的乘法計算過程，在降低譯碼難度的同時譯碼時間也被大幅減少。

LLR SPA算法的主要優點是在復雜度比較低的同時又有較高的譯碼效率，但這種方式也導致了邏輯資源被大量占用。為了解決該問題，研究者們用一種近似的方式來簡化計算過程，以損失少量計算精度的方式大大節省了邏輯資源，即Min-Sum（MS）算法[5]；以及通過增加一定的偏移量對損失的精度進行補償的Offset Min-Sum（OMS）算法。

SPA通常采用泛洪調度算法，即在迭代過程中校驗節點的更新和變量節點的更新是順序進行的，校驗節點的更新要在變量節點完成全部更新后進行，變量節點的更新也要在校驗節點全部更新后進行[6]。當選擇部分節點優先更新的調度算法時，可以有效加速迭代，提高收斂速度，黃捷等[7]采用動態調度的方式對信息進行有選擇的更新以此來加快收斂，陳發堂等[8]依據殘差值對振蕩較大的變量節點處理有效加快了迭代速度。

以上對SPA的改進算法中，LLR SPA、MS、OMS均降低了計算復雜度，并不能加速譯碼收斂，調度的改進雖然能加速迭代，但計算復雜度和控制開銷有較大增加。

受Gauss-Seidel法求解方程的啟發，本文在泛洪SPA中引入新的節點更新規則，確保節點更新時均利用鄰居節點的最新信息，減少了SPA的迭代次數，并改善其誤碼性能。需要指出，除了SPA，該算法還能直接應用上述各各種SPA的改進算法中，加速其譯碼收斂。

1 SPA簡介

SPA算法的譯碼方式是基于Tanner圖的，信道外信息輸入之后順著Tanner圖的邊在校驗節點和變量節點之間持續交換，兩種節點之間的信息輪流更新，兩種節點信息分別完成一次更新表示一次迭代，在匯總完所有信息之后進行譯碼判決并輸出譯碼結果。該過程中兩種節點更新產生的信息作為信道外信息，而一開始得自信道的信息作為內信息。

為便于闡述SPA的流程，譯碼中用到的符號如表1所示。

表1 符號定義

SPA譯碼算法：

校驗節點更新：

變量節點更新：

計算變量節點后驗概率：

譯碼判決：

2 迭代加速

在求解方程組時，Jacobi迭代法的迭代形式為：

Gauss-Seidel迭代法的迭代形式為：

由于Gauss-Seidel迭代法利用了當前迭代的最新結果，即式（6）中的部分，因而加快了迭代的收斂速度。仔細觀察可以發現SPA算法在校驗節點以及變量節點更新部分的式（2）和式（3）同樣可以利用這種方式進行改進，并且SPA譯碼算法中使用兩種不同節點之間進行信息交互，這種改進將更有效。

加速算法：

如圖1所示，變量節點收到信道初始信息之后進行信息的初始化，原始的信息更新步驟如下。

圖1 Tanner圖

將第n個變量節點第k次的傳遞的信息記為將第m個校驗節點第k次傳遞的信息記為

根據高斯迭代方式提出加速算法，在每次迭代中，校驗節點都能使用最新的迭代信息，則SPA中的變量節點信息更新過程變為：

3 仿真及分析

采用1/2碼率的（2304，1152）LDPC碼在AWGN信道下進行仿真，調制方式為BPSK，采用SPA譯碼，最大迭代次數為50。

圖2所示為SPA和加速算法1、以及引入松弛因子的加速算法2的平均迭代次數比較。從圖中可以看出，兩種加速算法所需的平均迭代次數均明顯好于SPA，且加速算法2較加速算法1有進一步加速性能。在信噪比超過1.6dB后，加速算法1所需迭代次數較SPA減少了43%，對加速算法2，這個減少量增加到56%。這意味著，采用加速算法后，只需不到SPA一半的迭代次數，便能達到同樣的錯誤性能。

圖2 （2304，1152）LDPC碼在不同算法下的迭代次數比較

仿真顯示三種算法誤比特率相差不大，并且由于兩種加速算法下譯碼收斂速度的提高，在平均迭代次數大幅減少的同時，其誤比特率較SPA也有明顯改善。

需要指出，由于兩種加速算法仍舊使用泛洪調度，并未增加任何控制開銷。計算復雜度和存儲開銷的增加更是微乎其微。

4 結束語

SPA每次迭代中，校驗節點與變量節點交替更新。將Gauss-Seidel迭代思想引入SPA中，使得每次節點更新均采用鄰居節點的最新信息。仿真結果表明，加速算法能夠減少一半以上的迭代次數，且錯誤性能亦有改善，而譯碼復雜度幾乎無任何增加。