基于等差數(shù)列與原模圖的QC-LDPC碼構(gòu)造方法

袁建國，孫樂樂，范福卓，袁 夢，劉家齊，鄭德猛

(重慶郵電大學 光電信息感測與傳輸技術(shù)重慶市重點實驗室，重慶 400065)

0 引 言

低密度奇偶校驗碼(low-density parity-check, LDPC)碼是一種線性分組碼，它的性能不僅十分逼近香農(nóng)限，而且它具有譯碼簡單，構(gòu)造靈活，易于硬件實現(xiàn)等優(yōu)點[1-3]。由于LDPC碼的結(jié)構(gòu)不同，最終得到的編譯碼復雜度和性能也有所不同。針對以上情況， LDPC碼構(gòu)造方法的研究已經(jīng)成為目前編碼領(lǐng)域研究的熱點之一。

準循環(huán)低密度奇偶校驗(quasi-cyclic low-density parity-check, QC-LDPC)碼[4-5]是一種新的LDPC碼，它結(jié)構(gòu)簡單，易于硬件實現(xiàn)且編碼效率高[6]，因此，在通信領(lǐng)域中，QC-LDPC碼應用十分廣泛。QC-LDPC碼的校驗矩陣H是由基矩陣通過循環(huán)子矩陣擴展而成，校驗矩陣H的編碼性能可由基矩陣和擴展因子P決定，因此，基矩陣的構(gòu)造尤為重要。

本文利用一種特殊的等差算法得出等差數(shù)列，并把此等差數(shù)列作為基矩陣中的元素，結(jié)合原模圖的擴展方法，最終得到一種新穎的QC-LDPC碼。這種新構(gòu)造的QC-LDPC碼，通過分析，校驗矩陣在構(gòu)造時，就避免了四六環(huán)的存在，所以圍長至少為8，且能夠靈活選擇碼長碼率，所構(gòu)造的碼字具有較好的糾錯性能。

1 QC-LDPC簡介

QC-LDPC碼的校驗矩陣H是通過分組矩陣構(gòu)造而成，而分組矩陣是由循環(huán)置換矩陣(circulant permutation matrix, CPM)和全零矩陣(zero matrix, ZM)組成的。QC-LDPC碼的校驗矩陣H的形式為

(1)

其對應的指數(shù)矩陣(基矩陣)E為

(2)

(1)—(2)式中：P為循環(huán)置換矩陣的維數(shù)大??；J和L分別代表基矩陣的行數(shù)和列數(shù)，碼長N=P×L。Ia(i,j)代表P×P維的循環(huán)置換矩陣或者全零矩陣，a(i,j)為移位因子，其中，1≤i≤J，1≤j≤L。a(i,j)取值為{1,2,3,…,P-1}或者-1，a(i,j)=0時表示Ia(i,j)為單位矩陣，a(i,j)=-1時表示a(i,j)為全零矩陣。校驗矩陣中的環(huán)可以利用對應的基矩陣中的移位因子表示，存在以下定理。

定理1[7](a1,a2,…,a2k-1,a2k)是基矩陣E中的序列，其中，ai和ai+1在同一行或者在同一列，而ai和ai+2在不同行且不同列，則(a1,a2,…,a2k-1,a2k)構(gòu)成長為2k環(huán)的充要條件為

(3)

2 等差數(shù)列的構(gòu)造

等差數(shù)列是一種常見的數(shù)學數(shù)列，屬于組合數(shù)學范疇。它是指從第二項起，每一項與它前一項的差等于同一個常數(shù)的一種數(shù)列。本文中所指的等差數(shù)列是利用數(shù)學分析的思想，構(gòu)造一種差值不斷變化的特殊的等差數(shù)列。

定理2[8]若(2)式中移位因子的公差由(4)式計算決定，則由此定義的QC-LDPC碼圍長至少為8。

(4)

(4)式中：d表示第一行的差值；k取整數(shù)；D3k,j表示第3k行元素差d3k+1,j(1≤j≤L-1)的總和，L為基矩陣中的行數(shù)。由定理2可知，應用定理2所構(gòu)造的QC-LDPC碼基矩陣沒有四、六環(huán)，圍長至少為8。

3 原模圖簡介

原模圖具有低譯碼門限，高速譯碼等優(yōu)點[9]，它本質(zhì)上就是一種Tanner圖，只是Tanner圖的節(jié)點數(shù)相對較少[10]。原模圖中允許有重邊，所以原模圖可分為2類，即完全連接的原模圖(無重邊)和有重邊的原模圖，舉例說明完全連接的原模圖和有重邊的原模圖，如圖1。

圖1 完全連接的原模圖Fig.1 Protograph with the complete connection

圖1對應的原模圖基矩陣B1為

(5)

這里幾重邊就代表該校驗節(jié)點(變量節(jié)點)與該變量節(jié)點(校驗節(jié)點)之間有幾條平行的邊相連接，圖2中同樣包含4個變量節(jié)點和3個校驗節(jié)點，對應的邊的總數(shù)為13。

圖2 有重邊的原模圖Fig.2 Protograph with parallel edges

圖2對應的原模圖基矩陣B2為

(6)

上述2種原模圖只有第1種完全連接的原模圖可以直接作為基礎(chǔ)矩陣并對其進行擴展；第2個原模圖必須進行處理后方可用于擴展，本文將使用第1種原模圖結(jié)合構(gòu)造的等差數(shù)列，對形成的基矩陣進行擴展。

4 一種結(jié)合等差數(shù)列和原模圖的QC-LDPC構(gòu)造方法

對于(2)式中的基矩陣E，通過設定不同的J，L和擴展因子P，可以得到不同碼長碼率的校驗矩陣H。在這里設J=4，L=9，即生成一個4行9列的基矩陣。假設定理2中(4)式每行的第一項為0且d=1，通過(4)式計算得出基矩陣E1，為了生成碼率為0.5的校驗矩陣，這里需要刪除任意一列，得到一個4行8列的基矩陣E2，此時選擇刪除的是第1列，E2為

(7)

本文用于結(jié)合等差數(shù)列構(gòu)造基矩陣的原模圖Bbase，是通過計算機搜索得到的，以下是搜索算法的簡要過程。

首先，構(gòu)造一個nrow×ncolumn的矩陣A[11]。

然后，利用定理1中的環(huán)存在公式，以及文獻[12]中所定義的譯碼門限，結(jié)合上一步得到的矩陣A進行搜索，相關(guān)的簡要搜索流程如下。

第1步：設定算法的輸入系數(shù)為k,A，A*，B*(一個全1矩陣)，C(一個全零矩陣)，搜索算法的輸出為矩陣B。

第2步：把B*復制給B，令A*=A?B，同時取k=2。

第3步：通過環(huán)存在定理，循環(huán)判斷A*中是否存在環(huán)長為2k的環(huán)，如果存在則將矩陣C中對應位置元素值加1。

第4步：如果C中有唯一最大值，則將B中對應位置的1置為0。否則令k=k+1，執(zhí)行第2步。

第5步：此時，如果B矩陣的譯碼門限小于矩陣B*的譯碼門限，則輸出矩陣B(此時，B為最終所得原模圖基矩陣Bbase)，否則，把B復制給B*，重新執(zhí)行第2步。

使用上述搜索算法，可以得到一個原模圖基矩陣Bbase，其中，nrow=4，ncolumn=8，搜索得到的基矩陣Bbase如式(8)所示。

(8)

利用基矩陣E2和基矩陣Bbase，使2個矩陣中相同位置處對應的數(shù)值進行相乘，可以得到最終的基矩陣Epro=Bbase?E2，如(9)式。

(9)

通過P×P大小的循環(huán)置換矩陣對(9)式進行擴展，將Epro中的元素“0”替換成P×P大小零矩陣，非零元素“ai,j”替換成循環(huán)右移位ai,j次得到的循環(huán)置換矩陣，從而得到最終的校驗矩陣H，它的維數(shù)為4P×8P(P不小于矩陣Epro中的最大移位值)?？梢园袳pro當做是E2被Bbase修飾后得到的矩陣，來分析Epro的圍長為8的問題。此時，Bbase為修飾矩陣，E2為原來矩陣，修飾過的矩陣Epro是循環(huán)置換矩陣和0矩陣的陣列。因為由上文分析已知原來矩陣E2滿足圍長為8的條件，所以修飾過的矩陣Epro也滿足圍長為8的條件，而不管修飾矩陣Bbase如何，因此，矩陣Epro的圍長至少也為8。

綜上可知，等差數(shù)列構(gòu)成的基矩陣E2本身具有大圍長的性質(zhì)，原模圖具有低譯碼門限，高速譯碼的優(yōu)點，但是對于原始的原模圖本身而言，往往存在圍長不夠大對性能產(chǎn)生影響。結(jié)合等差數(shù)列和原模圖得到的基矩陣Epro繼承兩者優(yōu)點的同時，也彌補了彼此相應的不足，并在下文仿真圖中得到證實。

5 仿真分析

本文擴展的維數(shù)選取P=500，由于基矩陣對應的碼率是0.5，所以擴展后的碼率仍然為0.5，最終得到的校驗矩陣H的碼長為4 000。已知迭代譯碼次數(shù)n對碼型的糾錯性能有一定的影響，首先根據(jù)不同的迭代次數(shù)影響糾錯性能的仿真對比圖，如圖3，選擇合適的迭代次數(shù)n。圖3中，當誤碼率為10-6時，本文基于等差數(shù)列和原模圖(arithmetic progression and protograph, APP)所構(gòu)造的APP-QC-LDPC(4 000,2 000)碼糾錯性能，在一定范圍內(nèi)隨迭代次數(shù)n的增加而提高，當n取值為40～60時，相對應的仿真曲線幾乎重合在了一起，糾錯性能并沒有顯著改善。因此，考慮到在迭代次數(shù)增加的同時，譯碼復雜度會增加的問題，本文后續(xù)在對QC-LDPC碼進行仿真時迭代次數(shù)均選擇為40，使其在糾錯性能和復雜度之間找到平衡。

圖3 不同迭代次數(shù)的仿真對比圖Fig.3 Simulation comparison graph of different iterations

為了驗證新構(gòu)造的碼字具有較好的糾錯性能，本文選用了基于漸進邊增長(progressive edge growth, PEG)算法構(gòu)造的PEG-QC-LDPC(4 000,2 000)碼、上文(7)式中基于等差數(shù)列(arithmetic progression, AP)構(gòu)造的AP-QC-LDPC(4 000,2 000)、參考文獻[13]中利用修飾(masking,M)技術(shù)構(gòu)造的M-QC-LDPC(4 000,2 000)碼和參考文獻[14]中基于最大公約數(shù)(greatest common divisor, GCD)構(gòu)造的GCD-QC-LDPC(4 000,2 000)碼與本文所構(gòu)造的APP-QC-LDPC(4 000,2 000)碼進行仿真對比。具體的仿真環(huán)境如下：選取高斯白噪聲信道(additive white gaussian noise, AWGN)作為仿真信道，使用二進制相移鍵控(binary phase shift keying, BPSK)進行調(diào)制，采用置信傳播(belief propagation，BP)算法進行譯碼，仿真圖對比結(jié)果如圖4。

圖4 仿真對比圖Fig.4 Simulation comparison graph

由圖4可知，在BER=10-6時，本文基于等差數(shù)列與原模圖構(gòu)造碼率為0.5的APP-QC-LDPC(4 000,2 000)碼相較于基于漸進邊增長算法構(gòu)造的PEG-QC-LDPC(4 000,2 000)碼，在同等條件下，凈編碼增益達到了約0.46 dB；相較于基于等差數(shù)列構(gòu)造的AP-QC-LDPC(4 000,2 000)碼，在圍長相等的條件下，性能提高了約0.55 dB。同樣，在BER為10-6時，基于等差數(shù)列與原模圖構(gòu)造的APP-QC-LDPC(4 000,2 000)碼與文獻[13]中利用修飾技術(shù)構(gòu)造的M-QC-LDPC(4 000,2 000)碼和文獻[14]中基于最大公約數(shù)構(gòu)造的GCD-QC-LDPC(4 000,2 000)碼相比，凈編碼增益分別約為0.9 dB和1.06 dB。從構(gòu)造方法的復雜度來看，可從2個方面對其進行分析：①編碼所需存儲的參數(shù)，編碼過程中用到的參數(shù)越少越好；②運算復雜度，一般指運算量和碼長的變化關(guān)系，即隨著碼長的變化，運算的次數(shù)相對應的越少越好。本文所構(gòu)造的碼型只需要存儲幾個初始值，存儲量小，通過等差公式，便可以獲得整個基矩陣，另外構(gòu)造原模圖節(jié)點較少，所需參數(shù)偏少。雖然與使用相同的等差數(shù)列構(gòu)造的AP-QC-LDPC碼型相比所需的參數(shù)略多，但與另外3種PEG-QC-LDPC碼、M-QC-LDPC碼和GCD-QC-LDPC碼相比，所需存儲的參數(shù)明顯較少。另一方面，本文的構(gòu)造方法，雖然增加了原模圖搜索機制，但是搜索節(jié)點較少，對編碼的運算復雜度影響不大。整體來說，本文構(gòu)造方法的編碼復雜度較小，同時因為原模圖的引入，使本文構(gòu)造的碼型具備了原模圖的低譯碼門限等優(yōu)點。綜上所述，本文構(gòu)造方法所構(gòu)造的碼型編譯碼簡單，且具有較好的糾錯性能。

6 結(jié) 論

本文針對QC-LDPC碼循環(huán)置換矩陣的移位次數(shù)確定問題，提出了一種基于等差數(shù)列和原模圖構(gòu)造QC-LDPC碼的新方法。通過該方法最終得到的QC-LDPC碼不僅可靈活變換碼長碼率，而且圍長至少為8。仿真結(jié)果表明，本文所提出的構(gòu)造方法構(gòu)造的APP-QC-LDPC碼優(yōu)于傳統(tǒng)經(jīng)典PEG算法構(gòu)造的PEG-QC-LDPC碼，優(yōu)于使用等差數(shù)列算法構(gòu)造的AP-QC-LDPC碼，也同樣優(yōu)于利用掩模技術(shù)構(gòu)造的M-QC-LDPC碼和基于最大公約數(shù)構(gòu)造的GCD-QC-LDPC碼，具有較好的糾錯性能。