消息復用下的空間耦合LDPC碼窗譯碼優(yōu)化算法*

周 華，葛旗偉，張 銳，司 闖

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

0 引 言

空間耦合低密度奇偶校驗(Spatially Coupled Low Density Parity Check，SC-LDPC)碼由Kudekar等人2011年在文獻[1]中首次提出。由于SC-LDPC碼的稀疏奇偶校驗矩陣與卷積碼半無限校驗矩陣的結構相似，故其又被稱為LDPC卷積碼。近年來，SC-LDPC碼被證明具有閾值飽和的特性，基于置信傳播(Belief Propagation，BP)其譯碼門限(Decoding Threshold)能夠達到對應規(guī)則LDPC碼的最大后驗概率(Maximum a Posterior，MAP)譯碼門限。

SC-LDPC碼的研究主要包括碼型的構造和譯碼方法。在SC-LDPC碼型的構造方面，一種新的折疊型結構和一種非對稱空間耦合結構分別于2017年[2]和2019年[3]提出，在很大程度上提升了SC-LDPC碼在突發(fā)刪除信道下的譯碼性能。隨后，為了避免SC-LDPC碼在信道中的速率損失，張亞坤等人[4]提出了一種碼率無損失的空間耦合LDPC碼。在譯碼方面，2012年，Iyengar等人[5]提出了應用于空間耦合LDPC碼的窗譯碼方案，與傳統(tǒng)BP譯碼算法相比，窗譯碼在降低復雜度和時延方面有一定的優(yōu)勢。2016年，Hassan等人[6]提出了便于硬件實現的完全并行SC-LDPC碼窗譯碼。2018年，Klaiber等人[7]利用失速檢測，提出了基于誤碼率預測的自適應窗口移位算法，有效地控制了窗譯碼突發(fā)式錯誤傳播問題。2020年，張婭妹等人[8]提出了窗口可變的空間耦合LDPC碼窗譯碼，通過先前窗口的對數似然比平均值計算閾值θ，若當前窗口譯碼產生的對數似然比值小于θ，則使窗口大小加一并重新開始迭代，這一做法有效降低了窗譯碼的誤碼率。同年，吳皓威等人[9]將分層譯碼引入SC-LDPC碼中，使譯碼性能進一步改進。

雖然窗譯碼非常適用于SC-LDPC碼，但還存在諸多局限性，如譯碼性能損失、復雜度和時延依然較高等。為改進這些問題，本文提出消息復用算法和動態(tài)多目標符號輸出算法。仿真表明，相比于傳統(tǒng)窗譯碼，消息復用算法在優(yōu)化譯碼性能的同時，譯碼復雜度進一步下降；動態(tài)多目標符號輸出算法與單目標符號輸出的譯碼算法相比，誤碼率損失可忽略不計，復雜度明顯下降，且在動態(tài)多目標符號窗譯碼中使用消息復用更新邊信息時，譯碼性能明顯優(yōu)于傳統(tǒng)窗譯碼，譯碼復雜度進一步下降。

1 空間耦合LDPC碼

SC-LDPC碼的基礎校驗矩陣構造基于原模圖，原模圖是一種二分圖，與LDPC碼的Tanner圖結構相似，對原模圖進行復制、置換交織、擴展可形成不同碼長的空間耦合LDPC碼[10]。原模圖一般表示為(J，K)，J表示原模圖中與變量節(jié)點相連的邊的數量，K表示與校驗節(jié)點相連的邊的數量。圖1(a)所示是一個(3，6)原模圖單元，將該原模圖復制L次，如圖1(b)所示，獲得長度為L的原模圖序列。假設原模圖序列的起始記為時刻t，則末尾時刻為t+L-1，L被稱為耦合長度。

圖1 原模圖單元到原模圖鏈

置換交織通過將原模圖中不同時刻校驗節(jié)點的邊端點交換，同時保持另一側與變量節(jié)點相連的邊端點位置不變，實現不同時刻原模圖的交織互連。如圖1(c)所示，將t時刻的原模圖校驗節(jié)點的邊端點分別連接到t，t+1，t+2,…,t+w時刻的校驗節(jié)點，該過程又稱為邊擴展，其中w稱作耦合寬度。當w=2時，圖1(b)中每個時刻的原模圖重復如圖1(c)所示的邊擴展，并在序列最右側補充w個校驗節(jié)點終止邊擴展，形成如圖1(d)所示的原模圖鏈。

原模圖的基矩陣表示方法為Bp=[bij]Jg×Kg，其中，bij表示校驗節(jié)點和變量節(jié)點相連邊的個數，Jg和Kg分別表示基矩陣行和列的大小。如圖1(a)中(3，6)的原模圖基矩陣表示為Bp=[3 3]，在邊擴展的過程中，基矩陣分解為w+1個分量矩陣Bpx，x=0，1，2，…，w。圖1(c)中，耦合寬度w=2，分量矩陣為Bp0=Bp1=Bp2=[1 1]，分量矩陣與基矩陣滿足

(1)

將原模圖鏈中的每一個原模圖轉化為矩陣形式可得到SC-LDPC碼的基礎校驗矩陣，校驗矩陣的行和列分別對應原模圖鏈中的校驗節(jié)點和信息節(jié)點。圖1(d)原模圖鏈校驗節(jié)點數量為(L+w)×Jg，變量節(jié)點數量為L×Kg，對應的基矩陣形式為

(2)

為得到SC-LDPC碼的稀疏奇偶校驗矩陣，對BSC進行擴展，定義擴展因子M，將基矩陣中的非零元素用M×M大小的單位矩陣替換并循環(huán)移位，零元素用大小為M×M的零矩陣替換，最終得到空間耦合LDPC碼的校驗矩陣

HSC=[hij](L+w)×Jg×M×L×Kg×M。

(3)

以上述方式生成的SC-LDPC碼的碼率為

(4)

2 SC-LDPC碼譯碼方案

2.1 傳統(tǒng)SC-LDPC碼窗譯碼

圖2(a)展示了傳統(tǒng)窗譯碼的過程，定義窗口的大小為W，w+1≤W≤L。窗口沿著校驗矩陣對角帶結構向右下方滑動，在窗口內執(zhí)行和積算法，窗口最左邊Kg×M個節(jié)點(圖2(a)中右斜線部分)稱為目標符號，譯碼結束只輸出目標符號。由于原模圖鏈中每一個原模圖與向前或向后的w個原模圖存在關聯，故當前時刻的窗譯碼包含了先前窗口譯碼所涉及的邊信息(圖2(a)中左斜線部分)，這些邊保存了先前窗口的輸出對數似然比值，并不需要通過信道信息重新初始化。同時，邊信息也將參與當前窗口的奇偶檢驗判斷。

(a)傳統(tǒng)SC-LDPC碼窗譯碼

2.2 SC-LDPC碼多目標符號窗譯碼

傳統(tǒng)SC-LDPC碼窗譯碼在每個窗口譯碼結束后僅輸出窗口中最左邊的子塊(單目標符號)，導致對角帶信息重復迭代次數過多，譯碼復雜度和時延較高。多目標符號窗譯碼在譯碼結束后輸出n個目標符號，表示為n-WD，其中n為輸出目標符號的數量。n-WD可有效降低傳統(tǒng)單目標符號(1-WD)譯碼的復雜度及時延。

如圖2(b)所示，假設窗譯碼輸出的目標符號數量為3(圖2(b)右斜線部分)，在每個窗口譯碼結束后，輸出窗口最左邊的3個目標符號，隨后窗口向右滑動3Kg×M，并向下滑動3Jg×M個碼元進入下一個窗口，直到整個矩陣完成譯碼。相比于傳統(tǒng)SC-LDPC碼窗譯碼，多目標符號窗譯碼窗口滑動次數減少，矩陣完成譯碼所需迭代總數降低，譯碼復雜度和時延均降低。但當輸出目標符號數量過多時，對角帶邊信息迭代不充分，導致輸出目標符號的誤碼率升高。

3 SC-LDPC碼譯碼優(yōu)化方案

3.1 消息復用下的SC-LDPC碼窗譯碼

與全矩陣采用BP算法不同的是，傳統(tǒng)窗譯碼在對目標符號譯碼時，產生的概率信息會以目標符號判決輸出LLR(Log-likelihood Ratio)的形式傳遞到之后的窗口，即后續(xù)窗口的譯碼對先前目標符號的譯碼輸出具有依賴性。當先前目標符號未能正確譯碼時，錯誤的輸出將傳遞到之后的窗口并對其譯碼造成干擾。在多目標符號輸出的SC-LDPC碼窗譯碼中，由于迭代的不足，錯誤傳播將更為嚴重。

為抑制錯誤傳播，保持當前窗口目標符號譯碼的獨立性，本文提出消息復用算法(Message Reuse for Window Decoding，MR-WD)，在邊信息的接收方式中，以邊軟信息替代目標符號判決輸出LLR，將存儲在存儲器中的外部邊信息LLR以只讀的形式傳遞到接下來的窗口。如圖3(p為窗口位置)，展示了碼長為768、窗口大小為6、在信噪比為3.2 dB的條件下，采用外部LLR和輸出LLR傳遞邊信息的差異。由圖可知，消息復用下的窗譯碼目標符號的譯碼性能優(yōu)于傳統(tǒng)窗譯碼，說明使用外部LLR傳遞邊信息的方式更加可靠。

圖3 兩種算法不同窗口位置目標符號誤碼率比較

消息復用算法的偽代碼如下：

輸入：HSC，HWD，M，E，W，L，Jg，Kg，I，l，n

1 對初始位置的窗口初始化

forj=1:W×Kg×M

Mj→i=rj

end

2 forp=1:L/n

3 ifp>1

窗口在邊信息位置(圖2中藍色左斜線)接收來自先前目標符號譯碼的外部LLR；對新進入窗口的信息(圖2中紅色網格狀)進行信道信息初始化

end if

4 forl=1:I

5 對窗口中所有的i，j節(jié)點進行校驗節(jié)點更新

(5)

6 對窗口中所有的i，j節(jié)點進行變量節(jié)點更新

(6)

7 判決

(7)

(8)

8 ifl=Ior [Z1,Z2,…,Zj]·HWD=0

9 break

10 end if

11 end for

12 存儲外部LLR(如圖2(b)綠色右斜線所示)

13 窗口向右滑動n×Kg×M，并向下滑動n×Jg×M個碼元位置

14 end for

消息復用算法是一種區(qū)別于傳統(tǒng)窗譯碼算法的新的邊信息更新機制，其譯碼步驟與傳統(tǒng)窗譯碼相似，主要的區(qū)別在于邊信息的接收方式(算法第3步和第12步)，消息復用接收先前窗口傳遞的外部只讀LLR作為邊信息更新當前窗口的校驗節(jié)點與變量節(jié)點，但這部分外部LLR并不參與當前窗口的譯碼迭代。在第一個窗口中，所有的變量節(jié)點均由接收到的信道信息初始化，在隨后的窗口中只有最右側新進入窗口的信息通過信道信息初始化。在奇偶校驗判斷階段(算法中第8步)，HWD包括與當前窗口左邊相關聯的部分(如圖2中藍色左斜線部分)。

3.2 動態(tài)多目標符號輸出SC-LDPC碼窗譯碼

單個目標符號輸出的譯碼算法優(yōu)勢在于譯碼性能的優(yōu)越性，但譯碼復雜度仍偏高；多目標符號輸出的譯碼算法優(yōu)勢在于更低的復雜度和時延，但發(fā)生突發(fā)式錯誤傳播的可能性更高。綜合兩種譯碼算法的優(yōu)缺點，本文提出一種動態(tài)多目標符號輸出的SC-LDPC碼窗譯碼(Dynamic Multi-target-symbol Output for Window Decoding，DMO-WD)，算法流程如圖4所示。

圖4 動態(tài)多目標符號輸出SC-LDPC碼窗譯碼流程圖

圖4中狀態(tài)1表示譯碼進程處于連續(xù)x個窗口均滿足奇偶校驗判定為零的狀態(tài)，狀態(tài)2表示譯碼進程處于連續(xù)x個窗口均不滿足奇偶校驗判定為零的狀態(tài)。參考文獻[7]中的分析，當譯碼器連續(xù)至少w個窗口發(fā)生錯誤輸出，譯碼器有失控的可能，反之譯碼器處于穩(wěn)定狀態(tài)，故圖4中x應滿足x≥w，本文取x=w。

在譯碼開始時，窗口位置p位于矩陣左上角，設置輸出目標符號變換的邊界值nmin、nmax，并令初始n=nmin。在譯碼過程中，當判定有狀態(tài)1或狀態(tài)2出現時，增加或減少目標符號輸出的數量分別為n=n+a、n=n+b直至下一個狀態(tài)1或狀態(tài)2出現，其中a、b為可設置的常量。在此算法中，窗口滑動的次數并非定值，故當窗口矩陣為全零矩陣時，判斷窗口不再處于校驗矩陣當中，跳出譯碼循環(huán)。

4 仿真分析

本文仿真采用碼長為7 200、耦合寬度w=3、耦合長度L為60的SC-LDPC碼，窗口大小設置為8，允許窗口內最大迭代次數為30次。仿真基于加性高斯白噪聲(Additive White Gaussian Noise,AWGN)信道，采用二進制相移鍵控(Binary Phase Shift Keying,BPSK)調制。

4.1 消息復用下的多目標符號窗譯碼仿真

文獻[8]算法的譯碼原理為，設置窗口大小W的邊界值為Wmin、Wmax并令初始W=Wmin，隨后計算出所有窗口從初始值到最大值相應目標符號的對數似然比，累加并求平均，得到閾值θ，若當前目標符號譯碼產生的對數似然比值小于θ，則令該窗口大小加一并重新開始迭代。將該算法與本文提出的算法進行對比，在文獻[8]中Wmin=8，Wmax=11。

圖5展示了目標符號輸出數量分別為1、2、4的窗譯碼采用消息復用帶來的譯碼性能收益，以及和文獻[8]仿真對比。由圖可知，消息復用下的SC-LDPC碼窗譯碼(MR-n-WD)性能優(yōu)于傳統(tǒng)SC-LDPC碼窗譯碼(n-WD)性能。在誤碼率為10-3、輸出目標符號數量為1時，消息復用下的窗譯碼(MR-1-WD)比傳統(tǒng)的窗譯碼(1-WD)信噪比下降約0.25 dB，比文獻[8]算法信噪比下降0.1 dB；輸出目標符號數量為2時，消息復用下的窗譯碼(MR-2-WD)比傳統(tǒng)的窗譯碼(2-WD)信噪比下降約0.2 dB，比輸出目標符號數量為1的窗譯碼(1-WD)信噪比下降約0.08 dB，與文獻[8]算法相比信噪比幾乎無損失；輸出目標符號數量為4時，消息復用下的窗譯碼(MR-4-WD)比傳統(tǒng)的窗譯碼(4-WD)信噪比下降約0.18 dB，比輸出目標符號數量為1的窗譯碼信噪比損失約0.05 dB，與文獻[8]算法相比信噪比損失約0.18 dB。

圖5 消息復用下的SC-LDPC碼窗譯碼

窗譯碼的復雜度與譯碼迭代次數緊密關聯，參考文獻[7]定義C為矩陣平均譯碼復雜度：

(9)

式中：N為窗口滑過矩陣所需要的次數，Ii為第i個窗口譯碼結束所需迭代次數，W為窗口大小。

圖6所示為消息復用下的多目標符號窗譯碼與傳統(tǒng)多目標符號窗譯碼復雜度對比。由于文獻[8]在譯碼過程中增大了窗口尺寸，故其譯碼復雜度較高，當信噪比較低時，傳統(tǒng)多目標符號窗譯碼(n-WD)與消息復用下的窗譯碼(MR-n-WD)窗口內迭代次數均接近設定的最大迭代次數，故差異并不明顯；當信噪比升高，信道環(huán)境變好，譯碼所需迭代總數降低，算法復雜度越來越低，信噪比處于3～3.9 dB區(qū)間(中信噪比區(qū)域)時，消息復用算法與非消息復用算法相比復雜度差異可達到20%上下，且消息復用算法相比文獻[8]復雜度下降40%以上；當信噪比大于3.9 dB時(高信噪比區(qū)域)，信道環(huán)境越來越好，兩種算法復雜度差異逐漸縮小。

圖6 消息復用下的多目標符號窗譯碼復雜度

4.2 動態(tài)多目標符號輸出仿真

圖7展示了變換輸出目標符號數量n的邊界值對誤碼率的影響，圖中實線部分采用傳統(tǒng)方式傳遞窗譯碼的邊信息，虛線部分采用消息復用方式。常量a、b取值分別為a=1，b=2。在誤碼率為10-3量級，當設定nmin為1、nmax為4時，動態(tài)多目標符號輸出窗譯碼(DMO-WD和DMO-MR-WD)相比于單目標符號輸出窗譯碼(1-WD和MR-1-WD)信噪比損失可忽略不計；當nmin為1、nmax=8時，動態(tài)多目標符號輸出窗譯碼相比單目標符號輸出窗譯碼信噪比損失依然較小；當nmin為4、nmax=8時，兩者信噪比差異明顯增大。

圖7 不同n邊界取值的動態(tài)多目標符號窗譯碼誤碼率

圖8展示了目標符號增加、減少幅度值a、b的不同取值對動態(tài)多目標符號窗譯碼的誤碼率影響，設置nmin為1，nmax為4。在誤碼率為10-3量級，當a為1、b為2時，動態(tài)多目標符號窗譯碼(DMO-WD和DMO-MR-WD)相比單目標符號輸出(1-WD和MR-1-WD)信噪比損失可忽略不計；當a、b值均為1時，兩者差距在0.05 dB左右；當a為2、b為1時，動態(tài)多目標符號相比單目標符號輸出信噪比損失0.18 dB左右。

圖8 不同a、b取值的動態(tài)多目標符號窗譯碼誤碼率

為比較消息復用算法、動態(tài)多目標符號算法在不同信道、調制方式下的有效性，圖9展示了在AWGN信道、瑞利信道下采用BPSK、QPSK、8PSK調制方式的誤碼率仿真結果。在相同信噪比的情況下，高斯信道的誤碼率低于瑞利信道。綜合圖7和圖8的仿真結果，在動態(tài)多目標符號輸出算法中，設置nmin=1，nmax=4，a=1，b=2。綜合6組仿真數據可知，誤碼率為10-3量級時，在同種邊信息處理方式下，動態(tài)多目標符號輸出算法相比于單目標符號輸出算法誤碼率損失可忽略不計，且消息復用下的動態(tài)多目標符號窗譯碼(DMO-MR-WD)相比于傳統(tǒng)窗譯碼(1-WD)信噪比改善0.2 dB左右，論證了該算法在其他信道或采用其他調制方式時依然有效。

圖9 不同信道、調制對算法性能的影響

圖10展示了幾種算法在AWGN信道下采用BPSK、QPSK、8PSK的復雜度差異。在調制方式為BPSK、QPSK時，當信噪比為3～3.9 dB區(qū)間(中信噪比區(qū)域)時，在同種邊信息處理方式下，動態(tài)多目標符號算法復雜度相比于單目標符號算法下降明顯，如在3.6 dB，消息復用下的動態(tài)多目標符號窗譯碼(DMO-MR-WD)復雜度最低，相比于文獻[8]復雜度降低55%，相比于傳統(tǒng)單目標符號窗譯碼(1-WD)降低35%，相比于非消息復用下的動態(tài)多目標符號輸出算法(DMO-WD)降低15%。而采用8PSK調制時，相同信噪比下的算法誤碼率較高，完成譯碼所需迭代總數較多，故其譯碼復雜度明顯升高，但在信噪比為3.6 dB時，消息復用下的動態(tài)多目標符號窗譯碼(DMO-MR-WD)相比傳統(tǒng)窗譯碼(1-WD)依然有20%左右的復雜度改善。

圖10 動態(tài)多目標符號算法譯碼復雜度

5 結束語

本文針對空間耦合LDPC碼窗譯碼提出了消息復用算法和動態(tài)多目標符號輸出算法。消息復用算法以外部LLR代替輸出LLR傳遞邊信息；動態(tài)多目標符號輸出算法在譯碼過程中借助奇偶校驗來估計譯碼進程是否穩(wěn)定，若穩(wěn)定則增加其輸出目標符號的數量，反之減少其輸出目標符號的數量。仿真結果表明，消息復用算法較傳統(tǒng)窗譯碼算法提高了譯碼性能，同時減少了譯碼復雜度；動態(tài)多目標符號輸出算法與消息復用算法疊加使用時，較傳統(tǒng)窗譯碼誤碼率下降約0.2 dB，復雜度下降最高可達35%。在該算法的基礎上，未來可將消息復用低誤碼率及多目標符號輸出低復雜度的特點應用于更多SC-LDPC碼的譯碼算法，如SC-LDPC的窗譯碼分層算法。