利用遺傳算法構(gòu)造QC－LDPC碼*

鄭丹玲，穆 攀，田 凱，袁建國

(重慶郵電大學(xué)光通信與網(wǎng)絡(luò)重點(diǎn)實(shí)驗(yàn)室，重慶400065)

1 引言

低密度奇偶校驗(yàn)(Low Density Parity Check，LDPC)碼因逼近Shannon限的優(yōu)秀性能、低的譯碼復(fù)雜度，近些年來成為了編碼領(lǐng)域的研究熱點(diǎn)，特別是準(zhǔn)循環(huán)LDPC(Quasi－cyclic LDPC，QC－LDPC)碼。QC－LDPC碼的奇偶校驗(yàn)矩陣H由循環(huán)置換矩陣或零矩陣構(gòu)成[1]，同隨機(jī)構(gòu)造的LDPC碼相比，QC－LDPC碼有以下優(yōu)點(diǎn):首先，QC－LDPC碼的編碼可以通過簡單的、呈線性復(fù)雜度的移位寄存器來實(shí)現(xiàn);其次，QC－LDPC碼可以由基礎(chǔ)矩陣表示，同H矩陣相比，基礎(chǔ)矩陣具有更小的尺寸，并且基礎(chǔ)矩陣?yán)醚h(huán)置換矩陣可以很容易地?cái)U(kuò)展為H矩陣。所以，QC－LDPC碼具有編譯碼復(fù)雜度更低、硬件實(shí)現(xiàn)更簡單、存儲(chǔ)空間更少等優(yōu)點(diǎn)，如何構(gòu)造性能優(yōu)異的QC－LDPC碼一直以來都是人們研究的重點(diǎn)[2－3]。研究中發(fā)現(xiàn)，當(dāng) Tanner圖中含有長度較小的環(huán)時(shí)，該碼的糾錯(cuò)性能就會(huì)下降，環(huán)的數(shù)量和大小的分布同碼的重量分布一樣對LDPC碼的性能有著重要影響。目前，已經(jīng)有許多消除小環(huán)的LDPC碼的構(gòu)造方法被提出，這些方法主要分為代數(shù)構(gòu)造[4－5]和隨機(jī)構(gòu)造[6－7]兩類。

本文結(jié)合這兩類方法，借助于遺傳算法(Genetic Algorithm，GA)提出了一種新的消除短環(huán)的碼字構(gòu)造方法，簡稱GA－QC－LDPC碼。該方法先使用遺傳算法消除基礎(chǔ)矩陣的四環(huán)得到六環(huán)的矩陣，再在此矩陣基礎(chǔ)上，消除六環(huán)得到八環(huán)，此種方法多次利用，即可得到符合要求環(huán)長的基礎(chǔ)矩陣。然后通過使用循環(huán)置換矩陣對基礎(chǔ)矩陣擴(kuò)展，得到具有準(zhǔn)循環(huán)結(jié)構(gòu)特性的LDPC碼，準(zhǔn)循環(huán)特性決定了它比隨機(jī)構(gòu)造方法使用的存儲(chǔ)空間更小、編譯碼復(fù)雜度更低。仿真進(jìn)一步顯示，GA－QC－LDPC比基于歐式幾何構(gòu)造方法、Gallager隨機(jī)構(gòu)造方法和Mackay隨機(jī)構(gòu)造方法構(gòu)造的LDPC碼在糾錯(cuò)性能上更加優(yōu)異。

2 采用遺傳算法構(gòu)造QC－LDPC碼的方法

構(gòu)造LDPC碼的校驗(yàn)矩陣最大問題是要防止出現(xiàn)短環(huán)，在Tanner圖中如果出現(xiàn)短環(huán)，其迭代譯碼時(shí)的信息在交換過程中就會(huì)變?yōu)橄嚓P(guān)的，阻止譯碼收斂或者收斂變慢，造成譯碼性能的急劇下降。此外，由文獻(xiàn)[8－9]看出，Tanner圖的最小環(huán)還與碼的最小距離有關(guān)，girth越大，最小距離也隨之增大，要增加碼間的最小距離可以反映到增加girth上來。所以，構(gòu)造性能良好的LDPC碼，可以集中反映到構(gòu)造大girth的LDPC碼上來。給定一個(gè)基礎(chǔ)矩陣，我們可以用下面定理檢測短環(huán)是否存在。

定理1(短環(huán)存在定理):對于一個(gè)m×n的基礎(chǔ)矩陣，存在短環(huán)的充分必要條件是

式中，s2k和s2k－1為基礎(chǔ)矩陣中的短環(huán)上兩個(gè)相鄰位置元素，P為循環(huán)置換矩陣的階數(shù)[1]。一般情況下，基礎(chǔ)矩陣的階數(shù)都比較小，因此，檢測矩陣中所有的元素相對容易。

遺傳算法作為一種優(yōu)化搜索算法，從初始種群的產(chǎn)生開始，然后對個(gè)體進(jìn)行選擇復(fù)制、交叉和變異遺傳操作以產(chǎn)生新的個(gè)體，選擇可以將適應(yīng)性好的個(gè)體復(fù)制到下一代作為種群迭代的父代，交叉操作將選中的兩個(gè)個(gè)體的某段基因進(jìn)行互換來產(chǎn)生新的個(gè)體，變異改變個(gè)體的某個(gè)基因產(chǎn)生新的個(gè)體。遺傳算法可使種群朝著最優(yōu)的方向發(fā)展。本文運(yùn)用遺傳算法可以不斷增大Tanner圖中的girth，具體方法是利用遺傳算法消除基礎(chǔ)矩陣中的四環(huán)得到girth=6的矩陣，在此基礎(chǔ)上，消除六環(huán)得到girth=8的矩陣?？傊?，多次運(yùn)用遺傳算法可分步提高girth，如圖1所示。

圖1 遺傳算法提高girth示意圖Fig.1 Diagram of improving girth based on Genetic Algorithm

2.1 消除四環(huán)得到girth為6的基礎(chǔ)矩陣方法

本小節(jié)運(yùn)用遺傳算法消四環(huán)得到girth為六環(huán)的基礎(chǔ)矩陣，將基礎(chǔ)矩陣進(jìn)行擴(kuò)展可得到H矩陣。

(1)候選個(gè)體初始化

隨機(jī)產(chǎn)生N個(gè)個(gè)體，每個(gè)個(gè)體為一個(gè)m×n的候選個(gè)體矩陣，表示為si，組成初始種群。

(2)適應(yīng)度函數(shù)

基礎(chǔ)矩陣si中的girth盡可能地大，且矩陣si中環(huán)長為girth的環(huán)盡可能地少。根據(jù)定理1，計(jì)算候選個(gè)體矩陣中四環(huán)的數(shù)目，環(huán)數(shù)越少的個(gè)體適應(yīng)性越好。如果種群中個(gè)體不存在四環(huán)，則結(jié)束迭代;否則，繼續(xù)下一步操作。

對于某一個(gè)候選個(gè)體s，即m×n的矩陣，其四環(huán)搜索算法如下:

步驟1:在矩陣s中的第i1(i1=1，2，…，m)行，對于第 j1(j1=1，2，…，n)列，如果 s(i1，j1)≠0，則跳至步驟2;否則，繼續(xù)步驟1，直到j(luò)1＞n時(shí)跳到第i1＞m時(shí)結(jié)束;

步驟2:對于第 j2(j2＞ j1)列，如果 s(i1，j1)≠0，則跳至跳至步驟3;否則，繼續(xù)步驟2，直到j(luò)2＞n時(shí)跳至步驟1;

步驟3:對于第i2(i2＞ i1)行，如果 s(i2，j2)≠0且s(i2，j1)≠0，則跳至步驟4;否則，繼續(xù)步驟3，直到i2＞m時(shí)跳至步驟2;

步驟4:如果滿足 s(i2，j2)－ s(i2，j1)+s(i1，j2)－s(i1，j1)=0(模 P)，則四環(huán)個(gè)數(shù) girth4_num=girth4_num+1;否則跳至步驟3。

(3)選擇

選出一個(gè)含girth=4最少的個(gè)體矩陣直接遺傳至下一代，并復(fù)制該個(gè)體一次。將girth=4含環(huán)數(shù)最多的個(gè)體直接淘汰，保持種群規(guī)模不變。

(4)交叉

對其余個(gè)體，隨機(jī)選取一對個(gè)體sa和sb，進(jìn)行單點(diǎn)交叉，產(chǎn)生兩個(gè)新的個(gè)體sx和sy。本小節(jié)中的交叉方式主要分為行向量單點(diǎn)交叉和列向量單點(diǎn)交叉兩種。

1)行向量單點(diǎn)交叉

將基礎(chǔ)矩陣sa和sb表示為

式中，ra(i)和rb(i)是長度為n的行向量。

矩陣sa和sb的行向量表示形式為

矩陣A和B單點(diǎn)交叉后產(chǎn)生的新個(gè)體為

式中，X、Y即為矩陣sx、sy的行向量表示形式。

2)列向量單點(diǎn)交叉

將基礎(chǔ)矩陣sa和sb表示為

式中，ca(i)和cb(i)是長度為m的列向量。矩陣sa和sb列向量單點(diǎn)交叉后產(chǎn)生的新個(gè)體為

行向量交叉會(huì)產(chǎn)生重量為0或1的列向量，導(dǎo)致誤碼率的增加。因此，本文采用列向量單點(diǎn)交叉方式，交叉概率設(shè)為0.9。

(5)變異

對種群中的所有候選個(gè)體，隨機(jī)變異矩陣中某一四環(huán)上的任意元素，即將該元素變?yōu)殡S機(jī)生成的某個(gè)數(shù)，變異概率設(shè)為0.1。

2.2 消除六環(huán)得到girth為8的基礎(chǔ)矩陣方法

將2.1節(jié)最終產(chǎn)生的種群作為本節(jié)中候選的初始種群。消除六環(huán)的方法與消除四環(huán)的方法基本相同，不同點(diǎn)在于:一是交叉操作可能會(huì)產(chǎn)生新的四環(huán)，所以交叉操作被禁止;二是變異操作更改為:對所有候選個(gè)體，隨機(jī)刪除矩陣中某一六環(huán)上的元素，即將非零元素變?yōu)椤?”。為了減小低重量碼字對性能的影響，選擇重量較大列的非零元素進(jìn)行刪除操作。

消除八環(huán)得到girth為10的基礎(chǔ)矩陣的方法同以上方法。

2.3 復(fù)雜度分析

本文提出的基于girth選擇遺傳算法構(gòu)造LDPC碼方法的復(fù)雜度主要集中在適應(yīng)度評(píng)價(jià)函數(shù)上，即搜索短環(huán)的過程中。本節(jié)主要介紹其時(shí)間復(fù)雜度，即搜索短環(huán)消耗的時(shí)間。

假設(shè)一個(gè)種群中有N個(gè)候選個(gè)體矩陣，每一個(gè)候選個(gè)體為m×n的矩陣，所有的候選個(gè)體矩陣在初始化時(shí)所有元素都為非零值。搜索四環(huán)的復(fù)雜度如式(7)所示:

在六環(huán)檢測過程中，候選個(gè)體矩陣中元素已經(jīng)不全是非零值。隨著種群迭代次數(shù)的增加，非零元素會(huì)相應(yīng)減少，故假設(shè)迭代一次后候選個(gè)體矩陣的行重和列重分別為ρ和γ，搜索六環(huán)的復(fù)雜度如式(8)所示:

由式(8)可得，搜索六環(huán)的復(fù)雜度與種群大小N、候選個(gè)體矩陣的行數(shù)m和列數(shù)n、行重ρ和列重γ有關(guān)。一般情況下，基礎(chǔ)矩陣都是非常小的矩陣，所以搜索短環(huán)相對容易。

3 仿真及性能分析

本文所進(jìn)行的仿真都采用二進(jìn)制相移鍵控(Binary Phase Shift Keying，BPSK)調(diào)制方式、置信傳播(Belief－Propagation，BP)譯碼算法，在加性高斯白噪聲(Additive White Gaussian Noise，AWGN)信道下進(jìn)行性能仿真。首先，對(530，265)GA－QC－LDPC碼在不同譯碼迭代次數(shù)(Iteration分別為1、5、10、20和50)下的糾錯(cuò)性能進(jìn)行對比分析，仿真性能曲線如圖2所示。由圖2可知凈編碼增益(Net Code Gain，NCG)隨著迭代次數(shù)的增大而提高，但當(dāng)?shù)螖?shù)增加到一定值時(shí)，NCG的變化非常小?？紤]到增加迭代次數(shù)會(huì)增加譯碼的時(shí)間，因此，本文選擇最大譯碼迭代次數(shù)為20次。

圖2 不同迭代次數(shù)下GA－QC－LDPC碼性能對比Fig.2 Performance comparison of GA －QC －LDPC codes with different iterations

圖3 是關(guān)于 GA－QC－LDPC(610，305)碼在girth分別為4、6、8和10下的誤碼率(Bit Error Rate，BER)和誤幀率(Frame Error Rate，F(xiàn)ER)性能比較。從圖中可以看出，girth分別為4、6、8和10時(shí)，在Eb/N0=3 dB的情況下，所對應(yīng)的BER分別約為2.0×10－3、9.8 ×10－4、6.6 ×10－5和5.4 ×10－6，印證了隨著girth不斷增加，碼的糾錯(cuò)性能越來越好。

圖3 不同girth的GA－QC－LDPC碼仿真性能對比Fig.3 Performance comparison of GA －QC －LDPC codes with different girth

最后將GA－QC－LDPC碼與基于歐式幾何構(gòu)造方法[10]、Gallager隨機(jī)構(gòu)造方法[11]和 Mackay 隨機(jī)構(gòu)造方法[12]進(jìn)行比較，如圖4所示。從圖4中我們可以看出，在BER為10－6時(shí)，GA－QC－LDPC碼同其他構(gòu)造方法相比有不同程度的性能提升，與基于歐式幾何、Gallager和Mackay隨機(jī)構(gòu)造方法相比，凈編碼增益分別提升了0.15 dB、0.5 dB和0.2 dB。

圖4 GA－QC－LDPC碼與其他LDPC碼的糾錯(cuò)性能比較Fig.4 Performance comparison between GA －QC －LDPC code and other LDPC codes

通過上述仿真可知，本文提出的算法具有優(yōu)于隨機(jī)構(gòu)造方法的性能。此外，由于GA－QC－LDPC碼具有準(zhǔn)循環(huán)性，因此其編碼復(fù)雜度要低于隨機(jī)構(gòu)造方法。

4 結(jié)束語

本文研究了基于Gallager和Mackay的隨機(jī)構(gòu)造方法，發(fā)現(xiàn)隨機(jī)構(gòu)造方法構(gòu)造的校驗(yàn)矩陣不具有確定的數(shù)學(xué)結(jié)構(gòu)，導(dǎo)致編譯碼復(fù)雜度高、存儲(chǔ)困難、硬件難以實(shí)現(xiàn)等缺陷，為此，提出了一種使用遺傳算法構(gòu)造QC－LDPC碼的方法，通過分步、多次使用遺傳算法設(shè)計(jì)出大girth、具有準(zhǔn)循環(huán)特性的LDPC碼，克服了隨機(jī)碼因無數(shù)學(xué)結(jié)構(gòu)造成的不足。仿真結(jié)果在驗(yàn)證了QC－LDPC碼的性能隨著girth的增加而提升的同時(shí)，也表明本文構(gòu)造出的GA－QCLDPC碼具有比RS和兩種典型隨機(jī)方法構(gòu)造的LDPC碼更好的糾錯(cuò)性能。

在今后的研究工作中，可以在本文提出的算法基礎(chǔ)上，考慮其他的方式來替代遺傳算法中的變異操作。因?yàn)楸疚闹惺峭ㄟ^將環(huán)上的元素置零以此來實(shí)現(xiàn)消除短環(huán)的目的，這種方法會(huì)減小校驗(yàn)矩陣的行重和列重，導(dǎo)致出現(xiàn)低重量的碼字，降低LDPC碼的糾錯(cuò)性能。

[1]Fossorier M P C.Quasi－cyclic low－density parity－check codes from circulant permutation matrices[J].IEEE Transactions on Information Theory，2004，50(8):1788 －1793.

[2]黃勝，龐曉磊.基于中國剩余定理和貪婪算法擴(kuò)展的QC－LDPC 碼[J].電訊技術(shù)，2014，54(11):1528－1533.HUANG Sheng，PANG Xiaolei.QC － LDPC Codes Based on Chinese Remainder Theorem and Greedy Algorithm[J].Telecommunication Engineering，2014，54(11):1528 －1533.(in Chinese)

[3]Huang Qin，Diao Qinju.Cyclic and Quasi－ Cyclic LDPC Codes on Constrained Parity－Check Matrices and Their Trapping Sets[J].IEEE Transactions on Information Throry，2012，59(1):2648 －2671.

[4]Wang Lei，Zhang Xing.QC － LDPC Codes with Girth Eight Based on Independent Row－Colunm Mapping Sequence[J].IEEE Communications Letters，2013，17(11):2140－2143.

[5]劉原華，張美玲.一種可快速編碼的QC－LDPC碼構(gòu)造新方法[J].電訊技術(shù)，2013，53(1):55 －59.LIU Yuanhua，ZHANG Meiling.A New Design Method for Quasi－cyclic LDPC Codes with Fast Encoding Ability[J].Telecommunication Engineering，2013，53(1):55 －59.(in Chinese)

[6]Jiang Xueqin，Xia Xianggen.Efficient Progressive Edge －Growth Algorithm Based on Chinees Remainder Theorem[J].IEEE Transactions on Communications，2014，62(2):442－451.

[7]Sharon E，Litsyn S.Constructing LDPC codes by error minimization progressive edge growth[J].IEEE Transactions on Communications，2008，56(3):359 －368.

[8]Tanner R M.Minimum－distance bounds by graph analysis[J].IEEE Transactions on Information Theory，2001，47(2):808－821.

[9]Hu X Y，Vetterli M.Low－delay low－complexity errorcorrecting codes on sparse graphs[D].Switzerland:Swiss Federal Insitute of Technology Lausanne(EPFL)，2002.

[10]Yu Kou，Shu Lin，F(xiàn)ossorier M P C.Low －Density Parity －Check Codes Based on Finite Geometries[J].IEEE Transactions on Information theory，2001，47(7):2711 －2736.

[11]Gal1ager R G.Low －density parity－check codes[J].IEEE Transactions on Information Theory，1962(8):21 －28.

[12]MacKay D J C.Good error－correcting codes based on very sparse matrices[J].IEEE Transactions on Information Theory，1999，45(2):399 －431.