基于 HLS 的 LDPC 译码设计与实现

杨伟 李慧 张鹏 韩星

摘要：针对低密度奇偶校验码（Low Density Parity Check Code，LDPC）码长长、码率多、校验矩阵复杂，导致 FPGA 开发难度大、开发周期长等问题。在对 LDPC 校验矩阵和译码算法深入分析基础上，提出了一种基于 HLS 的 LDPC 设计与实现方案。基于 HLS 开发流程完成了 LDPC 译码的 RTL 实现，详细说明了开发过程的关键问题及优化办法。与常规 HDL 开发流程相比，基于 HLS 开发的 LDPC 译码吞吐率更高，时序更好，且便于后期移植和升级。

关键词：LDPC;译码算法;FPGA;HLS

中图分类号：TN911 文献标志码：A 文章编号：1008-1739（2021）13-66-4

Design and Implementation of LDPC Decoder Based on HLS

YANG Wei1， LI Hui2， ZHANG Peng1， HAN Xing1

（1.Hebei Key Laboratory of Electromagnetic Spectrum Cognition and Control， Shijiazhuang 050081， China;2. Unit 75775， PLA， Kunming 650000， China）

Abstract： Aiming at the problem of long code length， different code rate and complex check matrix of low density parity check code（LDPC） codes， which lead to the difficulty of FPGA development and long development cycle， a LDPC design and implementationscheme based on HLS is proposed based on the in-depth analysis of LDPC check matrix and decoding algorithm. Based on the HLSdevelopment process， the RTL implementation of LDPC decoder is completed， and the key problems and optimization methods in thedevelopment process are described in detail. Compared with the conventional HDL development process， the LDPC decoder based onHLS has higher throughput， higher timing， and is convenient for later transplantation and upgrade.

Keywords：LDPC; decoding algorithm; FPGA; HLS

0 引言

低密度奇偶校驗码（Low Density Parity Check Code，LDPC）由 Gallager 博士于 1962 年首次提出[1]，LDPC 码具有接近香农极限的译码性能，而且译码复杂度低，适合并行处理。经过近几十年发展，LDPC 码已广泛应用于卫星传输、深空通信及数据存储等领域。第 2 代数字视频广播（DVB-S2）标准采用 BCH 码与 LDPC 码级联的前向纠错（FEC）方式，其性能接近理论极限[2]，支持 64800 和 16200 两种码长以及多达 11 种码率[3]。由于 LDPC 码码长较长、码率较多，FPGA 开发过程较为复杂。

与传统处理器相比，基于并行结构的 FPGA 在性能、成本、灵活性和功耗等方面有较大优势，因此在通信、电子及数据处理等领域得到广泛应用[4]。但是随着算法复杂度不断提高，FPGA 器件不断升级，基于 HDL 输入的常规开发方法开始面临开发难度大、开发周期长等问题。针对这个问题，Xilinx 公司推出了新一代的开发工具：高层次综合（High-Level Synthesis，HLS）。HLS 允许开发者直接使用 C/C++/System C 进行设计建模，并自动将其转换成 RTL 级的实现[5]。HLS 使开发者有更多精力进行系统级设计，不必关注具体时序细节，从而极大提高设计效率。

针对 LDPC 码译码过程时序复杂、开发周期长等问题，基于 HLS 开发工具进行了 LDPC 码的译码设计与实现。HLS 能够自动实现底层的时序设计、资源绑定及指标分析等功能。与常规开发流程相比，减小了开发难度，提高了设计效率。

1 LDPC 译码算法

1.1 校验矩阵分析

由 DVB-S2 标准可知，LDPC 码支持 1/4，1/3，2/5，1/2，3/5，2/3，3/4，4/5，5/6，8/9，9/10 共 11 种码率，64800 和 16200 两种码长[6]。

LDPC 码是非规则累积码[7]，校验矩阵可表示为，其中，是m×k的稀疏矩阵，m是校验比特个数，k是信息比特个数。是满秩矩阵[8]，如下：

。（1）

矩阵的行重和列重具有一定规律。矩阵可表示成如下形式[8]：

，（2）

式中，均為q×k的子矩阵，q的取值和码长及码率有关。每个子矩阵又可分成如下形式：

（3）

式中，均为q×360 的子矩阵，它们分别向右循环移 1 位，可得到即可得到，以此类推。利用矩阵的周期规律，可以在译码实现过程中，减少存储资源。

1.2 LDPC 译码算法

LDPC 码一般采用迭代译码，译码算法的基本思想是通过使概率信息在变量节点与校验节点之间来回传递，得到信息的独立统计，从而找到正确的码字。常用的有基于概率的 BP算法（Belief Propagation Algorithm）。基于对数域的 BP 算法，最小和算法以及归一化最小和算法等[9]。考虑不同算法的译码性能和实现过程复杂度，本文采用归一化最小和算法。

该译码算法的具体步骤为：

（1）初始化似然比信息

（4）

式中，（）表示接收端接收到的初始化似然比信息。

（2）迭代处理，包括校验节点信息更新和变量节点信息更新。对于第k次迭代，有校验节点信息更新：

，（5）

式中，表示校验节点j向变量节点i传输的外部概率信息;R（j）表示与校验节点相连的所有变量节点集合，R（j）＼i则表示除变量节点i之外所有与校验节点j相连的变量节点集合。

变量节点信息更新：

，（6）

式中，表示变量节点i向校验节点j传输的似然比信息。

（3）译码判决

计算所有变量节点的后验信息，并进行判决，如式（7）所示：

，（7）

式中，C（i）表示与校验节点i相连的所有变量节点集合，C（i）＼j则表示除变量节点j之外所有与校验节点i相连的变量节点集合;表示比例因子，取值范围表示 LDPC 译码后的码字，H表示对应的校验矩阵。若，则，否则。

经过判决得到 LDPC 译码后的码字，如果满足或者达到设定的最大迭代次数，则输出译码结果，结束译码。否则从步骤（2）继续迭代处理。

2 HLS 功能及设计流程

HLS 可以实现直接使用 C/C++/System C 规范对 FPGA 进行编程，而无需手动创建等效的 RTL 设计，从而加速设计开发[11]。相比传統的开发过程，HLS 允许设计人员在 C 语言级进行开发设计，从而大幅缩短开发和验证时间。设计人员可以通过不同的优化指令控制 C 综合过程，以探索最优的 RTL 实现，同时基于 C 的源代码容易移植和适配不同的器件。

在使用 HLS 工具之前，要首先理解 HLS 功能，设计流程以及开发过程的相关约束和限制。HLS 的主要功能包括[12：①从 C 源代码中创建一个 RTL 级实现;②从 C 源代码提取出控制信息和数据流;③基于默认的和用户定义的命令，实现设计;④从相同源代码描述中，探索实现更多的设计。

HLS 设计流程步骤如下：

①编译、仿真和调试 C 语言算法;

②将 C 语言程序综合为 RTL 实现，期间用户可根据实际情况添加优化指令;

③生成详细报告并分析设计;

④使用按钮式流程验证 RTL 实现;

⑤将 RTL 实现封装为一套选定的 IP 格式。

需要说明的是，HLS 工具并不能处理所有代码，对输入程序有一定的限制：不支持使用动态内存分配;减少使用指针对指针的操作;不使用系统调用，否则在综合时这些指令会被无视或直接删掉;减少使用其他标准库的内容;减少使用 C++ 中的函数指针和虚拟函数;不使用递归方程;精准表达交互接口等。

3 LDPC 译码实现过程

3.1 译码器结构框图

结合译码算法流程、校验矩阵特点及 FPGA 并行实现原理，设计的译码器结构如图 1 所示。

由图 1 可知，译码处理过程主要包括输入似然比信息的缓存与重排、变量节点与校验节点的计算，以及中间计算结果的缓存以及译码判决输出等。译码过程需要大量的计算和数据缓存。在后续的 HLS 开发过程中，以该结构为依据进行优化与调整。

3.2 原有 C 算法程序的限制及处理方法

在使用 HLS 进行开发时，首先需要对原有 C 算法程序进行修改，主要有以下几点：

①动态分配内存问题：利用固定长度的数组，只要保证数组长度满足最大码长的需求即可。

②浮点数问题：转为定点数计算，HLS 支持定义任意位宽的变量，打破 C 语言中 short，int，long 等类型的限制。针对定点小数，还支持对截位和溢出的处理。

③顶层函数的接口问题：最终的 RTL 输出会与其他 HDL代码交互，因此顶层函数的接口定义也需要进行修改。其中，数据的输入和输出采用 hls：：stream，对应 ap_fifo，综合后为FIFO 接口;参数的输入采用标量数据默认的 ap_none，直接输入，没有交互;其余的时钟、复位、启动的控制为 HLS 默认。

将 C 算法程序中的这些限制修改后，理论上该代码就可以被综合为 RTL 代码，但实际上，还要根据 HLS 和代码的特性进行优化，否则综合结果的 FPGA 资源占用和时序不可控。

3.3 数组的优化

LDPC 的译码过程从以下 2 个方面开展数组优化，提高并行处理能力。在 C 程序中，输入的似然比信息存储在一个数组中。HLS 会将数组映射为 BlockRAM，而 BlockRAM 最多有 2个读接口，会限制程序的并行性。需添加 ARRAY_PARTITION指令，将一个数组拆分为多个小数组，增加读写接口、提升并行性。

在 C 程序中，需要多个数组存储变量节点和校验节点更新后的中间信息。这些数组读写地址相同，且读写同时，可以通过 ARRAY_MAP 指令将这些数组按照位宽进行合并。如180 个 6 bit 位宽的数组，可以合并为 1 个 1 080 bit 位宽的数组，从而充分利用 FPGA 中的 36 bit 位宽的 BlockRAM，减少资源的使用。

3.4 流水线优化

流水线设计通过将一个复杂的计算分解为多个简单计算，通过流水处理的方式以提高吞吐率。如在校验节点更新过程中，需要依次执行计算输入数据的绝对值、最小值以及数据符号乘积 3 个步骤。通过 PIPELINE 参数，可以对该段代码进行流水线设置，流水优化示意图如图 2 所示。

图 2（a）和图 2（b）分别为流水线优化前后的处理时序。其中，图中的数字 1，2，3 分别代表计算输入数据的绝对值，最小值以及数据符号乘积 3 个步骤。前者需要 3 个时钟才能输入新的数据，而后者只需 1 个时钟即可输入新的数据，吞吐率提高了 3 倍。

在 C 程序中存在很多这样的循环函数，如果将循环进行流水处理，会增加部分逻辑资源，但大大提升循环的执行效率，因为此时无需等待本次循环执行完成即可输入下一次循环的数据进行流水处理。

3.5 综合结果分析与迭代优化

C 综合完成之后，HLS 会自动生成对应的时序和资源的报告，可在分析界面中查看。分析结果可以针对具体的函数或循环进行查看，便于查找性能限制的节点。需要说明的是，HLS开发过程往往需要不断对综合结果分析，进行多次参数及代码的优化，才能得到满足要求的 RTL 实现。

经过仿真与综合，最终确定译码实现参数为：并行度 180;迭代次数 20;比例因子 =0.75;工作时钟不低于 200 MHz;吞吐率不低于 200 Mb/s。

4 测试验证及总结

在进行 C/RTL 联合仿真验证后，可以将生成的 RTL 代码添加至工程中，进行功能与指标的实际测试。测试流程包括PN 序列产生、LDPC 编码、BPSK 调制、AWGN 信道、LDPC 译码、PN 序列验证及误码率统计等。测试流程如图 3 所示。

经过测试，在不同码长及码率参数下，LDPC 译码器均能正常译码，且译码性能满足工程需求。图 4 所示为帧长 64 800，码率 2/3 时，测试得到的误码率曲线。

与已有的 FPGA 译码程序相比，基于 HLS 开发的 LDPC译码器工作时钟更高，吞吐率更大，这是以增加了少量 LUT和 BlockRAM 资源为代价得到的。

HLS 以 C 程序作为设计输入，加快了仿真和验证速度。在HLS 工具的支持下，FPGA 开发人员可以有更多精力关注系统级性能，而不必关心具体的时序设计。同时在面对目标器件升级、校验矩阵更改、关注指标侧重不同等问题时，可以帮助开发人员更快地进行修改、移植和验证，极大提升效率。基于HLS 的设计流程，需要设计人员对 FPGA 的资源和时序等有一定了解，以保证最终 RTL 设计的可靠。

5 结束语

針对 LDPC 码长较长、码率较多，导致 FPGA 开发难度大，开发周期长，不方便移植和升级等问题，在对 LDPC 译码算法深入分析的基础上，提出了基于 HLS 开发流程的 LDPC译码设计思路。对 LDPC 译码功能指标进行了全面的验证测试，能够满足设计需求。同时，经过对比，基于 HLS 的设计更加易于移植和升级，缩短开发周期、提高设计效率。

参考文献

[1] GALLAGER R G. Low-density Parity-checks Codes [J].IEEETransactions on Information Theory，1962，1： 21-28.

[2] 李志勇，李文铎.一种高速 LDPC 编译码器的设计与实现[J].无线电工程，2009，39（7）：17-19，61.

[3] 王延鹏，潘申富，杨宏伟.基于 FPGA 的 DVB-S2 LDPC 编码器的设计与实现[J].无线电工程，2015，45（3）：30-33.

[4] 田耘，徐文波，张延伟.无线通信 FPGA 设计[M].北京：电子工业出版社，2009.

[5]党宏社，王黎，王晓倩.基于 Vivado HLS 的 FPGA 开发与应用研究[J].陕西科技大学学报（自然科学版），2015，33（1）：155-159.

[6] ETSIEN 302 307 V1.3.1.Digital Video Broadcasting（ DVB）;Second Generation Framing Structure，Channel Coding andModulation Systems for Broadcasting，Interactive Services，News Gathering and Other Broadband Satellite Applications[S].2013.

[7] 江桂芳，彭克荣.基于 FPGA 的高速并行 DVB-S2 标准LDPC 译码[J].空间电子技术，2013，10（1）：58-61，95.

[8] 贺鹤云.LDPC 码基础与应用[M].北京：人民邮电出版社，2009.

[9] 袁云云.DVB_S2 标准中多模级联纠错码研究及其高速FPGA 实现[D].西安：西安电子科技大学，2014.

[10] 袁东风，张海刚.LDPC 码理论与应用[M].北京：人民邮电出版社，2008.

[11] 符晓，张国斌.朱洪顺.Xilinx ZYNQ-7000 AP SoC 开发实战指南[M].北京：清华大学出版社，2016.

[12] 何宾.Xilinx FPGA 设计权威指南：Vivado 集成设计环境[M].北京：清华大学出版社，2014.