劉原華, 何 華

(西安郵電大學(xué) 通信與信息工程學(xué)院， 陜西 西安 710121)

低密度奇偶校驗(low-density parity-check， LDPC)碼是一種具有稀疏校驗矩陣的線性分組碼，能夠利用低復(fù)雜度迭代譯碼算法達(dá)到接近香農(nóng)限的糾錯性能。LDPC碼可分為隨機(jī)LDPC碼和結(jié)構(gòu)化LDPC碼。隨機(jī)LDPC碼圍長較大，性能優(yōu)異，但由于缺乏一定的結(jié)構(gòu)特性，編碼復(fù)雜度高，不利于硬件實現(xiàn)，且校驗矩陣的存儲復(fù)雜度也較高。結(jié)構(gòu)化LDPC碼具有循環(huán)或準(zhǔn)循環(huán)的結(jié)構(gòu)，可實現(xiàn)線性復(fù)雜度的編譯碼，中短碼長時性能可與隨機(jī)碼相比擬，正逐步進(jìn)入各種通信領(lǐng)域，在中國數(shù)字電視地面廣播傳輸標(biāo)準(zhǔn)、歐洲第二代數(shù)字電視地面廣播標(biāo)準(zhǔn)、無線局域網(wǎng)IEEE 802.16n中均已采納準(zhǔn)循環(huán)LDPC(quasi-cyclic LDPC，QC-LDPC)碼作糾錯編碼方式。

絕大多數(shù)歐氏幾何LDPC碼都是結(jié)構(gòu)化的循環(huán)碼或準(zhǔn)循環(huán)碼，可以通過移位寄存器實現(xiàn)線性復(fù)雜度編碼,同時可利用多種譯碼算法實現(xiàn)復(fù)雜度、速度以及糾錯性能之間的良好折衷。利用歐氏幾何的結(jié)構(gòu)特性,可構(gòu)造出不包含4環(huán)的性能優(yōu)異的LDPC碼[1-7]?；跉W氏幾何的QC-LDPC碼[6]雖然不包含4環(huán)，但在校驗矩陣的行重和列重給定的情況下，其譯碼門限就確定了，無法進(jìn)一步有效改善QC-LDPC碼的糾錯性能。

原模圖QC-LDPC碼可以由一個很小的原模圖通過復(fù)制和循環(huán)矩陣擴(kuò)展得到，其糾錯性能由原模圖、復(fù)制次數(shù)以及循環(huán)矩陣的移位數(shù)共同決定。原模圖QC-LDPC碼與一般的QC-LDPC碼的不同之處在于，其基矩陣中的元素不僅僅局限于0和1，可以是任意小于其復(fù)制次數(shù)的非負(fù)整數(shù)，即原模圖具有允許多邊存在的特點，有利于降低碼的譯碼門限，進(jìn)一步優(yōu)化QC-LDPC碼的性能?；赟idon序列的QC-LDPC碼[8]屬于一種原模圖QC-LDPC碼，其基矩陣中的元素均為2。對于給定的原模圖，為避免短環(huán)的出現(xiàn)，在設(shè)計循環(huán)矩陣的移位次數(shù)時需考慮原模圖中的環(huán)分布情況[9-12]。例如,在利用PEG算法構(gòu)造原模圖QC-LDPC碼時，通常先要基于PEG算法構(gòu)造原模圖，再借助附加的環(huán)檢測算法來設(shè)計循環(huán)矩陣的移位次數(shù)[13-15]。這種方法可有效地構(gòu)造短碼長的性能優(yōu)異碼，但當(dāng)碼長增加時，該方法的復(fù)雜度將很高。

為簡化構(gòu)造算法的復(fù)雜度，同時改善歐氏幾何QC-LDPC碼的糾錯性能，本文擬給出一種基于原模圖的歐氏幾何QC-LDPC碼構(gòu)造方法。利用歐氏幾何的結(jié)構(gòu)特性設(shè)計循環(huán)矩陣的移位次數(shù)，有效避免短環(huán)的出現(xiàn)，簡化實現(xiàn)復(fù)雜度；同時將原模圖多邊的特點引入歐氏幾何碼的基矩陣，降低譯碼門限，進(jìn)一步優(yōu)化其糾錯性能。

1 原模圖QC-LDPC碼

原模圖是節(jié)點相對較少的Tanner圖，記為

Gp=(V，C，E)。

其中V是變量節(jié)點集和，C是校驗節(jié)點集和，E是邊集和。原模圖對應(yīng)的基矩陣為

B=(bij)m×n。

其中m為校驗節(jié)點的個數(shù)，n為變量節(jié)點的個數(shù)，bij為第i個校驗節(jié)點和第j個變量節(jié)點之間連接邊的條數(shù)，當(dāng)bij>1時，原模圖中有并行邊的存在。對原模圖進(jìn)行T次復(fù)制，然后把T條相同類型的變量節(jié)點和校驗節(jié)點之間的邊置換，可以擴(kuò)展成不同大小的圖，這種圖稱為導(dǎo)出圖G，對應(yīng)的LDPC碼稱為原模圖LDPC碼。若邊置換為循環(huán)置換，則對應(yīng)的LDPC碼為原模圖QC-LDPC碼。

原模圖QC-LDPC碼可由其基矩陣經(jīng)循環(huán)矩陣擴(kuò)展得到：將基矩陣中的非零元素，用bij個不重疊的循環(huán)置換矩陣的和替換，零元素用全零矩陣替換，即可得到原模圖QC-LDPC碼的校驗矩陣H，該操作稱為循環(huán)矩陣擴(kuò)展。

2 原模圖歐氏幾何QC-LDPC碼

LDPC碼的性能可由譯碼門限值來衡量，門限值是LDPC碼成功譯碼所能容忍的最小信噪比，當(dāng)信道的信噪比高于門限值時，碼集中的幾乎任何一種碼的誤比特率都將隨著迭代次數(shù)或碼長的增加而趨于零，否則碼集中的碼的誤比特率將始終大于某個常數(shù)。因此，這個門限值是評價LDPC碼性能的重要參數(shù)。外信息轉(zhuǎn)移(extrinsic information transfer，EXIT)圖技術(shù)是分析LDPC碼迭代譯碼性能的有效方法之一，可根據(jù)LDPC碼的度分布，計算其譯碼門限。具有相同度分布的QC-LDPC碼可以具有不同的基矩陣，從而具有不同的譯碼收斂性能，而傳統(tǒng)的EXIT圖無法區(qū)分這些QC-LDPC碼譯碼性能的不同，故需引入基于原模圖的EXIT(protograph EXIT，PEXIT)圖技術(shù)[16]，用以分析相同度分布不同基矩陣的原模圖QC-LDPC碼的譯碼門限。

基于原模圖構(gòu)造歐氏幾何QC-LDPC碼，需先構(gòu)造具有低譯碼門限的多邊原模圖的基矩陣，再利用歐氏幾何的結(jié)構(gòu)特性設(shè)計循環(huán)矩陣的移位次數(shù)，并通過循環(huán)矩陣擴(kuò)展獲得不包含4環(huán)的歐氏幾何原模圖QC-LDPC碼。

2.1 歐氏幾何

令伽羅華域FG(pms)為域FG(ps)的擴(kuò)域，可以看作是FG(ps)上的所有m維向量構(gòu)成的向量空間，F(xiàn)G(pms)上的任意元素可表示成為FG(ps)上的m維向量，域FG(pms)上的pms個元素與歐氏幾何GE(m,ps)中的pms個點一一對應(yīng)，因此,伽羅華域FG(pms)等價于GE(m,ps)[6]。FG(pms)中的每個元素可由其本原元α的冪次表示，歐氏幾何中的每個點也可由α的冪次來表示，其中α∞表示原點。

將有限域FG(pms)中的一個本原元記為α，令

ai=αi-1(i=1,2,…,n)

v(ai)=(v1,v2,…,vn)，

vL=(v1,v2,…,vps)，

該向量包含ps個子向量，每個子向量為n維二進(jìn)制向量，其中第i個子向量vi是直線L上第i個點的關(guān)聯(lián)向量。

任一循環(huán)類中任一直線均可作為此循環(huán)類的代表元，將代表元的關(guān)聯(lián)向量進(jìn)行分段循環(huán)移位n次即可得到該循環(huán)類中的其他直線的關(guān)聯(lián)向量。

2.2 改進(jìn)歐氏幾何碼設(shè)計

對于第i個循環(huán)類(i=1,2,…,K)，將該類中n條直線的關(guān)聯(lián)向量作為列，可構(gòu)造出nps×n階矩陣Hi。由直線的循環(huán)特性可知，Hi可設(shè)計成一個由n×n的循環(huán)置換矩陣組成的ps×1矩陣陣列，Hi的每行包含1個非零元素1，每列包含ps個非零元素1，其余元素皆為0，即Hi的行重為1，列重為ps。將這K個矩陣H1，H2,…，HK作為子矩陣構(gòu)造矩陣

選擇H的任意γ×ρ子陣列，即可得到(γ，ρ)規(guī)則歐氏幾何QC-LDPC碼[6]，其中γ和ρ為碼校驗矩陣的行重和列重。該碼的基矩陣為一個γ行ρ列全1矩陣，其譯碼門限可由PEXIT算法計算得到。因此，無論如何選擇H的子陣列，只要參數(shù)γ和ρ確定了，其譯碼門限就固定不變了，無法進(jìn)一步有效改善QC-LDPC碼的糾錯性能。為解決這一問題，考慮利用原模圖碼的特點，將大于1的元素引入到基矩陣中，從而優(yōu)化QC-LDPC碼的糾錯性能。

原模圖QC-LDPC碼中存在不可避免短環(huán)的問題[9]，若QC-LDPC碼的基矩陣包含元素3，則無論如何設(shè)計循環(huán)矩陣的維數(shù)(即復(fù)制次數(shù))和循環(huán)矩陣的移位次數(shù)，必定存在長度為6的不可避免短環(huán)；若基矩陣的某行或某列包含兩個2，則必定存在長度為8的不可避免短環(huán)?；谝陨辖Y(jié)論，在設(shè)計基矩陣時，除了元素0和1，只引入元素2，不考慮元素3，且每行每列最多包含一個2。由于LDPC碼校驗矩陣的行重大于列重，即基矩陣的列數(shù)ρ大于行數(shù)γ，不失一般性，將元素2設(shè)計在基矩陣的前γ列，且處在基矩陣左邊γ行γ列子矩陣的對角線位置。為保證LDPC碼的列重不變，基矩陣的前γ列每列需設(shè)置一個元素0，為保證LDPC碼的行重不變，這γ個0需處在不同行且不同列。

例如，當(dāng)γ=4，ρ=8時，基矩陣可設(shè)計為

(1)

其譯碼門限可由PEXIT算法計算得到，與4行8列的全1基矩陣相比，式(1)的譯碼門限獲得了0.247 5的改進(jìn)，其對應(yīng)原模圖QC-LDPC碼的性能可得到有效提高。

利用歐氏幾何的結(jié)構(gòu)特性可設(shè)計循環(huán)矩陣的移位次數(shù)，再通過循環(huán)矩陣擴(kuò)展，即可獲得不包含4環(huán)的歐氏幾何原模圖QC-LDPC碼。

假設(shè)原歐氏幾何QC-LDPC碼的校驗矩陣是由n×n的循環(huán)置換矩陣組成的γ×ρ的矩陣陣列，具有形式

(2)

其中Iaij為n×n的循環(huán)置換矩陣，可由單位陣I每行向右循環(huán)移位aij位得到，而aij為該循環(huán)置換矩陣的循環(huán)移位次數(shù)，其值由歐氏幾何中直線的關(guān)聯(lián)向量確定。

矩陣(2)的基矩陣為一個γ行ρ列全1矩陣，為獲得形如式(1)的基矩陣，將矩陣H前γ列陣列的每列選擇一個子矩陣移入到左半邊陣列的對角線對應(yīng)的子矩陣Iaii(1≤i≤γ)中，基矩陣中的元素2對應(yīng)的循環(huán)子矩陣為2個不重疊的循環(huán)置換矩陣的疊加。以式(1)的基矩陣為例，改進(jìn)后的校驗矩陣

H′=[h1,h2,h3,h4,h5,h6,h7,h8],

(3)

h1=[Ia11+Ia21,0,Ia31,Ia41]T,
h2=[0,Ia22+Ia12,Ia32,Ia42]T,
h3=[Ia13,Ia23,Ia33+Ia43,0]T,
h4=[Ia14,Ia24,0,Ia44+Ia34]T,
h5=[Ia15,Ia25,Ia35,Ia45]T,
h6=[Ia16,Ia26,Ia36,Ia46]T,
h7=[Ia17,Ia27,Ia37,Ia47]T,
h8=[Ia18,Ia28,Ia38,Ia48]T,。

其中0為零矩陣，其零空間即為所設(shè)計的原模圖QC-LDPC碼。

2.3 碼結(jié)構(gòu)分析

3 仿真結(jié)果

對改進(jìn)方法構(gòu)造的原模圖QC-LDPC碼和已有歐氏幾何碼[6]的譯碼門限進(jìn)行比較，同時采用二進(jìn)制相移鍵控調(diào)制下的加性高斯白噪聲信道，仿真比較改進(jìn)方法和已有方法構(gòu)造的QC-LDPC碼在置信傳播迭代譯碼算法下的誤比特率(bit error rate，BER)和誤幀率(frame error rate，F(xiàn)ER)，譯碼的最大迭代次數(shù)設(shè)置為100次。

兩種方法構(gòu)造的三組(6,9)，(4,8)和(4,10)規(guī)則QC-LDPC碼的譯碼門限如表1所示。由其可見，與原歐氏幾何碼相比，改進(jìn)方法構(gòu)造的QC-LDPC碼譯碼門限更低，三組碼的門限改進(jìn)值均大于0.2。

表1 譯碼門限對比

圖1 兩種方法構(gòu)造QC-LDPC碼的糾錯性能

4 結(jié)論

為降低碼的譯碼門限,首先構(gòu)造了基于多邊的原模圖的基矩陣，然后利用歐氏幾何的結(jié)構(gòu)特性設(shè)計基矩陣對應(yīng)的循環(huán)矩陣的移位次數(shù)，獲得了不包含4環(huán)的歐氏幾何原模圖QC-LDPC碼。仿真結(jié)果表明，與已有歐氏幾何碼相比，改進(jìn)方法構(gòu)造的QC-LDPC碼通過降低譯碼門限獲得了更優(yōu)的糾錯性能。同時，所構(gòu)造的碼具有準(zhǔn)循環(huán)的結(jié)構(gòu)，具有編譯碼實現(xiàn)簡單的特點。