基于原模圖的歐氏幾何準(zhǔn)循環(huán)LDPC碼

劉原華, 何 華

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

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

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

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

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

1 原模圖QC-LDPC碼

原模圖是節(jié)點(diǎn)相對(duì)較少的Tanner圖，記為

Gp=(V，C，E)。

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

B=(bij)m×n。

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

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

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

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

基于原模圖構(gòu)造歐氏幾何QC-LDPC碼，需先構(gòu)造具有低譯碼門(mén)限的多邊原模圖的基矩陣，再利用歐氏幾何的結(jié)構(gòu)特性設(shè)計(jì)循環(huán)矩陣的移位次數(shù)，并通過(guò)循環(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個(gè)元素與歐氏幾何GE(m,ps)中的pms個(gè)點(diǎn)一一對(duì)應(yīng)，因此,伽羅華域FG(pms)等價(jià)于GE(m,ps)[6]。FG(pms)中的每個(gè)元素可由其本原元α的冪次表示，歐氏幾何中的每個(gè)點(diǎn)也可由α的冪次來(lái)表示，其中α∞表示原點(diǎn)。

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

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

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

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

該向量包含ps個(gè)子向量，每個(gè)子向量為n維二進(jìn)制向量，其中第i個(gè)子向量vi是直線L上第i個(gè)點(diǎn)的關(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è)計(jì)

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

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

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

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

(1)

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

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

假設(shè)原歐氏幾何QC-LDPC碼的校驗(yàn)矩陣是由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)的基矩陣為一個(gè)γ行ρ列全1矩陣，為獲得形如式(1)的基矩陣，將矩陣H前γ列陣列的每列選擇一個(gè)子矩陣移入到左半邊陣列的對(duì)角線對(duì)應(yīng)的子矩陣Iaii(1≤i≤γ)中，基矩陣中的元素2對(duì)應(yīng)的循環(huán)子矩陣為2個(gè)不重疊的循環(huán)置換矩陣的疊加。以式(1)的基矩陣為例，改進(jìn)后的校驗(yà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è)計(jì)的原模圖QC-LDPC碼。

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

3 仿真結(jié)果

對(duì)改進(jìn)方法構(gòu)造的原模圖QC-LDPC碼和已有歐氏幾何碼[6]的譯碼門(mén)限進(jìn)行比較，同時(shí)采用二進(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碼的譯碼門(mén)限如表1所示。由其可見(jiàn)，與原歐氏幾何碼相比，改進(jìn)方法構(gòu)造的QC-LDPC碼譯碼門(mén)限更低，三組碼的門(mén)限改進(jìn)值均大于0.2。

表1 譯碼門(mén)限對(duì)比

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

4 結(jié)論

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