一类准循环LDPC码的快速编码方法

1 引言

低密度奇偶校验(Low Densitv Paritv Check，LDPC)码已成为当今信道编码领域的研究热点之一。LDPC码属于线性分组码，根据其构造方法和相应的编码算法，主要分为两类：一类是随机构造的LDPC码，该类码在长码时具有很好的纠错能力，然而由于码组过长，以及生成矩阵与校验矩阵的不规则性，使编码过于复杂而难以用硬件实现，编码时间过长也不利于硬件的实时应用；另一类是结构码，它由几何、代数和组合设计等方法构造。大多数LDPC结构码是循环或准循环结构，准循环码在中短码时具有相当强的纠错能力，性能接近随机构造的LDPC码，又因其硬件实现极其简单，只需用反馈移位寄存器连接就可实现，因此具有很好的应用前景。

在LDPC码的理论和应用研究越来越受到人们关注的同时，探讨LDPC码在DSP，VLSI(超大规模集成电路)和FPGA(现场可编程门阵列)等上的实现也成为一个重要研究方向。笔者在科研项目的工作中，发现一种针对准循环LDPC码的快速编码实现方法，对于码长为15 360的LDPC码，基于Altera公司的EP2S60型FPGA芯片实现时可达到25 Mbit／s以上的编码速度。

2 LDPC码的通用编码方法

作为信道编码中纠错能力强的码型之一，LDPC码由于其译码器结构实现简单，可以用较少的资源消耗获得很高的吞吐量，但编码器的复杂度问题作为不利因素制约着LDPC码的应用。传统的编码方法是通过生成矩阵生成码字，其复杂度和码长的平方成正比，这使得LDPC码在编码上需要大量的硬件资源和很长的延时。Richardson在文献[4]中引入了一种新颖的算法在很大程度上解决了该问题，之后，Dong-U Lee等人利用这种新算法设计了相应的编码方法，这种编码方法适用于大多数的LDPC码；而对于基于有限几何或其他置换方法等构造出的具有循环或准循环特性的LDPC码，由于其特殊的构造，可简单地用移位寄存器来实现编码，编码算法复杂度进一步降低。

2.1 传统算法

LDPC码的传统编码算法和一般的线性分组码十分类似，需要求出生成矩阵。若已知长度为k的输入信息向量M，以及k×n的生成矩阵G，码字C就可以得到：C=M×G。在获得校验矩阵H后，利用H和G之间的正交性可以用高斯消元法来得到生成矩阵G。假设稀疏矩阵H有如下形式：H=[H1 H2]，其中H2是一个(n-k)×(n-k)的稀疏方阵，并且在二元域上是非奇异阵，那么G就可用式(1)给出

很容易验证：这样的G满足HGT=0，其中，Ik是一个k阶的单位矩阵，这样得到的码字具有系统码的形式。

该编码算法可简单概括为：若LDPC编码器将长度为k的信息比特m=(m0，m1，…，mk-1)编码为一个长度为n的LDPC码字C=(m，p)=(m0，m1，…，mk-1，p0，p1，…，pn-k-1)，其中p为校验位，设LDPC码的奇偶校验矩阵为H=[H1，H2]，其中，H1子矩阵包括H矩阵中的前k列，H2子矩阵包括H矩阵中的后n-k列，则由式(1)及C=mxG可得校验位

已知校验矩阵H求解生成矩阵G的主要算法是二元域上的高斯消元法，一般而言，这样得到生成矩阵G不是稀疏矩阵，因此在编码时所用到的矩阵乘法的运算量阶数是O(N2)。

2.2 基于RU算法的编码方法

Richardson和Urbanke指出通过对LDPC的校验矩阵进行一定规则的线性操作即预编码的算法(RU算法)，可以使LDPC编码器的复杂度控制在与码长成线性关系。设码字矢量x=(s，p1，p2)，其中s为信息位，p1与p2合起来表示校验位，利用校验方程Hx′=0来计算p1和p2。RU算法主要包括预处理和实际编码两个步骤。预编码通过行列变换把校验矩阵H转化为近似的下三角阵形式H′,预编码只需执行，可以在软件中预先处理。然后把H′分成6个稀疏矩阵，通过分步计算求得p1和p2，其中p1复杂度为O(N+g2)，p2的计算复杂度为O(N)。图1为H经预编码后的近似下三角阵形式H′。

但如何得到这个近似下三角矩阵仍没有令人满意的方法，T.J.Rrichdson等人通过贪心算法重排校验矩阵过于复杂，且这样的预处理需要很长时间。尤其当码长较长时，这种编码方法不是一种理想的实现方式。

2.3 准循环LDPC码及其编码方法

准循环LDPC码是一类构造比较特殊且应用范围越来越广的LDPC码，其校验矩阵Hqc由一系列的m×m小循环方阵组成，这些小循环方阵可以是置换矩阵或是基于有限几何的矩阵等。由于Hqc的准循环特性，可以得到具有系统码形式和准循环特性的生成矩阵，即通过式(1)所得到的生成矩阵具有准循环特性，则只需要采用移位寄存器即可实现输入信息和生成矩阵的编码运算。针对一些特殊的准循环LDPC码，D.E，Hocevar等人还提出一种仅利用校验矩阵即可用移位寄存器进行快速编码的方法，其结构如图2所示。B中存储着用来和信息比特相乘的循环移位值，循环移位单元在每个时钟周期循环右移或者左移。从实现的低复杂度考虑，它优于基于RU算法的LDPC编码方案，但它只适用于具有准循环特性的LDPC码。

3 准循环LDPC码的快速编码方法

对准循环LDPC的编码实现可分为如下3个步骤：

1) 计算中间变量DT=H1mT，根据H1矩阵具有准循环特性，使用循环移位寄存器实现，并对DT加以缓存。

2) 计算校验位，这一步是整个编码算法中复杂度也是耗费资源的部分。

3) 获得编码后的码字C=(m，p)。

常用的编码算法因通过高斯消去法获得的H2-1既不是稀疏矩阵，又不具备明显的准循环特性，因此造成第二步运算过程中运算复杂度较高，降低了运算速度，影响了整体编码速度和效率。此时，本文针对H2列重小于4的准循环LDPC码(通常H2矩阵的列重均较小)，介绍了该类码的快速编码算法，进一步简化了编码复杂度，以适当增加资源占用为代价，极大地提高了编码速度。

3.1 快速编码方法

基于FPGA平台，在对一类码长为15 360，行重为5～25，列重为2～12的准循环非正则LDPC码(其中每个子循环块的大小为32×32)，按照如下步骤进行编码：

1) 步求DT=H1mT的运算，由于H1矩阵为准循环矩阵，只需将信息序列m以32个bit为单位按照H1矩阵中循环子矩阵的要求进行循环移位操作就可完成运算过程，用FPGA实现时只要一个时钟的时间。

2) 进行第二步运算时，依据Ibrahim N.Imam等人提出的采用舒尔分解求解大矩阵逆矩阵的算法求解H2的逆矩阵H2-1可得：若用字符a表示32×32循环矩阵块为单位矩阵，字符b表示32×32单位矩阵各行分别循环右移一位所得的矩阵，字符c表示32×32单位矩阵各行分别循环右移两位所得的矩阵，则H2-1矩阵所有元素只有a／u，b／u，c／u，(b+c)／u，(a+b)／u，(a+c)／u这6种类型，其中u=a2+ab+b2。显而易见：将公因子u提取出来以后，H2-1矩阵中的所有元素都可由a，b，c这3个符号或其加法之和组成，而二进制加法可简单地用异或门实现。这样H2-1DT的运算就可由简单的移位寄存器和异或门构成，再用组合逻辑实现除以公因子u的运算，完成了准循环LDPC码的编码过程。整个编码算法的数据流程如图3所示。

其具体运算过程为：将日H2-1矩阵分成a，b，c 3部分独立存储，若H2-1矩阵相应位置含有元素a，则将a存储区相应位置1，否则置0，同理完成对b和c存储区的初始化，完成步运算的中间结果参与第二步运算时，若a存储区某位置为1，则数据保持不变参与后面的三输入异或运算，若该位置为0，则将所有数据置为0参与运算，同理若b存储区某位置为1，则数据右移1位后参与后面的三输入异或运算，若c存储区某位置为1，则数据右移2位后参与后面的三输入异或运算，为0则将数据置为0参与异或运算，移位和异或运算可在1个时钟周期内完成，终除以常数公因子u的运算可用组合逻辑实现，不占用时钟周期。

将H2-1矩阵分成3部分存储以后，采用流水线结构，将原本需要10个时钟周期左右的运算过程缩短到多4个时钟就可以完成，整个运算过程中除了存取数据外，只有移位操作和异或运算，大大提高了运算速度，同时也降低了编码的复杂度，而且由于采用了恰当的存储方式，虽然分成3部分存储，但对存储资源的占用并没有太大增加，所耗费的逻辑运算单元仅略有增加。

3.2 快速编码方法的优点

本文介绍的快速编码方法的本质就是根据式(2)对准循环LDPC码进行编码求取校验位时，将H2-1采取一种合理有效的方式加以存储，同时将整个求解过程简化为只有寄存器移位和异或运算。由于准循环LDPC码的校验矩阵Hqc由一系列的m×m小循环方阵组成，采用舒尔分解法求得的H2的逆矩阵H2-1中只由少数几个元素或其加法组合构成，因此，对于所有准循环LDPC码均可以采用如图3所示的快速编码算法加以实现。该实现算法中只有循环移位和异或运算，且每次运算可同时对m个信息位进行处理。因此，采用快速编码算法不仅可实现线性时间内编码，且其运算次数为O(N／m)，降低了LDPC编码的时间复杂度。

4 小结

随着集成电路技术和加工工艺的不断发展，大规模集成电路的逻辑资源数量呈几何级数增加，尤其是FPGA芯片的逻辑单元数量已达到数百万数量级，但运算速度虽有很大提高却受制于物理结构和加工工艺等因素不能呈倍数的增加。本文提出的准循环LDPC快速编码算法依据“面积换速度”的设计准则，通过适当增加对逻辑资源的占用，降低了运算复杂度，极大地提高了运算速度，且该方法对于准循环LDPC码具有通用性，对于应用越来越广泛的准循环LDPC码的编码具有重要的参考价值。