QC-LDPC碼基矩陣構造方法

摘 要：利用發現的大衍數列和Golomb-Ruler的特殊性質，給出了兩種準循環LDPC碼的校驗矩陣基矩陣的構造方法。根據校驗矩陣不含長度為4的環的充要條件判斷，設計的兩種準循環LDPC碼的環長至少為6。仿真顯示，在10-5誤碼率條件下，這兩種設計方案比傳統的RS碼和卷積碼級聯編碼方案有接近2 dB的性能提升；相比于IEEE 802.16e標準給出的設計方案，基于Golomb-Ruler構造的QC-LDPC碼在性能上有0.8 dB的差距，基于大衍數列構造的QC-LDPC碼在性能上有0.9 dB的差距；基于Golomb-Ruler構造的QC-LDPC碼與基于大衍數列構造的QC-LDPC碼有幾乎接近的性能，前者比后者大約有0.1 dB的增益。



關鍵詞：準循環; 校驗矩陣; 基矩陣; 大衍數列; Golomb-Ruler

中圖分類號：

TN919-34

文獻標識碼：A

文章編號：1004-373X(2012)05

-0068

-03

Construction methods of basis matrix for QC-LDPC code



ZHU Lei-ji， WANG Han， SHI Yu-song， XING Tao， WANG Ying-guan

(Shanghai Institute of Microsystem and Information Technology， Chinese Academy of Science， Shanghai 200050， China)



Abstract：

By using the special properties of Dayan Sequence and Golomb-Ruler， two methods are proposed to construct basis matrix of parity check matrix for quasi cyclic low density parity check code. According to the necessary and sufficient condition for parity check matrix that has no circle of length four， the designed QC-LDPC codes have circles no less than six. At the BER of 10-5， the simulation shows that comparing with RS and convolution code concatenate methods， the designs have nearly 2 dB more performance improvement. Meanwhile， comparing with methods proposed by IEEE802.16e standard， Golomb-Ruler method has 0.8dB performance decrease and Dayan Sequence method has 0.9dB performance decrease. Those two methods have almost the same performance， the former has 0.1 dB gain than the latter.



Keywords： quasi cyclic; parity check matrix; basis matrix; Dayan Sequence; Golomb-Ruler



收稿日期：2011-10-21

基金項目：國家重大科技專項(2009ZX03006-004)

0 引 言

LDPC碼最初由Gallager在1962年發現［1］，在被忽略了30年左右，由Mackay等再度發現，并被證明具有接近香農限的優異性能［2-3］。從此，很多學者開始堅持不懈地研究LDPC碼的設計與構造。黃翔等給出了一種大圍長的正則LDPC碼構造方法［4］。蘇凌杰等給出了一種輸出格式可控的多碼率LDPC編碼器實現方法［5］。可以看出，一個重要的研究熱點是準循環(QC)LDPC碼的校驗矩陣H的構造。QC-LDPC碼校驗矩陣H的構造重點就是基矩陣B的構造。Shu Lin等給出了一系列基于伽羅華域的非二進制的基矩陣B的構造方法［6-10］。林炳，彭立等給出了基于二進制的基矩陣B的構造方法［11-12］。

LDPC碼的環長定義為其校驗矩陣所含的最短環的長度。其中，長度為4的環對LDPC碼性能的影響最大。較短的環會導致譯碼的時候迭代信息在2次迭代以后互相關，影響譯碼的收斂。Fossorier推導出了H矩陣不存在長為2i的環的充要條件［13］，在這個結論之上，本文設計了兩種構造不含有4環的校驗矩陣H的基矩陣B的方法。

1 校驗矩陣H和基矩陣B

列重為J行重為L的規則(J，L)QC-LDPC碼的校驗矩陣H，由p×p循環置換矩陣構成的J×L陣列表示，其碼長n=Lp，定義為:



H=I(p0，0)I(p0，1)…I(p0，L－1)

I(p1，0)I(p1，1)…I(p1，L－1)



I(pJ－1，0)I(pJ－1，1)…I(pJ－1，L－1)



式中：0≤j≤J－1；0≤l≤L－1，I(pj，l)是p×p循環置換矩陣，該矩陣每行每列均只有一個1，pj，l代表該循環置換矩陣的偏移值，即該矩陣的第r行的1在第(r+pj，l) mod p列，0≤r≤p－1，該行的其他列為0。I(0)代表尺寸為p×p的單位矩陣。I(pj，l)表示I(0)循環右移pj，l以后得到的矩陣。對應地，取I(pj，l)的右移次數pj，l構成校驗矩陣H的基矩陣B，定義為:



B=

p0，0p0，1…p0，L－1

p1，0p1，1…p1，L－1



pJ－1，0pJ－1，1…pJ－1，L－1



上述QC-LDPC碼校驗矩陣含有的環可以用一個由p×p循環置換矩陣組成的序列來表示。QC-LDPC碼長為2i的環可以表示為(j0，l0)，(j1，l1)，…，(jk，lk)，…，(ji－1，li－1)，(j0，l0)，其中(jk，lk)表示H矩陣第jk行lk列所在的塊I(pjk，lk)，(jk，lk)和(jk+1，lk+1)之間的塊可以看作(jk+1，lk)。顯而易見，要正確地表示一個環，需滿足jk≠jk+1且lk≠lk+1。

文獻［13］提出長度為2i的環存在的充要條件是∑i－1k=0(pjk，lk－pjk+1，lk)=0 mod p，式中：ji=j0；jk≠jk+1；lk≠lk+1。為了使QC-LDPC碼的校驗矩陣不存在長為2i的環，就必須讓上述求和公式不成立。

2 兩種基矩陣B的構造方法

2.1 基于大衍數列的構造方法

定義1：對于一個數列f(n)，n為非負整數，若當n為奇數時，f(n)=n×n－12;當n為偶數時，f(n)=n×n2，則滿足這個遞推關系的數列稱為大衍數列，它的項就叫做大衍數列數。一個典型的大衍數列如下：0，2，4，8，12，18，24，32，…。

性質1：對于一個大衍數列，若n>m且n，m，k∈Z+，則有f(n+k)－f(n)>f(m+k)－f(m)。

性質1表述的一個含義就是大衍數列中項序號差相等的大衍數列數組成的新序列是單調遞增的。

由文獻［13］的結論可知，H矩陣長度為4的環可以表示為(j0，l0)，(j1，l1)，(j0，l0)，對任意的(j0，l0)和(j1，l1)，校驗矩陣H不含四環的充要條件是：(pj0，l0－pj0，l1)+(pj1，l1－pj1，l0)≠0 mod p。令校驗矩陣H的基矩陣B中第j行第l列的循環置換矩陣的偏移值為pj，l=f(j+l+l)+j。p取任意比基矩陣B中最大的數值大的值。不失一般性，令j0



(pj0，l1－pj0，l0)=［f(j0+l1+l1)+j0］－ 

［f(j0+l0+l0)+j0］

=f(j0+l1+l1)－f(j0+l0+l0)

(pj1，l1－pj1，l0)=［f(j1+l1+l1)+j1］－ 

［f(j1+l0+l0)+j1］

=f(j1+l1+l1)－f(j1+l0+l0)



利用性質1可知:



［f(j1+l1+l1)－f(j1+l0+l0)］>

［f(j0+l1+l1)－f(j0+l0+l0)］



進一步可得:



(pj1，l1－pj1，l0)>(pj0，l1－pj0，l0)



即:



(pj1，l1－pj1，l0)+(pj0，l0－pj0，l1)>0



滿足校驗矩陣不含長度為4的環的條件。因此，設計的校驗矩陣的環長至少為6。

例1：一個由上述方法構造的校驗矩陣H(3，6)的基矩陣B(3，6)如下所示：



B(3，6)=51325416185

1020345274100

1527436387115



2.2 基于Golomb-Ruler的構造方法

定義2：設集合G={a1，a2，a3，…，am－1，am}，a1

性質2：對于任意ai，aj∈G，i≠j，集合S:{f(n)=ai－aj}，n∈［a1－am，am－a1］中的元素各不相同。

令校驗矩陣H的基矩陣B參數為B(γ，ρ)。首先尋找階大于或等于ρ的Golomb-Ruler集合Gs，GsG。然后在Gs中隨機選取ρ個元素，構成向量V=［b1，b2，…，bρ］，bi∈Gs，i∈［1，ρ］。令Vq表示向量V循環右移q(mod ρ)次得到的新向量。取γ個各不相同的q值，即可得到γ個向量V的循環右移向量，記為：V(1)，V(2)，…，V(γ)。取V(i)，i∈［1，γ］作為B(γ，ρ)的γ個行向量，即可得到B(γ，ρ)。

同上，校驗矩陣H不含長度為4的環的充要條件是：(pj0，l0－pj0，l1)+(pj1，l1－pj1，l0)≠0 mod p。不失一般性，令j0

例2：一個由上述方法構造的校驗矩陣H(3，6)的基矩陣B(3，6)如下所示:



B(3，6)=014101217

410121701

121701410



3 仿真與分析

仿真采用1/2碼率，16 200碼長，譯碼采用BP算法，最大迭代次數為100，誤碼率取10次譯碼結果平均。兩種方法構造的碼字采用相同的參數分別在加性高斯白噪聲信道下仿真。仿真結果如圖1所示。出于對比的目的，在圖中同時給出了經典的RS碼與卷積碼級聯編碼的誤碼率曲線、IEEE 802.16e標準中定義的相同參數的LDPC碼的誤碼率曲線。

很明顯，由圖1中可以看出，LDPC碼比經典的RS碼和卷積碼級聯編碼方案至少有1.6 dB的編碼增益。基于Golomb-Ruler構造的QC-LDPC碼與基于大衍數列構造的QC-LDPC碼有幾乎接近的性能，在10-5誤碼率條件下，前者比后者大約有0.1 dB的增益。與IEEE 802.16e標準中的QC-LDPC碼相比，基于Golomb-Ruler構造的QC-LDPC碼性能在10-5誤碼率條件下有0.8 dB的性能差距，基于大衍數列構造的QC-LDPC碼性能在10-5誤碼率條件下有0.9 dB的性能差距。 

4 結 論

本文根據校驗矩陣不含長度為4的環的充要條件，設計了兩種準循環LDPC碼的校驗矩陣的構造方法。仿真顯示，本文的設計方案要優于傳統的RS碼和卷積碼級聯編碼方案。相比于IEEE 802.16e標準的設計方案，本文的方法有一定的性能差距，但是，由于基于Golomb-Ruler和大衍數列構造的QC-LDPC碼的特殊基矩陣構造方法，因此，在實現結構上，它們比IEEE 802.16e標準中給出的設計方法要簡單許多， 這在一定程度上彌補了性能上的差距帶來的影響。因此，本文的設計方案可以作為未來通信系統信道編碼部分

的一種備選方案。

參 考 文 獻

［1］GALLAGER R.G. Low density parity check codes \\[J\\]. IRE Transaction on Information Theory， 1962， 8: 21-28.



［2］MACKAY D J C， NEAL R M. Near Shannon limit performance of low density parity check codes \\[J\\]. Electronic Letter， 1996， 32: 1645-1646.



［3］MACKAY D J C. Good error-correcting codes based on very sparse matrices \\[J\\]. IEEE Transaction on Information Theory， 1999， 45: 399-432.



［4］黃翔，山拜·達拉拜.一種具有較大圍長的正則LDPC碼構造方法［J］.現代電子技術，2010，33(3):87-89，92.



［5］蘇凌杰，何明華，楊艇.一種輸出格式可控的多碼率LDPC編碼器實現［J］.現代電子技術，2009，32(18):147-149，152.



［6］ZHANG Li， HUANG Qin， LIN Shu， et al. Quasi-cyclic LDPC codes on latin squares and the ranks of their parity-check matrices \\[J\\]. Information Theory and Applications Workshop (ITA)， 2010， 20: 1-7.



［7］ZHANG Li， HUANG Qin， LIN Shu， et al. Quasi-cyclic LDPC codes: an algebraic construction， rank analysis， and codes on latin squares \\[J\\]. IEEE Transactions on Communications， 2010， 58: 3126-3139.



［8］ZHANG Li， LIN Shu， KHALED A G， et al. Circulant arrays: rank analysis and construction of quasi-cyclic ldpc codes \\[C\\]// Information Theory Proceedings (ISIT). Austin: TX， 2010， 814-818.



［9］KANG Jing-yu， HUANG Qin， ZHANG Li， et al. Quasi-cyclic LDPC codes: an algebraic construction \\[J\\]. IEEE Transactions on Communications， 2010， 58: 1383 -1396.



［10］LIN Shu， SONG Shu-mei， YING Y T， et al. Algebraic construction of nonbinary quasi-cyclic LDPC codes \\[C\\]// 2006 IEEE International Symposium on Information Theory. Seattle: WA， 2006， 1303 -1308.



［11］林炳，姜明，趙春明.基于二維優化的QC-LDPC碼構造方法［J］.東南大學學報:自然科學版，2010，40(1):6-10.



［12］彭立，朱光喜.QC-LDPC碼的置換矩陣循環移位次數設計［J］.電子學報，2010，38(4):786-790.



［13］FOSSORIER M P. Quasi-cyclic low-density parity-check codes from circulant permutation matrices \\[J\\]. IEEE Transactions on Information Theory， 2004， 50: 1788-1793.