一種基于距離圖的QC-LDPC構造算法

楊 帆，文曉聰，張會生，李立欣，王魯杰

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

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

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

1 距離圖的定義

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

距離圖和校驗矩陣是一一對應的關系，可以利用不同的距離圖得到不同的校驗矩陣，從而構造出許多種不同長度、碼率、girth大小的準循環(huán)LDPC碼。接下來將介紹基于距離圖的LDPC碼的搜索算法。

圖1 LDPC碼的距離圖以及對應的校驗矩陣Fig.1 Structure diagram of the distance graph and the corresponding check matrix

2 基于距離圖的搜索算法

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

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

3） 對于每個子組 GPt，令 t=1，2，…，k：

①從GPt中選取第一組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)結束。否則重新執(zhí)行上一步操作3。

4）把得到的距離圖轉(zhuǎn)換為LDPC的校驗矩陣H。距離圖中的頂點對應H矩陣的行，j個頂點的每一次連接都構成H矩陣的一列。

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

這兩種算法構造的LDPC碼的結構、誤碼率性能上會有較大的差異。下面分別介紹這2種搜索方式。

2.1 順序搜索方式

圖2是利用順序搜索方式構造一個圈長為8的（20，2，4）QC-LDPC的過程。由圖可知，行的總個數(shù)M等于10，行組的個數(shù)為2，因此每組的大小p為5，記為組1和組2，組 1 為（r1，r2，r3，r4，r5）行，組 2 為（r6，r7，r8，r9，r10）行。 由于行重k=4、列重j=2，因此子組的個數(shù)為4，每個子組都由組1和組2組成。每個子組需進行一次連接操作，因此一共進行4次連接過程。要求構造的LDPC碼的圈長為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）相連，這樣就完成了四次連接過程，并且圖中不存在長度為4的循環(huán)，滿足了圈長為8的要求。圖3為順序搜索時對應的校驗矩陣。由圖可知，校驗矩陣按列分為4個塊，每一塊對應一次連接過程；按行分為兩部分，上部分對應（r1，r2，r3，r4，r5）行，由 4 個 5×5 的單位子矩陣組成的，下部分對應（r6，r7，r8，r9，r10）行，由 4 個循環(huán)移位子矩陣組成。由于采用順序搜索方式，因此分別向左循環(huán)移0、1、2、3位。圖4是對圖3中的校驗矩陣進行隨機循環(huán)移位（即隨機列變換）所得到的校驗矩陣，每一塊分別向右循環(huán)移 3、1、2、2位，增加了“1”分布的隨機性。 由圖 4可以看出不存在長度小于8的循環(huán)。

圖2 順序搜索時圈長為8的（20，2，4）碼的距離圖構造過程Fig.2 Graph representation of the construction process of a girth-8（20，2，4）code using sequential search

圖3 順序搜索時圈長為8的（20，2，4）碼對應的校驗矩陣Fig.3 Check matrix representation of a （20，2，4）code with girth eight using sequential search

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

2.2 隨機搜索方式

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

圖5 隨機搜索時圈長為8的（20，2，4）碼的距離圖構造過程Fig.5 Graph representation of the construction process of a girth-8（20，2，4）code using random search

圖6 隨機搜索時圈長為8的（20，2，4）碼對應的校驗矩陣Fig.6 Check matrix representation of a （20，2，4）code with girth eight using random search

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

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

3 算法的復雜度分析

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

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

2）對于每一個子組，非參考組里的每一行，在算法搜索之前需要更新與參考行r1的距離，如果要求與參考行的距離不小于g，那么每次更新需要g步運算。對于一個行組，則要進行pg次運算，因為一共有j-1個非參考行組，因此一共需要pg（j-1）次運算，才能完成更新運算。

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

4 仿真結果

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

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

圖9 采用順序搜索方式時得到碼的誤碼率性能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 結 論

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