5G低密度奇偶校驗(yàn)碼的低復(fù)雜度偏移最小和算法

陳發(fā)堂，張友壽，杜 錚

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

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

0 引言

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

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

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

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

1 LDPC碼及其譯碼算法

1.1 LDPC碼的表示方法

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

對(duì)應(yīng)的Tanner圖如圖1，其中ci和vi分別表示校驗(yàn)節(jié)點(diǎn)和變量節(jié)點(diǎn)。令N(m)={n：H(m，n)=1}表示與校驗(yàn)節(jié)點(diǎn)m相連的變量節(jié)點(diǎn)集合，M(n)={m：H(m，n)=1}表示與變量節(jié)點(diǎn)n相連的校驗(yàn)節(jié)點(diǎn)集合，同時(shí)讓N(m) 表示排除變量節(jié)點(diǎn)n的變量節(jié)點(diǎn)集合，M(n)m表示排除檢驗(yàn)節(jié)點(diǎn)m的變量節(jié)點(diǎn)集合。把校驗(yàn)節(jié)點(diǎn)m傳遞給變量節(jié)點(diǎn)n的消息稱為C2V（Check-to-Variable）消息，用Lm→n表示；同理把變量節(jié)點(diǎn)n傳遞給校驗(yàn)節(jié)點(diǎ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 算法的核心是對(duì)校驗(yàn)節(jié)點(diǎn)和變量節(jié)點(diǎn)之間傳遞的外部消息進(jìn)行迭代處理，并利用校驗(yàn)方程的約束提高譯碼的可靠度。譯碼步驟［15］如下。

1）初始化：計(jì)算變量節(jié)點(diǎn)vn接收到的信道消息值ln=。

2）迭代過程如下：

校驗(yàn)節(jié)點(diǎn)更新（C2V）：

變量節(jié)點(diǎn)更新（V2C）：

3）硬判決：

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

1.3 MS和OMS算法

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

2 改進(jìn)的OMS算法

2.1 基本知識(shí)

當(dāng)把C2V 消息表示為符號(hào)和幅值時(shí)，從譯碼準(zhǔn)則可以看出，符號(hào)用來譯碼，幅值表示消息的可靠性。與LLR-BP 算法相比，MS 算法高估了C2V 消息的幅值，所以譯碼性能下降。通過引入一個(gè)常數(shù)β來改善MS 算法中的校驗(yàn)節(jié)點(diǎn)幅值過大的錯(cuò)誤，被稱為OMS 算法。讓L1和L2分別代表LLR-BP 算法和MS算法的C2V消息如式（7）和（8）：

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

其中：dc代表檢驗(yàn)節(jié)點(diǎn)的度，由無窮項(xiàng)的和組成，但通常取前幾次之和用作近似［18］。

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

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

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

2.2 基于DE的最優(yōu)β值計(jì)算

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

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

每個(gè)量化點(diǎn)的PMF由式（15）計(jì)算，其中s代表量化步長(zhǎng)：

2.3 迭代次數(shù)與不同的譯碼算法

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

圖2 偏移因子與迭代次數(shù)的關(guān)系Fig.2 Relationship between offset factor and number of iterations

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

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

于是式（18）可以近似等價(jià)于式（20）：

由于LDPC 碼的校驗(yàn)矩陣中變量節(jié)點(diǎn)存在兩個(gè)及以上的環(huán)，同時(shí)節(jié)點(diǎn)正確和錯(cuò)誤的LLR 消息在這些環(huán)中循環(huán)傳遞并在不同時(shí)刻到達(dá)該變量節(jié)點(diǎn)，造成變量節(jié)點(diǎn)振蕩現(xiàn)象，導(dǎo)致譯碼器無法收斂。該現(xiàn)象與校驗(yàn)矩陣的結(jié)構(gòu)有關(guān)，出現(xiàn)在幾乎所有的BP 譯碼算法中。然而最近所提出的譯碼算法并未采用特定方法消除變量節(jié)點(diǎn)的振蕩性。當(dāng)變量節(jié)點(diǎn)發(fā)生振蕩，很難區(qū)分更新前后的LLR 消息哪個(gè)是正確的，或者達(dá)到穩(wěn)定狀態(tài)。為了減弱其對(duì)迭代譯碼的影響，本文對(duì)變量節(jié)點(diǎn)更新前后的LLR 消息進(jìn)行加權(quán)處理，減弱變量節(jié)點(diǎn)LLR 消息的振蕩，提高譯碼的收斂性。具體處理規(guī)則如下：

用式（21）計(jì)算得到的Zn→m(xn)值替換式（2），其中k為迭代次數(shù)，μ是加權(quán)系數(shù)，經(jīng)實(shí)驗(yàn)本文最終選取μ等于0.5，則式（21）可以簡(jiǎn)化為：

該方法稍微增加了復(fù)雜度，但可以很好地降低振蕩影響，加快收斂?；谝陨戏椒ㄌ岢鰒wDEOMS-3算法。

3 仿真結(jié)果分析

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

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

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

4 復(fù)雜度分析

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

表1 不同算法校驗(yàn)節(jié)點(diǎn)消息計(jì)算復(fù)雜度Tab.1 Check node message computational complexities of different algorithms

收斂速度是衡量LDPC 算法復(fù)雜度和譯碼性能的另一個(gè)關(guān)鍵指標(biāo)，圖4 使用平均迭代次數(shù)來評(píng)估各種算法的收斂速度。顯然，相比其他算法，MS 算法和OMS 算法需要更多的迭代次數(shù)?？梢杂^察到，與MS算法相比，所提出的DEOMS算法的平均迭代次數(shù)得到顯著降低。盡管LLR-BP 算法的迭代次數(shù)略低于所提的DEOMS算法，但由于其檢驗(yàn)節(jié)點(diǎn)操作的復(fù)雜度較高，每次迭代都可能花費(fèi)大量的計(jì)算時(shí)間，而DEOMS 算法擁有較小的譯碼延遲。從圖中可得到的另一個(gè)重要結(jié)論是DEOMS-2算法的平均迭代次數(shù)非常接近DEOMS-1算法，這證明DEOMS-2算法對(duì)迭代次數(shù)的影響非常輕微。而vwDEOMS-3 算法的平均迭代次數(shù)比DEOMS-1/2 算法有所改進(jìn)，說明該算法是合理有效的。

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

5 結(jié)語

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