基于IEEE 802.16e标准的与CRC结合的LDPC编译码算法研究

王熙，陈雨

（四川大学电子信息学院，成都 610065）

0 引言

LDPC（Low Density Parity Check Code），即低密度校验码，是由Robert G.Gallager于1962年在他的博士论文中提出[1]。早先由于硬件计算能力和运算速度有限等原因，LDPC码沉寂了几十年，但是在1997年左右，D.MacKay、M.Sipser、Felstrom、Zigangirov 等相继对LDPC码重新进行研究，发现LDPC码十分逼近香农极限。随后LDPC码开始广泛应用于DVB-S2、光纤通信、深空通信等多种通信领域，在2016年的3GPP会议中，高通公司以LDPC码成为了5G通信数据传输长码和短码的编码标准。

LDPC码所具有的优势和性能，使其广泛应用于通信领域的各个方向，例如802.16无线城域网，广泛应用于高速、可移动的语音、视频等业务。为了降低LDPC编码的复杂度，IEEE 802.16e标准中提出了一种快速编码方法，本文的研究主要内容是结合CRC的LDPC编译码方法，这种方法进一步提高了LDPC编译码的准确度和可靠性。

1 LDPC编码算法

传统的LDPC码的编码算法是高斯消元法，主要算法流程是先利用校验矩阵H得到生成矩阵G，再将信息源码与G相乘得到与之对应的码字。这种方法的缺点是需要做的高斯消元法的次数过多、运算量和存储量过大，而且按照计算方式可能会得到不止一个G，这样的结果并不适合应用于硬件实现。

Efficient编码算法[2]主要是利用校验矩阵H的近三角形矩阵，可以将校验矩阵H表示为分块矩阵的形式，H是m×n维矩阵，m表示校验位的位数，n表示码长的位数。

其中 A 是（m-g）×（n-m）矩阵，B 是（m-g）×g矩阵，T 是（m-g）×（m-g）下三角形矩阵，C 是 g×（n-m）矩阵，D 是 g×g矩阵，E 是 g×（m-g）矩阵。

在校验矩阵H上左乘满秩矩F得到H：

假设编码后的码字C=（S,P1,P2）,其中S为信息位，P1和P2是校验位。由于码字Code满 CT=0T，因此可以得到公式（4-5）。

令φ=-ET-1B+D，有P1T和P2T的表达式：

这样，通过矩阵j和信息位S计算出校验位P1和P2,从而得到整个码字C。这种编码算法可以达到线性编码的时间性要求，复杂度得以降低。

IEEE 802.16e中定义的LDPC码的H完全由循环移位单位阵和零矩阵构成，属于准循环码，于是可以利用校验矩阵的稀疏性来完成编码。在IEEE 802.16e标准中已经给出了LDPC码的基校验矩阵Hb。

对于各种码长和码率的检验矩阵H都可以通过基校验矩阵Hb按照扩展因子为zf=n/24（其中n为码长）的方式扩展得到。其扩展规则为：

（1）Hb中 Pi,j=-1 的位置扩展为 zf×zf的零矩阵；

（2）Hb中 Pi,j=0 的位置扩展为 zf×zf的单位矩阵；

（3）Hb中除了-1 和 0 以外的值，扩展为 zf×zf的单位矩阵经过p（f,i,j）次循环右移获得的矩阵，其中p（f,i,j）由式（9）确定。

当码率为1/2，码率为3/4的A、B码，码率为2/3的 B 码和码率为5/6的码式p（f,i,j）由式（9）确定,其中z0=2304/24=96。

码率为 2/3的 A 码，p（f,i,j）由式（10）确定。

Hb经过扩展之后得到的校验矩阵H。H可以写成式（11）：

其中0表示0矩阵，-1表示单位矩阵，1表示循环位移1的单位矩阵，矩阵均为zf×zf维。

假设编码后的码字C=（S,P）,S为信息序列，将S分为k组，其中k=n-m,每组的比特数为zf。则C可以表示成式（12）。

由式（13）可以得到式（14）。

得到p0后可以依次迭代得到pi（i属于0到m-1）,进而得到码字C。

2 CRC

CRC（全称为循环冗余校验码），它的编码方式简单并且误判概率低。CRC能够以百分之百的概率检测出突发错误长度小于等于R（R为CRC的生成多项式g（x）阶数）和错误数为奇数的随机错误。CRC校验的基本原理：假设信息长度是K位，添加R位的校验码后，则得到N=K+R位信息总长度，此时将发送信息用多项式C(x)表示，将C(x)左移R位，左移R位的位置即校验码的位置，用信息多项式除以生成多项式得到的余数即校验码。在本文中采用CRC12先对数据信息进行编码，然后使用IEEE 802.16e的快速编码算法进行LDPC编码，其中CRC12的生成多项式为式（15）。

3 LDPC译码算法

LDPC码译码算法一般采用基于Tanner图的置信传播（Belief Propagation,BP），对数域置信传播算法将概率消息用似然比（LLR-BP）表示，大量的乘法运算可以变为加法运算减少运算时间。在二进制调制下和置信传播是等效的。

LLR-BP算法的算法流程如下：

图1 算法流程

①初始化节点。计算信道传递给变量节点的初始概率似然比消息L(Pi)，i=1,2,…,n。然后对每一个变量节点i和与其相邻的校验节点 j∈C(i)，设定变量节点传向校验节点的初始消息。

②将信息从比特节点传到校验节点（校验节点消息处理）。对所有的校验节点j和与其相邻的变量节点i∈R(j)，第l次迭代时，计算变量节点传向校验节点的消息。

③将信息从校验节点传回比特节点（变量节点消息处理）。对所有的消息节点i和与其相邻的校验节点j∈C()i，第l次迭代时，计算校验节点传向变量节点的消息。

④对所有变量节点计算硬判决消息

⑤译码判决

若L(l)(qi)>0 ，则 ĉ(i)=0 ，否则 ĉ(i)=1。

⑥停止条件

如果 ĉHT=0（其中 ĉ是 n维的行向量）或者 l=max_iter（最大迭代次数）就终止，否则继续返回到过程B迭代。

在结合CRC的LDPC的译码过程中，首先对信道接收到的信息进行LLR-BP译码，然后在译码结束的时候对在编码前加入的检验位进行CRC校验，如果校验正确或满足停止条件，就继续执行下面的译码，若检验过程中发现有错误，就将错误的码字收集起来，并停止迭代，以减少不必要的迭代，然后将错误码字的似然值进行翻转并重新进行译码。

4 仿真结果

为了验证算法的有效性，在MATLAB中采用码率为0.5，码长为1024的IEEE 802.16e标准的LDPC码结合上CRC，经过AWGN信道，在不同译码方法下运行，可以得到图2所示的性能对比图。从图2可以看出，CRC-LLRBP比起LLP-BP和BP算法，在相同的误码率情况下，它具有更高的信噪比，或者说在相同的信噪比情况下，CRC-LLRBP降低了LDPC码的错误平层，获得了更低的误码率。

图2 不同算法下的性能对比图

5 结语

本文给出的结合CRC的LDPC的编译码方法，在编码中使用CRC结合LDPC快速编码算法，在译码过程中使用LLR-BP结合CRC后处理算法，这种算法能够快速地定位错误的码字并翻转其似然值进行再次译码，这样可以明显减少无法译码的信息位，降低其错误平层。