基于(17,9)平方剩余碼的廣義LDPC碼構造及性能研究

李西亞，黎 勇

(重慶郵電大學 重慶市移動通信技術重點實驗室，重慶 400065)

0 引 言

1960年代初，Gallager[1]首次提出了低密度奇偶校驗(low-density parity check, LDPC)碼的概念，它是一類優(yōu)秀的糾錯碼，具有較好的譯碼性能。近年來，LDPC碼的研究獲得了較大關注，在迭代譯碼情況下，LDPC碼性能可以逼近香農極限。傳統(tǒng)LDPC碼盡管有著較高的編碼增益，但其錯誤地板和譯碼復雜度往往較高。為了獲得更低的錯誤地板，1999年，Lentmaier 和Zigangirov首次構造了以漢明碼作為分量碼替換LDPC碼中單奇偶校驗(single parity-check, SPC)碼的廣義LDPC(generalized LDPC, GLDPC)碼，其仿真性能相比同碼率下的LDPC碼表現更加優(yōu)秀[2]。同時也在理論上證明了GLDPC碼能夠以較快的收斂速度取得較低的錯誤地板[2]。

GLDPC碼是對LDPC碼概念的進一步拓展。通過觀察GLDPC碼的Tanner圖[3]發(fā)現，GLDPC碼的變量節(jié)點和校驗節(jié)點使用更為靈活，不再局限于傳統(tǒng)的LDPC碼的變量節(jié)點和SPC節(jié)點，這也使得GLDPC碼的譯碼方式更為靈活[4]。目前常見的替換SPC碼的分量碼有BCH(Bose，Ray-Chaudhuri，Hocquenghem)，里德-所羅門(Reed-Solomon, RS)等碼[5]，它們的糾錯能力比SPC碼強，構造出的GLDPC碼的性能也比同碼率下的LDPC碼更加優(yōu)秀。然而這種為了增強校驗節(jié)點約束而引入了更多的校驗方程的方式，使得GLDPC碼的碼率大大降低。為了減少碼率損失，在設計 GLDPC碼時就必須減少LDPC 母碼(也稱全局碼)中被替換的校驗節(jié)點的數量，但這反過來又會影響碼字的性能。鑒于此，必須采用比傳統(tǒng)的漢明碼、BCH 碼更強大的碼型作分量碼，從而使只替換母碼中少部分校驗節(jié)點即可設計出性能優(yōu)異的GLDPC碼。本文針對分量碼為平方剩余(quadratic residue, QR)碼的GLDPC碼提出了一種構造方法，構造了一個QR-GLDPC碼。

QR碼是BCH碼的一個子類，有著比傳統(tǒng)的循環(huán)碼更大的最小漢明距離。1957年，QR碼由Prange[6]首次提出，因具有完美的代數結構，受到眾多代數編碼學家的青睞，這極大地加快了QR碼用于糾錯應用的研究進展。

1 GLDPC碼和QR碼介紹

1.1 GLDPC碼的定義

GLDPC碼的校驗矩陣構造由2部分組成，分別是校驗母矩陣HGLDPC和分量碼校驗矩陣HCPT，其中，HGLDPC有m0行n0列。基于以上2種矩陣擴展而成的GLDPC碼的校驗矩陣為HGLDPC,有M行N列，其中N=n0。如果HGLDPC是滿秩的，則GLDPC碼的碼率R可表示為

(1)

1.2 GLDPC碼的Tanner圖表示

通過Tanner圖可以直觀地看出GLDPC碼和LDPC碼的不同以及兩者之間的關系。圖1是使用分量碼替換SPC碼擴展而成的GLDPC碼的Tanner圖。圖1中，左邊黑色圓圈表示變量節(jié)點，右邊黑色實線方塊表示SPC節(jié)點，右下方黑色虛線方塊表示分量碼。

圖1 GLDPC碼的Tanner圖Fig.1 Tanner graph of GLDPC codes

1.3 QR碼介紹

QR碼是碼率略大于1/2的BCH碼的一個子類，在同等碼長下，比RS碼、漢明碼等具有更優(yōu)異的糾錯性能。

考慮在伽羅華域GF(2m)上定義一個QR碼(n,k,d)或(n,(n+1)/2,d)，其生成多項式為

g(x)=g0+g1X+…+gn-kXn-k

(2)

(2)式中：n是碼字長度，k=(n+1)/2是碼字信息位的長度；d是最小漢明距離。假設h(x)是QR碼的校驗多項式，由文獻[7]可知Xn+1的一個因式是g(x)，即

g(x)·h(x)=Xn+1

(3)

(3)式中，h(x)可以表示為如下的多項式形式

h(X)=h0+h1X+…+hkXk

(4)

(4)式中，h0=hk=1。經計算，可以得到(n-k)個方程式。

(5)

(5)式中，vn-i-j表示碼字中的一位。因此，可以推導出h(x)的反多項式，即

Xkh(X-1)hk+hk-1X+hk-2X2+…+h0Xk

(6)

不難看出Xkh(X-1)也是Xn+1的一個因式。假設把因式Xkh(X-1)看成一個生成多項式，它能夠產生一個(n,n-k)循環(huán)碼，相應的校驗矩陣可以表示為

(7)

通過觀察(5)式可知，QR碼字集合中的所有碼字與HQR的每一行相乘均為零，即HQR·vT=0。所以，矩陣HQR是QR碼的校驗矩陣。下文中所使用的替換SPC的分量碼(17,9)QR碼的校驗矩陣便是利用以上方法求出，從文獻[7]中我們可以知道，(17,9)QR碼的生成多項式為

g(x)=x8+x5+x4+x3+1

(8)

由(3)—(6) 式計算，可以得到

x9h(x-1)=x9+x6+x5+x4+x3+1

(9)

多項式x9h(x-1)可以生成一個(17,9)循環(huán)碼，則根據 (7) 式可知該碼的校驗矩陣為

該矩陣便是分量碼(17,9)QR的校驗矩陣。

2 GLDPC碼構造和譯碼

2.1 GLDPC碼的構造

假設使用參數(N,M,K,n,m,k)表示GLDPC碼，其中，N為碼長；M為校驗矩陣的行數；K表示信息位長度。同樣，n,m和k表示分量碼的對應參數。特別地，M=p·m，這里p是個整數。K,k分別與GLDPC碼校驗矩陣和分量碼校驗矩陣的秩相關[8]。

構造GLDPC碼的校驗矩陣HGLDPC需要2個步驟。

步驟1構造母碼LDPC碼的校驗矩陣HLDPC和分量碼校驗矩陣HCPT，且HLDPC的行重必須等于分量碼碼長。

步驟2對HLDPC逐行擴展，“0”位置使用長度為n-k的零向量替換，“1”位置使用HCPT中的某一列替換，注意每一列只能使用一次。

已知分量碼QR的糾錯能力強于SPC碼，即分量碼QR的置信值比SPC碼的置信值更大，在糾正一個錯誤變量節(jié)點的過程中，只需要有一個來自QR碼的置信值即可完成。相反，SPC碼的置信值較低，即使一個變量節(jié)點有多個來自SPC碼的置信值也未必能夠實現糾錯的目的。因此，確保變量節(jié)點接收到的信息至少有一個來自QR碼是譯碼成功的關鍵。鑒于此，本文提出了一種基于(17,9)QR碼的GLDPC碼的構造方法，其中，母碼LDPC碼的校驗矩陣的列重為2，具體構造方法如下。

步驟1在校驗母矩陣中，任選M0個SPC碼用QR碼替換，初步構造出GLDPC碼的校驗矩陣，M0≤M。 然后通過分析GLDPC碼的Tanner圖發(fā)現，有如圖2所示的3種類型的變量節(jié)點。圖2中，變量節(jié)點var0，2條邊分別連接SPC和QR；變量節(jié)點var1，2條邊全部來自SPC；變量節(jié)點var2，2條邊全部來自QR。

圖2 3種類型的變量節(jié)點Fig.2 Three types of variable nodes

步驟2找出所有var1和var2類型的變量節(jié)點，然后對2種不同類型的變量節(jié)點進行邊交換。圖3為交換邊的原理圖，任意交換節(jié)點var1和var2的一條邊，使它們成為節(jié)點var0的形式。

步驟3當步驟2中所有變量節(jié)點交換邊的過程完成之后，即可得到一個新的GLDPC碼。

圖3 交換邊的原理Fig.3 Principle of exchange sides

2.2 GLDPC碼的譯碼

文獻[2]中提出了一種GLDPC碼的軟判決迭代譯碼算法，其主體架構類似于LDPC碼的置信傳播譯碼算法，分量碼采用最大后驗概率APP譯碼[9]來計算外信息。然而該算法因為概率消息用似然比(likehood ratio, LR)表示，致使公式中出現了大量乘法運算，增加了運算復雜度。鑒于此，本文中概率消息采用對數似然比(log likehood ratio, LLR)表示，大量的乘法運算被簡化為加法運算，從而降低了運算復雜度。

(10)

設迭代次數l=1,2,…,L,譯碼算法流程如下。

(11)

圖4 變量節(jié)點i從第t個分量碼獲得的外信息Fig.4 External information obtained of the variable node ifrom the tcomponent code

步驟2若i≠N-1,對所有的變量節(jié)點計算置信值

(12)

該置信值作為下一次迭代中步驟1中的輸入；T(i)表示與變量節(jié)點i相連的所有分量碼節(jié)點的集合，其中，T(i) 表示去除t節(jié)點。

步驟3最后一次迭代，即l=L,計算變量節(jié)點上收到的所有置信值

(13)

步驟4軟判決，輸出：

(14)

2.3 分量碼的APP譯碼算法

APP譯碼算法[9]是一種適用于線性分組碼的最大后驗概率譯碼算法。下面介紹該算法以及算法中相關符號的含義。

假設v=(v1,v2,…,vN)是[N,K]線性分組碼中的一個碼字，線性分組碼的校驗矩陣用H表示，則H的轉置形式為

(15)

(15)式中，hn=(hn1,hn2,…,hn(N-K))，1≤n≤N。

如果定義符號v[1,n]=(v1,v2,…,vn)，

(16)

對于已給定的校驗矩陣H，存在一個長度為N的網格圖，μ(s,n)表示在狀態(tài)s時，路徑長度為n的度量值，其中，1≤n≤N。

碼字v=(v1,v2,…,vN)通過AWGN信道傳送，在接收端，信道的輸出碼字是r=(r1,r2,…,rN)。

輸入：P(r1|v1)，P(r2|v2)，…，P(rn|vn)。

步驟2對n=1,…,N更新

μ(s,n)=μ(s,n-1)P(rn|vn=0)+

μ(s+hn,n-1)P(rn|vn=1)

步驟3對n=1,…,N，設

等號成立的條件是P(rn|vn=0)≠P(rn|vn=1)。

輸出：P(v1=0|r,v),…,P(vN=0|r,v)。

3 仿真結果

本文采用(17,9)QR碼作為分量碼來研究GLDPC與LDPC碼在不同碼長和碼率條件下的性能，仿真條件為AWGN信道，仿真平臺VS2010，采用C/C++語言編程。LDPC碼的校驗矩陣與GLDPC碼的校驗矩陣相同，譯碼中最大迭代次數為50次。

利用邊遞增(progressive edge-growth, PEG)算法[10]構造規(guī)則的母碼LDPC碼的校驗矩陣，其列是476，行是56，列重是2，行重是17。使用分量碼(17,9)QR碼對LDPC碼進行擴展，生成(476,252,224,17,9,8)QR-GLDPC碼，碼率為0.471，仿真結果如圖5所示。由仿真結果可知，QR-GLDPC碼的性能優(yōu)于同等碼率下的LDPC碼，即使我們選擇最大迭代次數為5，GLDPC碼性能依然超過LDPC碼的性能。此外，可以看到在最大迭代次數為20時，GLDPC的性能得到顯著提升，這意味著，GLDPC碼經過20次迭代便可快速收斂。它也表明，GLDPC碼的平均迭代次數低于LDPC碼。因此，GLDPC碼相比LDPC碼，有著更快的收斂速度。

圖5 GLDPC碼與LDPC碼性能Fig.5 Performance of GLDPC and LDPC

同樣，利用PEG算法構造規(guī)則的母碼LDPC碼的校驗矩陣，其列是952，行是112，列重和行重分別是2和17。用(17,9)QR碼作為分量碼進行擴展，得到(952,504,448,17,9,8)QR-GLDPC碼，碼率為0.471，仿真結果如圖6所示。與LDPC碼相比，QR-GLDPC碼性能有明顯優(yōu)勢。同時，在相等碼率下，BER為4×10-5時，碼長952的GLDPC碼與碼長476的GLDPC碼相比，有近0.8 dB的性能增益。

在同等碼長不同碼率條件下，利用上文中碼長為476的母矩陣構造出(476,238,238,17,9,8)GLDPC碼，碼率為0.5(仿真結果如圖6所示)。碼率為0.471的GLDPC碼性能超過碼率為0.5的GLDPC碼性能。其中碼率0.471的碼字總共替換28個SPC節(jié)點，每個分量碼對應17個變量節(jié)點，17×28=476，恰好保證每個變量節(jié)點有一條邊來自QR，而碼率為0.5的碼字總共替換了26個SPC，17×26<476，即有部分變量節(jié)點的邊全部來自SPC，導致譯碼性能大大降低。

4 結 論

本文提出了一種基于(17,9)QR碼的GLDPC碼的構造方法，并簡化了基于線性分組碼的GLDPC碼的譯碼算法。仿真結果表明，在AWGN信道中，基于(17,9)QR碼的GLDPC碼相比同碼率下的LDPC碼，在錯誤比特率和譯碼收斂速度上都取得了更優(yōu)異的表現。

圖6 同碼率不同碼長、同碼長不同碼率GLDPC碼性能比較Fig.6 Comparison of the performance of different length of GLDPC at the same rate and the same length of GLDPC at the different rate