QC-LDPC码基矩阵构造方法
开篇：润墨网以专业的文秘视角，为您筛选了一篇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(p0,0)I(p0,1)…I(p0,L－1)
I(p1,0)I(p1,1)…I(p1,L－1)
I(pJ－1,0)I(pJ－1,1)…I(pJ－1,L－1)
式中：0≤j≤J－1；0≤l≤L－1,I(pj,l)是p×p循环置换矩阵，该矩阵每行每列均只有一个1，pj,l代表该循环置换矩阵的偏移值，即该矩阵的第r行的1在第(r+pj,l) mod p列，0≤r≤p－1，该行的其他列为0。I(0)代表尺寸为p×p的单位矩阵。I(pj,l)表示I(0)循环右移pj,l以后得到的矩阵。对应地，取I(pj,l)的右移次数pj,l构成校验矩阵H的基矩阵B，定义为:
B=
p0,0p0,1…p0,L－1
p1,0p1,1…p1,L－1
pJ－1,0pJ－1,1…pJ－1,L－1
上述QC-LDPC码校验矩阵含有的环可以用一个由p×p循环置换矩阵组成的序列来表示。QC-LDPC码长为2i的环可以表示为(j0,l0),(j1,l1),…,(jk,lk),…,(ji－1,li－1),(j0,l0)，其中(jk,lk)表示H矩阵第jk行lk列所在的块I(pjk,lk)，(jk,lk)和(jk+1,lk+1)之间的块可以看作(jk+1,lk)。显而易见，要正确地表示一个环，需满足jk≠jk+1且lk≠lk+1。
文献［13］提出长度为2i的环存在的充要条件是∑i－1k=0(pjk,lk－pjk+1,lk)=0 mod p，式中：ji=j0；jk≠jk+1；lk≠lk+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的环可以表示为(j0,l0),(j1,l1),(j0,l0)，对任意的(j0,l0)和(j1,l1)，校验矩阵H不含四环的充要条件是：(pj0,l0－pj0,l1)+(pj1,l1－pj1,l0)≠0 mod p。令校验矩阵H的基矩阵B中第j行第l列的循环置换矩阵的偏移值为pj,l=f(j+l+l)+j。p取任意比基矩阵B中最大的数值大的值。不失一般性，令j0
(pj0,l1－pj0,l0)=［f(j0+l1+l1)+j0］－
［f(j0+l0+l0)+j0］
=f(j0+l1+l1)－f(j0+l0+l0)
(pj1,l1－pj1,l0)=［f(j1+l1+l1)+j1］－
［f(j1+l0+l0)+j1］
=f(j1+l1+l1)－f(j1+l0+l0)
利用性质1可知:
［f(j1+l1+l1)－f(j1+l0+l0)］>
［f(j0+l1+l1)－f(j0+l0+l0)］
进一步可得:
(pj1,l1－pj1,l0)>(pj0,l1－pj0,l0)
即:
(pj1,l1－pj1,l0)+(pj0,l0－pj0,l1)>0
满足校验矩阵不含长度为4的环的条件。因此，设计的校验矩阵的环长至少为6。
例1：一个由上述方法构造的校验矩阵H(3,6)的基矩阵B(3,6)如下所示：
B(3,6)=51325416185
1020345274100
1527436387115
2.2 基于Golomb-Ruler的构造方法
定义2：设集合G={a1,a2,a3,…,am－1,am}，a1
性质2：对于任意ai,aj∈G，i≠j，集合S:{f(n)=ai－aj}，n∈［a1－am,am－a1］中的元素各不相同。
令校验矩阵H的基矩阵B参数为B(γ,ρ)。首先寻找阶大于或等于ρ的Golomb-Ruler集合Gs，GsG。然后在Gs中随机选取ρ个元素，构成向量V=［b1,b2,…,bρ］，bi∈Gs，i∈［1,ρ］。令Vq表示向量V循环右移q(mod ρ)次得到的新向量。取γ个各不相同的q值，即可得到γ个向量V的循环右移向量，记为：V(1),V(2),…,V(γ)。取V(i)，i∈［1,γ］作为B(γ,ρ)的γ个行向量，即可得到B(γ,ρ)。
同上，校验矩阵H不含长度为4的环的充要条件是：(pj0,l0－pj0,l1)+(pj1,l1－pj1,l0)≠0 mod p。不失一般性，令j0
例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.