袁建国，李媛媛，梁梦琪，尚晓娟，王 永

（重庆邮电大学光通信与网络重点实验室，重庆　400065）

利用完备差集构造QC-LDPC码*

袁建国**，李媛媛，梁梦琪，尚晓娟，王 永

（重庆邮电大学光通信与网络重点实验室，重庆400065）

针对准循环低密度奇偶校验（QC-LDPC）码中循环置换矩阵的移位次数的确定问题，提出了一种利用组合设计中完备差集（PDF）构造QC-LDPC码的新颖方法。当循环置换矩阵的维度大于一定值时，该方法所构造的规则QC-LDPC码围长至少为6，具有灵活选择码长和码率的优点，且所需的存储空间更少，降低了硬件实现的复杂度。仿真结果表明：在误码率为10-5时，所构造的码率为3/4的PDF-QC-LDPC（3136，2352）与基于最大公约数（GCD）构造的GCD-QC-LDPC（3136，2352）码和基于循环差集（CDF）构造的CDF-QC-LDPC（3136，2352）码相比，其净编码增益（NCG）分别有0.41 dB和0.32 dB的提升；且在码率为4/5时，所构造的PDF-QC-LDPC（4880，3584）码比GCD-QC -LDPC（4880，3584）码和CDF-QC-LDPC（4880，3584）码的NCG分别改善了0.21 dB和0.13 dB。

准循环低密度校验码；循环置换矩阵；完备差集；净编码增益

1　引　言

低密度奇偶校验（Low-Density Parity-Check，LDPC）码是一种性能逼近香农限的线性分组码，具有编译码实现复杂度低、易于硬件实现的优点［1］。由于在相同的码的参数下，LDPC码的结构不同，编译码复杂度也不同，同时性能也有所差异。因此，如何构造编译码简单、性能优异的LDPC码是LDPC码的研究热点之一。

LDPC码的构造主要分为随机构造和结构化构造两大类。随机码结构灵活且纠错性能优异，但是码的生成矩阵及校验矩阵的结构没有确定的形式，因此编译码的复杂度很高，硬件实现存在一定难度［2-3］。而结构码是由代数、组合数学和有限几何等方法构造的［4-6］，循环码或准循环低密度奇偶校验（Quasi-Cyclic Low-Density Parity-Check，QC-LDPC）码都属于结构码。由于结构码的校验矩阵存在循环特性，因此编译码复杂度大大降低，尤其是QC -LDPC码的编码可以利用简单移位寄存器实现编码，硬件实现容易，因此受到了广泛的关注和研究。文献［4］中基于有限域构造出了两个性能优异的1/2码率的中短码，但是由于使用了掩模矩阵和度分布对技术，校验矩阵的描述变得比较复杂，且结构变得不规则，因而在一定程度上提高了硬件实现的复杂度。文献［5］提出了一种基于有限仿射平面的QC-LDPC码，但该构造方法对码率及码长具有严格的限制且有较大的冗余度。文献［6-7］则利用组合数学中的均衡不完全区组设计构造出了具有准循环结构的LDPC码，但该方法构造的码字的码长仍受限制。基于此，本文利用组合数学中的完备差集，结合另一种代数构造方法循环置换矩阵构造法［8］，提出了一种新颖的方法构造QC-LDPC码，该方法具有所需存储空间少、能够灵活选择码长及码率的优点，且所构造的码字具有良好的纠错性能。

2　完备差集

定义1 设v是一个正整数，对于一个加法群Zv=｛0，1，…，v-1｝，取Zv中的t个子集，每个子集包含k个元素，t个子集表示为Di=｛di1，di2，…，dik｝，di1＜di2＜…＜dik，i=1，2，…，t，Zv中的每个非零元素在差集运算dim-dinmod v的结果中都出现λ次，其中m≠n，且m、n=1，2，…，k，则定义这样的集合Di为一组t-（v，k，λ）循环差集（Cyclic Difference Family，CDF）［9］。

由定义1引出完备差集的定义如下∶

定义2 对于t-（v，k，λ）-CDF，当λ=1且v=k（k-1）t+1时，差集dim-dinmod v的前（v-1）/2个结果称为前项差，剩余的（v-1）/2个结果称为后项差。若t-（v，k，1）-CDF的后项差中的元素恰为Zv的前（v-1）/2个元素构成的子集｛1，2，…，（v-1）/2｝中的取值，称这样循环差集Di为完备差集（Perfect Difference Family，PDF）［8］。Di＇为Di对应的负集，即Di＇中每个元素的值等于v减去Di中对应位置元素的值［10］。其中∶t为循环差集中基块数；v称为完备差集的模；k称为循环差集的大小；λ为Zv中的元素在子集Di中出现的次数。

例1 取t=4，k=4，则v=12×4+1=49，选取加法群Z49中一组4-（49，4，1）-PDF，Di=｛di1，di2，…，dik｝，i=1，2，3，4，Di的具体值如下∶

D1=｛0，5，22，24｝，后项差为5，22，17，24，19；

D2=｛0，7，13，23｝，后项差为7，13，6，23，16；

D3=｛0，3，14，18｝，后项差为3，14，11，18，15；

D4=｛0，1，9，21｝，后项差为1，9，8，21，20，12。

对应的负集为

D1＇=｛0，44，27，25｝，后项差为44，27，32，25，30，47；

D2＇=｛0，42，36，26｝，后项差为42，36，43，26，33，39；

D3＇=｛0，46，35，31｝，后项差为46，35，38，31，34，45；

D4＇=｛0，48，40，28｝，后项差为48，40，41，28，29，37。

由例1可以看出∶Di及Di＇中除0元素外各不相同；Di中元素的后项差为Zv的前（v-1）/2个元素构成的子集｛1，2，…，（v-1）/2｝中的取值；Di＇中元素的后项差为Zv的后（v-1）/2个元素构成的子集｛（v-1）/2+1，…，v-1｝中的取值，满足完备差集的定义。

性质1 对于Zv=｛0，1，…，v-1｝中的一组λ=1的t-（v，k，1）-PDF，Di=｛di1，di2，…，dik｝，i=1，2，…，t，Di中元素各不相同，Zv=｛0，1，…，v-1｝中的元素在所有子集Di中仅出现1次，Di中任意两个元素的模差运算dim-dinmod v结果各不相同。

定理1 （k（k-1）t+1，k，1）-PDF存在满足的条件［11-12］∶

（1）（6t+1，3，1）-PDF存在，当t≡0或1 mod 4时；

（2）（12t+1，4，1）-PDF存在，当t=1，4≤t≤1 000时；

（3）（20t+1，5，1）-PDF存在，当t=6，8，10时；

（4）PDF不存在，当k≥6时。

3　基于完备差集的QC-LDPC码的构造方法

3.1QC-LDPC码的构造

QC-LDPC码是一类高度结构化的特殊的LDPC码，其奇偶校验矩阵H可用单位矩阵的循环移位矩阵和全零矩阵来表示，形式如（1）所示［8］∶

式中∶pij∈｛0，1，2，…，p｝表示单位矩阵向右循环移位的次数；当pij=0时，Q（0）表示一个p×p的全零矩阵；pij≠0时，Q（pij）表示一个p×p的循环移位矩阵。定义H的准循环基矩阵P，P中的元素对应H中单位矩阵循环移位的次数，如式（2）所示∶

当P确定后，对应的校验矩阵也随之确定。

定理2 考虑Di=｛di1，di2，…，dik｝为加法群Zv=｛0，1，…，v-1｝中的一组t-（v，k，1）-PDF。其中∶i=1，2，…，t；di1＜di2＜…＜dik；Di＇为Di对应的负集。定义k×k的循环矩阵Pi和Pi＇的第一行分别为Di和Di＇中的元素，余下每一行都是上一行向左循环移一位得来，I为一个k×k的单位矩阵。2k×2tk的基矩阵P定义为式（3）所示的形式∶

用p×p的循环矩阵和零矩阵分别去置换P中的非零元素和零元素得H矩阵。当p≥2v时，该方法所构造的H对应的Tanner图中无四环。

3.2围长分析

取P中的一个2×2的子矩阵X如式（4）所示∶式中∶dt+s和dt＇+s分别为P中第s行中的第t列及t＇列的元素；同理dt+s＇和dt＇+s＇分别为P中的第s＇行中的第t列及t＇列的元素；1＜s＜s＇＜k；1＜t＜t＇＜k。由于P中的零元素是用全零矩阵去替换，所以当X中有零元素时，不会构成四环。故以下讨论的均为X中不含有0元素的情况。

下面分情况去说明P中无四环存在。

（1）当X中的元素均来自完备差集或其负集时，X的形式如式（4），假设存在四环，则式（5）成立∶

根据PDF的定义，dt+s≠dt＇+s，dt+s≠dt+s＇，dt+s＇≠dt＇+s＇，dt＇+s≠dt＇+s＇，且dt+s-dt+s＇≠dt＇+s-dt＇+s＇。当dt+s-dt+s＇＞0时，若dt+s＇-dt＇+s＇＞0，因为p≥2v，所以dt+sdt+s＇＜v＜p，dt+s＇-dt＇+s＇＜v＜p，因此等式（5）不成立；若dt+s＇-dt＇+s＇＜0，则dt+s=dt＇+s＇，dt+s＇=dt＇+s，式（5）改写为2dt+s=2dt＇+smod p，由于2dt+s≠2dt＇+s，且2dt+s＜p，2dt＇+s＜p，因此等式（5）不成立。

（2）由于0元素不参与构成四环，X中的元素分别来自完备差集或其负集和单位矩阵中的1元素，X的形式如式（6）和式（7）所示∶

对于式（6），假设不存在四环，则式（8）成立∶

由于p≥2v，所以0＜dt+s-1＜v，1-dt＇+s＇modp＞v，因此式（8）不成立。

对于式（7）无四环的证明情况与式（6）相似。

综上所述，该方法所构造的H中不存在四环。

3.3该构造方法的优势分析

由于基矩阵的大小为2k×2tk，则该方法构造的H大小为2kp×2tkp，则码率为R≥（t-1）/t。由此可知∶可根据t的不同取值去灵活选择码率；同时，当k和p取不同值时，码长n=2tkp的取值也不同。表1给出了t和k取不同值时该方法所构造的码长及码率的数值分析。

表1　码长及码率的数值分析Tab.1 The numerical analysis of code-length and rate-code

另外，本文基于完备差集提出的QC-LDPC码的构造方法与大多数构造QC-LDPC码的方法相似，首先利用完备差集的特殊性质灵活构造其基矩阵P，然后再利用零矩阵和循环置换矩阵将基矩阵扩展为其校验矩阵H。而本文构造的基矩阵P是由k×k的循环矩阵和k×k的单位排列构造的，循环矩阵中的每一行元素都是由上一行元素向左循环移一位得来的，且单位矩阵的引入减少了基矩阵中的非零项的存在。因此，该方法构造的QC-LDPC码的储存复杂度仅考虑对基矩阵P中的循环矩阵的首行的元素及单位矩阵中的1元素的存储，然后可利用线性移位寄存器实现编码，相对于一般QCLDPC码而言很大程度上降低了H矩阵所需要的存储空间。相应地，这也一定程度上降低了硬件实现的复杂度。

4　性能分析

由于码的综合性能与码长及码率均有关系，码长越长，纠错性能越好，但引入的时延也越大。因此，为满足实际通信系统实时性对时延的要求及对信息传输的可靠性要求，本文构造的均为中短码长的码字。另外，就码率而言，码率越小，纠错性能越好，但冗余度也越高，比如当码率为1/2时，冗余度高达50%。因此综合考虑纠错性能和冗余度因素，本文构造的两种码字的码率分别为3/4和4/5。

本文采用在加性白噪声高斯（AWGN）信道下、二进制相移键控（BPSK）调制、和积算法（SPA）迭代译码的仿真环境下进行仿真，迭代次数取30次。因为虽随着迭代次数的增加，其纠错性能逐渐变好，但当迭代次数超过30时，其性能提升不大，而迭代次数越多译码时间越长，因而考虑译码时间及译码性能的折衷，本文在对QC-LDPC码进行仿真时选取迭代次数为30。

首先利用例1中4-（49，4，1）-PDF，根据式（3）构造一个8×32的基矩阵P，选取p为98，再利用式（1）构造出码率为3/4的规则QC-LDPC（3136，2352）码，记为PDF-QC-LDPC（3136，2352）码。从图1可看出，当误码率为10-5时，在码率同为3/4的条件下，本文所构造的PDF-QC-LDPC（3136，2352）码与文献［13］GCD-QC-LDPC（3136，2352）码相比具有0.41 dB左右的净编码增益（Net Coding Gain，NCG）改善，比文献［10］的CDF-QC-LDPC（3136，2352）码NCG提高了0.32 dB左右。

图1　码率为3/4的PDF-QC-LDPC（3136，2352）码与其他码的性能比较Fig.1 The comparison of the error correction performances between the PDF-QC-LDPC（3136，2352）code and other codes at the code-rate of 3/4

为了进一步说明本文所构造的码字的性能的优越性，利用5-（61，4，1）-PDF，根据式（3）构造一个8×40的基矩阵P，取p为122，再利用式（1）构造出码率为4/5的PDF-QC-LDPC（4880，3584）码。从图2可看出，当误码率为10-5时，在码率同为4/5的条件下，所构造的PDF-QC-LDPC（4880，3584）码与文献［13］的GCD-QC-LDPC（（4880，3584）码相比具有0.21 dB的NCG的改善，比文献［10］的CDFQC-LDPC（4880，3584）码NCG提高了0.13 dB。

图2　码率为4/5的PDF-QC-LDPC（4880，3584）码与其他码的性能比较Fig.2 The comparison of the error correction performances between the PDF-QC-LDPC（4880，3584）code and other codes at the code-rate of 4/5

5　结束语

本文基于完备差集和循环置换矩阵提出了一种新颖的构造QC-LDPC码的方法。该方法构造的QC-LDPC码除了具有所需存储空间少、易于硬件实现的优势外，还在避免短环的同时，在高信噪比区域具有较快的收敛速度。仿真结果表明∶在对应的同等条件下，本文所构造的PDF-QC-LDPC码的纠错性能优于文献［13］基于最大公约数构造的GCDQC-LDPC码以及文献［10］中基于循环差集构造的CDF-QC-LDPC码；除此之外，通过选取不同的参数，还可以灵活选择所需的码长和码率，为实际通信系统中应用QC-LDPC码提供了一种选择方案。

本文所提出的构造方法中仅无四环的存在，由于环长是影响LDPC码译码性能的重要因素，因此在以后的研究过程中，可在该算法的基础上进一步深入探讨与改进，以期消除六环的存在，进一步提高码字的纠错性能。

［1］ MACKEY D J C，NEAL R M.Near Shannon limit performance of low-density parity-check codes［J］.Electronics Letters，1996，33（6）∶1645-1646.

［2］ JIANG X，XIA X G，LEEM H.Efficient progressive edge -growth algorithm based on chinese remainder theorem［J］.IEEE Transactions on Communications，2014，62（2）∶442-451.

［3］ 郑丹玲，穆攀，田凯，等.利用遗传算法构造QC-LDPC码［J］.电讯技术，2015，55（4）∶355-359.

ZHENG Danlin，MU Pan，TIAN Kai，et al.Construction of QC-LDPC codes with genetic algorithm［J］.Telecommunication Engineering，2015，55（4）∶355-359.（in Chinese）

［4］ LAN L，SHU L.Construction of quasi-cyclic LDPC codes for AWGN and binary erasure channels∶a finite field approach［J］.IEEE Transactions on Communications，2007，53（7）∶2429-2458.

［5］ KAMIYA N.High-rate quasi-cyclic low-density parity-check codes derived from finite affine planes［J］.IEEE Transactions on Information Theory，2007，53（4）∶1444-1459.

［6］ VASIC B，MILENKOVIC O.Combinatorial constructions of low-density parity-check codes for iterative decoding［J］.IEEE Transactions on Information Theory，2004，50（6）∶1156-1176.

［7］ AMMAR B，HONARY B，KOU Y，et al.Construction of low density parity-check codes based on balanced incomplete block designs［J］.IIEEE Transactions on Information Theory，2004，50（6）∶1257-1268.

［8］ 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.

［9］ PARK H，HONG S，NO J S，et al.Construction of highrate regular quasi-cyclic LDPC codes based on cyclic difference families［J］.IEEE Transactions on Communications，2013，61（8）∶3108-3113.

［10］ ESMAEILI M，JAVEDANKHERAD M.4-cycle free LDPC

codes based on difference sets［J］.IEEE Transactions on Communications，2012，60（12）∶3579-3586.

［11］ GE G N，MIAO Y，SUN X W.Perfect difference families，perfect difference matrices，and related combinatorial structures［J］.Journal of Combinatorial Designs，2010，18（6）∶415-449.

［12］ IBRAHEEM S M，ELRAZZAK M M A，ELDINS M S，et al. A class of structured quasi-cyclic LDPC codes based on planar difference families［C］//Proceedings of 2013 International Conference on Advanced Technologies for Communications.Ho Chi Minh City∶IEEE，2013∶614-619.

［13］ ZHANG J H，ZHANG G H.Deterministic girth-eight QC-LDPC codes with large column weight［J］.IEEE Communications Letters，2014，18（4）∶656-659.

袁建国（1968—），男，重庆人，2007年于重庆大学获工学博士学位，现为教授、硕士生导师，主要研究方向为光通信系统、信道编码技术；

YUAN Jianguo was born in Chongqing，in 1968.He received the Ph.D.degree from Chongqing University in 2007.He is now a professor and also the instructor of graduate students.His research concerns optical communication systems and channel coding technologies.

Email∶yyyyjg@126.com

李媛媛（1992—），女，四川人，硕士研究生，主要研究方向为通信系统中FEC编译码技术；

LI Yuanyuan was born in Sichuan Province，in 1992.She is now a graduate student.Her research concerns forward error correction（FEC）encoding/decoding technologies for communication systems.

Email∶liyuanyax@163.com

梁梦琪（1991—），女，重庆人，硕士研究生，主要研究方向为通信系统中FEC编译码技术；

LIANG Mengqi was born in Chongqing，in 1991.She is now a graduate student.Her research concerns FEC encoding/ decoding technologies for communication systems.

Email∶1194685995@qq.com

尚晓娟（1991—），女，安徽人，硕士研究生，主要研究方向为通信系统中FEC编译码技术；

SHANG Xiaojuan was born in Anhui Province，in 1991. She is now a graduate student.Her research concerns FEC encoding/decoding technologies for communication systems.

Email∶1390115692@qq.com

王 永（1977—），男，四川自贡人，教授、硕士导师，主要研究方向为信息安全与FEC编译码技术。

WANG Yong was born in Zigong，Sichuan Province，in 1977.He is now a professor and also the instructor of graduate students.His research concerns information security and FEC encoding/decoding technologies.

Email∶wangyong_cqupt@163.com

Constructing QC-LDPC Codes by Using Perfect Difference Families

YUAN Jianguo，LI Yuanyuan，LIANG Mengqi，SHANG Xiaojuan，WANG Yong
（Key Laboratory of Optical Communication and Networks，Chongqing University of Posts and Telecommunications，Chongqing 400065，China）

∶For the problem of determining shift times of the circulant permutation matirx（CPM）in quasi-cyclic low-density parity-check（QC-LDPC）codes，a novel construction method based on the perfect difference family（PDF）among combinatorial mathematics is proposed.When the dimension of the CPM exceeds a certain particular value，the girth of the Tanner graph of QC-LDPC codes constructed by this method is at least six，and the proposed algorithm has high flexibility with respect to the design of code-length and coderate.In addition，it has less requirement about storage space，so the complexity of the hardware implementation is reduced.The simulation results show that the net coding gain（NCG）of the PDF-QC-LDPC（3136，2352）code with the code-rate of 3/4 is respectively improved 1.15 dB and 0.58 dB than those of the GCD -QC-LDPC（3136，2352）code based on the greatest common divisor（GCD）and the CDF-QC-LDPC（3136，2352）code based on the cyclic difference family（CDF）at the bit error rate（BER）of 10-5.In addition，the NCG of the proposed PDF-QC-LDPC（4880，3584）code is improved 0.21 dB and 0.13 dB than those of the GCD-QC-LDPC（4880，3584）code and the CDF-QC-LDPC（4880，3584）code with the same conditions correspondingly with the code-rate of 4/5 and the BER of 10-5.

∶quasi-cyclic low-density parity-check code；circulant permutation matirx；perfect difference family；net coding gain

The National Natural Science Foundation of China（61472464）；Chongqing Research Program of Basic Research and Frontier Technology（cstc2015jcyjA0554）

TN911.22

A

1001-893X（2016）05-0471-05

10.3969/j.issn.1001-893x.2016.05.001

袁建国，李媛媛，梁梦琪，等.利用完备差集构造QC-LDPC码［J］.电讯技术，2016，56（5）∶471-475.［YUAN Jianguo，LI Yuanyuan，LIANG Mengqi，et al.Constructing QC-LDPC codes by using perfect difference families［J］.Telecommunication Engineering，2016，56（5）∶471-475.］

2015-12-25；

2016-04-12Received date：2015-12-25；Revised date：2016-04-12

国家自然科学基金资助项目（61472464）；重庆市基础与前沿研究计划项目（cstc2015jcyjA0554）

**通信作者：yyyyjg@126.comCorresponding author：yyyyjg@126.com