基于FPGA的LDPC编码设计

在通信系统中纠错码被用来提高信道传输的可靠性和功率利用率，低密度奇偶校验码LDPC(Low Density Parity Check code)是目前性能最好的纠错码，最初由GaUager提出，但当时并没有引起足够的重视。直到Turbo码提出后，人们在研究Turbo码的迭代解码时，发现二者具有相同的特性，即约束随机码集合和迭代解码算法，这导致了随后LD-PC码的复出。1996年，Mackay和Neal随机构造出的LDPC码，当码长很长时其性能超过Turbo码，并在实现上更有优势，从而激起编码界对LDPC码的研究热情，成为当今信道编码领域最令人瞩目的研究热点之一。LDPC码出色的纠错性能以及可以并行解码的特点特别是其简单实用性使其成为下一代通信纠错编码的首选。因此，这里介绍一种基于FPGA的LDPC编码设计。

1 LDPC码
    LDPC码是一种线性分组码，其校验矩阵是稀疏矩阵，因为相应的校验矩阵中包含绝大多数的0而仅有极少数的1而得名。一个(n，k)二进制LDPC码可以用一个非常稀疏的奇偶校验矩阵H来表示。其中，H是一个mxn的矩阵，n表示编码比特长度，m表示校验比特长度，k=n-m是信息比特长度。与校验矩阵H相对应的是一个生成矩阵G，生成矩阵将要发送的信息s={sl，s2，…，sm}转换成被传输的码子c={c1，c2，…，cn}，n>m。对于任何一个合法的码字c，都有校验方程HcT=0。

2 RU编码算法
    LDPC码属于线性分组码。信号通过LDPC编码后的码字符合公式：
   
式中，c为码字，H为校验矩阵。
    直接的编码方案：1)高斯消元，将校验矩阵H化为下三角形式：2)将c分为信息比特和校验比特2部分，如x=(s，p)，其中s为已知信息比特向量，p为待求校验信息比特向量；3)利用前向迭代方法解方程HcT=O，得到p。由于高斯消元后的矩阵不再具有稀疏性，因此这种编码方法的硬件实现方案，其复杂度是与码长的平方成正比。为了降低复杂度，Richardson和Urbanke充分利用校验矩阵的稀疏性，将LDPC码的编码复杂度降到与码长n成线性关系，即RU算法。
    RU算法包括两个阶段：预处理阶段和信号编码阶段。通过预处理将校验矩阵日变为一个近似下三角的矩阵，由于这种变换仅仅通过行置换来实现，所以矩阵的稀疏特性被保留。如图1所示，在校验矩阵H的近似下三角形式中，分块矩阵A、B、C和c都保持了稀疏性，D为密集矩阵，T为稀疏的下三角矩阵。当g很小时，即矩阵D很小时，可以大大降低编码运算复杂度。为减少运算量应在设计H矩阵时使g越小越好。
    实际编码由矩阵相乘、前向迭代和向量相加操作组成。对于给定的一个校验矩阵，预处理编码预处理过程和矩阵的计算只需要做一次，所以可先用软件完成，实际编码在硬件上完成。RU编码算法中可以进行部分并行运算，使得吞吐率最大化。通过有效的矩阵存储，降低存储单元的消耗量。
2．1 编码器设计

    预处理包括2步：三角化和秩校验。三角化通过行列置换处理将校验矩阵转化成图1所示的形式，则：
   
式中，A为(m-g)×(n-m)，B为(m-g)×g，T为(m-g)×(m-g)，C为gx(n-m)，D为gxg，E为gx(m-g)。除D外，其他全是稀疏矩阵，且T为对角线上全为l的下三角矩阵。
    设c：[sp1 p2]，其中s为系统信息部分，p1和p2共同组成校验信息部分，p1长为g，p2长为(m-g)。HcT=0左乘得到
    
    定义F=-ET-1 B+D，并且假定F是非奇的，由式(3)可得到p1和p2的求解式分别为
    
    在式(4)求解p1的过程中，要求矩阵F可逆，因此F必须为非奇异的，即可逆。因此实际编码前必须进行秩校验。为得到F，对原始H矩阵进行高斯消元得到式(6)的形式：
    
    如果F为奇异的，则将F中的列与其最左边的列进行交换，直到F非奇异为止。
    编码复杂度主要由g×g维矩阵F-1与向量(-ET-1 A+C)sT相乘决定。RU算法在g很小时，即g2<<n时，编码复杂度与码长n成线性关系。因此，为了进行有效编码，预处理要使得g应尽量的小。
2．2 编码器硬件结构
    基于RU算法的LDPC编码实现过程主要是计算p1、p2的过程。设计编码器时，为了提高编码速度，将可以同时计算的步骤作并行处理，得到编码器的硬件结构如图2所示。

    图2中，A、B、C、E分别代表图1中相应的矩阵，其中，F=-ET-1 B+D。从图2可知LDPC编码器主要由矩阵向量相乘(MVM)、前向迭代(FS)、向量相加(VA)和向量合成器(CWG)等运算单元以及存储各个矩阵相关信息的存储器组成。因为前向迭代运算基本上是矩阵与向量的乘法计算，所以矩阵向量乘法是LDPC编码过程最核心的单元。

3 矩阵向量乘法器(MVM)的实现
    矩阵与矩阵的乘法运算以及前向迭代运算实质上都是矩阵与向量的乘法。下面说明矩阵向量乘法器硬件实现。

    对于LDPC编码器，如何有效存储各个矩阵的信息是降低复杂度的关键。本文采用存储矩阵中元素‘1’在行中的位置以及对应行行重，如表1所示。例如矩阵X第3行的“1”元素，在行中的位置分别为“0”、“4”，该行的行重为2。由于LDPC编码过程中使用的矩阵大多是稀疏矩阵，所以采用该矩阵存储方案能比较有效地利用存储的空间并有利于矩阵与向量乘法的快速实现。
    
    矩阵X每行中“1”的位置可看作选择向量s相应元素的地址索引，将选择的所有元素相加作和，即完成X中某行与向量的运算。由于涉及的运算都是二进制加法，相加作和操作可简化如下：根据矩阵每行“1”的位置选择向量s的元素。统计被选择的元素中“1”的个数，若结果为奇数则说明相加的结果为“l”，否则说明相加的结果为“0”。判断结果为奇数或者偶数可由其二进制形式的末位是“1”或者“0”得到。通过设置2个计数器分别计算各行行重和选择的向量s相应位置的元素中“1”的个数，即可实现乘法单元的运算。矩阵向量乘法器的硬件结构如图3所示。

    从图3可知矩阵向量乘法器包括1)调度单元，产生各模块单元的使能信号；2)缓存单元，对输入信息序列进行缓存处理；3)存储器控制单元，产生存储器的地址信号；4)“1”位置存储器，存储矩阵各行“1”的位置；5)行重存储器，存储矩阵相应各行行重；6)乘法单元，进行向量乘法运算，最后输出码字。

4 结果验证
    矩阵向量乘法器仿真结果验证在Qum-tusⅡ环境下，实现output=XsT，得到如图4所示的仿真时序图。图4中“en”是使能信号，“cloc-k”是时钟信号，addr_nun、adds_t分别为2个存储器的地址信号，info_seq是输入信息信号，rece是信息信号经过缓存后的输出信号，num_t是“1”在各行的位置信息，rOW_t是相应各行的行重，output是矩阵与向量相乘的结果。

    由图4可知，output=[1 1 1]，信号输出有一个时钟周期的延时，仿真结果正确。

5 结束语
    用本文描述的方法，在1片Stratix系列的FPGAEPIS25F67217中，实现了最大码长为4 096的灵活编码方案，编码器占用约lO％的逻辑单元，约13％的存储单元，综合后时钟频率达到166 MHz，数据吞吐率达到48．33 Mb／s。该编码器结构是一种通用的设计方案，可以灵活地应用于各种不同类型的LDPC编码中，并可有效地分配存储器单元和最大可能地实现运算过程中的并行处理，但由于其采用通用的编码算法，实现的复杂度高于某些特殊结构的LDPC编码器，比如准循环LDPC码。另外通过优化时序和编码结构，可以进一步提高本文编码器的编码速度。