空間耦合低密度奇偶校驗碼殘差滑窗譯碼算法

周 華 李子杰

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

1 引言

低密度校驗矩陣定義的卷積碼由Jimenez等人[1]1999年首次提出。與分組碼相比，低密度奇偶校驗碼(Low-Density Parity-Check, LDPC)卷積碼在性能上卷積增益更大[2]。由于LDPC卷積碼具有半無限空間交織校驗矩陣結構，故其被命名為空間耦合低密度奇偶校驗(Spatially-Coupled LDPC, SCLDPC)碼[3]，其具有置信傳播(Belief Propagation,BP)譯碼閾值接近對應規則LDPC碼的最大后驗概率(Maximum A Posterior, MAP)譯碼閾值的特性[4,5]。

SC-LDPC碼研究主要包括編碼碼型的構造和譯碼方法的優化。針對SC-LDPC碼型的構造，2016年，Koganei等人[6]提出一種空間耦合強度不均勻的編碼方式，結果表明該碼與具有均勻度分布的SC-LDPC碼相比，具有更好的譯碼性能。2019年，Kwak等人[7]進一步提出了利用線性規劃方法設計非均勻度分布的非規則SC-LDPC碼，一定程度上提升了SC-LDPC碼在二進制擦除信道下的譯碼性能。為了降低誤碼率和譯碼復雜度，Dehaghani等人[8]在2022年提出了一種基于小單鏈和循環結構相結合的碼字集成方法。在譯碼研究方面，Iyengar等人[9]在2012年提出應用于SC-LDPC碼的滑動窗口譯碼(Sliding Window Decoding, SWD)方法，與傳統方案相比，較大幅度降低了譯碼復雜度與時延。2018年，Ali等人[10]針對滑窗譯碼提出了提前終止、消息重用(Message Reuse, MR)和有效信息放大3種方法，同時改善了滑窗譯碼的譯碼性能、復雜度和延時。同年，Zhu等人[11]針對滑窗譯碼中存在錯誤傳播的現象，引入了同步機制算法。2020年，吳皓威等人[12]將分層譯碼引入窗口譯碼中，進一步降低SC-LDPC碼的譯碼延時。張婭妹等人[13]也在當年提出了窗口擴展(Window Extension SWD, WE-SWD)滑窗譯碼方法，從而提高滑窗譯碼性能。

滑窗譯碼存在時延較高和譯碼性能較差的局限性，窗口內更新差異值較小的邊信息對提高譯碼性能收益較低，且由于窗口內目標符號邊信息更新受到前續窗口譯碼時關聯邊信息的影響，所以其更容易受到錯誤傳播的干擾。為了提高SC-LDPC碼滑窗譯碼性能和抑制錯誤傳播，本文提出基于動態殘差的滑窗譯碼(Residual SWD, RSWD)算法。該算法通過計算殘差的方式動態選擇窗口內更新前后邊信息差異最大的邊優先更新，降低邊信息無效更新的頻率，減少譯碼平均迭代次數，提高窗內譯碼收斂速度。仿真結果表明：相比于傳統SWD算法，RSWD算法在窗口中各位置的誤比特數明顯降低，抑制錯誤傳播現象更明顯；在高信噪比區域或者低迭代次數的情況下，RSWD算法的誤碼率性能均優于SWD算法；將動態殘差應用到消息復用和窗口擴展兩種窗譯碼算法中，以犧牲較少復雜度為代價，提升窗譯碼性能。

2 空間耦合LDPC碼

SC-LDPC碼的構造基于原模圖，原模圖是由校驗節點和變量節點組成的小型二分圖，其與Tanner圖結構類似。對單個原模圖復制多次，然后通過邊置換交織和擴展[14]的方式進行空間耦合可形成不同碼長的SC-LDPC碼[15]。規則LDPC碼原模圖的度分布為(J, K)，其中J表示原模圖中連接到變量節點的邊數，K表示原模圖中連接到校驗節點的邊數。

圖1展示SC-LDPC碼原模圖的構造過程，其中圖1(a)所示是一個度分布為(3, 6)LDPC碼原模圖單元，其中V代表變量節點，C代表校驗節點。將單原模圖復制L次，如圖1(b)所示，形成耦合長度為L的原模圖序列，t為原模圖序列的起始時刻，t+L-1為序列的末尾時刻。圖1(c)展示了邊緣擴展的過程，將t時刻原模圖的邊端變量節點連接到位置為t,t+1,t+2,···,t+w的檢驗節點上，w為耦合寬度。圖1(d)表示耦合長度為L且w=2時，將圖1(b)中每個時刻的單原模圖重復圖1(c)中邊緣擴展后，形成的SC-LDPC原模圖鏈，在原模圖鏈右側需要額外的w個校驗節點終止邊緣擴展。

圖1 SC-LDPC碼原模圖的構造過程

單原模圖包含Jg個校驗節點和Kg個變量節點，其中Jg=J/gcd(J, K),Kg=K/gcd(J, K),gcd(J, K)表示J和K的最大公約數。該原模圖對應的矩陣稱為基矩陣，大小為Jg×Kg。圖1(a)中度分布為(3, 6)單原模圖對應的基矩陣為B=[3 3]，對其進行邊緣擴展之后，基矩陣被劃分為分量基矩陣Bi,i=0,1,2,···,w。圖1(c)中耦合寬度w=2時，對應的分量基矩陣B0=B1=B2=[1 1]，將原模圖鏈中的每個單原模圖轉為矩陣形式排列可以得到SC-LDPC碼的基矩陣Bsc，如式(1)所示

將Bsc中“1”和“0”分別替換為M0×M0的單位循環移位矩陣和M0×M0的全零矩陣，M0定義為擴展因子，可得到SC-LDPC碼的奇偶校驗矩陣Hsc，大小為(L+w)JgM0×LKgM0。該方法生成的SC-LDPC碼的碼率RL，如式(2)所示

3 SC-LDPC碼滑窗譯碼和錯誤傳播現象

LDPC碼常用的譯碼方法為BP譯碼，將接收到的碼字信息在變量節點和校驗節點之間迭代更新，直到滿足奇偶校驗方程或者達到最大迭代次數。由于SC-LDPC碼的奇偶校驗矩陣具有對角帶結構，可以在尺寸為W的窗口內運行BP譯碼[16]，其中W為窗口大小，w+1≤W≤L, W∈Z+。

圖2展示了滑窗譯碼過程，即SWD算法。窗口矩陣HWD的校驗節點數量為W×Jg×M0，變量節點數量為W×Kg×M0，窗口尺寸為W JgM0×WKgM0。首先窗口矩陣位于校驗矩陣左上角，在整個窗口內執行BP譯碼，在整個窗口譯碼結束后只輸出目標符號，目標符號譯碼完成之后，整個窗口向右下方滑動JgM0行和KgM0列，在下一個窗口內繼續對目標符號進行譯碼，直到譯碼窗口移出校驗矩陣。

圖2 SC-LDPC碼滑窗譯碼

在SC-LDPC碼中，由于原模圖鏈中相鄰的w個原模圖單元具有耦合關系，即目標符號的校驗節點與相鄰原模圖的部分信息節點相連，因此每個窗口內目標符號的信息更新受到前續窗口譯碼時關聯邊信息的影響，相關的邊信息也將參與每個窗口的奇偶校驗判斷。

圖3為w=2的窗口譯碼示意圖，編號①的碼塊信息是來自時刻p的窗口的輸出對數似然比，該碼塊將作為目標符號相關信息參與到第p+1時刻窗口的譯碼中。依據耦合寬度w的取值，第p時刻的碼塊信息將會對連續w個時刻窗口譯碼產生影響，因此如果當前窗口未能譯碼成功，不可靠的目標符號的判決對數似然比信息會傳遞到后續的w個窗口中從而可能觸發一系列碼塊的譯碼錯誤，這種現象稱為滑窗譯碼的錯誤傳播[11]。在這種情況下，錯誤傳播在窗與窗之間有可能引發“譯碼失控”，產生“爆炸式”的譯碼錯誤。

圖3 滑窗譯碼中的錯誤傳播

下面介紹兩種SC-LDPC碼滑窗譯碼算法的優化算法，本文所提算法將與其進行對比。

SWD算法將目標符號接收先前窗口的判決對數似然比作為目標符號相關信息參與當前窗口譯碼。文獻[10]中提出消息復用滑窗譯碼(MR-SWD)算法，將先前窗口的邊信息(非判決信息)作為只讀數據參與當前窗口譯碼。當窗口位置滑動離開初始位置后，窗口僅對新進入窗口的區域初始化，且目標符號相關信息位置開始接收先前窗口保留的只讀邊信息對數似然比。

SWD算法中窗口尺寸固定不變，文獻[13]提出窗口擴展滑窗譯碼(WE-SWD)算法，根據目標符號的平均對數似然比調節窗口大小。首先設置窗口初始大小Wmin和窗口最大值Wmax，定義閾值θ為碼字在特定信噪比所有窗口從初始值Wmin到最大值Wmax計算出的對數似然比累計平均值。如果計算出的目標符號對數似然比小于閾值θ，則遞增當前窗口大小并重新開始迭代譯碼，重復該過程直到目標符號滿足閾值條件或者窗口大小達到預設最大值。

4 SC-LDPC碼殘差滑窗譯碼算法

在信息傳輸過程中，由于受噪聲和干擾的影響，接收序列中會出現一些可靠性較低的節點，這些節點可能導致譯碼算法難以收斂。在某種意義上，可靠性較低的節點比可靠性較高的節點更需要接收新的有用信息以便完成正確的判決[17]。在一個窗口內并不是所有的信息更新對實現譯碼收斂都具有相同的作用，更新前后差異較小的邊信息值對譯碼收斂幾乎是冗余的，且對譯碼性能提升幾乎無益，優先更新迭代前后差異較大的邊信息更有助于譯碼收斂和提高譯碼效率。本文提出的RSWD算法，通過動態選擇窗口內可靠度最低的邊信息優先傳輸，降低邊信息無效更新的頻率，加快窗口內譯碼的收斂速度，提高譯碼效率，減少譯碼平均迭代次數，從而提高譯碼性能和降低整體譯碼時延。

RSWD算法將邊信息更新前后的變化量稱為殘差，用于篩選窗內邊信息更新的優先級，如式(3)所示

假設有碼字序列X=[x1,x2,...,xn]，其中n表示碼長，經二進制相移鍵控(Binary Phase Shift Keying, BPSK)調制后，經加性高斯白噪聲(Additive White Gaussian Noise, AWGN)信道傳輸，接收序列表示為Y=[y1,y2,...,yn]，對接收序列進行RSWD算法譯碼，其具體步驟描述如下：

步驟1 參數設置。輸入擴展因子M0、窗口尺寸W、迭代上限I和耦合長度L。

步驟2 窗口初始化。當窗口位于校驗矩陣左上角(p=1)時，基于接收序列對譯碼窗口進行邊信息初始化，初始化信息的計算如式(4)、式(5)所示，其中Vj表示當前窗口第j個變量節點，rVj表示第j個變量節點接收的信道觀測值，MVj→Ci表示第j個變量節點傳遞給第i個校驗節點的邊信息，E和HR矩陣均初始化為全0矩陣

當窗口開始滑動(p＞1)后，如圖2所示，對新進入窗口信息窗口右下角區域初始化(黃色的信息塊)，目標符號信息位接收前一窗口的輸出對數似然比LLR。

步驟3 迭代譯碼。根據式(3)在窗口內計算殘差矩陣HR，并搜索HR獲得最大殘差值對應的校驗節點Ci和變量節點Vj，更新邊信息ECi→Vj并對該邊信息的殘差值更新置0，分別如式(6)和式(7)所示，i→Vj表示第l次迭代中第i個校驗節點傳遞給第j個變量節點的邊信息， HRCi→Vj表示更新前后ECi→Vj的殘差值，→Ci表示第l次迭代中將第j個變量節點傳遞給第i個校驗節點的邊信息，N(Ci)/Vj表示除變量節點Vj外與校驗節點Ci相連的變量節點集合

通過式(8)，更新變量節點Vj與相連校驗節點Ca{Ca|Ca ∈N(Vj)/Ci} 邊信息，N(Vj)/Ci表示除校驗節點Ci外與變量節點Vj相連的校驗節點集合

通過式(9)，更新校驗節點Ca與相連變量節點Vb{Vb|Vb ∈N(Ca)/Vj}所在邊信息的殘差值

步驟4 譯碼判決。通過式(10)計算本次迭代結束后的目標符號輸出對數似然比，表示第j個變量節點經過l次迭代后輸出的對數似然比，xVj表示對的硬判決輸出，如式(11)所示

當達到最大迭代次數或者 [xV1,xV2,...,xVj]符合奇偶校驗，則當前窗口內停止迭代，并輸出判決結果；否則返回步驟3繼續譯碼。

步驟5 窗口滑動。當譯碼窗口完成當前目標符號譯碼后，輸出目標符號譯碼結果，窗口向右下方滑動JgM0行和KgM0列，然后返回步驟2，譯碼下一個目標符號。

上述譯碼流程中，由于當前窗口目標符號的譯碼結果將傳遞給后續窗口，其判定結果會影響后續目標符號的譯碼準確性。因此如果在達到最大的譯碼迭代次數后仍無法滿足奇偶校驗，不可靠的信息會導致當前窗口目標符號譯碼失敗，亦或傳遞給后續窗口，導致各窗口輸出的目標符號誤碼率上升。RSWD算法根據殘差確定信息更新的優先順序，在當前窗口內選擇可靠度最低的邊信息優先更新，從初始窗口譯碼目標符號開始時就可減少不可靠信息傳遞概率。當窗口滑動有新的信息進入窗口時，與前窗口傳入的邊信息相比，新進入窗口的邊信息殘差值較大，有助于窗口將譯碼重心側重到新入信息，提高了窗口內邊信息更新的精準性和窗口輸出的可靠性，能夠抑制滑窗譯碼中錯誤傳播現象。

為驗證殘差譯碼的有效性，圖4展示了碼長為714、耦合長度L為24、窗口大小W為8、信噪比為4 dB的RSWD算法和SWD算法在窗口各位置的誤碼率(Bit Error Ratio, BER)曲線。由圖可知，窗口中每個位置RSWD算法的誤碼率均優于SWD算法，在窗口內使用殘差譯碼能夠有效抑制錯誤傳播。

圖4 SWD算法和RSWD算法窗口各位置的誤碼率比較

5 仿真分析

圖5展示了本文仿真所使用的SC-LDPC碼校驗矩陣。如無特殊說明，仿真采用碼長714、碼率為0.625、耦合長度L為24、耦合寬度w為3、擴展因子M0為7的矩陣，即單位矩陣為7×7的SC-LDPC碼，矩陣內陰影部分的數字表示單位矩陣循環右移的位數。仿真采用BPSK調制，基于AWGN信道。

圖5 仿真使用的SC-LDPC碼校驗矩陣

圖6給出了所提RSWD算法同SWD算法、MRSWD算法和MR-RSWD算法在窗口大小為8，最大迭代次數為50次時誤碼率曲線，MR-RSWD算法是在MR-SWD算法基礎上引入殘差所得。由圖可知，引入殘差的消息復用滑窗譯碼(MR-RSWD)算法性能最優異，殘差滑窗譯碼(RSWD)算法性能優于消息復用滑窗譯碼(MR-SWD)算法和滑窗譯碼(SWD)算法。在誤碼率為10-5時，SWD算法信噪比需要大約4.96 dB, MR-SWD算法需要約4.91 dB, RSWD算法需要約4.78 dB，而消息復用下的RSWD算法(MR-RSWD)需要4.72 dB，相較于滑窗譯碼、消息復用下滑窗譯碼、殘差滑窗譯碼分別提升約0.24 dB, 0.19 dB, 0.06 dB。

圖6 SWD算法、MR-SWD算法、RSWD算法和MR-RSWD算法譯碼性能比較

圖7給出了4種算法在信噪比分別為4 dB和5 dB時譯碼性能與最大迭代次數的關系。如圖7所示，MR-RSWD算法為達到相同誤碼率，所需迭代次數最少，其次是RSWD算法。在信噪比為5 dB、BER為10-5量級時，SWD算法、MR-SWD算法需30次迭代，而RSWD算法、MR-RSWD算法僅需15次迭代，在同等誤碼率情況下，引入殘差可有效降低譯碼迭代次數，文獻[10]所提MR-SWD算法和MR-RSWD算法在最大迭代次數30和20次之前時性能相較于SWD算法和RSWD算法有所下降。

圖7 最大迭代次數對SWD算法、MR-SWD算法、RSWD算法和MR-RSWD算法誤碼率性能的影響

圖8給出了所提RSWD算法同SWD算法和WESWD算法誤碼率性能比較，其中初始窗口大小Wmin為8，最大窗口Wmax為10，最大迭代次數為50，WE-RSWD曲線是在WE-SWD算法的基礎上引入殘差所得。由圖可見，WE-RSWD算法性能優勢明顯，RSWD算法和WE-SWD算法在中低信噪比下性能接近，在信噪比4 ～5 dB，RSWD算法譯碼性能略差于WE-RSWD算法。在BER為10-5量級時，WE-RSWD算法相較于SWD算法、RSWD算法和WE-SWD算法分別有0.45 dB, 0.24 dB和0.18 dB性能優勢。

圖8 SWD算法、WE-SWD算法、RSWD算法和WE-RSWD算法譯碼性能比較

圖9所示為在信噪比為4.5 dB下，最大迭代次數對不同算法誤碼率性能的影響。由圖可見，本文所提算法有明顯的瀑布區，隨著迭代次數增多，RSWD算法和WE-SWD算法誤碼曲線下降迅速，WERSWD算法誤碼率性能優于其余算法。在誤碼率為7×10-5時，SWD算法、RSWD算法、WE-SWD算法和WE-RSWD算法所需迭代次數約為50次、18次、14次和8次可達相同的誤碼性能。綜合上述仿真結果，通過引入殘差可以有效提高滑窗譯碼及其他窗譯碼算法的譯碼性能，減少平均譯碼迭代次數，降低整體譯碼時延。

圖9 最大迭代次數對SWD算法、WE-SWD算法、RSWD算法和WE-RSWD算法誤碼率性能的影響

窗口譯碼的復雜度與譯碼的迭代次數有關，文獻[18]提出滑窗譯碼復雜度C，表示為C=Ii×W。其中N為窗口滑動的次數，Ii表示為第i個窗口譯碼結束所需的平均迭代次數，W為窗口大小。如圖10所示，對比了6種算法譯碼復雜度。由圖10可見，對比RSWD算法、SWD算法、MR-SWD算法和WE-SWD算法，WE-SWD算法譯碼復雜度最高，原因在于其譯碼過程中增加了窗口的尺寸。由于在殘差滑窗譯碼算法中，需要計算窗口內殘差值大小再進行信息傳遞，因此在SWD算法、MRSWD算法和WE-SWD算法的基礎上增加殘差算法，復雜度略有上升，在信噪比為3 dB和3.5 dB時復雜度增加約11%和15%，隨著信噪比升高，整體譯碼算法的復雜度會降低。

圖10 滑窗譯碼算法復雜度

6 結束語

針對空間耦合LDPC碼滑窗譯碼中錯誤傳播導致的高誤碼率問題，該文提出基于動態殘差的滑窗譯碼算法。該算法利用殘差值的方式篩選掉窗口內冗余的信息，在窗口內選擇最大殘差所在的邊優先更新，降低邊信息無效更新的頻率，提高譯碼誤碼率性能，減少譯碼平均迭代次數，提高窗口內譯碼收斂速度。仿真結果表明，在高信噪比區域或者低迭代次數的情況下，RSWD算法的誤碼率性能均優于SWD算法；將動態殘差應用到傳統滑窗譯碼、消息復用滑窗譯碼和窗口擴展滑窗譯碼3種窗譯碼算法中，可以有效地提升窗譯碼性能和減少平均迭代次數，抑制錯誤傳播效果明顯且復雜度增加不大。