基于FPGA 的LDPC 编译码的高速并行化设计与实现*

吴文俊，张 锐，程敏敏

（中国电科第五十研究所，上海 200331）

0 引言

低密度单奇偶校验码（Low-Density Parity-Check，LDPC）具有接近香农限的性能[1-4]，码率具有很大的灵活性，能够在不进行打孔的条件下得到合适的码率，以降低系统性能的损失。LDPC 译码速度快，适用于高吞吐量和低时延系统，但是对硬件资源需求开销较大。此外，全并行化的译码结构对计算单元和存储单元的需求都很大。根据硬件资源量，可以选择不同的并行实现层次，以满足高速率需求，实现资源和速率上的平衡。本文采用可配置的并行化LDPC 译码实现结构，根据不同的芯片和速率需求对其进行应用。

1 LDPC 编译码器实现结构

1.1 LDPC 码基础知识

LDPC 码定义为具有如下结构特性的奇偶校验矩阵H的零空间：

（1）每一行含有ρ个1；

（2）每一列含有γ个1；

（3）任何两列之间位置相同的1 的个数不大于1；

（4）与码长和H的行数相比，ρ和γ都较小。

对于一个(n,k)的LDPC 码，编码长度为n，信息数为k，校验为r=n-k个比特，以使得码字满足H×CT=0，H为一个(n-k)×n的校验矩阵。每个校验矩阵可以分为大小为b×b的循环子矩阵，这种子矩阵为单位矩阵的循环矩阵或者零矩阵。

8×8 的单位循环矩阵实例为：

1.2 准循环QC_LDPC 码

确定性结构的LDPC 码也称为准循环码（Quasi-Cyslic Low-Density Parity-Check，QC-LDPC）。相对于随机结构的矩阵，人们很容易获得确定性结构矩阵，使得矩阵可以通过更少的参数来定义LDPC码[5]。QC-LDPC 码是一种特殊结构化的LDPC 码，校验矩阵Hqc形式如下：

校验矩阵由大小相同的循环子矩阵构成。循环矩阵是一个方阵，且每行都是前一行的循环右移动，每列都是前一列的循环下移。它的行重和列重都相同。这种循环矩阵的信息便于实现后续的编译码。

1.3 LDPC 编码器设计及实现

1.3.1 编码器基本结构

本文中LDPC 支持的编码速率、信息块长度以及编码块长度如表1 所示。

表1 LDPC 编码参数

通信系统的编码器对实时性要求较高，本文根据QC_LDPC 准循环矩阵采用全并行化的处理实现方式，信息段按照8 bit 位宽进入编码器，码字长度按照8 位划分即为输入的信息长度，编码后的码字也按照8 bit 位宽送出。

编码预处理可以通过软件将生成矩阵提前写入FPGA 的缓存区，根据不同的编码速率调用不同的生成矩阵。由于是准循环矩阵，根据处理流程的规格化方式相同，可将可以同时计算的内容进行并行化处理。图2 为实现的编码器结构。

图2 FPGA 实现编码器结构

根据准循环矩阵的特性，基于不同码率的需求，LDPC 编码的码长较长，如果存储整个生成矩阵会造成巨大的资源开销，也会增大处理延时。因此，编码器根据生成矩阵需进行并行化处理。按照64路并行化处理方式，只存储非零元素的位置信息，存储信息量小于原矩阵的1/64，极大地降低了存储资源消耗。本文中针对（1 536，1 024）2/3 码率、（1 024，512）1/2 码率和（2 048，1 280）5/8 码率3 种不同码率进行实现。

图3 为实现时调用的生成矩阵，编码块（2 048，1 280）。

图3 存储简化的编码矩阵块

编码器的实现流程描述如下。

（1）将需要编码的信息按照每段8 bit 位宽进行划分即u=(u0,u1,…,uk/b-1)，其中ui=(u(i-1)b+1,u(i-1)b+2,…,uib)。编码后的码字为v=(u,p1,p2,…,pr)，r=n-k为校验位，其中pj=(pj,1,pj,2,…,pj,b)。

（2）预先通过软件将矩阵写入缓冲区，待编码使用。由于QC-LDPC 的循环特性，只需存储原矩阵信息的1/64，大大降低了对资源的占用。

（3）根据输入比特位宽，通过移位寄存器实现校验位的输出，编码电路如图4 所示。

图4 编码电路

对编码速率（2 048，1 280）进行详细分析。编码块矩阵为2 048×1 280，根据描述的矩阵存储规则，存储矩阵大小为20×12（行数=n/64，列数=r/64），输入信号位宽为8 bit。图4 中B 是一个反馈移位寄存器，A 是普通寄存器。开始编码时，通过读取ROM 中的预存矩阵因子，B 载入第一个8 bit 的生成因子，A 开始依次输入第一个8 bit 信息段。根据预先存储好的对应信息段，每个比特的生成因子循环移位，同时进行8 bit 信息的编码操作，矩阵以64 长度为循环划分，每载入8 个8 bit 数据，加载下一个矩阵因子。12 行操作同时并行进行，完成20 次列操作，最终生成对应信息的编码数据。该编码实现结构简单速度快、效率高且可复用性强。

1.3.2 编码器的FPGA 仿真

为提高编码效率，按照数据位宽8 bit 进行64路并行化处理。编码器资源情况如图5 所示，编码时序图和仿真结果如图6 和图7 所示。根据不同的码率，只需根据参数调用不同的生成矩阵，即可快速完成编码，适用于实时性要求较高的通信系统。

从图5 编码器资源使用情况可以看出，该编码器的资源占用率较低，所以具有很强的适用性。根据编码实现流程进行数据仿真分析，图6 是编码处理过程中的矩阵载入情况，按照每64 位循环载入，输入数据从0～159 共8×160=1 280 bit 编码，wea_done_out_o 是编码输出使能信号，地址从160开始到255 都是编码校验位的输出。可以看出，待编码数据输入完毕后，8 个clk 开始输出校验结果。由于是线性分组码，前面输出数据个数和输入编码数据一致，后面输出增加校验位r（r=n-k）。本文所实现的编码方案针对不同速率速度快且效率高。

图5 编码器资源情况

图6 矩阵载入

图7 编码仿真实例

1.4 LDPC 译码算法及译码器结构

译码器算法采用最小和积算法MSPA（Min-Sum Product Algorithm），通过分层的并行化来实现译码功能[6]。具体算法步骤如下。

（1）初始化信息。根据校验矩阵H中1 的位置信息(i,j)，初始化对应变量qi,j为输入的待译码信息源。

（2）校验节点计算。本文中采用分层修正的最小和译码算法，所以对应的计算校验信息ri,j为：

其中∂参数用来减小迭代过程中的摆幅，且在每次完成校验节点计算后更新似然比，然后参与下一次校验计算。

（3）比特节点计算。对于校验矩阵H中的每一列中的非零项，计算变量信息qi,j：

（4）迭代译码。对于校验矩阵H中的每一列，任取一个非零元素(i,j)，则第j个比特的对数似然比为llrj=qi,j+ri,j。根据似然比得到码字的硬判结果，如果，则通过校验或者达到最大迭代次数，译码结束；否则，继续进行校验节点计算。

1.4.1 译码器基本结构

首先解调后的数据通过硬判和软判结果送入译码模块，译码模块根据需求选择待译码数据源，然后进入分层修正最小和计算模块开始进行最大迭代次数的迭代计算。译码器结构如图8 所示。

分层修正最小和计算的内部实现模块如图9 所示。核心计算模块中存储校验矩阵的行重信息和每行中1 所在的位置信息。通过访问这两个模块，核心计算模块可以计算出校验信息。R_MATRIX 中存储的是校验信息ri,j，APP_BUF 中存储的是所有信息的对数似然比llrj，即为后验概率。

核心计算模块首先通过读取校验矩阵H相应行1 的位置，通过式（6）计算该行变量信息qi,j；其次，通过式（5）计算得到校验信息ri,j；再次，计算第j个比特的对数似然比为llrj=qi,j+ri,j，更新相应的APP_BUF 中的数值。最后，当校验矩阵遍历一遍后，迭代次数加1，重复上述过程，直至完成译码或者达到最大迭代次数。

图8 译码器结构

图9 分层修正最小和计算模块内部

1.4.2 译码器的扩展结构

本文基于最小和译码算法设计了一种可配置并行化的层次译码器结构，具体算法采用分层模式，但是对数据处理按照并行化方式进行，即一次迭代同时对N个待译码数据进行计算，以提高吞吐量。

为满足多种速率需求，将不同速率的校验矩阵按照64 间隔划分，并通过外部接口写入内部存储，需要时从缓冲区中读取校验矩阵，节省资源，提高灵活度。

存储译码需要H矩阵时，利用准循环矩阵的循环特性，只存储矩阵信息的1/64 以及对应的行重，并且采取全并行化实现。李江林等人实现的并行化方案按照单位矩阵为粒度进行[7]，实现灵活度较低，且根据不同的码率还需要重新修改代码。该方式依据准循环矩阵的特性以及其正交性，只需获知极少的有效信息便可进行译码操作，极大地降低了资源存储的消耗，根据不同的码率调用不同的矩阵即可。经过仿真验证对比，在处理速度上码率的影响并不是很大，只有不同的并行化方式对处理速度影响较大。本例中依据（2 048，1 280）码率进行分析，根据校验矩阵H，在FPGA 中预先存储行重以及每一行中1 的位置，如表2 所示。

本文在FPGA 实现中采用了软判决和硬判决都可选的译码方式。硬判决是对信道的输出做出是0还是1 的判决；软判决不作出0、1 判决，只输出有关信息，如0、1 的后验概率。具体应用中，可根据需求可以选择不同的译码判决方式进行对比。硬判决译码算法是通过传递比特信息进行解码，如比特翻转译码算法。虽然它具有译码算法简单的优势，但是达不到最佳的译码性能。软信息是译码算法传递和后验信息相关的置信度信息，通过置信传播译码具有优秀的纠错性能。

表2 校验矩阵

1.4.3 译码器实现结构比较

本文中译码器实现采用了16 路、32 路、64 路并行的3 种并行化实现方式，通过在模块外部配置参数，改变#defineN的值来改变并行化处理路数模式，从而实现3 种并行化可选。图10～图13 依次列出了16 路并行实现方式的仿真结果，包括资源使用情况、16 路矩阵、一次译码迭代时间以及一次译码成功时间。仿真条件：时钟频率61.44 MHz，编码速率（2 048，1 280），译码数据错误率50%以下均可译码成功。

图10 译码器资源使用情况

图11 16 路矩阵

图12 一次译码迭代时间（12 μs）

图13 一次译码成功时间（45.7 μs）

同时，本文对3 种并行化实现方式的结果进行对比，如表3 和表4 所示。

表3 资源使用情况对比

表4 译码时间对比

通过ModelSim 仿真对比分析可以看出，资源使用和译码效率成反比，需根据需求选择不同的译码方式。该实现方式能够满足多种速率的需求，提高波形的灵活性和可靠性。实际验证平台中，模块的工作时钟是61.44 MHz，编码方式（2 048，1 280），译码最大迭代次数16 次，并行方式为64路，最长译码时间为98 μs；同试验平台原纠错方案RS 编解码实现相比有2 dB 左右的编码增益，意味着采用该实现方式后可以大大提高系统的抗干扰性能和纠错性能。

2 LDPC 码和Turbo 码性能比较

LDPC 的译码算法是一种基于稀疏矩阵的并行迭代译码算法，运算量低于Turbo 码的译码算法。由于结构并行的特点，在硬件实现上比较容易。因此，在大容量通信应用中，LDPC 码更具有优势。LDPC 的码率具有很大的灵活性，而Turbo 需要打孔来提高码率，导致选择打孔图案的十分谨慎，否则会造成较大的性能损失。

3 结语

本文基于xilinx-A7 平台实现了基于LDPC 的编译码器的并行化可配置的设计与实现，并在ModelSim的仿真环境下对该实现进行仿真。对（1 536，1 024）、（1 024，512）、（2 048，1 280） 这3 种码率进行编译码仿真联试，主要针对0.625 码率的（2 048，1 280）进行编译码分析，结果显示编码器占用资源开销较小，译码器在高度并行化、较高吞吐量情况下占用资源较多，但是具有较高的数据吞吐量，能够达到40 MHz，满足不同速率的编译码需求和灵活的资源利用率。根据设计需求，采用不同的译码器并行实现结构应用于不同场景，证明本文的设计具有较高的灵活性。最后，通过试验验证了本文编译码算法实现的有效性，它在高速率传输中具有很好的可靠性和优越性。