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

　

概要：SP，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，码字

一类准循环LDPC码的快速编码方法,http://www.592dz.com
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码。

[1] [2]  下一页