论文部分内容阅读
摘要：针对低密度奇偶校验码（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） ③顶层函数的接口问题：最终的 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.
关键词：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） ③顶层函数的接口问题：最终的 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.