一種類Raptor多速率QC-LDPC碼的代數構造方法

李華安，白寶明，徐恒舟，陳 超

(1.西安電子科技大學 綜合業務網理論及關鍵技術國家重點實驗室，陜西 西安 710071；2.周口師范學院 網絡工程學院，河南 周口 466001)

低密度校驗(Low-Density Parity-Check，LDPC)碼是一類具有可逼近香農容量限的信道編碼，由稀疏矩陣的零空間定義。低密度校驗碼最早由GALLAGER[1]于20世紀60年代在其博士論文中提出，在此后的近35年里，幾乎被編碼界忽略。在此期間，關于低密度校驗碼的研究甚少。值得一提的是TANNER[2]的工作，他推廣了低密度校驗碼，并為其引入了圖表示方法，即現在廣被使用的Tanner圖。直到上世紀90年代中期，多位編碼學者發現具有稀疏(低密度)校驗矩陣的線性分組碼在迭代譯碼算法下具有逼近信道容量限的性能[3]，而且這類碼還具有線性編譯碼復雜度，因此低密度校驗碼又重新引起大家的研究興趣。雖然低密度校驗碼的早期研究不夠成熟，錯過了3G和4G標準，但因為其出色的性能和較低的譯碼復雜度，被重新發現后迅速被廣泛且深入地研究。起初低密度校驗碼的校驗矩陣很少具有結構特性，即原始低密度校驗碼是隨機的。而若一個碼沒有結構特性，則編譯碼過程將比較復雜，因此人們提出了結構化低密度校驗碼。最為典型的結構化低密度校驗碼是準循環低密度校驗(Quasi-Cyclic LDPC，QC-LDPC)碼[4]。這類碼編譯碼復雜度低，且在中短碼長下，設計良好的QC-LDPC碼譯碼錯誤平層低，性能優于隨機低密度校驗碼，因此被廣泛研究，包括設計與構造[5-8]、譯碼算法[9-11]以及應用[12-15]，并且這類碼已被多個重要國際標準采納，如WiMAX[12]、CCSDS[13]、WiFi[14]以及5G[15]等。

在實際的移動通信系統中，無線信道的時變特性以及多徑衰落影響了信號傳輸，一些不可預測的干擾也會導致信號傳輸失敗。除了采用糾錯碼，還會采用自動重傳請求和自適應編碼調制等方法進行差錯控制，以確保服務質量，而可支持多種碼率的變碼率低密度校驗(Variable-Rate LDPC，VR-LDPC)碼可以滿足這一要求。目前最為常見的VR-LDPC碼主要有兩種：具有固定信息位長度的速率兼容低密度校驗(Rate-Compatible LDPC，RC-LDPC)碼[15-17]和具有固定碼長的多速率低密度校驗(Multi-Rate LDPC，MR-LDPC)碼。其中，打孔、縮短以及擴展是構造RC-LDPC碼的常見方法，最為典型的是標準5G LDPC碼[15]。由于MR-LDPC碼的碼長固定，非常適用于一些特殊的應用場景，包括多級編碼調制系統和衛星通信，因此也被廣泛研究。如在文獻[18]中，作者基于刪除的方法分別構造了多元MR-LDPC碼，仿真結果顯示所構造的碼在不同碼率下均具有較好的譯碼性能。

5G通信是通信基礎研究與科技創新的結晶，也代表著信道編碼技術在移動通信領域的突破與變革。3GPP關于5G信道編碼的標準化基本完成，相關結論也已寫入NR的R15規范[15]。R15階段屬于基礎功能階段，完成了增強移動寬帶場景下信道編碼研究與標準化工作，而后續階段主要任務之一是增強超高可靠性的低時延通信等。我國科技部于2018年11月擬將“與5G/6G融合的衛星通信技術研究與原理驗證”課題列入國家重點研發計劃“寬帶通信和新型網絡”重點專項中。這說明了探索地面網絡與其他通信系統融合方案的必要性與重要性，也是我國實現無線通信技術與星地融合從跟跑、并跑到領跑的重大需求。5G NR R15標準化的低密度校驗碼是一類具有類Raptor(Raptor-like)結構的RC-QC-LDPC碼[17]。因此，筆者主要研究具有Raptor-like結構的MR-QC-LDPC碼的構造方法，探索未來地面網絡與其他對MR-LDPC碼有需求的通信系統的編碼融合方法。

結合代數和疊加構造方法，通過漸進改變移位尺寸，筆者構造了一類碼長固定、具有Raptor-like結構的MR-QC-LDPC碼。所構造的碼具有易于硬件可實現的編譯碼器，而且可基于校驗矩陣直接編碼。此外，因為結合了代數方法，所構造的碼的循環移位矩陣具有明顯的代數結構，矩陣存儲復雜度極低，即在已知基矩陣條件下，根據兩個值就可得到MR-QC-LDPC碼不同碼率的循環移位矩陣。這種方法適用于構造具有類Raptor結構的MR-QC-LDPC碼，在多種速率下具有較好的整體性能。

1 Raptor-like低密度校驗碼與準循環低密度校驗碼

1.1 Raptor-like LDPC碼

二元低密度校驗碼是一類特殊的線性分組碼，由稀疏矩陣H(矩陣中包含多數個“0”和相對少量的“1”)的零空間定義，這里矩陣H被稱為低密度校驗碼的校驗矩陣。而Raptor-like LDPC碼的校驗矩陣具有如下形式：

其中，HHR為高碼率的校驗矩陣，HIR是在高碼率矩陣的基礎上擴展得到的矩陣，I為單位陣。可以看出，Raptor-like LDPC碼可以看成是高碼率校驗矩陣碼為外碼、擴展校驗矩陣碼為內碼的串行級聯碼，非常適用于設計RC-LDPC碼。因為擴展部分引入了很多重量為1的列，這些列一般會惡化碼的譯碼錯誤平層性能，但由于此處低碼率擴展部分[HIRI]只是作為內碼，并不會引起明顯的錯誤平層問題。

Raptor-like LDPC碼可否基于校驗矩陣直接編碼與HHR的結構有關。當考慮系統Raptor-like LDPC碼時，可以將其校驗矩陣分為5個部分，如圖1左邊所示。此時，校驗矩陣是否支持可直接編碼與矩陣D的結構有關。而當D設計為下三角、單對角或者雙對角矩陣以及三者的混合結構時，即可根據校驗矩陣直接編碼。筆者只關注D為雙對角或者“單對角+雙對角”的混合形式，而圖1中的D即為雙對角矩陣。

圖1 一種可直接編碼的Raptor-like LDPC碼校驗矩陣結構

1.2 準循環低密度校驗碼的疊加構造

考慮正整數Z和整數集合SZ={0，1，…，Z-1}。對于集合中的任意元素p∈SZ，可以用Z×Z大小的二元循環置換矩陣(Circulant Permutation Matrix，CPM)表示。為簡單起見，將該循環置換矩陣表示為Q(p)。Q(p)具有如下特點(注：行和列標注方式均為0，1，…，Z-1)：

(1) 首行惟一非零元素“1”所在位置為p；

(2) 每一行由上一行循環右移一位得到；

(3) 最后一行循環右移一位得到首行。

不難看出，p∈SZ和Q(p)具有一一對應關系。方便起見，引入Q(-1)表示Z×Z大小的全零矩陣。稱上述過程為Z階矩陣散列(Z-fold Matrix Dispersion)，參數Z被稱為移位尺寸。

二元(N，K)QC-LDPC碼的校驗矩陣H通常可以表示為陣列H=[Hi，j]0≤i

上述過程統稱為疊加構造過程。這個過程依次設計基矩陣B和循環移位矩陣P，將P中的移位值散列為循環矩陣或大小相同的全零矩陣，從而得到QC-LDPC碼的校驗矩陣H。因此，疊加構造主要涉及3個矩陣和一個過程，即基矩陣、循環移位矩陣、循環矩陣和矩陣散列。

相關研究表明，影響QC-LDPC碼迭代譯碼性能的主要因素有碼字分布、環分布、圍長和陷阱集等結構，而環分布均與其他結構有著直接或間接的聯系。研究中還發現，QC-LDPC碼Tanner圖中的環由循環移位矩陣P以及移位尺寸Z決定，具體如下面引理所述。

引理1(Fossorier公式[4])設QC-LDPC碼的循環移位矩陣P=[pi，j]0≤i

(1)

其中，0≤iZ

引理1指出了長度為2d∈[g，2g-2]的環的個數的一種計算方法，即只需搜索矩陣P中滿足式(1)的非負移位值組數即可。在下文中，“d-環”表示長度為d的環，Nj(P，Z)表示對于移位尺寸為Z、圍長為g的循環移位矩陣P，考慮長度為(2j+2)∈[g，2g-2]的環時滿足式(1)的非負移位值組數。

1.3 一類代數構造方法及其有關結論

有很多代數方法可以用來構造不存在長度為4的環的循環移位矩陣。一種典型且非常靈活的方法是基于非二元素有限域的兩個任意集合來設計。設S1={i0，i1，…，imb-1}(mb

P=[pk，t]0≤k

(2)

下面的引理給出了基于式(2)所示代數方法構造的循環移位矩陣的圍長特性。

引理2基于素域GF(q)任意兩個集合構造的具有如式(2)形式的循環移位矩陣P，其q階矩陣散列定義的QC-LDPC碼的Tanner圖不存在4-環，圍長至少為6[19]。

因此，當待設計的循環移位矩陣的移位尺寸為素數時，可以基于式(2)方法構造循環移位矩陣P，此時由P散列得到的陣列H不存在4-環。此外，還可以通過對P或H進行掩模處理以進一步改善QC-LDPC碼的環分布。

2 Raptor-like MR-QC-LDPC碼的代數構造

在QC-LDPC碼的疊加構造中，要求基矩陣B已知。一般要求B具有較好的迭代譯碼門限，設計方法主要有計算機輔助的EXIT圖搜索算法(如P-EXIT[20])和代數方法[19]。好的迭代譯碼門限可以提供較好的瀑布區性能，但不能保證所設計的碼有較低的譯碼錯誤平層。而影響錯誤平層的主要因素有距離分布、環分布、圍長以及陷阱集等。為獲得較低的錯誤平層性能，在構造QC-LDPC碼的循環移位矩陣P時應綜合考慮這些因素的影響。在筆者提出的構造方法中，主要考慮環分布以及圍長。

筆者提出的Raptor-like MR-QC-LDPC (RL-MR-QC-LDPC) 碼代數構造方法需要已知具有類Raptor結構的基矩陣，而設計這類基矩陣的常見方法有基于P-EXIT的擴展方法。為提高性能，在設計基矩陣時可以基于打孔打掉某些信息比特，即假設前np列為內置打孔列。這些列的重量一般較高，與這些列對應的信息位不會被送入信道中傳輸，接收端譯碼時將這些信息位按照打孔比特處理。由于基矩陣是基于擴展方法設計的，高碼率部分的基矩陣嵌套在低碼率部分的基矩陣中，而低碼率的基矩陣由高碼率的基矩陣擴展而得，基矩陣的大小會隨著碼率的減小而增大。因此，構造這類碼的難點在于：在保證碼長固定不變的條件下，如何構造RL-MR-QC-LDPC碼不同碼率的循環移位矩陣，即隨著碼率變小(此時對應的基矩陣/循環移位矩陣的大小變大)，如何同時增加校驗位和減少信息位。針對該難點，筆者結合代數方法和疊加構造，通過漸進改變移位尺寸來設計RL-MR-QC-LDPC碼。

已知基矩陣B的信息位列數為kb，內置信息位打孔列數為np。為簡單起見，將np固定為2。假設要構造的RL-MR-QC-LDPC碼的碼長為N，碼率集合R={R1，R2，…，RT}(對于1≤i

(3)

(1) 計算參數：確定基矩陣B=[bi，j]0≤i

(2) 構造系數矩陣：構造mb×nb大小的系數矩陣C=[ci，j]mb×nb，其中

(4)

因此，待確定的值為{c0，kb，cr2nd，kb，cmdual-1，kb}。為了保證校驗矩陣可直接編碼，要求c0，kb=cmdual-1，kb，最終只有{c0，kb，cr2nd，kb}兩個值需要確定。進一步，基于基矩陣B對C的前kb列進行掩模處理，得到Cmask=[c′i，j]0≤i

(5)

(3) 循環移位矩陣：碼率Rt的循環移位矩陣為Pt=[pi，j]mt×nt，對于0≤i

(6)

因為所有循環移位矩陣均基于Cmask獲得，而Cmask基于式(2)的代數方法構造，因此要求Zt∈SP，其中，SP表示由所有素數構成的集合。

(7)

其中，gt表示Pt的圍長。選取{c0，kb，cr2nd，kb}，同時使M1和M2盡可能小，即只考慮圍長g以及長度為g+2的環的影響。可以看出，準則M1和M2摒除了移位尺寸大小的影響，從而實現對可支持不同移位尺寸的循環移位矩陣的構造。

例如，大小為7×10、支持3種碼率的RL-MR-QC-LDPC碼的基矩陣以及系數矩陣如圖2所示，其中mdual=4，r2nd=2。如圖2所示，為了編碼簡單，雙對角部分除了第1列，其余非負移位值均固定為0。根據Fossorier公式，即使C的多數值具有式(2)的形式，但因為雙對角部分0的存在，也可能存在4-環，因此需要優化選取{c0，kb，cr2nd，kb}，改善最終循環移位矩陣的環分布，以獲得較好的性能。

圖2 一個RL-MR-QC-LDPC碼的基矩陣與系數矩陣

圖3 Raptor-like MR-QC-LDPC碼的打孔與縮短示意圖

筆者所構造的低密度校驗碼在不同碼率下校驗矩陣均具有類Raptor結構，這類碼的快速編碼參見文獻[20]。

綜上，筆者提出的設計與構造方法融合了多種技術，包括擴展、打孔和縮短處理，以及代數與疊加構造方法。所構造的RL-MR-QC-LDPC碼的碼率越低，基矩陣/循環移位矩陣越大，移位尺寸越小。因為Cmask具有明顯的代數結構，在已知基矩陣B前提下，只需已知{c0，kb，cr2nd，kb}即可獲得所提出的RL-MR-QC-LDPC碼所有碼率的循環移位矩陣，因此存儲復雜度極低。

基矩陣B的非零元用于指示循環移位矩陣中非負移位值的位置，而置換非打孔信息列并不影響B的迭代譯碼門限。因此，還可以通過置換基矩陣B的非打孔信息列得到新的基矩陣和系數矩陣Cmask，并同時優化選取{c0，kb，cr2nd，kb}，保證最終的循環移位矩陣整體具有較好的環分布，進一步提高性能。

3 數值結果

根據上一節介紹的方法構造了RL-MR-QC-LDPC碼，并通過仿真驗證所設計的碼的性能。在所有仿真中，考慮二進制輸入加性高斯白噪聲(Binary Input Additive White Gaussian Noise，BI-AWGN)信道，譯碼算法采用最大迭代次數為50的和積算法(Sum-Product Algorithm，SPA)[20]。

筆者所構造的RL-MR-QC-LDPC碼的碼長為960 bit，可支持的碼率集合R={1/2，2/3，5/6}，基矩陣B的散點圖如圖4(a)所示，因此mb=18，nb=34，np=2，kb=16，r2nd=2。選取Wc=(10 000，1 000，100，1)，根據上一節介紹的代數方法，選取{c0，16，c2，16}={31，35}。基于上一節方法可獲得不同碼率的循環移位矩陣Pt(1≤t≤3)，將Pt(1≤t≤3)進行Zt階矩陣散列，最終得到碼率Rt(1≤t≤3)的編譯碼校驗矩陣Ht(1≤t≤3)。3種碼率的相關編碼參數如表1所示，包括基矩陣大小、移位尺寸、信息位縮短位數和校驗位打孔位數。對于3組碼率，信息位打孔位數均為2Zt(1≤t≤3)。

表1 構造碼長為960 bit的RL-MR-QC-LDPC碼的編碼參數

圖4(b)展示了所構造的RL-MR-QC-LDPC碼的誤塊率(BLock Error Rate，BLER)性能，以及WiMAX標準中具有相同參數的低密度校驗碼的誤塊率性能。從圖中可以看出，筆者所構造的碼整體性能優于標準WiMAX LDPC碼[12]。需要說明的是，不同參數下標準WiMAX LDPC碼對應不同的循環移位矩陣，而筆者構造的RL-MR-QC-LDPC碼的矩陣存儲復雜度極低，即只需要知道基矩陣和數值對{c0，16，c2，16}，就可以得到不同碼率的循環移位矩陣。

(a) 基矩陣

(b) BLER性能

4 結束語

結合代數和疊加構造方法，通過漸進改變移位尺寸，筆者提出并構造了具有固定碼長的類Raptor多速率準循環低密度校驗碼。基于該方法，隨著碼率減小，對應的基矩陣/循環移位矩陣增大，移位尺寸變小。為了獲得固定碼長和匹配不同信息位長度，還引入了信息位縮短和校驗位打孔操作。筆者所構造的碼兼具準循環和類Raptor結構，因此具有易于硬件可實現的編譯碼器，其編碼也可直接基于校驗矩陣實現。此外，因為引入了代數方法，所構造的碼具有極低的矩陣存儲復雜度，即只需知道基矩陣以及兩個數，就可得到不同碼率的循環移位矩陣。數值仿真表明，所構造的碼的整體性能優于相同參數下的標準WiMAX LDPC碼。NR R15規范的標準5G LDPC碼是具有類Raptor結構的速率兼容低密度校驗碼，因此筆者提出的方法可為未來地面網絡與其他對MR-LDPC碼有需求的通信系統的編碼融合提供一種可行方案。