一种高效LDPC编码器的FPGA实现

1、一种高效LDPC编码器的FPGA实现史可显(中电集团第五十研究所)摘要本文介绍了一种高规DPC编码器的FPGA实现方法。该方法在保持了校验矩阵的稀疏性 前提下，简化了编码运算。它将校验矩阵通过行和列变换得到一个近似下三角分块稀疏矩 阵，从而通过线形复杂度运算就能得到校验比特，完成编码过程。和用A对该方法的实 现算法进行优化后可以得到一种高效勒PC编码器。关键词LDPC； RU 算法；FPGA正文1.引言LDPC码是Gallager提出的一种线性分组码，故又称为Gallager码。早在1962 年 Gallager 就提出 了规则低密度校验码(regular low density parity

2、 check codes) 和迭代译码(iterative decoding)的概念。但直到上世纪90年代，Spielman， Mackay和Neil重新发现了 LDPC后，它才得到了人们的广泛关注。LDPC是一种 具有优良渐进特性的非常好码，它的性能能够逼近香农限。其利用信息在校验节 点与变量节点间的传递进行迭代译码，具有优良的性能与相对很低的实现复杂 度。但LDPC码的编码一直是一个难题，相对于其译码来说，其编码有更大的实 现难度。这是因为LDPC码的编码有较高的编码复杂度和编码时延。采用高斯消 元法直接编码时，破坏了校验矩阵H的稀疏性，其复杂度与LDPC码的码长的二 次方成正比，即O(N

3、2)。当码长较长时，编码复杂度将导致难以实现T.J.Richardson 和R.L.Urbanke提出了一种高效的LDPC码编码方法(RU算法)，有效的降低了 LDPC码编码的复杂度。其复杂度基本与码长呈线性关系，为FPGA实现带来了可 能性，初步解决了 LDPC码应用的一大难题。2. RU算法对矩阵H的行和列重排不会破坏H阵的稀疏性。这样做虽然不能得到一个 完全的下三角矩阵，但可获得一个近似下三角矩阵。图1近似下三角矩阵将图11中的矩阵左乘一个矩阵，得到用于来计算校验比特的矩阵。 TOC o 1-5 h z I0 丫 ABT _6 ABTET-iI 人 CDE 厂-ET-1A + C-ET

4、一 1B + D0 /令编码后的码字x = (s,p ,p )。其中s为系统比特，p和p为校验比特。p的12121长度为g，p的长度为M-g。则，p ,p由式(2)来计算得出: 212(ET-1A + C )st +(-ET-1B + D )p： = 0Ast + Bp t + Tp t = 0将式(2)中的算法经过整理得到p1和p2的计算式如下： TOC o 1-5 h z pT 二一0-1 -ET-1 Ast + Cst(3) HYPERLINK l bookmark16 o Current Document LL pT 二 一T-i L Ast + BpT(4)L1 -I其中，0 =-E

5、T-1B + D。在一些实用的准循环结构QC-LDPC编码中，如802.16e中，取0为I或I的循环移位，则有：PT = -ET-1Ast + Cst(5)计算步骤以及算法复杂度如下表：表1 LDPC高效编码计算步骤及复杂度算法运算性质复杂度1Ast稀疏矩阵与列向量相乘O(n)2T-1Ast矩阵与列向量相乘(可优化)O(n)3-ET-1L Ast 稀疏矩阵与列向量相乘O(n)4Cs T稀疏矩阵与列向量相乘O(n)5-ET-1Ast + Cst列向量相加O(n)6BpT稀疏矩阵与列向量相乘O(n)7Ast + BpT1列向量相加O(n)8-T-1Ast + BpTL1矩阵与列向量相乘(可优化)O

6、(n)由表1可见，利用了准循环结构的QC-LDPC校验矩阵，所有编码的运算复杂 度都为O(n)。3. LDPC编码器的实现3.1.整体设计LDPC码校验矩阵的最大特点就是稀疏性，在实现上应当尽可能的利用这个 特点。在整体结构上，可以利用只读内存(ROM)来存储校验矩阵。由于信源的输入大多是串行的，整体考虑了资源的开销与实现速度的均衡，采用串行运算的 实现方式比较适合高效编码的实现。P2 图2 LDPC编码器数据流从表2中可以看出，运算资源分为3种，即：稀疏矩阵一列向量乘法器，列 向量加法器，T逆矩阵一列向量乘法器。由于每一步的运算都没有使用相同的运 算资源，因此非流水线方式下只需要3个不同的运

7、算资源即可。表2编码器的运算分级级运算占用资源类型延时1AsT稀疏矩阵一列向量乘法器A中“1”的个数2CsT； T-iAst稀疏矩阵一列向量乘法器；T逆矩阵一列向量乘法器Max（C中“1”的个 数，T中“1”的个数）3-ET-i Ast ；-ET-iAst + Cst稀疏矩阵一列向量乘法器；列向量加法器E中“1”的个数+ g的长度4BpT ； Ast + BpT ；-T-iAst + BpT L1稀疏矩阵一列向量乘法器； 列向量加法器；T逆矩阵一 列向量乘法器B中“1”的个数+ M-g 的长度+T中“1”的 个数LDPC的校验矩阵有着显著的稀疏性特点，这种特点为FPGA的矩阵存储提供 了很大的

8、优化可能性。由于校验矩阵中的“1”的个数非常少，因此总体的优化 思路是只存储“1”的位置，而不是存储整个矩阵。存储结构可以这样设计：行 起始标志位+列位置。表3优化的矩阵存储结构行起始标志位列位置xxxxx行起始标志位表示是否为新的一行开始，如果是则为“1”，如果否则为“0”。“列位置”则存储矩阵为“1”的列的位置。矩阵的行数越大，相对于传统的存 储结构，这种存储结构可以节省更多的存储空间。3.3.列向量加法器列向量加法器是前文提到的3种运算单元中最简单的一种。要实现X+Y=Z 的计算，X，Y，Z都为列向量，结构如下图：读地址图3列向量加法器由于所有的运算都是模2的，所以加法可以用逻辑异或来代

9、替。计数器产生 的当前地址对于X，Y都是读地址，对于写入的内存Z来说都是写地址。X，Y，Z 都是RAM，顺序存储了列向量的值，0，1，2，n为其地址。34.稀疏矩阵-列向量乘法器该模块需要完成的算法是XY=Z，其中X为稀疏矩阵，Y为列向量，Z为列向 量。设计思路如下，X中存储的都是为“1”的元素列位置，行数从第1行开始， 最高位为1时行数加1。X的当前行数就是数据写入Z的写地址。X中的数据代 表“ 1”的列位置，应当乘以Y的对应位置的元素。由于X中存储的元素只能是 “1”，因此乘法的结果就是Y对应位置元素的值。所以乘法运算可以简化为用 X中的值作为读地址查询Y，得到的值就是运算结果。由于运算是

10、模2的，累加 器可以简化为1个D触发器。结构如下：图4稀疏矩阵-列向量乘法器需要注意的是，Z的写地址一般是从0开始编址，所以计数器B输出需要减 1才是Z的写地址。图中的加法器同样可以用异或代替。3.5. T逆矩阵一列向量乘法器T矩阵也是一个稀疏矩阵，但其逆矩阵却一般不再具备稀疏性。因此，如果 采用存储T-1再与列向量进行乘法运算的实现方式，就会耗费大量的存储资源和 运算时钟周期。但这一运算是可以优化的。需要实现的算法是： TOC o 1-5 h z T-1X = Z(6)即：X = TZ(7)其中X，Z都是列向量。T为下三角矩阵，我们可以得到表达式：（1,1） 1X2= t（2,1）Z1 +

11、t（2,2 ）Z2x = t z +1 z +.+1 z(8)n(n,1) 1(n,2) 2(n,n) n值得注意的是，当i = j，t(ij)=1。将上式改写后可以得到递推公式：z = Xz2 = *(盘z = x 一 t z 一tz -.一t z(9)n n(n,1) 1(n,2) 2(n,n -1) n-1由于是模2运算，上式中的减号都可以改写为加号。这样我们采用如下的设计思路：计算采用递推的方式，从Z1的计算开始。当t,、等于0时，t z不用计算，因此t,、也不必存储。(i,j)(i,j)j(i,j)与稀疏矩阵-列向量乘法器相同，当t,、等于1时，t z就是z的值。(i,j)(i,j)

12、j jZ的写地址可以由T矩阵的当前行数决定。我们得到了如下的结构:图5 T逆矩阵一列向量乘法器乘法器耗用的运算延时为T矩阵中“1”的个数。需要注意的是用来存储T 矩阵的存储器深度并等于T矩阵中“ 1”的个数，而是少了 n。这是因为T的对 角线都是“ 1”，就不必要占用存储器空间了。因此对T存储器寻址的计数器必 须在新的一行开始时暂停一个时钟周期，利用这个周期从X中取值运算。可以利 用T的最高位，即行起始标志位产生计数器A的封门信号。4.结论这种LDPC的编码实现方案很简单，只用到了 3种运算模块，且运算复杂度 都比较低，从而大大的节省了 FPGA的资源开销。本文也给出了一些进一步优化 结构的设

13、计细节，如矩阵的存储，T逆矩阵的运算等等。这些细节不仅可以节省 开销，也可以很大程度上提高系统性能。在利用本文编码器方案设计的项目中， 都运行到了 100MHz的速度以上。随着对LDPC码算法与实现领域的不断研究，相信不久就会出现更优的编译码算法，从而为系统提供更高的纠错性能。那时，LDPC码在无线通信，深空通信，光通信，磁/光存储系统，固定无线通信，电 缆调制解调等等通信前沿产业上，都将拥有广阔的应用前景。参考文献Gallager R.G., Low-Density Parity Check Codes, Cambridge, MA: MIT Press, 1963T Richardson

14、and R Urbanke, Efficient Encoding of Low-density Parity-check Codes. IEEE Transactions on Information Theory, Feb.2001,47:638-656RICHARDSON T, SHOKROLLAHIA, URBANKE R., Desing of capacity-approaching low-density parity check codes. IEEE Trnas. Inform. 2001，47(2)： 619-637.LEE Dong一U,WAYNE Luk，WANG Connie,et al., A flexible hardware encoder for low-density parity-check codesJ. Proceedings of the 12th