LDPC译码器中SISO模块的高层次综合实现
2015-09-11段倩妮吴迪
段倩妮++吴迪
摘要：日益增长的硬件设计复杂度和越来越短的芯片研发周期给集成电路设计带来了极大的挑战。通过更高抽象层实现硬件设计自动化的方法是解决问题的关键。 VivadoTM High-Level Synthesis（HLS）是Xilinx公司发布的高层次综合工具。针对信道编解码LDPC译码器芯片的核心模块—软输入软输出（Soft-Input Soft-Output， SISO）模块，采用HLS设计方法进行了基于C语言模型的实现。HLS的综合结果能与手工使用Verilog实现的性能接近，但明显缩短了设计时间。
关键词：High-Level Synthesis； SISO； Log-Map； IEEE 802.11ac； LDPC
中图分类号：TP319 文献标识码：A 文章编号：1009-3044（2015）17-0183-04
Implementation of SISO Module in LDPC Decoder with High-Level Synthesis Tool
DUAN Qian-ni1，WU Di2
（1. Nanjing University of Aeronautics and Astronautics， Nanjing 210016， China；2. Soochow University， Suzhou 215006， China）
Abstract：The increasing complexity of hardware and decreasing time of development brings challenges to integrated circuit design. High-level synthesis-based design automation is the key to solve the problem. VivadoTM High-Level Synthesis is a high-level synthesis tool from Xilinx Inc. Targeting the Soft-Input Soft-Output （SISO） module which is the core unit of LDPC decoder， HLS methodology is applied by programming the SISO module in C. The synthesis result shows that HLS based design achieves similar hardware efficiency as compared to the manually coded design using Verilog， while significantly reducing the design effort.
Key words：High-Level Synthesis； SISO； Log-Map； IEEE 802.11ac； LDPC
1 概述
低密度奇偶校验Low Density Parity Check（LDPC）码最早于1962年由R.Gallager第一次提出[1]，是一类校验矩阵为稀疏矩阵的线性分组码，在1996年被再次发现[2]。非规则LDPC码的构造使得数据传输速率能够接近香农容限，无线通信标准如DVB-T2，WLAN（802.11n，802.11ac）都考虑了LDPC码的使用。
由于LDPC译码器的高处理要求，通常用硬件来实现。在软件无线电系统中，可编程逻辑阵列（FPGA）的灵活性和高处理能力使得LDPC译码器的硬件设计成为可能[3-5]。基于RTL级的HDL设计是目前最为广泛的数字电路实现方法。但是，随着时间的推移，各类产品应用中使用的信号处理算法比以往更加复杂，传统基于RTL设计FPGA的实现需要更多的时间来分析设计，迭代仿真和优化性能。为了摆脱这个困境，Xilinx公司发布了VivadoTM HLS工具，可由高层次抽象层（如C语言）直接综合出硬件设计。因此，设计者可将关注点集中在抽象层而不是执行细节。设计者只需在抽象层验证函数功能的正确性即可，验证的速度将比基于HDL的设计流程快得多。再加之LDPC译码器的很多设计架构在抽象层次上就具有很高的并行性[6]，很容易通过约束条件来实现高性能的硬件。更高的设计层次带来更大的设计空间，也增加了寻找到最佳设计的可能性。
本文将展示如何通过Xilinx VivadoTM HLS工具实现LDPC译码器中用于更新校验节点的SISO模块。首先，根据算法所采用的架构写成C代码；其次，利用Xilinx VivadoTM HLS工具对C代码进行综合，实现SISO模块；最后验证了SISO的性能是否满足设计需求。
2 VivadoTM HLS的开发流程
图1是VivadoTM HLS工具的设计流程。设计的输入是C、C++或者SystermC代码，约束条件和Test Bench。
1）C、C++或者Systerm C代码。C代码根据算法的硬件架构来实现，并完成算法应有的功能。
2）约束条件。添加的约束条件用来指导C代码综合的流程，循环、接口、数组都可以添加约束条件，设计者通过优化C代码和添加适当的约束条件来获得最大吞吐率。
3）Test Bench。Test Bench用来在综合前验证C代码功能的正确性，并可以在之后的C/RTL联合仿真时比对RTL的输出结果。
VivadoTM HLS的输出结果是可综合的Verilog、VHDL或SystemC代码，可以在FPGA硬件上执行[7]。
以下是设计的流程。
1）在使用VivadoTM HLS工具进行设计前，首先应该对算法实现的硬件架构有初步的框架，根据这个架构来写出实现算法功能的C代码。再编译、执行和调试C代码，并验证代码功能的正确性。
2）根据实现需求添加适当的约束条件，综合C代码生成相应的RTL设计，同时产生综合报告和设计分析。分析生成的报告是否符合要求，如果不符合要求，继续优化C代码并修改约束条件。
3）C/RTL联合仿真，利用Test Bench来验证RTL实现的正确性。
4）如果需要，可以将实现的RTL设计封装成IP核。
在高层次具有较高并行度的算法用VivadoTM HLS软件实现，容易通过添加适当的约束条件，综合出高效的处理流水线。
3 SISO模块的Log-Map算法
在LDPC译码器的分层迭代译码算法中，复杂度最高的是更新校验节点信息[Λ（xi）]的计算，文献[8]提出了一种代替双边图来表示LDPC码的方法，来简化[Λ（xi）]的计算过程。
一个LDPC码完整的网格结构非常大，会使得和—积算法难以实现。然而，一个[M×N]的LDPC码可以看成[M]个并行级联的单校验码，每个单校验码对应一个校验节点。如图2所示，一个单校验码可以表示成两个状态的有限长卷积码。每一个单校验码都可以通过Log-Map的算法来译码，即更新校验节点信息[Λ（xi）]的计算可以利用Log-Map算法。
Log-MAP的译码算法同样也在文献[9]中提出。具体内容如下考虑到[H]矩阵第[j]行有[n]个1，位置为{[j1，j2，???，jn]}，则对应的码字[x]中的{[xj1，xj2，....，xjn]}满足校验矩阵每行的偶校验约束，如果是[LLR]值，我们使用一种boxplus（
IEEE 802.11ac中LDPC码是准循环码（QC-LDPC），协议中定义了三种码长（648、1296、1944）和四种码率（1/2、2/3、3/4、5/6），总共12个矩阵。观察协议中的矩阵发现，矩阵每一行中1的个数最多为8个[11]。为了支持IEEE 802.11ac，输入数组[γ]和存储[γ]的数组[γ_stack]设为最大值8。因为在由C代码综合的过程中需要分配硬件资源，如果写成动态的参数，则综合不出结果，所以在数组定义时大小需设置具体的数值。根据算法，数组[α]、数组[β]、数组[α_temp]的最大长度为7。
两个循环的内部主要执行的都是条件分支。条件分支可以在并行中以分离的路径来执行，允许数据从一个任务流进里面有状态执行的下一个任务，导致系统有更高的性能。
下面是SISO主体部分的伪代码。
γ_stack、α_stack
LOOP1：
for k=0 to iter do
if k γ_stack[k] ← γ[k] end if if k==0 then α[0] ← γ[0] α_stack[0] ← α[0] end if if 0 α[k] DFU（α[k-1]，γ[k]） α_stack[k] ← α[k] end if if k==iter-1 then Λ[indexlast] ← α[k] end if end for LOOP2： for k=iter to iter2 then if k==iter then β[indexlast] ← γ[k] end if if iter β[index] ← DFU（γ_temp[index+1]，β[index+1]） end if if iter Λ[index] ←DFU（α_temp[index-1]，β[index-1]） end if if k==iter2-1 then Λ[0] β[0] end if end for 实现算法之后的C代码经过调试和仿真，如果功能正确将显示： 4.3 约束条件 在SISO模块中，当最大值为8时，LOOP1执行次数为7次，LOOP2执行次数也为7次，每次根据判断条件来执行相应的操作。根据伪代码，LOOP1本身没有并行性，因为[α]一次迭代的计算需要用到上一个迭代的值。但是LOOP1和LOOP2之间，一旦[α]的最后一个值有效就可以输出给[Λ]，并同时开始[β]和后续[Λ]值的计算。根据伪代码，[β、Λ]的值可以并行计算。因此对两个循环分别添加约束条件UNROLL，能使数据一有效就被执行使用，并可以并行执行循环内的操作。这个约束条件大大增加了吞吐率。 VivadoTM HLS工具在综合C代码时，有时会牺牲资源来换取算法并行度的增加，因而浪费了部分资源并增加了硬件延迟。根据伪代码，总共有3个DFU的函数调用，分别用来计算[α、β、Λ]的值。因此整个设计就只需要给[α、β、Λ]分别实例一个DFU。为了将资源的利用控制在一定的范围内，对SISO主函数添加约束条件ALLOCATION，规定设计中只有3个DFU函数的实例。
根据伪代码，输入参数是数组形式。在VivadoTM HLS中默认将数组参数综合成ap_memory类型的接口。这是一个标准块RAM接口，一般只使用双端口中的一个接口。根据SISO模块的硬件设计，外部连接的块RAM只需要使用单接口。为了防止VivadoTM HLS工具在综合C代码时增加并行度而使用双端口。对SISO主函数添加约束条件RESOURCE，规定数组使用的是一个单接口的块RAM。
对字长的优化能进一步提高设计的性能。根据SISO的设计要求，字长设定为8bit定点数。C代码的数据类型只支持8的整数倍字长，可RTL的总线支持任意字长。VivadoTM HLS中提供了一种支持任意精度字长的规范，可以在C代码的设计中使用尽可能小的位宽来减少硬件资源，但实现同样的功能。将数据设置为8bit定点数（7bit整数和1bit小数）比浮点数利用更少的资源。
下面是本次设计的字长配置。
4.4 C/RTL联合仿真
添加好约束条件后可以对C代码进行综合，根据综合后的结果和期望的要求进行迭代优化，最终实现最后的RTL设计。
为了验证RTL设计的正确性，综合完成后，利用VivadoTM HLS提供的C/RTL联合仿真功能，在选择Verilog进行仿真的情况下，HLS工具利用Test Bench给RTL代码提供激励，并将RTL的输出结果与正确结果进行比对，如果正确，显示如下。说明RTL的输出结果正确，SISO模块的延迟为16个时钟周期。
5 结果与性能
通过上述C代码综合出的硬件，当设为最大值8时，SISO的延迟是16个时钟周期，如果连续进数，之后每8个时钟周期计算输出8个数。产生的设计文件是基于FPGA器件xc7z020clg484-1。仿真结果最小时钟周期为10.65ns，也就是频率为93MHz，VivadoTM HLS生成的SISO模块资源利用情况如图5所示，共使用了129个寄存器，484个LUT。
文献[2]中更新校验节点的模块稳定工作在100MHz时，如果连续进数，更新12个数据需要12个cycle。与本文的设计一样，都平均一个时间周期计算输出一个数，只是本次设计的频率略低于文献[2]，但是本次设计直接通过C代码综合成硬件设计，周期短，开发简单，说明利用VivadoTM HLS软件进行硬件设计开发是可行的。
浮点和定点的LDPC译码器性能如图6所示。其中，LDPC译码器使用了Log-Map算法来更新校验节点信息。可以看出在10～20dB范围内，浮点和定点的性能是差不多的，只有当信噪比更高的情况下定点才比浮点差一些。
6 结论
本文采用Xilinx VivadoTM HLS设计方法完成了LDPC译码器中SISO模块设计。生成的硬件结构性能与手工Verilog完成的设计性能接近，但基于C语言的HLS设计和手工RTL设计相比，显著缩短了开发周期，减少了设计的复杂度。证明了具有较高复杂度的数字电路是可以通过HLS来进行高效实现的[12]。
参考文献：
[1] R. G. Gallager. Low Density Parity Check Code [M]. America： M.I.T. Press， 1963.
[2] 江涛. QC-LDPC码设计和分层译码器的FPGA实现[D]. 南京：南京航空航天大学，2011.
[3] 张玉凯. 准循环LDPC码的编译码器设计及FPGA 实现[D]. 西安：西安电子科技大学，2009.
[4] 徐欢，雷菁，文磊. 准循环LDPC码低存储量译码器设计与实现[J]. 重庆邮电大学学报，2010.22（6）： 771-774.
[5] 雷瑾亮，陈洪美，王爱华. 基于FPGA的准循环LDPC码低时延译码器设计[J]. 北京理工大学学报， 2013， 33（7）： 732-735.
[6] 姚远，叶凡，任俊彦. 采用并行分层译码的LDPC译码器设计研究[J]. 计算机工程与应用，2012， 48（4）：57-60.
[7] Xilinx. Vivado Design Suite User Guide High-Level Synthesis[Z]. 2014.
[8] Yang Sun， Joseph R. Cavallaro. Unified Decoder Architecture for LDPC/Turbo Codes[J]. Signal Processing Systems.2008， 13-18.
[9] Miquel Esteve Martin. Design of a Configurable LDPC Decoder for High-speed Wireless[D]. Spain： Universitat Politècnica de Catalunya， 2012.
[10] Xiao-Yu Hu， Evangelos Eleftheriou， Dieter-Michael Arnold， Ajay Dholakia. Efficient implementations of the SPA for decoding LDPC Codes[J]. IBM Research， Zurich Research Laboratory/IEEE GLOBECOM， 2001. 2：1036-1036E
[11] IEEE P802.11acTM/D4.0， Draft STANDARD for
Information Technology—Telecommunications and information exchange between systems—Local and metropolitan area networks—Specific requirements
Part 11： Wireless LAN Medium Access Control
（MAC） and Physical Layer （PHY） specifications[S]， 2012.
[12] Peyic M， Baba H， Guleyuboglu E， et al. A low power multi-rate decoder hardware for IEEE 802.11n LDPC codes[J]. Microprocessors and Microsystems， 2012，36（3）：159-166
