基于改进PEG算法的多元LDPC码设计

沙岩　王辉　李娜娜　朱婷婷

【摘 要】如何构造高性能的LDPC码是LDPC研究领域的关键技术。本文利用改进的PEG算法构造出多元LDPC码，使其既能保持码字的性能，又能降低编码复杂度。实验结果表明PEG编码的LDPC码的性能明显优于随机编码的码字，并且改进的PEG算法能大大降低编码复杂度，使其更加实用。

【关键词】低密度奇偶校验；信道编码；PEG算法

中图分类号： TN911.2 文献标识码： A 文章编号： 2095-2457（2018）12-0041-003

DOI：10.19694/j.cnki.issn2095-2457.2018.12.018

Multivariate LDPC code design based on improved PEG algorithm

SHA Yan WANG Hui LI Na-na ZHU Ting-ting

（School of Medical Informatics，Xuzhou Medical University，Xuzhou 221004，China）

【Abstract】How to construct high - performance LDPC code is a key technology in LDPC research field. In this paper， the improved PEG algorithm is used to construct the multivariate LDPC code， which can not only maintain the performance of code word， but also reduce the coding complexity. The experimental results show that the performance of the LDPC code of PEG encoding is better than that of random code words， and the improved PEG algorithm can greatly reduce the coding complexity and make it more practical.

【Key words】Low-density parity-check； Channel Coding； PEG algorithm

0 引言

低密度奇偶校验码是（LDPC）近年发展起来的一种纠错码[1]，随着理论研究越来越成熟，它被日益广泛的应用于各种通信系统中[2-3]，尤其是在大数据容量通信应用非常广泛[4]。LDPC的构造方法种类多样，LDPC码的一个子集对应一种方法，这些子集在硬件复杂度和译码性能上各有优势，所以可根據实际需求选择不同的子集[5]。LDPC码的诸多优点使它在数字视频广播、下一代移动通信、深空通信等多个领域的越来越多的应用， 比如我国的数字电视地面广播传输系统（CDTV-T）[6]。

PEG算法是目前构造低码率下中短码长LDPC码的最好构造方法之一[7]。LDPC码一种常用的表示方法是二分图，也称为Tanner图。该算法通过依次在已有Tanner图上添加边来构造最终的Tanner图，每次添加边时都尽可能减少对已有Tanner图的围长的影响。它不但适用于正则LDPC码的构造，也适用于非正则LDPC码的构造[7]。

在校验矩阵构造方面，基于PEG算法的构造方法能使环长最大化，进而有效降低误码平层，并且相应的校验矩阵H很稳定，不必像随机编码中，要通过计算机搜寻最佳的H[8]。

本文利用改进的PRG算法构造出的LDPC码的性能优异，明显优于随机编码的码字，并且相应的校验矩阵H很稳定，不必像随机编码中，要通过计算机搜寻最佳的校验矩阵H。

1 LDPC码的传统编码算法

LDPC码是一种特殊的线性分组码，所以它也适用于通用码字生成方法[9]。码字x可以通过信息位s与生成矩阵G相乘得到，具体如公式（1）所示：

x=s·G（1）

如果给出校验矩阵H，生成矩阵G可以利用H和G之间的正交性通过高斯消元来得到。生成矩阵G的形式为G=[I，P]。H=[p1，p2]，可以得到公式（2）：

P=P-12·P1（2）

可以验证HGT=0，由于在生成矩阵G中存在单位矩阵I，因此通过公式（1）生成的码字是系统码的形式，即码字中所有校验位紧接在所有信息位之后，校验位与信息位是分开的。假如x=[s，c]，其中c为校验位信息，那么根据公式（1）和公式（2）可以得到公式（3）：

c=s·P-12·P1（3）

这种编码方式具体有以下步骤：

（1）利用高斯消元法求出P2的逆矩阵，然后计算P=P-12P1，其中H=[P1，P2]，P1为m×（n-m）阶矩阵，P2为m×m阶的矩阵；

（2）将码字x分成信息位s和校验位c，根据c=s·P-12·P1计算出校验位信息；

（3）将算出的校验位放在信息位后面，生成码字x。

然而这种算法存在缺陷。当用高斯消元求逆再算出生成矩阵G时，G就不再是稀疏矩阵了。当码长较长时，存储生成矩阵G需要消耗很大的资源；同时，进行编码运算时需要巨大的运算量和存储量来计算校验位，编码吞吐量很很大程度的降低。

2 利用PEG改进算法构造LDPC码

LDPC码的最大的缺点就是其编码复杂度比较高，针对这个问题，许多学者都进行了研究。如Richardson和Urbanke提出了一种基于近似下三角矩阵的有效编码方法[10]。

PEG算法可以构造出LDPC码，但是PEG算法的编码复杂度与码长成正比，本文对PEG算法进行改进，使得构造出的LDPC码既保持码字的性能，又能降低编码复杂度。

为便于描述，LDPC码的校验矩阵为H={hij}（0≤i

若已知边的度分布函数λ（x）=∑iλixi-1和ρ（x）=∑i ρi xi-1，则可求出变量节点的度分布函数 （x）=∑ xi、校验节点的度分布函数 （x）=∑ xi，并按照该分布随机给各个变量节点和校验节点分配度数，变量节点记为Ds={d ，d ，…d }、校验节点记为Dc={d ，d ，…d }，其中d （d ）表示变量节点sj（校验节点ci）的度数，通常集合Ds和Dc按照升序排列，即有d ≤d ≤…≤d ，和d ≤d ≤…≤d ；同时，将边的集合根据变量节点集Vs表示为E=E ∪E ∪…E ，其中E ={E ，0≤k≤d -1}表示所有与变量节点sj相连的边构成的集合，E 为与变量节点sj相连的第k条边。定义N 为当前Tanner图中所有与变量节点sj之间的最短路径长度（所经过的边的个数）不超过2l+1的校验节点构成的集合，并用N =Vc＼N 表示校验节点集中除去N 后剩下的集合。

改进的PEG算法可以总结如下：

（1）添加边E →（ci，sj），其中ci为当前Tanner图中度数最小的校验节点

（2）添加E →（ci，sj），其中k

（3）若 l∈N，使得N ≠φ，且N =φ，ci则为集合N 中度数最少的校验节点。

改进的PEG算法举例如下：

令校验矩阵H为（6，3）线性分组码，则校验位长m=6-3=3。设变量节点度分布为[1，2，1，1，2，2]。

（1）首先对变量节点s1连线，连至校验节点c1，见图1。

（2）对s2连线，s2度数为2，第一条边首先连在前面图中度数最小的校验节点，即c1，第二条边在连在其余校验节点随机选择c2，见图2

（3）对s3连线，在第二步中c2度数最小，所以s3第1个校验节点选择c2，见图3。

（4）对s4连线，度数最小的是c1、c2，所以第一个校验节点选择c2，见图4。

（5）对s5连线，度数最小的校验节点是c1，s5所以首先连至c1，第二节点连至c3，见图5。

（6）对s6连线，校验节点度数最小的是c3，所以首先连至c3，再以s6为根节点展开，s6另一条边连至c2构成一个环，见图6。

3 仿真与结果分析

如果定义中的域不限于二元域就可以得到多元域GF（q）上的LDPC码，q为码元数。多进制LDPC码的二部图类似于二进制LDP码，只是变量节点有q种取值，并且，校验节点的约束更复杂。令q=2p，这样我们可以用p位二进制比特来传输一个q进制符号。当H是一个大的稀疏矩阵时，我们通过高斯消去得到生成矩阵G进而产生码字。

由图7可知：码长为200、码率为1/2的4元基于PEG改进算法构造的LDPC在误符号率为10-3时比随机码长为200性能好0.6dB左右。码长为400、码率为1/2的4元基于PEG改进算法构造的LDPC在误符号率为10-3时比随机码长为400性能好0.1dB左右。可见基于PEG改进算法构造的4元LDPC码性能于远优于没有采用纠错编码而直接传输的方法。性能优势会随着码长的增长而削弱。

4 结语

本文利用PEG改进算法构造了LDPC码。实验结果表明改进的PEG算法构造的多元LDPC码具有优秀的性能。下一步的研究方向是进一步改进PEG算法，降低编码复杂度。

【参考文献】

[1]Kaufman T， Wigderson A. Symmetric LDPC codes and local testing[J]. Combinatorica， 2016， 36（1）：91-120.

[2]Lyu Y， Hong S， Wang L， et al. Reliability Oriented Decoding Strategy for LDPC Codes Based D-JSCC System[J]. IEEE Communications Letters， 2017， PP（99）：1-1.

[3]Zhang S， Yang F， Tang L， et al. Joint design of QC-LDPC codes for coded cooperation system with joint iterative decoding[J].International Journal of Electronics， 2016， 103（3）：384-405.

[4]Chen C，Wang L，Liu S.The Design of Protograph LDPC Codes as Source Codes in a JSCC System[J].IEEE Communications Letters，2018，PP（99）：1-1.

[5]黄胜，庞晓磊，贾雪婷，等.基于卢卡斯数列的大围长QC-LDPC码构造方法[J].电子科技大学学报， 2016，45（2）：174-178.

[6]童龙文， 黄少俊. 基于地面数字电视的信息推送系统[J]. 电视技术， 2017， 41（7）：15-18.

[7]He X， Zhou L，Du J.A New Multi-Edge Metric-Constrained PEG Algorithm for Designing Binary LDPC Code with Improved Cycle-Structure[J].IEEE Transactions on Communications， 2017， PP（99）：1-1.

[8]Frost J，Dhanda A，Ratcliffe J，et al.PTU-098 Improving PEG Completion Rates：Adoption of an Algorithm to Maximise Success：An 18 Month Single-Centre Review[J].Gut，2016，65（Suppl 1）：A103.1-A103.

[9]陶雄飞， 王跃东， 柳盼. 基于变量节点更新的LDPC码加权比特翻转译码算法[J]. 电子与信息学报， 2016， 38（3）：688-693.

[10]Richardson T J， Shokrollahi M A， Urbanke R L. Design of capacity-approaching irregular low-density parity-check codes[J].IEEE Transactions on Information Theory， 2002， 47（2）：619-637.