流水线式LDPC译码器的FPGA设计与仿真

单元旭+崔闻

摘 要： LDPC码在深空通信中有很好的实用价值，同时LDPC码也被广泛应用于光纤通信、卫星数字视频和音频广播等领域。针对LDPC译码器提出一种新的设计思路，将流水线思想从译码算法本身扩展到译码器的整体设计中，设计出可以多帧并行且结构简单的译码器，最后从吞吐量和资源消耗两方面进行仿真验证。

关键词： LDPC； 译码器； 流水线； FPGA

中图分类号： TN91?34 文献标识码： A 文章编号： 1004?373X（2014）21?0015?04

Design and simulation of pipeline style LDPC decoder based on FPGA

SHAN Yuan?xu， CUI Wen

（School of Electronics and Information Engineering， Harbin Institute of Technology， Harbin 150001， China）

Abstract： LDPC code in deep space communication has very good practical value， and has been widely used in optical fiber communication， satellite digital video and audio broadcasting. A new method to design LDPC decoder is proposed. The idea of pipeline is abstracted from decoding algorithm and applied to the overall design of decoder. Based on this method， a decoder with simple structure， which can process multiple parallel frames， was designed. Its throughput and resource consumption were verified by simulation.

Keywords： LDPC； decoder； pipeline； FPGA

0 引 言

LDPC码已被广泛应用于深空通信、光纤通信、卫星数字视频和音频广播等领域[1]。在加性高斯白噪声信道环境下，BPSK调制时，归一化最小和译码算法能很好地平衡译码性能和算法复杂度，易于硬件实现[2]，且常以流水线的形式出现在译码器的设计中。本文针对LDPC译码器提出一种新的设计思路，将流水线思想应用到译码器的整体设计中，设计出可以多帧并行且结构简单的译码器，最后通过仿真对其性能进行验证。

1 归一化最小和译码算法的流水线化

归一化最小和译码算法分为两步迭代，即变量节点运算（VNP）与校验节点运算（CNP）。

VNP：

[qnm=Pn+m∈M（n）＼mrmn] （1）

CNP：

[rmn=n∈N（m）＼nsign（qnm）×minn∈N（m）＼nqnm×α] （2）

式中：[M（n）]表示[H]矩阵中第n列中1的所有位置；[N（m）]表示[H]矩阵中第m行中1的所有位置；[M（n）＼m]表示从[M（n）]中去掉第m行那个1之后的子集；[N（m）＼n]表示从[N（m）]中去掉第n列那个1之后的子集；Pn表示第n列对应的接收到的初始电平值；[qnm]表示本次迭代中第n列第m行那个1对应的变量节点运算结果；[rmn]表示本次迭代中第m列第n行那个1对应的校验节点运算结果；[α]为归一化因子。初始化时先进行VNP运算，此时的rmn均为0。每次进行VNP运算时可同时计算本次迭代的判决结果：

[Qn=Pn+m∈M（n）rmn] （3）

如果Qn≥0，则令第n列判决码字xn=0，否则xn=1。若[x]=[x1，x2，…，xn]满足[HxT=0，]则停止迭代，将[x]作为译码输出，否则继续迭代，直到满足[HxT=0]或达到最大迭代次数为止。

图1是对三输入VNP进行流水线化的一个实例，其中“扩位补零”是为了防止加法结果溢出，通过补零的方式增加输入数据的整数位；“截位”将绝对值超出原有位数范围的数据转化为原有位数下的极值；“添位”将判决码字[xn]附加在数据的末尾，便于在CNP运算时计算[HxT]对应各行的结果。

图2是对四输入CNP进行流水线化的一个实例，其中“相乘比较”结果的符号位为2个输入数据符号位的异或值，数据位为2个输入数据数据位中的较小者。为了便于硬件实现将[α]定[3]为0.75，即0.5+0.25，因此“乘以[α]”可以用移位相加来实现。同时CNP还应将四个输入的末位取出并进行异或运算，得出[HxT]对应本行的结果。

图1 三输入流水线化VNP

图2 四输入流水线化CNP

2 基于FPGA的流水线式译码器的结构设计

VNP与CNP的运算结果同时也是彼此的输入数据，将二者首尾相连就构成了一个流水线环路，如图3所示。如果以图1和图2的方法为例，VNP是6级流水线，那么在VNP中可容纳6帧数据，在CNP中可容纳3帧数据，两个RAM各1帧，那么在环路中总共可以实现11帧数据的循环并行处理。

图4是根据一个简单的LDPC码的校验矩阵画出的结构图，其中寄存器组“M”的位置与[H]矩阵中1的位置对应，“M”阵列将多个流水线环路交织在一起就构成了整个译码器。“M”由两个容量为2的RAM组成，容量为2是为了避免读写地址冲突，读写方式如图5中左图所示。

图3 流水线环路示意图

图4 流水线式译码器结构图

图5 VNP与CNP对“M”的读写方式

不过这种全并行结构却不适用于较长的LDPC码，如果给一个1 008×504的[H]矩阵中的每行与每列都配备一个CNP或VNP，硬件资源的消耗量是很大的[4]。QC?LDPC码可以解决这个问题。

图6所示是一个24×12的校验基矩阵，其中每个数字代表一个42×42的子矩阵，这些子矩阵都是由单位阵循环右移得到的，数字的大小表示单位阵循环右移的位数。此时译码器的结构就要与基矩阵相对应，即部分并行结构，译码器的并行处理能力将体现在单帧内部，VNP或CNP可以同时对多列或多行进行循环处理。但VNP与CNP不能同时对同一帧数据进行处理，因为那样会带来诸多问题[5]，解决的方法是让译码器对两帧数据并行译码，VNP对第一帧处理的同时CNP对第二帧进行处理，然后依次交替。每两帧为一轮，当两帧都译码成功或达到最大迭代次数时，才进行下一轮译码。

寄存器组“M”的位置与基矩阵中的数字对应，“M”由两个容量为42的RAM构成，读写方式如图5中右图所示，图中实线与虚线交替存在，在每轮译码中每个RAM始终与同一帧数据对应。以基矩阵中数字“17”对应的“M”为例，该列的VNP与该行的CNP对此“M”的读地址时序如图7所示。若VNP为6级流水线，那么VNP对“M”的写地址永远比读地址滞后6，CNP亦如此。

图6 （1 008，504）双对角QC?LDPC码校验基矩阵

图7 长码译码器VNP与CNP的读地址时序

在译码器启动时各模块的读写地址的相对关系就已确定并被永久保持，使得各条流水线环路按着正确的规则不停地运转下去。为实现“乒乓操作”，本文将Pn寄存器的容量扩大一倍，在译码器工作的同时把下一轮的初始值写入Pn寄存器的闲置区间。当本轮译码结束并且下一轮的初始值已被写入闲置区间时，只需控制模块发出区间切换信号，指示VNP将此刻Pn寄存器的读地址加或减84，译码器就很自然地进入到下一轮的译码工作中，而且这种切换可以随时进行，不必顾及当时各模块读写地址的位置。控制模块在发出区间切换信号后立即将内部的周期性计数器归零并开始重新计数，根据计数值在相应的时段上连续收集各个VNP与CNP得出的[xn]与[HxT]信息，当所有的[HxT]信息均为0或达到最大迭代次数时将[xn]输出，否则进入下一个计数周期。流水线式译码器的核心思想就是将整个译码过程流水线化，并尽量避免对流水线的干预，这样不仅可以实现多帧并行，还省去了每轮译码之间的准备时间，同时也让辅助模块的功能得到简化。

3 基于QuartusⅡ的仿真分析

本文采用CycloneⅢ系列EP3C120F780I7型号的FPGA芯片作为仿真平台，使用QuartusⅡ9.0作为开发工具，根据LDPC码长度的不同设计了两款译码器：码长为20 b的8帧并行短码译码器和码长为1 008 b的2帧并行长码译码器，二者码率均为[12。]译码器最高工作频率为117.65 MHz，稳定工作频率取110 MHz。

利用Matlab将编码后的码字进行BPSK调制，再通过AWGN信道，接收端信噪比为4 dB，最后进行取样量化得到初始值。初始值的量化位数[6]为8 b，包括1 b符号位，3 b整数位和4 b小数位。仿真前将初始值预先存入ROM中，并在仿真开始时向INPUT_FIFO中顺序写入。

图8为短码译码器的仿真时序图，图中judge1～ judge10为10个CNP得出的[HxT]对应各行的结果，在每个times区间里顺序输出本次迭代中各帧的[HxT]信息；times为迭代次数；signal为区间切换信号；checkout为译码完成信号，由于在第6次迭代时8帧数据对应的各行judge均为零，故checkout发出了一个高脉冲；answer为OUT_FIFO的输出，即译码码字，一轮译码后译码器串行输出8个20位数据。每次迭代需11个时钟周期，假设每轮需20次迭代[7]，那么短码译码器的吞吐量为[20×][8×110 MHz（11×20）]=80 Mb/s。

图8 短码译码器的仿真时序图

图9为长码译码器的仿真时序图，一轮译码后译码器串行输出24个42 b数据，即2帧码字的信息位。每次迭代需84个时钟周期，假设每轮需20次迭代，那么长码译码器吞吐量为[1 008×110 MHz（84×20）=132] Mb/s。

表1为全编译后QuartusⅡ给出的硬件资源消耗情况。

综上可见，与其他LDPC译码器相比[8?10]，在硬件资源消耗量大致相当的情况下，流水线式译码器具有较为突出的吞吐量。当然，本文设计的译码器仍有很大的优化空间，比如可以将8帧数据分成两组分别进行判决和输出，并在输出端对各组进行排序，这样就能降低平均迭代次数，进一步提高吞吐量。

图9 长码译码器的仿真时序图

表1 译码器硬件资源消耗情况

[资源名称＼&短码译码器＼&长码译码器＼&芯片总资源＼&Total logic elements＼&6 599＼&16 516＼&119 088＼&Total combinational functions＼&5 107 ＼&15 617＼&119 088＼&Dedicated logic registers＼&5 517＼&10 008＼&119 088＼&Total memory bits＼&7 304＼&147 476＼&3 981 312＼&]

4 结 语

本文针对LDPC译码器提出一种新的设计思路，将流水线思想应用到译码器的整体设计中，并利用Verilog语言设计出可以多帧并行且结构简单的译码器，其综合性能突出，且具有很大的优化空间，因此流水线式LDPC译码器具有很好的开发前景。

参考文献

[1] 杨雪飞，高俊.LDPC码在深空通信中的应用技术研究[J].现代电子技术，2009，32（23）：33?34.

[2] 孙汝杰.LDPC译码方法研究及应用[D].南京：南京理工大学，2012.

[3] 窦戈.基于CMMB标准的LDPC码译码研究与实现[D].南京：南京航空航天大学，2011.

[4] 江涛.QC?LDPC码设计和分层译码器的FPGA实现[D].南京：南京航空航天大学，2011.

[5] 袁瑞佳.LDPC码的高效编译码实现技术研究[D].西安：西安电子科技大学，2012.

[6] 吴斌，杨波，叶明.LDPC硬件实现中的数据量化位数选择及其性能仿真[J].信息通信，2012（2）：26?28.

[7] 吉晋龙.LDPC码的高速编译码器设计及FPGA实现[D].西安：西安电子科技大学，2013.

[8] 杨建平，陈庆春.IEEE802.16标准LDPC译码器设计和实现[J].通信技术，2010，43（5）：18?19.

[9] 王鹏，陈咏恩.高速LDPC码分层译码器设计[J].小型微型计算机系统，2009，30（11）：2294?2297.

[10] XIAO Peng， GOTO Satoshi. Implementation of LDPC decoder for 802.16e [C]// 2009 IEEE 8th International Conference on ASIC. [S.l.]： IEEE， 2009： 501?504.