QC-LDPC码最小环路检测算法

薛宇丛，周 华，铁 鑫

(南京信息工程大学 电子与信息工程学院，江苏 南京 210044)

0 引 言

自从信道编码理论被提出以来，人们就在寻找一种在性能上能够无限接近香农极限的编码。早期的BCH码、Turbo码尽管具有结构规整、复杂度较低等优点，但是满足不了在高信噪比时低误码率的要求，LDPC码的出现则使信道编码的发展有了新的突破。LDPC(low-density parity-check)码由Gallager提出[1]，它因性能逼近香农极限而成为近年来的研究热点，并且被应用到DVB2、4G、5G等标准中。

LDPC码性能的优越性源于其校验矩阵的结构，校验矩阵常用Tanner图表示。Tanner图是一种双向图，当LDPC码校验矩阵对应的双向图存在环路时，从某一节点发出的信息经过环路的传递，会回到自身，破坏了置信传播中边信息的独立性[2]。所以在LDPC码的构造上，应该尽量减小环路对于译码性能的影响，避免短环结构出现[3]。对于码长较小的LDPC码，长度为4的最小环路可以由校验矩阵直观地观察到，对于环路长度大于4的环，就需要用相关的算法检测。本文提出了一种计算QC-LDPC码最小环路围长的方法，基于这种方法，构造最小环路为4、6、8的QC-LDPC码的校验矩阵，并通过仿真比较在相同信噪比情况下，最小围长不同的QC-LDPC码的误码率和误帧率。

1 LDPC码

二进制LDPC码是一种线性分组码，并由稀疏奇偶校验矩阵定义。稀疏指奇偶校验矩阵中“1”的数量相对“0”较少。若各行(列)中包含的“1”的个数相同，则称为规则LDPC码，否则称为非规则LDPC码[4]。如式(1)所示，以规则LDPC码为例给出了对应的校验矩阵H，其中行重为3，列重为2

(1)

LDPC码的常用表示方法，除了矩阵形式，还有Tanner图形式。Tanner图是一种双向图，且与校验矩阵相对应[5]，图1表示式(1)所给的校验矩阵H对应的Tanner图。校验矩阵中的行对应Tanner图中的校验节点(check node)，记为Ci，用方形来表示；列对应Tanner图中的变量节点(bit node)，记为Vj，用圆形来表示。Tanner图中的连接特性由校验矩阵表示，若某行某列的位置上是“1”，则表示对应的校验节点与变量节点之间存在一条边相连[6]。由变量节点、边和校验节点首尾相连组成的闭合回路称为环路。构成环路的边的总数称为围长(最小围长称为girth)，且围长是一个大于等于4的偶数。

图1 校验矩阵H的Tanner图表示

图1中C1→V1→C3→V5→C2→V2→C1就构成了完整的环路，其中路径长度为6。

2 基于循环置换矩阵的QC-LDPC码

LDPC码可以分为两大类：随机LDPC码和QC-LDPC码[7]。在随机LDPC码的校验矩阵中，“1”的分布没有规律，存储时需记录生成矩阵和校验矩阵的所有行向量，在实现上比较困难[8]。准循环低密度奇偶校验(quasi-cyclic low-density parity-check，QC-LDPC)码是一种高度结构化的LDPC码，可以由指数矩阵和扩展维数来表示得到的码字结构，其自身的准循环特性使编码和解码的过程更加高效。由单位矩阵经过循环移位后的循环置换矩阵组成QC-LDPC码的校验矩阵H，矩阵H形式为

(2)

其中，I(pn,l)表示将一个大小为M×M的单位矩阵向左循环移pn,l位，1≤n≤N，1≤l≤L。每个循环置换矩阵都由其维数M和循环移位次数pn,l唯一确定，因此QC-LDPC码的H矩阵比较容易在硬件中实现，且方便寻址储存。

3 QC-LDPC码最小环路检测算法

本文以式(1)中的矩阵H为例，提出一种检测QC-LDPC码中最小环路围长的方法。本算法借鉴了比特翻转(bit-flipping，BF)译码算法的思想。比特翻转译码算法是用于LDPC码的硬判决消息传递算法，首先对输入译码器的向量数据做硬判决，将所得的二进制序列带入全部校验方程。如果校验节点所有比特值的模2和为零，则校验方程成立。如校验方程不成立，则找出使其不成立数目最多的变量节点，把此变量节点所对应的比特位进行翻转，此原理请参见文献[9]。整个BF译码过程需要不断迭代，直至所有奇偶校验方程均成立，或者达到最大迭代次数自动跳出。BF译码算法只进行比特翻转、模2加等简单的运算，没有复杂的算法，而且一旦所有奇偶校验方程满足就终止解码器，可以避免额外的迭代。本算法同样将二进制序列在变量节点和校验节点之间迭代交换。不同的是，本算法的硬判决不依靠比特翻转和模2加运算，只进行简单的加法运算。下面以式(1)矩阵H为例，检测最小环路的长度，步骤如下：

(1)参数设定：k=1，初始化长度为e的输入序列E=[Ek]1×e为全零序列。

(2)设置序列E的第k位为1，即Ek=1，其余位为0。

(3)变量节点Vb将Ek发送到每个与其连接的校验节点，该消息标记为qji，表示从变量节点Vj到校验节点Ci的消息。用Ui表示校验节点Ci接收到的信息之和，即

(3)

式(1)矩阵H中，变量节点V1与校验节点C1、C3相连，E1从V1被传递到C1、C3，序列E中的零元素也沿对应的连线传递，得到U1=1,U2=0,U3=1,U4=0。此步骤对应图2(a)。

(4)校验节点将消息发送回与之连接的变量节点。该消息标记为rij，表示从校验节点Ci到变量节点Vj的消息。用Dj表示变量节点Vj接收到的信息之和，即

(4)

其中

(5)

Nj：与变量节点Vj相连的校验节点的下标集合。

Nj/i：除校验节点Ci之外，与变量节点Vj相连的校验节点的下标集合。

由步骤(3)可知，式(1)矩阵H中有U1=1,U2=0,U3=1,U4=0。变量节点V1此刻的信息为之前变量节点V2，V4传递到校验节点C1的信息之和，即D1=0。最初传递的E1=1并没有返回变量节点V1，也就是没有形成完整环路，需要继续进行迭代。此步骤对应图2(b)。

(5)变量节点将不同的消息发送回每个连接的校验节点，定义以下变量：

Ni：与校验节点Ci相连的变量节点的下标集合。

Ni/j：除变量节点Vj之外，与校验节点Ci相连的变量节点的下标集合。

定义校验节点Cj接收到的信息值qji为其它校验节点传递到与之相连的变量节点的信息之和，即

(6)

以校验节点C1为例，校验节点C1接收到的信息来自变量节点V1、V2和V4，根据式(3)和式(6)可知，此时C1的信息值U1=0。此步骤对应图2(c)。

(6)校验节点将不同的消息发送回每个与之连接的变量节点。变量节点V1接收到的信息来自校验节点C1、C3，根据式(6)可知，V1此时的信息值D1=0，最初传递的E1=1没有返回变量节点V1，需要继续迭代。此步骤对应图2(d)。

(7)步骤(5)和步骤(6)完成一个迭代过程。重复步骤(5)和步骤(6)，直到最初传递的E1=1回到变量节点V1，即D1=1时，迭代结束(如图2(e)、图2(f)所示)，环路长度等于2倍的迭代次数。

(8)依次设置全零序列E的第k位为1(k=2,3,…,e)，其余位为0，重复步骤(2)至步骤(7)，并根据Ek的取值更新Ui、Dj取值，得到各序列在上述迭代算法中的环路长度。最终在各环路长度中取最小值，则得到LDPC码校验矩阵H所对应的Tanner图中的最小环路围长。

图2 当k=1时，本算法对式(1)中H的环路检测步骤

为了便于理解，下面给出算法流程如图3所示。设置循环次数为k，存放数据的集合为g。初始化令k=1，g=∅。

图3 最小环路检测算法流程

4 性能仿真及分析

校验矩阵中的环路是影响LDPC码性能的重要因素之一，本文的算法已经可以准确的检测出校验矩阵中的最小环路围长。为了验证算法的正确性和合理性，以表明矩阵最小环路围长对误码性能的影响，基于最小环路检测算法，构造一组QC-LDPC码，并进行仿真。

定义单位矩阵I(pn,l)的大小M=64。按照式(2)构造由I(pn,l)构成的3行5列的矩阵H，即矩阵H由15个经过循环移位的单位矩阵I(pn,l)组成。利用上述的最小环路围长检测算法，在MATLAB R2014a软件中输入矩阵H并随机改变各移位次数pn,l的值，其中0

(7)

(8)

(9)

译码方式选择传统BP译码算法，BP算法的主要思路是将接收到的信息在校验节点与变量节点之间迭代[10]。设置最大迭代次数为100，信噪比Eb/No为1.5 dB，2.0 dB，2.5 dB，3.0 dB，3.5 dB。

不同信噪比下，矩阵H1，H2，H3误码率(BER)及误帧率(FER)性能曲线如图4所示，其中实线表示BER，虚线表示FER。矩阵H1的数值点用圆形表示，矩阵H2的数值点用星形表示，矩阵H3的数值点用方形表示。

图4 不同信噪比下矩阵H1，H2，H3的BER及FER性能曲线

由图4中可以看出，对于行列数相同的校验矩阵H1、H2、H3，在信噪比较低的情况下，3个矩阵的误码率曲线接近，误帧率曲线也接近。但是随着信噪比的增加，在相同信噪比下，最小环路数越大，对应的误码率和误帧率就越小，即误码性能更优越。如图4所示，误码率BER=5×10-4时，矩阵H3的信噪比值比矩阵H2的信噪比值小0.06 dB，矩阵H2的信噪比值比矩阵H1的信噪比值小0.2 dB。误帧率FER=5×10-3时，矩阵H3的信噪比值比矩阵H2的信噪比值小0.06 dB，矩阵H2的信噪比值比矩阵H1的信噪比值小0.25 dB。

为验证算法的适用性，构造4行8列的矩阵H，矩阵H由32个经过左循环移位的单位矩阵I(pn,l)组成，其中单位矩阵的大小为64×64。基于环路检测算法得到一组大小相同、最小环路长度不同的校验矩阵H4、H5、H6， 且H4，H5，H6的最小环路围长依次为4、6、8，构造方法同校验矩阵H1、H2、H3

(10)

(11)

(12)

设置最大迭代次数为100，信噪比Eb/No为1.5 dB，2.0 dB，2.5 dB，3.0 dB，3.5 dB，3.75 dB。不同信噪比下，矩阵H4，H5，H6误码率(BER)及误帧率(FER)性能曲线如图5所示，其中实线表示BER，虚线表示FER。矩阵H4的数值点用圆形表示，矩阵H5的数值点用星形表示，矩阵H6的数值点用方形表示。

图5 不同信噪比下矩阵H4，H5，H6的BER及FER性能曲线

类似于H1，H2，H3，两组仿真的结果均验证了在相同信噪比下，增加最小环路围长能够改进QC-LDPC码的误码率和误帧率。

对比图4及图5可以发现，在相同信噪比下，对于最小环路围长相同的校验矩阵，随着矩阵的增大，误码率和误帧率的值变大，即译码性能降低。以最小围长均为4的校验矩阵H1和H4为例，当信噪比为2.0 dB时，矩阵H4的误码率约为矩阵H1误码率的5倍，矩阵H4的误帧率约为矩阵H1误帧率的5倍，这会影响QC-LDPC码在实际中的应用。如何在减少短环和扩大校验矩阵结构的同时，提高译码性能，还需要进一步研究。

5 结束语

本文在比特翻转译码算法的基础上，提出了一种QC-LDPC码最小环路围长的检测算法，该算法将输入的二进制序列在变量节点和校验节点之间迭代交换，把得到的输出序列做硬判决，计算特定的标识信息回传至起始节点的迭代数，环路长度为2倍的迭代次数，最小环路围长即各节点所在环路围长集合的最小值。利用上述算法构造最小环路围长递增的QC-LDPC码组，借助MATLAB R2014a软件对码组进行性能仿真，验证了最小环路围长对于QC-LDPC码译码性能的影响：增大最小环路围长，有利于降低译码的误码率和误帧率。