低存储可线性编码的QC-LDPC码设计

孔令军 姜 明 赵春明

(1东南大学移动通信国家重点实验室, 南京 210096)(2南京邮电大学通信与信息工程学院, 南京 210003)

低存储可线性编码的QC-LDPC码设计

孔令军1,2姜 明1赵春明1

(1东南大学移动通信国家重点实验室, 南京 210096)(2南京邮电大学通信与信息工程学院, 南京 210003)

为了解决构造任意长度、无小停止集且无短环QC-LDPC码的设计问题,研究了基于Tanner图的停止集、围长和最小码重三者之间的关系,提出了QC-LDPC码无短停止距离且无短环的充要条件.在此基础上,为了进一步降低编码复杂度并保留结构化特性,提出了一种具有线性编码复杂度的基于后向迭代的QC-LDPC码.仿真结果表明:所构造的QC-LDPC码的纠错性能与IEEE 802.11n中QC-LDPC码相近,与IEEE 802.16e中QC-LDPC码相比,在误码率为10-6时,可获得0.15 dB的性能增益;此外,该码字只需存储移位因子和单位子矩阵的阶数,所占硬件存储空间明显小于另外2种QC-LDPC码.

QC-LDPC码;准循环码;停止集;停止距离;围长

近年来,LDPC码[1-2]凭借其在AWGN等信道中具有接近香农限的纠错性能且可实现的译码复杂度,成为当今信道编码领域的研究热点之一[3-5].QC-LDPC码是借用数学分析法(如几何代数方法)来构造的一类非常重要的LDPC码,其校验矩阵具有类循环特性,实现复杂度低,可以采用简单的移位寄存器硬件来实现编码器,易于硬件实现[6-7].

LDPC码的校验矩阵主要基于停止集和围长来进行构造.停止集及其停止距离制约着迭代译码收敛速率;当围长趋于无穷时,和积译码算法近似为最优译码算法.文献[8]指出,经过二进制删除信道或AWGN信道传输, 采用迭代译码算法时停止集具有重要的作用.文献[9-10]指出,采用迭代译码算法时译码性能差的主要原因是LDPC码对应的Tanner图中含有小的停止集.编码复杂度是影响LDPC码应用的一个主要问题.通常采用生成矩阵的方法进行编码,编码运算复杂度为码长的平方.LDPC码的码长往往多达数千比特,会影响编码器的实现.为此,需要回避生成矩阵,直接通过校验矩阵进行编码.在码字性能允许的范围内,校验矩阵结构化能最大限度地降低编码复杂度.IEEE 802.16e和IEEE 802.11n标准中均采用了可近似线性编码的LDPC码方案,虽然降低了编码的复杂度,但破坏了LDPC码校验矩阵的结构特性,增加了编解码器所占的硬件存储资源.

为了在降低编码复杂度的同时保留结构化特性,本文提出了一种基于后向迭代的可线性编码的QC-LDPC码,综合考虑了停止集、围长、最小码重三者之间的关系,在增加围长和停止距离的同时尽可能提高最小码重.仿真结果表明,所设计的码字具有良好的误码率性能,更适于实际应用.

1 QC-LDPC码的停止集与围长

对于每个变量节点v∈V和校验节点c∈C,dv和dc分别表示v和c的度,dV(c)表示连接c到变量节点集合V的边的数量.集合S为LDPC码对应的Tanner图的变量节点集合V的子集.如果集合S的所有邻节点(与Tanner图中集合S的变量节点相连的校验节点)与S相连的次数不少于2,则称S为停止集.停止集一般由多个环构成.构成停止集的变量节点分为2种:① 变量节点与其他变量节点构成环;② 变量节点连接不同的环.

QC-LDPC码的校验矩阵由单位阵的循环移位组合而成,其移位数由索引矩阵确定[6].索引矩阵P可表示为

(1)

式中,索引矩阵元素Px,y=aybx,其中0≤x≤j-1,0≤y≤k-1,j和k分别为矩阵的行数和列数,a和b为移位因子.

QC-LDPC码的校验矩阵H可由P得到,其元素IPx,y由m阶单位阵I循环移位Px,y(modm)位构成.

定理1 QC-LDPC码的校验矩阵H含有停止距离为3的停止集的充要条件为：至少存在一组数(x,x′,x″,y,y′,y″)使得方程组

(2)

中至少一个方程成立,同时满足

H(i,y)+H(i,y′)+H(i,y″)≠1

(3)

式中,0≤x≤j-3;1≤x′≤j-2;2≤x″≤j-1;x≠x′≠x″;0≤y≤k-3; 1≤y′≤k-2;2≤y″≤k-1;y≠y′≠y″;0≤i≤j-1;i≠x≠x′≠x″.

证明 至少存在一组数(x,x′,x″,y,y′,y″)使得方程组(2)中任意一方程成立时,QC-LDPC码的校验矩阵H含有6环.定理1的证明等价于若校验矩阵H含有6环,其6环所含有的3个变量节点构成停止距离为3的停止集.由停止集定义可知,其邻节点与本身连接边的数目不少于2.构成6环的3个邻节点满足定义,只要确保其他邻节点也满足定义即可.式(3)确保了其他校验节点与构成6环的变量集合S连接次数不等于1.此时,变量集合S构成停止距离为3的停止集.

推论1 QC-LDPC码校验矩阵H中无停止距离为3的停止集的必要条件为

(4)

式中, 1≤s≤k-2;2≤s′≤k-1;s

根据推论1,本文提出停止距离为3的停止集检测方程组为

(5)

式中,1≤s≤k-2;2≤s′≤k-1;s

以列重为3、行重为6的(3,6)QC-LDPC码为例,根据式(5)得出停止距离为3的停止集检测矩阵F为

F=F1&F2&F3&F4&F5&F6

(6)

式中

(7)

式中,1≤v≤6.

设定移位因子a,b及最小单位子矩阵的阶次m后,检测矩阵F中非下三角矩阵的值是否无零元素,即可确定QC-LDPC码是否含有停止距离为3的停止集. 根据式(5),可得出任意QC-LDPC码的检测矩阵,从而构造出任意行重和列重的无停止距离为3的QC-LDPC码,进一步构造出无停止距离为2的QC-LDPC码.低码重码的存在使译码器纠错能力低下,不能纠正多个比特的错误.根据最小码重定义可知,生成矩阵行向量的最小码重小于该码字的最小码重,可作为最小码重的一个上界,从而为构造无低码重的LDPC码提供依据.

2 低存储可线性编码的QC-LDPC码构造算法

根据定理1及推论1,给定移位因子,计算其对应的QC-LDPC码停止集检测矩阵,筛选出使码字无停止距离为2和3的移位因子.为进一步降低编码复杂度,令所构造LDPC码的校验矩阵Hd为

Hd=[HtHbs]

(8)

式中,Ht和Hbs分别表示具有准循环结构的子矩阵和后向迭代的双对角矩阵,且Ht的索引矩阵满足式(1).由式(1)可知,只需确定移位因子a和b、单位子矩阵阶数p以及列重cw,即可得出校验矩阵Ht.

低存储可线性编码的QC-LDPC码构造算法步骤如下:

①κ=1,根据Tκ=(aκ,bκ)可得移位因子aκ和bκ,令a=aκ,b=bκ,根据式(1)可得到Htκ.

② 后向双对角矩阵Hbsκ矩阵为

(9)

式中,I0表示无移位的单位矩阵.

④ 根据Tκ中的移位因子，构造出无短环和无小停止集、具有线性编码复杂度的QC-LDPC码.

⑦ 得到最终所构造码字的最小汉明距离dmin≈wmin.

综合考虑环、停止集以及最小码重对LDPC码性能的影响,进行低存储、可线性编码的QC-LDPC码设计.此外,采用本文方法还可估算QC-LDPC码的最小汉明距离.

3 性能分析与仿真比较

所构造的QC-LDPC码校验矩阵Hd为

(10)

式中,单位阵I的下标根据式(1)确定.

表1 LDPC码的参数

与IEEE 802.11n和IEEE 802.16e中QC-LDPC码的校验矩阵相比,所提出的基于后向迭代的子矩阵结构最为简单,IEEE 802.11n和IEEE 802.16e中码字的校验矩阵只是具有近似的双对角结构.此外,IEEE 802.11n和IEEE 802.16e中QC-LDPC码的校验矩阵左边子矩阵不具备准循环特性,因此需要大量的硬件存储资源存储校验矩阵,而所构造的校验矩阵只需存储移位因子a和b.

图1为本文构造的QC-LDPC码与其他LDPC码的BER曲线比较.由构造方法可知,所设计的码字既不含停止距离为2和3的停止集,又有效避免了4环和6环;同时,所提方案确保码字的最小码重尽可能最大化.仿真结果证明,与等长的随机LDPC码相比,基于后向迭代的不规则QC-LDPC码具有较好的BER性能,在SNR<2 dB时能迅速收敛.本文构造的QC-LDPC码具有优于IEEE 802.16e 中标准中等长QC-LDPC码的BER性能,当BER=10-6时,具有大约0.15 dB的增益;而与IEEE 802.11n中的QC-LDPC码相比,两者具有相近的纠错性能.此外,所构造的QC-LDPC码具有线性编码复杂度,且在码率和码长已知时,只需存储移位因子和单位子矩阵的阶数,因而存储校验矩阵所占硬件存储空间较小,而另外2种QC-LDPC码为近似线性编码,需要较大的存储空间.

图1 LDPC码仿真误码率比较

4 结论

1)为了在降低编码复杂度的同时保留结构化特征,本文提出了一种基于后向迭代的可线性编码的不规则QC-LDPC码.该码字具有良好的BER性能,既不含停止距离为2和3的停止集,又有效避免了4环和6环;所提方案确保码字的最小码重尽可能最大化.

2)仿真结果表明,该码字具有优于IEEE 802.16e标准中等长码的BER性能,以及和IEEE 802.11n中码字相近的误码率性能；所构造的QC-LDPC码具有线性编码复杂度,且存储校验矩阵所占的硬件存储空间较小,因而实际应用更加可行.

References)

[1]Gallager R. Low-density parity-check codes[J].IEEETransactionsonInformationTheory, 1962, 8(1): 21-28. DOI:10.1109/tit.1962.1057683.

[2]Richardson T J. LDPC design for high parallelism, low error floor, and simple encoding:US, US9306601[P]. 2016-04-05.

[3]Ganesan K, Grover P, Rabaey J, et al. On the total power capacity of regular-LDPC codes with iterative message-passing decoders[J].IEEEJournalonSelectedAreasinCommunications, 2016, 34(2): 375-396. DOI:10.1109/jsac.2015.2504276.

[4]Song L, Huang Q, Wang Z, et al. Two enhanced reliability-based decoding algorithms for nonbinary LDPC codes[J].IEEETransactionsonCommunications, 2016, 64(2): 479-489. DOI:10.1109/tcomm.2015.2512582.

[5]Tasdighi A, Banihashemi A H, Sadeghi M R. Efficient search of girth-optimal QC-LDPC codes[J].IEEETransactionsonInformationTheory, 2016, 62(4): 1552-1564. DOI:10.1109/tit.2016.2523979.

[6]Tanner R M, Sridhara D, Sridharan A, et al. LDPC block and convolutional codes based on circulant matrices[J].IEEETransactionsonInformationTheory, 2004, 50(12): 2966-2984. DOI:10.1109/tit.2004.838370.

[7]林炳, 姜明, 赵春明. 基于二维优化的QC-LDPC码构造方法[J]. 东南大学学报(自然科学版), 2010, 40(1): 6-10. DOI:10.3969/j.issn.1001-0505.2010.01.002. Lin Bing, Jiang Ming, Zhao Chunming. Construction of QC-LDPC codes based on two-dimentional optimization[J].JournalofSoutheastUniversity(NaturalScienceEdition), 2010, 40(1): 6-10. DOI:10.3969/j.issn.1001-0505.2010.01.002.(in Chinese)

[8]Di C A, Proietti D, Telatar I E, et al. Finite-length analysis of low-density parity-check codes on the binary erasure channel[J].IEEETransactionsonInformationTheory, 2002(6): 1570-1579. DOI:10.1109/tit.2002.1003839.

[9]Tian T, Jones C, Villasenor J D, et al. Construction of irregular LDPC codes with low error floors[C]//Proceedingsof2003IEEEInternationalConferenceonCommunications. Anchorage, Alaska, USA, 2003: 3125-3129.

[10]马克祥. LDPC码快速及低错误平层译码算法研究[D]. 西安: 西安电子科技大学通信工程学院, 2014.

QC-LDPC code design with low hardware storage and linear encoding

Kong Lingjun1, 2Jiang Ming1Zhao Chunming1

(1National Mobile Communications Research Laboratory, Southeast University, Nanjing 210096, China)(2College of Telecommunications and Information Engineering, Nanjing University of Posts and Telecommunications, Nanjing 210003, China)

To solve the design problem of constructing quasi-cyclic low-density parity-check (QC-LDPC) codes of any length without small stopping sets or small girth, the relationship among the stopping set, the girth and the minimum weight based on the Tanner graph is investigated. The necessary and sufficient conditions of the QC-LDPC codes without small stopping sets or small girth are proposed. To further reduce the encoding complexity and maintain the structural characteristics, the backward iteration based QC-LDPC code with linear encoding complexity is proposed. The simulation results show that the error correction performance of the constructed QC-LDPC code is similar to that of the QC-LDPC code in IEEE 802.11n. And the designed code achieves a performance gain of 0.15 dB at the bit error rate of 10-6compared with the QC-LDPC code in IEEE 802.16e. Meanwhile, the proposed code only needs to store the shift factor and the order of the unit sub-matrix, inducing that the hardware storage resource is obviously smaller than those of the other two QC-LDPC codes.

low-density parity-check (QC-LDPC) code; quasi-cyclic (QC) code; stopping set; stopping distance; girth

10.3969/j.issn.1001-0505.2017.03.001

2016-11-10. 作者简介: 孔令军(1982—),男,博士,副教授,ljkong@njupt.edu.cn.

中国博士后科学基金资助项目(2015M581698)、国家自然科学基金青年基金资助项目(61501250)、教育部留学回国人员科研启动基金资助项目(BJ215002)、江苏省博士后科研资助计划资助项目(1501037B)、江苏省自然科学基金青年基金资助项目(SJ214029)、江苏省高校自然科学研究面上项目资助项目(14KJB510021)、南京邮电大学引进人才科研启动基金资助项目(NY214015).

孔令军，姜明，赵春明.低存储可线性编码的QC-LDPC码设计[J].东南大学学报(自然科学版),2017,47(3):421-425.

10.3969/j.issn.1001-0505.2017.03.001.

TN911.22

A

1001-0505(2017)03-0421-05