馮志宇，彭海英，郭振勇，胡 蓉

(1.重慶郵電大學(xué) 光電學(xué)院，重慶400065；2.重慶郵電大學(xué) 移通學(xué)院，重慶 401520)

0 引 言

低密度奇偶校驗(yàn)(low-density parity-check, LDPC)碼由Gallager[1]于1962年所提出，它是一種性能逼近Shannon限的好碼。近年來(lái)，大量的研究人員為了獲得高效的LDPC碼，提出了各種LDPC碼的構(gòu)造方法。根據(jù)構(gòu)造方式的不同，大致可以分為2種：①隨機(jī)構(gòu)造法，根據(jù)一定的設(shè)計(jì)準(zhǔn)則利用計(jì)算機(jī)搜索構(gòu)造所需要的校驗(yàn)矩陣；②結(jié)構(gòu)化構(gòu)造法，利用代數(shù)方法或者組合方法確定性構(gòu)造所需要的LDPC碼校驗(yàn)矩陣。

準(zhǔn)循環(huán)低密度奇偶校驗(yàn)(quasi-cyclic low-density parity-check, QC-LDPC)碼[2]是結(jié)構(gòu)化LDPC碼中一個(gè)支系，占據(jù)著重要的位置，可以由指數(shù)矩陣和擴(kuò)展維數(shù)表示得到的碼字結(jié)構(gòu)。以往我們主要關(guān)注校驗(yàn)矩陣的構(gòu)造，使之滿足無(wú)短環(huán)或其他條件的要求，但是實(shí)際上編碼復(fù)雜度也是制約碼字性能及實(shí)際應(yīng)用的一個(gè)重要因素。Richardson等[3]通過(guò)對(duì)校驗(yàn)矩陣執(zhí)行分塊和行列變換，將復(fù)雜度降為O(n+g2)。當(dāng)g數(shù)值較大時(shí)，復(fù)雜度也會(huì)呈近似二次方增長(zhǎng)。Myung等[4]利用QC-LDPC碼準(zhǔn)循環(huán)特點(diǎn)，把校驗(yàn)矩陣的校驗(yàn)部分直接設(shè)計(jì)成近似下三角結(jié)構(gòu)，達(dá)到快速編碼和降低復(fù)雜度的雙重效果。已經(jīng)提出的典型具備近似下三角結(jié)構(gòu)的編碼方案有雙對(duì)角線結(jié)構(gòu)[5]和準(zhǔn)雙對(duì)角線結(jié)構(gòu)[6]，可以直接通過(guò)校驗(yàn)矩陣進(jìn)行迭代，求得校驗(yàn)碼元序列，最后完成編碼，并已在實(shí)際通信系統(tǒng)中得到了應(yīng)用。

此后眾多研究人員對(duì)上述校驗(yàn)部分進(jìn)行了深入研究，提出了一些有效且結(jié)構(gòu)良好的編碼方案。然而，這些在雙對(duì)角線基礎(chǔ)上改進(jìn)的方案，雙對(duì)角線為單位矩陣或一對(duì)角線為單位矩陣，另一對(duì)角線為移位矩陣，形式固定且列重為2。Tam等[7]提出的改進(jìn)方案中第一列列重設(shè)為3，但是對(duì)這3個(gè)移位矩陣系數(shù)做出了限制。此外，以往研究人員主要關(guān)注校驗(yàn)部分的設(shè)計(jì)，對(duì)信息部分矩陣的設(shè)計(jì)研究較少，構(gòu)造出的校驗(yàn)矩陣中存在少量的四環(huán)和大量的六環(huán)，對(duì)碼字的性能有一定的不利影響。王汝言等[8]提出了一種大圍長(zhǎng)低復(fù)雜的QC-LDPC碼，碼字性能優(yōu)異。但是該構(gòu)造方法分別獨(dú)立設(shè)計(jì)校驗(yàn)矩陣的信息部分和校驗(yàn)部分，最后驗(yàn)證得到的校驗(yàn)矩陣圍長(zhǎng)為8，其構(gòu)造過(guò)程證明繁瑣。因此，怎樣通過(guò)直接構(gòu)造校驗(yàn)矩陣使之同時(shí)兼容大圍長(zhǎng)和快速編碼雙重特性是一個(gè)值得深入研究的課題。

本文針對(duì)上述難題，設(shè)計(jì)了一種大圍長(zhǎng)可快速編碼的QC-LDPC構(gòu)造方法。首先提出一種結(jié)構(gòu)新穎更加靈活適合構(gòu)造大圍長(zhǎng)QC-LDPC碼的低復(fù)雜度快速編碼方案，其次對(duì)利用最大公約數(shù)(greatest common divisor, GCD)算法得到的指數(shù)矩陣進(jìn)行行列操作，驗(yàn)證得到的新指數(shù)依然滿足大圍長(zhǎng)的特性，最后與掩飾矩陣和快速編碼方法相結(jié)合，達(dá)到了QC-LDPC碼大圍長(zhǎng)和快速編碼的目的。本文所提方法無(wú)須對(duì)QC-LDPC碼的信息部分和校驗(yàn)部分分別構(gòu)造，而是直接在圍長(zhǎng)為8的原指數(shù)矩陣上通過(guò)一系列變化來(lái)實(shí)現(xiàn)低復(fù)雜度的快速編碼。最后，通過(guò)仿真驗(yàn)證了所構(gòu)造的QC-LDPC碼的優(yōu)異性能。

1 基于GCD算法的QC-LDPC碼

QC-LDPC碼是一種高度結(jié)構(gòu)化的LDPC碼，其校驗(yàn)矩陣H是由單位矩陣循環(huán)移位后的循環(huán)置換矩陣組成。該矩陣形式為[9]

(1)

(1)式中,Hj,l=I(pj,l)表示校驗(yàn)矩陣中的子矩陣,其中，1≤j≤J，1≤l≤L，I(pj,l)表示將一個(gè)P×P的單位矩陣向右循環(huán)移位pj,l位得到的循環(huán)置換矩陣。根據(jù)QC-LDPC碼的循環(huán)特性可以得到對(duì)應(yīng)的指數(shù)矩陣為

(2)

因此，QC-LDPC碼的構(gòu)造可以歸結(jié)為指數(shù)矩陣E的設(shè)計(jì)。QC-LDPC碼的校驗(yàn)矩陣由循環(huán)置換矩陣和零矩陣構(gòu)成，這一特點(diǎn)使其可以通過(guò)簡(jiǎn)單的移位寄存器實(shí)現(xiàn)線性編碼，且只需要1/P的存儲(chǔ)空間。

在指數(shù)矩陣中，如果若干個(gè)元素(p1,p2,…,p2l)構(gòu)成一個(gè)長(zhǎng)度為2l的環(huán)，則對(duì)應(yīng)的校驗(yàn)矩陣H中也存在與之對(duì)應(yīng)的P個(gè)同樣大小的環(huán)?？梢钥闯鲈赒C-LDPC碼的校驗(yàn)矩陣中，短環(huán)是以集合的形式出現(xiàn)。QC-LDPC碼中長(zhǎng)為2l的環(huán)可以表示為(j0,l0),(j1,l0),(j1,l1),…,(jl-1,l0),(j0,l0)，其中，(jk,lk)表示H矩陣第jk行l(wèi)k列所在的循環(huán)子矩陣I(pjk,lk)。(jk,lk)和(jk+1,lk+1)之間的子矩陣可以看作(jk+1,lk)。顯而易見(jiàn)，要正確地表示一個(gè)環(huán)，需滿足jk≠jk+1，且lk≠lk+1。文獻(xiàn)[10]提出長(zhǎng)度為2l的環(huán)檢測(cè)定理。

定理1對(duì)于指數(shù)矩陣E中的序列pj0,l0,pj1,l0,…,pjl-1,l0,pj0,l0，其中，pjk,lm和pjk,ln在同一行或同一列，pjk,lm和pje,lf在不同行且不同列，則pj0,l0,pj1,l0,…,pjl-1,l0,pj0,l0構(gòu)成長(zhǎng)為2l環(huán)的充分必要條件是

(3)

短環(huán)的存在會(huì)導(dǎo)致LDPC碼在譯碼時(shí)相關(guān)信息經(jīng)過(guò)2次迭代后互相關(guān)，產(chǎn)生錯(cuò)誤傳播信息，譯碼收斂速度減慢，甚至不能收斂，造成誤碼比特率(bit error rate, BER)性能變差。因此，若要使構(gòu)造的QC-LDPC碼中不含長(zhǎng)為2l的環(huán)，就必須通過(guò)一定的設(shè)計(jì)規(guī)則，使得(3)式不成立。圖1給出了6環(huán)存在的6種形狀。

圖1 6環(huán)的6種形狀Fig.1 Six types of six cycles

張國(guó)華等[11]提出了一種基于GCD算法構(gòu)造的QC-LDPC碼，得到的碼字無(wú)4環(huán)和6環(huán)，且具有大圍長(zhǎng)特性。其指數(shù)矩陣形式為

(4)

每個(gè)單位矩陣的移位值為pj,l=aj-1·(l-1)，其中,j=1,2,…,J；l=1,2,…,L；0≤a0

2 大圍長(zhǎng)可快速編碼的QC-LDPC碼設(shè)計(jì)

2.1 一種快速編碼算法及編碼復(fù)雜度分析

通過(guò)研究我們知道無(wú)論是采用傳統(tǒng)編碼還是高斯消元法，其編碼復(fù)雜度較高，不利于實(shí)際應(yīng)用。經(jīng)過(guò)研究人員的不懈努力及QC-LDPC碼的發(fā)現(xiàn)，提出了眾多快速編碼方案，降低了編碼復(fù)雜度，取得了優(yōu)異的碼字性能。本文提出一種改進(jìn)型下三角結(jié)構(gòu)的快速編碼算法，靈活性更好，對(duì)直接構(gòu)造大圍長(zhǎng)可快速編碼的QC-LDPC碼有很大的促進(jìn)作用。

將QC-LDPC碼的校驗(yàn)矩陣H分為(5)式所示的2部分。

H=[HkHp]

(5)

信息部分矩陣Hk為

(6)

快速編碼算法主要是對(duì)校驗(yàn)部分Hp的構(gòu)造，本文所提出的可快速編碼算法的校驗(yàn)部分Hp矩陣為

(7)

(7)式中，hi,j表示校驗(yàn)部分矩陣Hp的第i行，第j列的非單位矩陣，2≤i≤M,1≤j≤M。第1列3個(gè)子矩陣對(duì)應(yīng)的移位值非零且不相等，從第2列到最后一列每一列的hi,j只有1個(gè)非零移位值且是隨機(jī)存在的，也即列重是2。

將碼字序列c分為2部分：信息比特序列和校驗(yàn)比特序列，如(8)式所示。

c=[sp]

(8)

由碼字生成式HcT=0，把(5)式和(8)式代入其中可得：

HksT=HppT

(9)

把(6)式和(7)式代入(9)式展開(kāi)后形式為

(10)

然后對(duì)矩陣的每一行進(jìn)行計(jì)算，得到以下等式：

(11)

i=2,…,M-3

(12)

i=M-2

(13)

i=M-1

(14)

i=M

(15)

由(11)式和(12)式可求得pi(i=2,…,M-2)為

(16)

根據(jù)(13)式和(14)式求得pM-1，pM分別為

(17)

根據(jù)(15)式可得p1為

(18)

由上述一系列式子可以看出，校驗(yàn)比特序列可以直接以簡(jiǎn)單迭代的方式逐一求出，進(jìn)而與信息比特序列結(jié)合起來(lái)組成碼字c，最后完成編碼。

編碼復(fù)雜度主要是對(duì)編碼過(guò)程中產(chǎn)生的乘法運(yùn)算次數(shù)、加法運(yùn)算次數(shù)、存儲(chǔ)復(fù)雜度來(lái)進(jìn)行分析。乘法運(yùn)算和加法運(yùn)算的運(yùn)算量直接決定著運(yùn)算復(fù)雜度，而這一點(diǎn)正是能否實(shí)現(xiàn)線性快速編碼的關(guān)鍵。因?yàn)闃?gòu)造的校驗(yàn)部分矩陣Hp第2列至最后一列每列列重為2，且非零移位值hi,j是隨機(jī)存在的，為了計(jì)算復(fù)雜度，對(duì)第2列至最后一列取hi,i(2≤i≤M)為非零值。下面對(duì)上述提出的快速編碼算法計(jì)算乘法和加法次數(shù)，結(jié)果如表1所示。表1中，R表示碼率，P表示指數(shù)矩陣的擴(kuò)展維數(shù)，n表示LDPC碼的碼長(zhǎng)，且n=N×P。

表1 快速編碼算法的計(jì)算復(fù)雜度Tab.1 Computation complexity of fast encoding algorithm

對(duì)表1結(jié)果分析可知，每個(gè)校驗(yàn)位分矢量的計(jì)算復(fù)雜度為O(n)。這說(shuō)明使用該形式構(gòu)造的QC-LDPC碼編碼復(fù)雜度與碼字的碼長(zhǎng)成線性關(guān)系，能實(shí)現(xiàn)線性快速編碼，為后面構(gòu)造大圍長(zhǎng)可快速編碼的QC-LDPC碼奠定了基礎(chǔ)。

2.2 符合可快速編碼的大圍長(zhǎng)QC-LDPC碼設(shè)計(jì)

一般情況下構(gòu)造低編碼復(fù)雜度的快速編碼方法，研究人員更多關(guān)注的是校驗(yàn)部分的構(gòu)造，信息部分常常采用隨機(jī)方法或者其他方案，對(duì)構(gòu)造的碼字圍長(zhǎng)考慮較少，存在數(shù)量較多的短環(huán)，而短環(huán)的存在會(huì)嚴(yán)重影響碼字性能。文獻(xiàn)[8]提出的大圍長(zhǎng)快速編碼方法是分別獨(dú)立構(gòu)造指數(shù)矩陣的信息部分和校驗(yàn)部分，然后證明圍長(zhǎng)為8，使得構(gòu)造的LDPC碼同時(shí)具備了大圍長(zhǎng)和低編碼復(fù)雜度的可快速編碼的雙重特點(diǎn)，最后仿真驗(yàn)證了碼字性能。

上述方案都是分別對(duì)校驗(yàn)矩陣的2部分進(jìn)行構(gòu)造，不管是構(gòu)造方法還是圍長(zhǎng)都存在不足。觀察上述快速編碼方案可知，若采用GCD算法直接構(gòu)造指數(shù)矩陣，然后把其校驗(yàn)部分轉(zhuǎn)化為(7)式，受制于對(duì)角線上單位矩陣的存在，勢(shì)必會(huì)影響最后得到的碼字圍長(zhǎng)大小狀態(tài)。本文利用GCD算法構(gòu)造的指數(shù)矩陣的某一行或某一列加減相等的公差，不影響圍長(zhǎng)的大小，依然保持圍長(zhǎng)為8的特性。下面圍繞定理2展開(kāi)討論。

定理2如果基于GCD算法構(gòu)造的QC-LDPC碼沒(méi)有4環(huán)、6環(huán)存在，則分別對(duì)指數(shù)矩陣中的某行或某列加減相等的公差后，所得到的指數(shù)矩陣圍長(zhǎng)不變。

證明圍長(zhǎng)大小不變意味著指數(shù)矩陣中不存在4環(huán)和6環(huán)，下面分別驗(yàn)證2種環(huán)狀態(tài)。

1)無(wú)4環(huán)驗(yàn)證。不失一般性，任取指數(shù)矩陣中一個(gè)2×2維的子矩陣，令0≤i

air-ais+ajs-ajr≠0(modP)

(19)

設(shè)公差為di≥0,dj≥0(0≤i,j≤J-1)，對(duì)指數(shù)矩陣的任意2行的數(shù)值進(jìn)行加減公差操作。若存在4環(huán)，則根據(jù)環(huán)檢測(cè)定理得到的充要條件為

(air+di)-(ais+di)+(ajs+dj)-

(ajr+dj)=0(modP)

(20)

對(duì)(20)式計(jì)算可得：

air-ais+ajs-ajr=0(modP)

(21)

(21)式與 (19) 式矛盾，故不存在4環(huán)。同理，對(duì)指數(shù)矩陣的任意2列也執(zhí)行上述同樣的操作，可證明也不存在4環(huán)。進(jìn)而可知，對(duì)指數(shù)矩陣的某行或某列加減相等的公差不會(huì)存在4環(huán)。

2)無(wú)6環(huán)驗(yàn)證。根據(jù)圖1可知，矩陣中存在6環(huán)有6種情況。不失一般性，任取指數(shù)矩陣的3行3列，即0≤i

air-ais+ajs-ajt+akt-akr≠0(modP)

(22)

設(shè)公差di≥0,dj≥0,dk≥0(0≤i,j,k≤J-1)，對(duì)指數(shù)矩陣的任意3行的數(shù)值進(jìn)行加減公差操作。若存在6環(huán)，則根據(jù)環(huán)檢測(cè)定理得到的充要條件為

(air+di)-(ais+di)+(ajs+dj)-(ajt+dj)+

(akt+dk)-(akr+dk)=0(modP)

(23)

對(duì)(23)式計(jì)算可得：

air-ais+ajs-ajt+akt-akr=0(modP)

(24)

(24)式與 (22) 式矛盾，故不存在6環(huán)。同理，對(duì)形如圖1a指數(shù)矩陣的任意3列也執(zhí)行上述同樣的操作，可證明也不存在6環(huán)。同樣，可以對(duì)6環(huán)存在的其他5種形狀用上述證明方法進(jìn)行證明也不存在6環(huán)。所以，對(duì)指數(shù)矩陣的某行或某列加減相等的公差不會(huì)存在6環(huán)。

因此，由定理2可知，對(duì)利用GCD算法得到的確定性指數(shù)矩陣的某行或某列加減相等的公差，不會(huì)影響圍長(zhǎng)的大小，即新得到的指數(shù)矩陣圍長(zhǎng)依然為8。運(yùn)用此定理，首先使用GCD算法對(duì)序列A={a0,a1,…,aJ-1}進(jìn)行搜索，得到確定的指數(shù)矩陣。然后對(duì)指數(shù)矩陣的行或列進(jìn)行加減公差運(yùn)算，使得其校驗(yàn)部分轉(zhuǎn)化為上述提出的快速編碼算法形式，即對(duì)角線為單位矩陣。然后利用掩飾技術(shù)[12]不會(huì)影響圍長(zhǎng)大小的特點(diǎn)設(shè)計(jì)掩飾矩陣，最后得到的指數(shù)矩陣同時(shí)滿足圍長(zhǎng)為8和快速編碼的特性。

3 仿真與分析

本部分在AWGN(additive white Gaussian noise)信道下進(jìn)行仿真，調(diào)制方式采用二進(jìn)制相移鍵控(binary phase shift keying， BPSK)，譯碼方式采用置信傳播(belief propagation，BP)算法，最大迭代次數(shù)設(shè)置為100。

首先，利用GCD算法構(gòu)造一個(gè)維數(shù)為5×10的指數(shù)矩陣。分別設(shè)置參數(shù)列重J=5，行重L=10，通過(guò)GCD算法搜索得到序列{a0,a1,…,a4}={0,1,10,11,23}，根據(jù) (4) 式計(jì)算得到確定的指數(shù)矩陣為

E=

(25)

然后，根據(jù)本文提出的快速編碼算法，通過(guò)對(duì)指數(shù)矩陣中校驗(yàn)部分的數(shù)值進(jìn)行加減數(shù)值，使對(duì)角線數(shù)值變?yōu)?，也即單位矩陣。得到新的指數(shù)矩陣為

E=

(26)

掩飾技術(shù)[12]不會(huì)改變圍長(zhǎng)的大小，利用此性質(zhì)可以靈活設(shè)計(jì)掩飾矩陣，不僅能滿足快速編碼算法第2列到最后一列除單位矩陣外另一個(gè)數(shù)值隨機(jī)分布的特點(diǎn)，而且能使校驗(yàn)矩陣整體更加稀疏，有效地提高碼字的性能。掩飾矩陣M(5,10)設(shè)計(jì)為

(27)

最后，得到的指數(shù)矩陣為

E=

(28)

仿真1當(dāng)擴(kuò)展維數(shù)取P=217時(shí)，根據(jù)上述指數(shù)矩陣得到非規(guī)則(2 170,1 085)碼與原始基于GCD算法構(gòu)造的同等碼長(zhǎng)、碼率、圍長(zhǎng)為8的QC-LDPC碼的誤碼率(bit error rate, BER)、誤幀率((frame error rate，F(xiàn)ER)性能對(duì)比，結(jié)果如圖2所示。

圖2 與GCD算法的QC-LDPC碼性能比較Fig.2 Comparison of the error performance for GCD QC-LDPC codes

由圖2可知，與基于GCD算法構(gòu)造的圍長(zhǎng)為8的QC-LDPC碼相比，本文提出的基于GCD算法的快速編碼方法在誤碼率為10-5時(shí)，獲得了0.25 dB的編碼增益。另外，本文所提出的碼字可以利用校驗(yàn)矩陣直接進(jìn)行編碼，不僅圍長(zhǎng)不會(huì)減小，而且能實(shí)現(xiàn)線性快速編碼。

仿真2漸進(jìn)邊長(zhǎng)(progress edge growth, PEG)算法[13]是一種隨機(jī)算法，雖然實(shí)際應(yīng)用難度較大，但以其自身優(yōu)異的碼字性能成為眾多研究人員構(gòu)造LDPC碼相比較的對(duì)象。圖3是本文構(gòu)造的(2 170,1 085)非規(guī)則QC-LDPC碼與同等碼長(zhǎng)、碼率等指標(biāo)一致的基于PEG算法構(gòu)造的隨機(jī)碼性能比較。

圖3 與PEG算法的LDPC碼性能比較Fig.3 Comparison of the error performance for PEG LDPC codes

從圖3中可以看出，本文構(gòu)造的QC-LDPC碼在誤碼率為10-5時(shí)，碼字性能與PEG算法相比提高了約0.1 dB。也從側(cè)面證實(shí)了結(jié)構(gòu)化LDPC碼具有不輸于隨機(jī)化LDPC碼的碼字性能。

4 結(jié)束語(yǔ)

本文針對(duì)影響LDPC碼碼字性能的高編碼復(fù)雜度的問(wèn)題，提出了一種具有線性編碼復(fù)雜度的可快速編碼方案。該方案相較經(jīng)典的近似下三角結(jié)構(gòu)靈活性更高，更適合構(gòu)造大圍長(zhǎng)的QC-LDPC碼。證明了對(duì)基于GCD算法構(gòu)造的指數(shù)矩陣的行列進(jìn)行加減數(shù)值運(yùn)算不改變圍長(zhǎng)的大小。最后采用掩飾技術(shù)與提出的快速編碼方案相結(jié)合，使得構(gòu)造的QC-LDPC碼同時(shí)兼容了大圍長(zhǎng)和低編碼復(fù)雜度的雙重特性。由仿真部分可以看出本文構(gòu)造的QC-LDCP碼性能優(yōu)異，且無(wú)誤碼平層。