5G低密度奇偶校驗碼的低復雜度偏移最小和算法

陳發堂，張友壽，杜 錚

（重慶郵電大學通信與信息工程學院，重慶 400065）

（*通信作者電子郵箱1375743499@qq.com）

0 引言

低密度奇偶校驗（Low Density Parity Check，LDPC）碼作為一種最佳糾錯碼之一，具有顯著的編碼性能和效率，近年來受到了廣泛的研究關注［1］。在許多情況下，它展現出比Turbo碼更好的譯碼性能［2-3］，因此LDPC 碼被多種通信標準采用［4］。此外，已經確認在增強移動寬帶（enhanced Mobile BroadBand，eMBB）場景的5G系統中采用LDPC碼，滿足5G新無線（New Radio，NR）的高吞吐量需求。

LDPC碼是具有稀疏奇偶校驗矩陣的線性分組碼，其校驗矩陣可以用Tanner圖描述［5］，圖中包含變量節點和校驗節點，變量節點和校驗節點之間的連接用邊表示。置信傳播（Belief Propagation，BP）算法，也稱為和積（Sum-Product，SP）算法［6］通過迭代使LDPC 碼的譯碼性能接近香農極限。信息在變量節點和校驗節點之間反復傳遞。SP 算法雖然性能好，但是需要對數等復雜運算，給硬件實現帶來了困難。為了降低復雜度，提出了最小和（Min-Sum，MS）算法，將校驗節點中的對數轉換為比較和求和來簡化復雜的計算［7］。與SP算法相比，MS算法存在擴大校驗節點消息幅度值的錯誤，導致性能出現損失。為了減少錯誤，提高性能，提出了兩種改進算法，分別稱為歸一化最小和（Normalized-MS，NMS）算法和偏移最小和（Offset-MS，OMS）算法［8］。OMS算法使用求和系數改進MS中校驗節點的結果；NMS算法中使用乘法系數，雖然提高了譯碼性能，但是引入的修正系數與實際期望因子值的差異使得譯碼性能不如BP算法。而且MS和兩種改進算法要求在矩陣的每一行中計算第一和第二最小值，增加了復雜度。為進一步降低復雜性：單最小值最小和（single-minimum MS，smMS）算法僅使用一個常量糾正系數簡化了第二最小值計算，卻損失了部分性能［9］；在此基礎上提出的簡化可變權最小和（simplified variable weight MS，svwMS）算法［10-11］，引入隨迭代次數變化的加權因子維持第一和第二最小值的比例，性能得到了提升，卻增加了復雜度。

另一方面，近年來人們對LLR-BP譯碼算法的錯誤類型進行了研究［12］，其中一種就是變量節點的振蕩性。這種振蕩性被視為變量節點更新前后LLR 消息值符號發生了變化，最終導致譯碼器無法收斂［13-14］。變量節點的振蕩現象與檢驗矩陣的結構相關而與譯碼算法無關，出現在幾乎所有的BP算法中而且并沒有得到足夠的重視。

為了解決以上問題，一種新的改進偏移最小和的算法被提出。密度進化理論（Density Evolution，DE）是分析LDPC 碼譯碼算法性能，確定關鍵參數最佳值，并評估有限量化效果的一種重要方法。本文使用密度進化理論計算最佳的偏移因子值，克服了傳統OMS 算法的不足，提高了譯碼性能，并使用線性近似方法對獲取的最佳偏移因子進行近似處理，降低算法的實現復雜度。現有BP 算法中變量節點振蕩性問題也被討論，并提出了一種處理振蕩性的方法，將節點更新前后的LLR消息值加權處理。仿真結果說明與其他改進MS算法相比，所提算法不僅提高了譯碼器收斂速度，而且改進了在中高信噪比下的糾錯性能，且具有復雜度較低的優勢。

1 LDPC碼及其譯碼算法

1.1 LDPC碼的表示方法

5G NR 標準LDPC 碼的校驗矩陣H包括N列和M行，其中M=N-K，N代表變量節點數，M代表校驗節點數，可由基矩陣HBG定義。HBG包含Mb行和Nb列，基矩陣每個元素都映射到H中的一個維度為ZC×ZC子塊矩陣。用全0 矩陣去替換HBG中的-1 值，用循環置換矩陣I(pi，j)替換HBG中的1 值，其中I(pi，j)是維數為ZC×ZC的單位矩陣右循環pi，j次獲得，ZC是矩陣的擴展因子。LDPC 碼的校驗矩陣也可用Tanner 圖表示，如果H(i，j)=1，表示在Tanner 圖中第i校驗節點與第j變量節點之間相連。假設校驗矩陣如下：

對應的Tanner圖如圖1，其中ci和vi分別表示校驗節點和變量節點。令N(m)={n：H(m，n)=1}表示與校驗節點m相連的變量節點集合，M(n)={m：H(m，n)=1}表示與變量節點n相連的校驗節點集合，同時讓N(m) 表示排除變量節點n的變量節點集合，M(n)m表示排除檢驗節點m的變量節點集合。把校驗節點m傳遞給變量節點n的消息稱為C2V（Check-to-Variable）消息，用Lm→n表示；同理把變量節點n傳遞給校驗節點m的消息稱為V2C（Variable-to-Check）消息，用Zn→m表示。

圖1 LDPC碼的Tanner圖表示Fig.1 Tanner graph representation of LDPC codes

1.2 LLR-BP算法

LLR-BP 算法的核心是對校驗節點和變量節點之間傳遞的外部消息進行迭代處理，并利用校驗方程的約束提高譯碼的可靠度。譯碼步驟［15］如下。

1）初始化：計算變量節點vn接收到的信道消息值ln=。

2）迭代過程如下：

校驗節點更新（C2V）：

變量節點更新（V2C）：

3）硬判決：

4）終止條件：如果滿足X?HT=0 或者達到最大迭代次數時譯碼終止并返回譯碼結果；否則重復第2）步。

1.3 MS和OMS算法

MS 算法是對BP 算法迭代過程中的C2V 消息進行簡化，其余處理不變［16］，如式（5）所示。顯然MS算法計算比較簡單，但降低了譯碼性能。OMS 算法對MS 算法進行了改進如式（6）［17］，使得該算法的譯碼性能接近BP算法。

2 改進的OMS算法

2.1 基本知識

當把C2V 消息表示為符號和幅值時，從譯碼準則可以看出，符號用來譯碼，幅值表示消息的可靠性。與LLR-BP 算法相比，MS 算法高估了C2V 消息的幅值，所以譯碼性能下降。通過引入一個常數β來改善MS 算法中的校驗節點幅值過大的錯誤，被稱為OMS 算法。讓L1和L2分別代表LLR-BP 算法和MS算法的C2V消息如式（7）和（8）：

第一次迭代時的β可以通過式（9）計算得到，其中通過式（10）和式（11）［18］計算：

其中：dc代表檢驗節點的度，由無窮項的和組成，但通常取前幾次之和用作近似［18］。

Q(?) 代 表V2C 消息的概率密度函數（Probability Distribution Function，PDF），由信道消息初始化：Q(x)=，μ=4/N0，σ2=8/N0。

一般做法，會在所有的迭代中使用相同的β值以達到簡化譯碼處理的效果。然而，真實的β值與迭代次數有關。如果β的值隨著迭代次數變化而變化并用于迭代譯碼，這樣才能徹底改進譯碼性能，因此提出一種基于密度進化（Density Evolution，DE）計算每次迭代β值的方法。

在引進密度進化（DE）理論之前，說明兩點：1）在使用DE理論進行求值時，有必要對消息進行量化。需要的是V2C 消息的概率質量函數（Probability Mass Function，PMF）而不是概率密度函數［19］。2）使用Matlab工具可以獲取每次迭代中V2C消息的PMF。

2.2 基于DE的最優β值計算

首先，用L3表示OMS 算法中C2V 消息，如式（12），其中k代表迭代次數：

均值E(|L3|)由式（13）計算得到：

每個量化點的PMF由式（15）計算，其中s代表量化步長：

2.3 迭代次數與不同的譯碼算法

基于DE 理論計算得到的偏移因子βk與迭代次數的關系如圖2 所示。在相同的信噪比下經過幾次迭代過后，βk的值越來越小并收斂于0。這說明L3的概率密度函數非常接近L1的概率密度函數，而且偏移因子的值對譯碼的影響越來越小。說明本文所提譯碼算法是正確的。

圖2 偏移因子與迭代次數的關系Fig.2 Relationship between offset factor and number of iterations

理論上，在不同的信噪比下每次迭代使用不同的βk，則譯碼性能能夠得到提升。然而這會增加硬件復雜度。為了降低復雜度，對前5 次迭代的βk值采用加權平均處理［20］。改進的偏移因子的值如式（18），其中λk是加權平均系數，對應分別設置為λ1=0.25，λ2=0.25，λ3=0.2，λ4=0.2，λ5=0.1。使用該方法改進的β被稱為DEOMS-1算法。

另外從圖2 可以看出，在每個信噪比下偏移因子與迭代次數的曲線斜率近似于常量，并且易于計算。于是提出一種線性近似方法，這種關系可寫為：

于是式（18）可以近似等價于式（20）：

由于LDPC 碼的校驗矩陣中變量節點存在兩個及以上的環，同時節點正確和錯誤的LLR 消息在這些環中循環傳遞并在不同時刻到達該變量節點，造成變量節點振蕩現象，導致譯碼器無法收斂。該現象與校驗矩陣的結構有關，出現在幾乎所有的BP 譯碼算法中。然而最近所提出的譯碼算法并未采用特定方法消除變量節點的振蕩性。當變量節點發生振蕩，很難區分更新前后的LLR 消息哪個是正確的，或者達到穩定狀態。為了減弱其對迭代譯碼的影響，本文對變量節點更新前后的LLR 消息進行加權處理，減弱變量節點LLR 消息的振蕩，提高譯碼的收斂性。具體處理規則如下：

用式（21）計算得到的Zn→m(xn)值替換式（2），其中k為迭代次數，μ是加權系數，經實驗本文最終選取μ等于0.5，則式（21）可以簡化為：

該方法稍微增加了復雜度，但可以很好地降低振蕩影響，加快收斂。基于以上方法提出vwDEOMS-3算法。

3 仿真結果分析

本文使用5G NR 標準構造的準循環LDPC（Quasi Cyclic Low Density Parity Check，QC-LDPC）碼對不同譯碼算法LLRBP、MS、NMS、OMS的譯碼性能進行仿真并與本文所提出的低復雜度偏移最小和算法的譯碼性能進行比較。選擇5G NR LDPC 碼的基矩陣HBG2，采用信息長度K=1 000，碼字長度N為2 500，碼率R為0.4，評估了不同信噪比下各譯碼算法的誤碼率性能。在碼率為0.4時NMS 算法的歸一化因子取值0.65。所有的仿真都在加性高斯白噪聲（Additive White Gaussian Noise，AWGN）信道模型下，經過BPSK（Binary Phase Shift Keying）調制，最大迭代次數設置為30，每個信噪比下設置幀數為2 000。

圖3 展示了不同譯碼算法的誤比特率（Bit-Error Rate，BER）性能比較，顯然LLR-BP 譯碼算法擁有最佳的性能。在BER 為10-5時，相對于LLR-BP 算法，MS 算法性能損失接近1.2 dB，這是校驗節點的幅值過大造成的。與MS 算法相比，OMS 算法與NMS 算法的譯碼性能可以獲得0.6～0.8 dB 的增益，但是還與LLR-BP 算法的譯碼性能相差0.4～0.6 dB，說明雖然引入了校正因子對MS算法進行改進，但是該校正因子并不是最佳的值。DEOMS-1 算法使用更準確的偏移因子，在BER 為10-5時，相比MS 算法可以獲得大約1 dB 的增益。在BER 為10-5時，DEOMS-2算法與DEOMS-1算法誤碼性能非常接近，大約只有0.01 dB 的差距，說明線性近似處理是合理有效的；而vwDEOMS-3 算法比OMS 算法的性能提高約0.5 dB，比NMS 算法提高約0.3 dB，與LLR-BP 算法相比性能上也只相差近0.1 dB。通過使用更接近真實的偏移因子和削弱變量節點的振蕩性，所提算法可以實現較好的譯碼性能和迭代性能。

圖3 不同算法的誤比特率性能對比Fig.3 BER performance comparison of different algorithms

4 復雜度分析

結合上面的分析，表1 給出了不同譯碼算法的校驗節點更新操作中的計算復雜度。可以看出LLR-BP 算法需要更多的乘法操作，復雜度最高，其次是MS 算法、NMS 算法、OMS 算法。DEOMS-1 算法中的偏移因子是基于密度進化計算的，增加了些許復雜度，但極大提高了譯碼性能，考慮到這一點，DEOMS-2 算法采用線性近似方法，進一步降低計算的復雜度。vwDEOMS-3 算法對變量節點的加權操作在硬件資源上并不需要多余的乘法器，只是信息位的右移。本文使用Matlab 計算最優的偏移因子值并保存在硬件中，而不會消耗多余的硬件資源。經典的OMS 算法通過蒙特卡洛方法獲取偏移因子或者僅僅基于DE 計算第一次迭代時得到的偏移因子的值，需要大量的加法和比較操作，計算復雜度總體來說較高。總的來說，DEOMS 算法擁有較低的計算復雜度和較少的譯碼延遲，譯碼性能也有0.3～0.5 dB的提升。

表1 不同算法校驗節點消息計算復雜度Tab.1 Check node message computational complexities of different algorithms

收斂速度是衡量LDPC 算法復雜度和譯碼性能的另一個關鍵指標，圖4 使用平均迭代次數來評估各種算法的收斂速度。顯然，相比其他算法，MS 算法和OMS 算法需要更多的迭代次數。可以觀察到，與MS算法相比，所提出的DEOMS算法的平均迭代次數得到顯著降低。盡管LLR-BP 算法的迭代次數略低于所提的DEOMS算法，但由于其檢驗節點操作的復雜度較高，每次迭代都可能花費大量的計算時間，而DEOMS 算法擁有較小的譯碼延遲。從圖中可得到的另一個重要結論是DEOMS-2算法的平均迭代次數非常接近DEOMS-1算法，這證明DEOMS-2算法對迭代次數的影響非常輕微。而vwDEOMS-3 算法的平均迭代次數比DEOMS-1/2 算法有所改進，說明該算法是合理有效的。

圖4 不同算法的平均迭代次數Fig.4 Average numbers of iterations of different algorithms

5 結語

本文提出了一種5G LDPC 碼的低復雜度偏移最小和算法，所提算法的優點是使用密度進化理論獲得了最佳的偏移因子，并對其使用線性近似方法進行處理，降低了計算復雜度；提出了一種處理變量節點振蕩性的方法，對變量節點LLR消息加權處理，加快了譯碼器的收斂。仿真結果表明，對于5G NR 標準的QC-LDPC 碼，所提算法與MS 及其改進算法相比存在誤碼性能和迭代次數優勢。