楊 帆，文曉聰，張會(huì)生，李立欣，王魯杰

（西北工業(yè)大學(xué) 陜西 西安 710129）

自從LDPC碼被發(fā)現(xiàn)以來(lái)，許多專家學(xué)者都致力于尋找好的構(gòu)造算法，要求構(gòu)造的LDPC碼既要具有優(yōu)異的譯碼性能，又有較低的硬件實(shí)現(xiàn)復(fù)雜度。目前LDPC的構(gòu)造方法主要有兩類(lèi)，一類(lèi)是隨機(jī)構(gòu)造法，另一類(lèi)是結(jié)構(gòu)構(gòu)造法。與結(jié)構(gòu)碼相比，隨機(jī)碼具有更好的譯碼性能，特別是在碼長(zhǎng)較長(zhǎng)的情況下[1]。 例如，BF[2]、PEG[3-4]等隨機(jī)構(gòu)造法得到的 LDPC碼能夠使圈長(zhǎng)達(dá)到最大，同時(shí)其碼長(zhǎng)、碼率、圈長(zhǎng)等參數(shù)選擇比較靈活，但由于行列之間的連接不確定性，大大增加了硬件實(shí)現(xiàn)復(fù)雜度。結(jié)構(gòu)構(gòu)造法對(duì)校驗(yàn)矩陣的行列之間的連接進(jìn)行一定地約束，使之具有結(jié)構(gòu)性，減小了硬件編譯碼復(fù)雜度，但是一般的結(jié)構(gòu)碼在碼率、碼長(zhǎng)和圈長(zhǎng)等方面的限制，減少了其應(yīng)用范圍。

本文利用了隨機(jī)構(gòu)造的思想，并加入了一些約束行條件，提出了一種基于距離圖的搜索算法，它有兩種實(shí)現(xiàn)方式—順序搜索方式和隨機(jī)搜索方式。這種算法能夠保證得到的LDPC碼具有準(zhǔn)循環(huán)特性和給定的圈長(zhǎng)，并且碼率、碼長(zhǎng)和圈長(zhǎng)等參數(shù)能夠在很大范圍內(nèi)選取。仿真結(jié)果表明：隨機(jī)搜索方式的性能明顯優(yōu)于順序搜索方式；文中采用隨機(jī)搜索方式構(gòu)造的（1 500，3，6）QC-LDPC碼，具有非常優(yōu)異的誤碼率性能，與隨機(jī)碼接近，當(dāng)信噪比為3時(shí)，誤碼率甚至可以達(dá)到10-9。與隨機(jī)構(gòu)造法相比，這種算法構(gòu)造的碼都具有準(zhǔn)循環(huán)特性，因此易于硬件編碼和譯碼，并且構(gòu)造速度更快；與其他結(jié)構(gòu)構(gòu)造法相比，該算法更加靈活，應(yīng)用范圍也大大增加。

1 距離圖的定義

距離圖中的一個(gè)循環(huán)是由頂點(diǎn)x為起點(diǎn)并以x為終點(diǎn)的一條閉合路徑構(gòu)成的，最短的循環(huán)稱為最小圈長(zhǎng)，簡(jiǎn)稱圈長(zhǎng)（girth）。在距離圖中，長(zhǎng)度為g的循環(huán)相當(dāng)于校驗(yàn)矩陣中長(zhǎng)度2g為的循環(huán)。距離圖中圈長(zhǎng)等于閉合路徑中頂點(diǎn)個(gè)數(shù)或邊數(shù)，而在校驗(yàn)矩陣中，圈長(zhǎng)等于“1”的個(gè)數(shù)，所以距離圖中的圈長(zhǎng)為校驗(yàn)矩陣圈長(zhǎng)的一半。圖1（a）中的虛線代表一個(gè)長(zhǎng)度為3的循環(huán)，對(duì)應(yīng)的校驗(yàn)矩陣循環(huán)長(zhǎng)度為6，如圖1（b）中虛線所示。

距離圖和校驗(yàn)矩陣是一一對(duì)應(yīng)的關(guān)系，可以利用不同的距離圖得到不同的校驗(yàn)矩陣，從而構(gòu)造出許多種不同長(zhǎng)度、碼率、girth大小的準(zhǔn)循環(huán)LDPC碼。接下來(lái)將介紹基于距離圖的LDPC碼的搜索算法。

圖1 LDPC碼的距離圖以及對(duì)應(yīng)的校驗(yàn)矩陣Fig.1 Structure diagram of the distance graph and the corresponding check matrix

2 基于距離圖的搜索算法

1）假設(shè)一個(gè)LDPC碼的距離圖的頂點(diǎn)個(gè)數(shù)為M，行重為k，列重為j，頂點(diǎn)的個(gè)數(shù)即為校驗(yàn)矩陣的行數(shù)。將行（或者頂點(diǎn)）分成 j個(gè)大小相等的組，記為（G1，G2，…，Gj）。 每個(gè)組包含p行，其中p=M/j，p一定要大于理論上的最小值。第x行記為rx，Uxj記為所有與rx距離不超過(guò)g的行的集合。在距離圖上，兩個(gè)行（或頂點(diǎn)）最短路徑的邊數(shù)作為兩個(gè)行（或頂點(diǎn)）之間的距離，g就是期望的圈長(zhǎng)的一半。

2） 將（G1，G2…，Gj）一共 j個(gè)組作為一個(gè)子組，一共取 k個(gè)這樣的子組，子組依次標(biāo)記為（GP1，GP2…GPk）。

3） 對(duì)于每個(gè)子組 GPt，令 t=1，2，…，k：

①?gòu)腉Pt中選取第一組G1作為參考組；

②從G1中選取第一行r1作為參考行；

④令:z=1，…，p-1

如果（rx2+z，rx3+z…，rxj+z）與 r1+z的距離至少為 g，則使 r1+z與（rx2+z，rx3+z…，rxj+z）相連，連接完成之后，則轉(zhuǎn)入第 3）步繼續(xù)執(zhí)行，直到循環(huán)結(jié)束。否則重新執(zhí)行上一步操作3。

4）把得到的距離圖轉(zhuǎn)換為L(zhǎng)DPC的校驗(yàn)矩陣H。距離圖中的頂點(diǎn)對(duì)應(yīng)H矩陣的行，j個(gè)頂點(diǎn)的每一次連接都構(gòu)成H矩陣的一列。

5）將得到的H矩陣按列分成k塊，每一塊的大小為p，對(duì)每一塊進(jìn)行循環(huán)移位操作，移位偏量q隨機(jī)選擇，q∈{0，1，…，p-1}。

這兩種算法構(gòu)造的LDPC碼的結(jié)構(gòu)、誤碼率性能上會(huì)有較大的差異。下面分別介紹這2種搜索方式。

2.1 順序搜索方式

圖2是利用順序搜索方式構(gòu)造一個(gè)圈長(zhǎng)為8的（20，2，4）QC-LDPC的過(guò)程。由圖可知，行的總個(gè)數(shù)M等于10，行組的個(gè)數(shù)為2，因此每組的大小p為5，記為組1和組2，組 1 為（r1，r2，r3，r4，r5）行，組 2 為（r6，r7，r8，r9，r10）行。 由于行重k=4、列重j=2，因此子組的個(gè)數(shù)為4，每個(gè)子組都由組1和組2組成。每個(gè)子組需進(jìn)行一次連接操作，因此一共進(jìn)行4次連接過(guò)程。要求構(gòu)造的LDPC碼的圈長(zhǎng)為8，因此距離圖中兩行之間的距離不能小于4。第一次連接，順序搜索組2中第一行即r6，由圖可知滿足與參考行r1的距離大于等于4的條件，因此使 r6和行 r1相連，組 1 剩下的行（r2，r3，r4，r5）分別與組 2 剩余的行（r7，r8，r9，r10）相連。第二次連接，順序?qū)ふ业浇M 2的下一行即r7，由圖可知r7滿足與參考行r1的距離不小于4的要求，因此使 r7與 r1相連，使剩余的行（r2，r3，r4，r5）分別與（r8，r9，r10，r6）相連。 第三次連接，順序?qū)ふ业浇M 2 中的下一行r8，由圖可知r8滿足與參考行r1的距離不小于4的要求，因此使 r8與 r1相連，同理使行（r2，r3，r4，r5）分別與行（r9，r10，r6，r7）相連。第四次連接，順序?qū)ふ业浇M2中的下一行r9，由圖可知r9滿足與參考行r1的距離不小于4的要求，因此使r9與r1相連，同理使行（r2，r3，r4，r5）分別與行（r10，r6，r7，r8）相連，這樣就完成了四次連接過(guò)程，并且圖中不存在長(zhǎng)度為4的循環(huán)，滿足了圈長(zhǎng)為8的要求。圖3為順序搜索時(shí)對(duì)應(yīng)的校驗(yàn)矩陣。由圖可知，校驗(yàn)矩陣按列分為4個(gè)塊，每一塊對(duì)應(yīng)一次連接過(guò)程；按行分為兩部分，上部分對(duì)應(yīng)（r1，r2，r3，r4，r5）行，由 4 個(gè) 5×5 的單位子矩陣組成的，下部分對(duì)應(yīng)（r6，r7，r8，r9，r10）行，由 4 個(gè)循環(huán)移位子矩陣組成。由于采用順序搜索方式，因此分別向左循環(huán)移0、1、2、3位。圖4是對(duì)圖3中的校驗(yàn)矩陣進(jìn)行隨機(jī)循環(huán)移位（即隨機(jī)列變換）所得到的校驗(yàn)矩陣，每一塊分別向右循環(huán)移 3、1、2、2位，增加了“1”分布的隨機(jī)性。 由圖 4可以看出不存在長(zhǎng)度小于8的循環(huán)。

圖2 順序搜索時(shí)圈長(zhǎng)為8的（20，2，4）碼的距離圖構(gòu)造過(guò)程Fig.2 Graph representation of the construction process of a girth-8（20，2，4）code using sequential search

圖3 順序搜索時(shí)圈長(zhǎng)為8的（20，2，4）碼對(duì)應(yīng)的校驗(yàn)矩陣Fig.3 Check matrix representation of a （20，2，4）code with girth eight using sequential search

圖4 隨機(jī)循環(huán)移位得到的校驗(yàn)矩陣Fig.4 Obtained check matrix using random cyclic shift

2.2 隨機(jī)搜索方式

圖5是采用隨機(jī)搜索方式構(gòu)造一個(gè)圈長(zhǎng)為8的（20，2，4）QC-LDPC的過(guò)程。第一次連接，隨機(jī)選擇組2中的行r8，由圖可知r8與參考r1的距離大于4，因此使r8與r1相連，并且分別使組 1 剩下的行（r2，r3，r4，r5）分別與組 2 剩余的（r9，r10，r6，r7）相連。 第二次連接，隨機(jī)搜索到行 r6，由圖可知 r6與r1的距離大于4，使行r6與r1相連，并且使組1中剩下的行（r2，r3，r4，r5）分別與組 2 剩余的行（r7，r8，r9，r10）相連。 第三次連接隨機(jī)搜索到行r10，由圖可知與r1的距離大于4，同理使行（r1，r2，r3，r4，r5）分別與行（r10，r6，r7，r8，r9）相連。 第四次連接，隨機(jī)搜索到r7，由圖可知r7與參考行r1的距離不小于4，因此使行（r1，r2，r3，r4，r5）分別與行（r7，r8，r9，r10，r6）相連。 經(jīng)過(guò) 4 次這樣的連接，就構(gòu)成了一個(gè)完整的距離圖。

圖5 隨機(jī)搜索時(shí)圈長(zhǎng)為8的（20，2，4）碼的距離圖構(gòu)造過(guò)程Fig.5 Graph representation of the construction process of a girth-8（20，2，4）code using random search

圖6 隨機(jī)搜索時(shí)圈長(zhǎng)為8的（20，2，4）碼對(duì)應(yīng)的校驗(yàn)矩陣Fig.6 Check matrix representation of a （20，2，4）code with girth eight using random search

圖7 隨機(jī)循環(huán)移位得到的校驗(yàn)矩陣Fig.7 Obtained check matrix using random cyclic shift

圖6是采用隨機(jī)搜索方式時(shí)對(duì)應(yīng)的校驗(yàn)矩陣。圖6的上半部分是由4個(gè)的單位字矩陣構(gòu)成，下半部分是由四個(gè)循環(huán)移位字矩陣構(gòu)成，分別向右循環(huán)移3位、0位、1位、4位。由于采用隨機(jī)搜索的方式，因此4個(gè)循環(huán)移位子矩陣的移位偏移量也是隨機(jī)的。由圖可以看出非零元“1”的分布比順序搜索方式更加具有隨機(jī)性，因此誤碼率性能也將會(huì)提高。圖7是對(duì)圖6中H矩陣進(jìn)行隨機(jī)循環(huán)移位所得的校驗(yàn)矩陣，每一塊的分別向右循環(huán)移 3、3、1、0 位，這樣非零元“1”的分布更具有隨機(jī)性。

3 算法的復(fù)雜度分析

假設(shè)LDPC碼的行數(shù)為M，行重為k，列重為j，那么算法的復(fù)雜度分析如下。

1）行組的個(gè)數(shù)為j，每一行組的的大小為p=M/j；

2）對(duì)于每一個(gè)子組，非參考組里的每一行，在算法搜索之前需要更新與參考行r1的距離，如果要求與參考行的距離不小于g，那么每次更新需要g步運(yùn)算。對(duì)于一個(gè)行組，則要進(jìn)行pg次運(yùn)算，因?yàn)橐还灿衘-1個(gè)非參考行組，因此一共需要pg（j-1）次運(yùn)算，才能完成更新運(yùn)算。

由此可知，算法的實(shí)現(xiàn)復(fù)雜度與碼長(zhǎng)成正比，因此一般情況下能夠較快的構(gòu)造出所需的碼字。算法的復(fù)雜度還與實(shí)現(xiàn)的搜索方式有關(guān)，順序搜索法可能會(huì)需要很長(zhǎng)的時(shí)間，特別是當(dāng)行組p很大時(shí)。對(duì)于行組p越大的碼，搜索算法成功的機(jī)率越大期望的圈長(zhǎng)可以設(shè)置的越大。利用上文中基于距離圖的搜索算法可以很容易得到圈長(zhǎng)為6、8、10甚至超過(guò)12的碼。

4 仿真結(jié)果

本文利用基于距離圖的兩種構(gòu)造方式—隨機(jī)搜索方式和順序搜索方式，構(gòu)造了一組圈長(zhǎng)為分別為6、8、10的QCLDPC碼，其碼長(zhǎng)為1 500，行重和列重分別為6和3。為了進(jìn)行對(duì)比，用 PEG 算法構(gòu)造一種圈長(zhǎng)為 8的（1 500，3，6）PEG隨機(jī)碼。仿真是在AWGN信道下，采用BPSK調(diào)制，譯碼采用了基于整數(shù)運(yùn)算的最小和譯碼算法[7]，迭代次數(shù)20次。圖8是采用隨機(jī)搜索方式下（1 500，3，6）碼的性能仿真圖。圖9是采用順序搜索方式下（1 500，3，6）碼的性能仿真圖。圖10是2種搜索方式的性能比較圖。從以上3個(gè)仿真圖可以得出：隨機(jī)搜索方式的性能明顯優(yōu)于順序搜索方式；采用同樣方式構(gòu)造的碼，隨著圈長(zhǎng)的增大誤碼率性能越來(lái)越好；在相同的圈長(zhǎng)下，PEG算法比文中隨機(jī)搜索方式的性能好，但相差不大；本算法中隨機(jī)搜索方式構(gòu)造的QC-LDPC碼性能非常優(yōu)異，當(dāng)SNR為3 dB時(shí)，誤碼率甚至可以達(dá)到10-9，非常適合小信噪比環(huán)境下通信。

圖8 采用隨機(jī)搜索方式時(shí)得到碼的誤碼率性能Fig.8 BER performance curves for codes using random search

圖9 采用順序搜索方式時(shí)得到碼的誤碼率性能Fig.9 BER performance curves for codes using sequential search

圖10 兩種搜索方式的誤碼率性能比較Fig.10 BER performance curves for codes using sequential search and random search

5 結(jié) 論

文中設(shè)計(jì)了一種基于距離圖的搜索算法，它有兩種實(shí)現(xiàn)方式—順序搜索方式和隨機(jī)搜索方式，其中隨機(jī)搜索方式的性能更優(yōu)，與隨機(jī)碼的性能接近。這種構(gòu)造算法具有以下幾個(gè)優(yōu)點(diǎn)：第一，圈長(zhǎng)可以設(shè)定，能夠構(gòu)造出圈長(zhǎng)為6、8、10甚至12的QC-LDPC碼；其次，其行重、列重和碼長(zhǎng)在一定條件下也可以設(shè)定，靈活性好，適用范圍大；此外，與隨機(jī)構(gòu)造法相比，這種搜索算法構(gòu)造的LDPC碼具有準(zhǔn)循環(huán)特性，易于硬件實(shí)現(xiàn)，并且構(gòu)造速度更快；第四，文中采用隨機(jī)搜索方式構(gòu)造的 （1 500，3，6）QC-LDPC碼，具有非常優(yōu)異的誤碼率性能，與隨機(jī)碼接近，當(dāng)信噪比為3時(shí)，誤碼率甚至可以達(dá)到10-9，非常適合小信噪比環(huán)境下通信。

[1]HU Xiao-Yu.Progressive edge-growth tanner graphs[D].Switzerland:the SwissFederalInstitute ofTechnology Lausanne，2001.

[2]Campello J，Dodha D S，Rajagopalan S.Designing LDPC codes using Bit-Filling [C]//In Proceedings of the International Conference on Communications，2001:55-59.

[3]Uchoa A G D，Healy C， de Lamare，et al.Design of LDPC codes based on progressive edge growth techniques for block fading channels[J].IEEE Communication Letters，2011（15）:1221-1223.

[4]HUANG Li-qun，WANG Yu-liang，GONG Ping.An improved construction method of QC-LDPC codes based on the PEG algorithm [C]//Circuits， Communications and System（PACCS），2011:1-4.

[5]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.

[6]Sullivan M E O.Algebraic construction of sparse matrices with large girth[J].IEEE Transactions on Information Theory，F(xiàn)ebruary 2006，52（2）:719-727.

[7]LI Li-xin，CHEN Zheng-kang，F(xiàn)AN Jie，et al.Implementation of LDPC codes decoding based on maximum average mutual information quantization[J].International Review on Computers and Software （I.RE.CO.S.），2011:1135-1139.