张 轶,达新宇,苏一栋

(空军工程大学信息与导航学院,陕西西安 710077)



任意列重大围长QC-LDPC码的确定性构造

张 轶,达新宇,苏一栋

(空军工程大学信息与导航学院,陕西西安 710077)

针对准循环低密度奇偶校验(Quasi-Cyclic Low-Density Parity-Check,QC-LDPC)码中准循环基矩阵的移位系数确定问题，提出基于等差数列的确定方法.该方法构造的校验矩阵围长为8，列重可任意选取，移位系数由简单的数学表达式确定，编码复杂度与码长呈线性关系，节省了编解码存储空间.研究结果表明，列重和围长是影响码字性能的重要因素.在加性高斯白噪声(Additive White Gauss Noise,AWGN)信道和置信传播(Belief Propagation,BP)译码算法下，该方法构造的码字在短码时可以获得与IEEE 802.11n、802.16e码相一致的性能，在长码时误比特率性能接近DVB-S2码.同时表明该方法对码长和码率参数的设计具有较好的灵活性.

准循环低密度奇偶校验码;列重;围长;准循环基矩阵;高效编码

电子学报URL:http://www.ejournal.org.cn DOI:10.3969/j.issn.0372-2112.2016.08.006

1 引言

码的结构决定了低密度奇偶校验(Low-Density Parity-Check,LDPC)码的性能.基于循环移位矩阵构造的QC-LDPC码，其校验矩阵的准循环特性使其易于高效编解码，码的代数结构为超大规模集成电路的实现提供了可能，因此受到广泛关注和研究.围长是码中最小的环长度，增大围长可以提高码字的性能.借助于计算机搜索，人们已经提出了一些围长大于6的QC-LDPC码构造方法[1～6]，但为了满足各种约束条件，这些准随机方法通常花费时间长、存在失败可能，且对编解码存储空间提出了更高要求.

针对上述问题，国内外学者对确定性构造方法的研究屡有成果涌现.Tanner[7]和Zhang Fan[8]分别采用群结构法、3维循环网络法构造出了围长在10以上的QC-LDPC码，但是校验矩阵的行重只局限于特定范围内；Zhang Guo-hua[9]提出了基于二次函数的确定性方法，但方程系数与行重有关，任意行重只能构造两种校验矩阵；张国华[10～12]基于贪婪算法构造了围长为8的QC-LDPC码，其循环移位矩阵尺寸具有连续变化的优点，但该方法要求准循环基矩阵首行首列元素必须为0；Zhang Jian-hua[13]首次提出任意列重的构造方法，然而固定码参数下的校验矩阵形式是唯一的.此外，以上方法均未考虑由校验矩阵直接编码的方案，这在一定程度上限制了它们的实际应用.

在此基础上，本文提出一种构造任意列重、围长为8的QC-LDPC码确定性方法.首先构造了列重为4的基矩阵，分析了其围长特性；通过总结推导将特殊情形推广，进而提出任意列重的确定性构造方法，并证明了该码的围长至少为8；然后利用特殊的子矩阵结构实现了由校验矩阵进行迭代编码，降低了编码复杂度；最后通过软件仿真，验证了该方法构造的QC-LDPC码参数设置灵活、性能优良.

2 QC-LDPC码

QC-LDPC码的校验矩阵以单位阵的循环移位阵和零方阵为子阵，可表示为

(1)

其中：I(pij)表示一个p×p的循环移位矩阵.把循环右移系数pij写成一个矩阵P，称为准循环基矩阵，如式(2)所示[14]：

(2)

在基矩阵P中，若干个点(元素)p1,p2,…,p2k构成一个环，则对应的H矩阵也存在与之对应的p个同样大小的环.显然，环的长度只能是大于或等于4的偶数.表示H中长为2k环的序列(p1,p2,…,p2k)满足如下定理：

定理1[15]对于基矩阵P中的序列(p1,p2,…,p2k)，其中pi和pi+1在同一行或同一列，pi和pi+2在不同行且不同列，则(p1,p2,…,p2k)构成长为2k环的充要条件是

(3)

短环的存在使LDPC码在译码时不能快速收敛，造成误比特率(Bit Error Rate,BER)性能变差.因此，为了使校验矩阵不含长为2k的环，就必须通过某种设计，使得式(3)不成立.图1给出了6环存在的六种形状.

3 构造方法

将校验矩阵H分为校验部分Ha和信息部分Hb，如式(4)所示：

H=

(4)

其中，Ha为下三角结构，大小为mp×mp，主对角线由单位阵构成，0表示零矩阵；Hb大小为mp×kp(k=n-m).

首先考虑一种(4,n)基矩阵P的配置方式：

p1,j+1-p1,j=d1>0,1≤j

(5)

p2,j+1-p2,j=d2>d1,2≤j

(6)

p3,j+1-p3,j= max[(n-j)·(d2-d1)+d1+1,(j-1)

·(d2-d1)+d1+1], 3≤j

(7)

p4,j+1-p4,j=p3,j+1-p3,j+1, 4≤j

(8)

显然P中第1、2行元素分别构成单增等差数列.首先证明一些引理.

引理1 P中无4环.

证明 由式(5)～式(8)，对任意4≤i

p4,j-p4,i>p3,j-p3,i>p2,j-p2,i>p1,j-p1,i>0

(9)

同理对任意2≤i

引理2 P中无图1(a)～(d)所示6环.

证明 根据引理1的证明过程，引理2显然成立.

引理3 P中无图1(e)～(f)所示6环.

证明 令P中第x,y,z行(1≤x,y,z≤4)构成的矩阵为P(x,y,z).考虑P(1,2,3)和图1(e)的情形，不失一般性，令2≤i

由式(7)可得p3,j-p3,l≥(d2-d1)·l+d1+1，故

(p3,j-p3,l)+(p1,l-p1,i)+(p2,i-p2,j)

≥(d2-d1)·l+d1+1+(l-i)·d1+(i-j)·d2

=(d2-d1)·(i-1)+1>0

(10)

因此P(1,2,3)中无图1(e)所示6环，同理也不存在图1(f)所示6环.采用相同的分析方法易知P(1,2,4)、P(1,3,4)和P(2,3,4)的中均无6环.

将其推广至任意列重的基矩阵，令di,j=pi,j+1-pi,j，1≤i≤m，i≤j

(1)当m≤4时，按照式(5)～式(8)配置P.

(2)当m>4时，设

d4k+1,j=p4k-1,n-(n-4k)·d1+1,k≥1

(11)

d2k+2,j=d2k+1,j+1,k≥2

(12)

d4k+3,j=max(d4k+1,j+n-j

+1,d4k+1,j+j-4k),k≥1

(13)

引理4 (m,n)基矩阵P中无6环.

证明 不失一般性，令1≤r

考虑关系①和图1(e)的情形，注意到此时4k+1≤i≤4k+4，得到：

(14)

因此有

(pt,j-pt,l)+(pr,l-pr,i)+(ps,i-ps,j)

≥p4k+3,n-(n-4k-4)·d1+1+(n-4k-5)

·d1-p4k+4,n

=p4k+3,n-p4k+4,n-d1+1

(15)

由式(12)易知

p4k+4,n=p4k+3,n-p4k+3,4k+4+(n-4k-4)

(16)

再由式(13)可得：

p4k+3,4k+4=d4k+3,4k+3

=d4k+1,4k+3+n-4k-2

(17)

将式(16)、式(17)代入式(15)可知其结果大于0.同理可得，当行指数满足关系②、③、④，以及m为任意值时引理4成立.证毕.

根据引理1～4可得到定理2.

定理2 对于任意列重m、任意行重n，由式(4)～式(8)、式(11)～式(13)定义的基矩阵P的围长至少为8.

可以发现，基矩阵P的第4k+1、4k+2(k≥0)行元素均构成单增等差数列；当初始值m、n、d1、d2确定后，移位系数可由数学公式计算得到；本文方法参数设置灵活，而移位矩阵的维数p大于移位系数，故p的取值下界为

infp=max(pi,n)+1,1≤i≤m

(18)

例1 利用本文方法设计的一种(6,8)基矩阵如式(19)所示：

(19)

4 编码复杂度分析

由式(4)易知Ha满秩，因此H是非奇异的，即可回避生成矩阵G而直接由校验矩阵进行编码.

采用LU分解法，令信息比特向量为s=[s1s2…sk]，校验比特向量为p=[p1p2…pm]，编码器输出行向量为c，它的长度N=np=(m+k)p，则有

(20)

根据校验等式H·cT=0可得：

Ha·pT+Hb·sT=0

(21)

由于运算在GF(2)中进行，所以有

(22)

将式(22)展开由第m式可得：

(23)

将式(23)回代到方程组式(22)的第m-1式可得：

(24)

依次类推可得到各个pi，代入到式(20)，编码完毕.

编码复杂度主要关注编码过程的运算量、运算复杂度和编码所需存储的参数.运算量即乘法和加法次数，运算复杂度即运算量与码长的变化关系.QC-LDPC码的各个子矩阵都是稀疏矩阵，因此按照稀疏矩阵的运算方式可大大减小运算量.现计算pi的运算量如表1所示.

表1 编码算法的运算量

从表1可明显地看到，计算各个校验分向量pi的运算复杂度为O(N)，即运算复杂度与码长呈线性关系.同时由于该码采用代数构造法，校验矩阵中的元素由简单的数学运算得到，只需要存储一组初始参数和几个数学表达式即可，编码器的实际存储量需求非常小.

5 仿真与实验

5.1 最小码重、码距分析

一般认为码重小于10的码为低码重码[16]，这类码的存在使LDPC译码器纠错能力低下.目前尚没有办法准确求出码字的最小码重，本文采用文献[16]给出的搜索算法，即通过生成矩阵的行向量估计LDPC码的最小码重和最小码距的上界.仿真选取4种码字，基矩阵尺寸分别为(4,8)，(4,12)，(5,10)，(6,12)，初始参数均为d1=1，d2=2.各码字码长及码重分布情况如图2所示，计算机搜索得到的最小码重、最小码距的上界如表2所示.

表2 最小码重、最小码距搜索结果

仿真结果表明，(4,8)和(4,12)两种基矩阵下其最小码重的上界均为14，这是因为两种校验矩阵的列重结构是一样的，都包含4种列重，而(4,12)中小列重的比例更小，因此码重为16的行向量所占比重较大；随着列重的增大，LDPC码的最小码重和码距也增大，因此校验矩阵使用大的列重可减小产生低码重码的可能性.

5.2 性能分析

IEEE 802.11n、802.16e以及DVB-S2标准中均采用准双对角线子矩阵实现迭代编码，与本文设计的方法类似，故与这3种码字进行性能比较.仿真环境为加性高斯白噪声(AWGN)信道，译码采用置信传播(BP)算法，最大迭代次数为30，调制方式为BPSK.

实验1 与IEEE 802.11n、802.16e标准LDPC码的比较

根据IEEE 802.11n标准选择2种参数的基矩阵：维数p=27，码长N=648，码率R=1/2；维数p=54，码长N=1296，码率R=2/3.利用本文方法构造同码长码率的2种基矩阵分别为：维数p=81，d1=5，d2=7；维数p=108，d1=3，d2=4.仿真结果如图3所示.

根据IEEE 802.16e标准选择2种参数的基矩阵：维数p=24，码长N=576，码率R=1/2；维数p=48，码长N=1152，码率R=2/3B类.利用本文方法构造同码长码率的2种基矩阵分别为：维数p=72，d1=3，d2=5；维数p=96，d1=1，d2=2.仿真结果如图4所示.

仿真结果表明，在中短码条件下，本文构造的码字与IEEE 802.11n、802.16e标准的LDPC码相比BER性能相一致.从仿真参数可以看到，本文给出的校验矩阵的列重显然比上述两类标准的要小，即最小码重更小，然而BER性能却并未由此下降，说明大围长特性促进了该部分的性能增益，验证了理论推导的正确性.此外，IEEE 802.11n、802.16e标准的LDPC码分别只提供了4种和6种基矩阵形式，不同码率下需要存储不同的移位系数，随着通信技术的不断发展在实际应用中难免受到约束.而本文方法可根据需求灵活地设置初始参数，校验矩阵由数学公式自动计算得到，大大节省了编解码存储空间，校验矩阵形式也更多样化.

实验2 与DVB-S2标准LDPC码的比较

DVB-S2标准中的LDPC码只有两种码长，即使短码也长达16200 bit，这对于编解码器的实现具有较大的难度，故采用文献[17]中的缩短码设计，选择2种码率R=1/2的基矩阵，码长分别为5400和8100.利用本文方法构造同码长码率的2种基矩阵分别为：维数p=540，d1=11，d2=13；维数p=675，d1=16，d2=17；仿真结果如图5所示.

仿真结果表明，DVB-S2标准的LDPC码比本文构造的码字性能略优.这是因为该标准下校验矩阵的最大列重为8，在长码条件下的性能增益会更凸显，而本文设计的码字在无列重优势的情况下，BER性能已经可以与之接近.另外，与IEEE 802.11n、802.16e标准类似，DVB-S2标准针对不同码率规定了不同的编码信息表，同样可能存在编码器存储与应用范围受限等问题.综上所述，本文构造码字不失为一种好码.

6 结论

本文提出了一种构造围长至少为8的(m,n)QC-LDPC码的确定性方法.该码的准循环基矩阵由数学表达式确定，构造方法简单，节省了编解码存储空间，校验矩阵可直接进行迭代编码，降低了编码复杂度.研究结果表明，这类码只需少量的初始值控制就可设计任意参数的基矩阵，同时在AWGN信道中能够获得较好的纠错能力，因此对信道编码理论的研究和应用具有一定的参考价值.在此方法基础上，如何构造围长大于8的QC-LDPC码是今后深入研究的内容之一.

[1]O’Sullivan M E.Algebraic construction of sparse matrices with large girth[J].IEEE Transactions on Information Theory,2006,52(2):718-727.

[2]Jiang X,Lee M H.Large girth non-binary LDPC codes based on finite fields and Euclidean geometries[J].IEEE Signal Processing Letters,2009,16(6):521-524.

[3]Huang Jen-Fa,Huang Chun-Ming,Yang Chao-Chin.Construction of one-coincidence sequence quasi-cyclic LDPC codes of large girth[J].IEEE Transactions on Information Theory,2012,58(3):1825-1836.

[4]Zhang Guo-hua,Sun Rong,Wang Xin-mei.Construction of girth-eight QC-LDPC codes from greatest common divisor[J].IEEE Communications Letters,2013,17(2):369-372.

[5]Park H,Hong S,NO J S,et al.Design of multiple-edge protographs for QC LDPC codes avoiding short inevitable cycles[J].IEEE Transactions on Information Theory,2013,59(7):4598-4614.

[6]Wang Ju-hua,Zhang Guo-hua,Zhou Quan.Coset-based QC-LDPC codes without small cycles[J].Electronics Letters,2014,50(22):1597-1598.

[7]Kim S,NO J S,Chung H,et al.On the girth of tanner (3,5) quasi-cyclic LDPC codes[J].IEEE Transactions on Information Theory,2006,52(4):1739-1744.

[8]Zhang Fan,Mao Xue-hong,Zhou Wu-yang,et al.Girth-10 LDPC codes based on 3-D cyclic lattices[J].IEEE Transactions on Vehicular Technology,2008,57(2):1049-1060.

[9]Zhang Guo-hua,Sun Rong,Wang Xin-mei.Deterministic construction of girth-eight (3,L) QC-LDPC codes from quadratic function[J].Electronics Letters,2013,49(9):600-602.

[10]张国华,陈超,杨洋，等.Girth-8 (3,L)-规则QC-LDPC码的一种确定性构造方法[J].电子与信息学报,2010,32(5):1152-1156.

Zhang Guo-hua,Chen Chao,Yang Yang,et al.Girth-8 (3,L)-regular QC-LDPC codes based on novel deterministic design technique[J].Journal of Electronics & Information Technology,2010,32(5):1152-1156.(in Chinese)

[11]Zhang Guo-hua,Sun Rong,Wang Xin-mei.Several explicit constructions for (3,L) QC-LDPC codes with girth at least eight[J].IEEE Communications Letters,2013,17(9):1822-1825.

[12]张国华,孙蓉,王新梅.围长至少为8的QC-LDPC码的新构造:一种显示框架[J].电子学报,2012,40(2):331-337.

Zhang Guo-hua,Sun Rong,Wang Xin-mei.Novel constructions of QC-LDPC codes with girth at least eight:an explicit framework[J].Acta Electronica Sinica,2012,40(2):331-337.(in Chinese)

[13]Zhang Jian-hua and Zhang Guo-hua.Deterministic girth-eight QC-LDPC codes with large column weight[J].IEEE Communications Letters,2014,18(4):656-659.

[14]郑健,别红霞,类春阳,等.优化循环转移矩阵偏移量的QC-LDPC码构造[J].北京邮电大学学报,2014,37(1):16-19.

Zheng Jian,Bie Hong-xia,Lei Chun-yang,et al.A construction algorithm with optimized shift value of circulant permutation matrix for QC-LDPC codes[J].Journal of Beijing University of Posts and Telecommunications,2014,37(1):16-19.(in Chinese)

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

[16]肖扬.Turbo与LDPC编解码及其应用[M].北京:人民邮电出版社,2010.

Xiao Yang.Turbo and LDPC Codes and Their Applications[M].Posts & Telecom Press,Beijing,2010.(in Chinese)

[17]肖扬,范俊,黄希.DVB-S2标准的LDPC码改进[J].铁道学报,2011,33(2):52-59.

Xiao Yang,FAN Jun,HUANG Xi.Improvement in LDPC codes in DVB-S2 standard[J].Journal of The China Railway Society,2011,33(2):52-59.(in Chinese)

张 轶 男,1986年10月出生，山西太原人.空军工程大学信息与导航学院博士研究生，从事信道编码理论方面的有关研究.

E-mail:zhangyi1290@163.com

达新宇 男,1961年4月出生，陕西眉县人.教授、博士生导师、国家精品课程《通信原理》负责人.1983年、1988年和2007年分别在西安电子科技大学、空军地空导弹学院和西北工业大学获工学学士、工学硕士和工学博士学位.现为空军工程大学信息与导航学院教授，主要从事卫星通信、信道编码、认知无线电等方面的研究工作.

Deterministic Construction of QC-LDPC Codes for Any Column Weight with a Large Girth

ZHANG Yi,DA Xin-yu,SU Yi-dong

(InformationandNavigationCollege,AirForceEngineeringUniversity,Xi’an,Shaanxi710077,China)

To cope with the issue of determining cyclic shift coefficients of the quasi-cyclic sub-matrix in the Quasi-Cyclic Low-Density Parity-Check (QC-LDPC) codes,a method was presented based on the arithmetic progression to compute the cyclic shift coefficients.By this method,a class of girth eight QC-LDPC codes for any column weight is obtained,and the cyclic shift coefficients can be expressed in simple analytic expressions to reduce required memory usage.Meanwhile,the encoding complexity is linearly proportional to code length due to the lower triangular parity matrix.The simulation result shows that column weight and girth have important influences on code performance.Furthermore,over an Additive White Gauss Noise (AWGN) channel and under the Belief Propagation (BP) decoding algorithm,the simulation results represent that bit error rate of the proposed QC-LDPC codes is no less than the LDPC codes in IEEE 802.11n and 802.16e with short code length,and is close to the LDPC codes in DVB-S2 with long code length.Moreover,the study result also confirms that the proposed algorithm has high flexibility with respect to the design of code length and rate.

quasi-cyclic low-density parity-check (QC-LDPC) codes;column weight;girth;quasi-cyclic sub-matrix;efficient encoding

2014-12-17;

2015-04-10；责任编辑：马兰英

国家自然科学基金(No.61271250)

TN911.22

A

0372-2112 (2016)08-1814-06