基于FPGA的不可分层LDPC码译码器

江 涛，仰枫帆

(南京航空航天大学电子信息工程学院，江苏南京210016)

0 引言

LDPC码［1］是近年来发展较快也日趋成熟的信道编码方案。具有准循环特性的QC-LDPC码已经成 为 IEEE 802.11n(Wi-Fi)、IEEE 802.16e(WiMAX)［2］、(DVB-S2)［3］等众多标准的信道编码方案。QC-LDPC译码器设计初期多采用部分并行译码结构［4］，此后分层译码［5］策略又被提出。分层译码策略因其更好的译码速度和性能以及更简单的硬件结构，逐渐成为QC-LDPC译码器的主流结构。但是分层译码要求LDPC码的伴随校检矩阵每一个分层中列权重不能大于1。而在DVB-S2，CMMB以及IEEE 802.15.3c等标准中采用的LDPC码不满足这一条件，称为不可分层码。文献［6］提出了一种并行分层置信度传播(Parallel Layered Belief Propagation，PLBP)译码算法，应用PLBP算法设计了一种适用于不可分层QC-LDPC码的高速译码器，并进一步优化了硬件结构，降低了算法实现复杂度。

1 QC-LDPC码的译码策略

置信传播(Belief Propagation，BP)算法是LDPC的标准译码算法，在它的基础上又可以改进得到最小和(Min-Sum)算法、归一化最小和(Normalization Min-Sum，NMS)算法等。此类算法皆通过校检节点更新和变量节点更新2个步骤完成一次译码迭代，因此又被称为2项迭代置信传播(Two phase Message Passing，TPMP)算法。TPMP算法因为在一次迭代过程中，全部校检节点更新完后，才对所有变量节点进行更新，所以一次迭代过程中，所有信息只能进行一次更新，收敛速度较慢，译码延时较大。虽然此后又提出了复用处理的方法［7］，但未能从根本上提升算法的收敛性和译码性能。

分层译码策略则改变了TPMP算法的译码方式，它将校检矩阵按行或列划分成若干分层。在一次迭代过程中，先并行更新第1分层中的所有校检节点和相关的变量节点，然后逐层进行更新。因此在一次更新过程中，后更新的分层会利用到前面已更新分层的输出信息，变量节点在此过程中得到多次更新，大大加快了译码的收敛速度，提高了译码性能。但为保证变量节点信息在各个分层之间能够进行传递，校检矩阵一个分层中的列权重必须不大于1。

2 并行分层置信传播译码算法

2.1 不可分层QC-LDPC码

通常QC-LDPC码采用分层译码时，将它校检矩阵中的一个子块行作为一个分层，但并非所有的QC-LDPC码这样分层都能满足上一节中所提到的分层译码策略对校检矩阵结构的要求。以图1中的码长8 192，码率为3/4的(3，12)正规QC-LDPC码为例。伴随矩阵由大小为128×128的子矩阵组成，其中含有很多和圈出的子矩阵类似的列权重为3的子矩阵，这些子矩阵都是由3个经过循环右移的单位矩阵组成。显然该矩阵不适于应用分层译码算法，称这样的 LDPC码称为不可分层 LDPC码。DVB-S2，CMMB以及IEEE 802.15.3c等系统中的LDPC都有类似的不可分层特点。对于这样的QCLDPC码，可以采用对分层译码算法进行改进后的PLBP算法，使其也能采用分层译码结构。

图1 码长8 192的不可分层(3，12)规则QC-LDPC的校检矩阵

2.2 PLBP 算法

PLBP算法解决不可分层QC-LDPC码译码的基本思路是改变传统QC-LDPC分层译码的分层方式。传统的分层译码是将QC-LDPC每一个子块行作为一个分层，分层内实行并行运算，分层与分层之间实行串行运算。PLBP算法则是从所有子块行中各取出一行，这些行两两之间不超过2个位置皆为1，将这些行组成一个分层，在该分层内可以实行并行运算，然后在这样组成的分层与分层之间实行串行运算。因为这些行两两之间不超过2个位置皆为1，所以它们所组成的分层的列权重必不大于1。

设高斯白噪声信道的噪声方差为σ2，接收到的信号序列为y，伴随矩阵H大小为M×N。迭代过程中信道固有信息Ln，校检节点信息Rmn，变量节点信息Lmn，其中0≤m≤M －1，0≤n≤N－1。以BPSK调制为例，以NMSA为基础，将PLBP算法的译码过程列述如下:

①初始化

②迭代过程(第t次迭代的第k层)Step1:分层更新

式中，当t=1时，设R(0)mn=0，m为属于第k层的校检节点;

Step2:译码判决

若L(t，k)n＜0，则c^n=1，否则c^n=0，更新译码结果 c^。

③译码结构校检

完成一次迭代后，对更新的译码结果进行校检。若满足c^×HT=0，或者迭代次数达到系统设置的最大迭代次数，则停止译码，输出译码结果;否则，跳回步骤②进行新一次迭代。

3 不可分层QC-LDPC译码器

3.1 译码器结构

对图1所示的QC-LDPC码进行译码器设计。该码的行权重为12，列权重为3，码长为8 192，码率3/4，子矩阵大小为128，共有16个子块行，64个子块列，192个非零子矩阵。采用PLBP算法实现该译码器，译码过程中只保存Ln和Rmn2种中间数据，变量节点信息则通过式(2)计算得出，以减小数据存储量。为便于硬件实现，可以选择α=0.75作为修正因子，这样只需要简单的带符号位右移和加法运算就可以完成数据修正。由于从16个子块行中各取一行组成一个分层，因此译码器的并行度为16，即共需要16个基本运算单元。对译码器中的数据进行6 bits量化，对计算过程中产生溢出的数据采用截位处理，这样的量化处理使译码性能大约有0.1 dB的损失，但大大节约了硬件资源。

图2为分层译码器硬件结构，下面将详细介绍译码器各模块的功能与结构。

图2 分层译码器硬件结构

(1)数据输入模块

接受解调模块输出的量化后的LLR数据，完成Ln的初始化。模块采用乒乓操作，即当其中一个存储器接收数据的同时，译码器读取另一个存储器中的数据进行译码，以此来提高译码器的吞吐量。

(2)数据存储模块

根据译码过程中存储数据的不同，存储模块划分为3块:① 后验概率存储模块Lmem，用于存储Ln。单个Ln的长度为6位，每一子块列对应的存储空间为6×128=768位，对应子块列数，共需要64个此类模块。②校检信息更新存储模块Rmem，用于存储Rmn，单个Rmn的长度为6位，每一行有12个非零元素，所以每行对应的存储空间为6×12=72位，而每一子块行所对应的存储空间为6×12×128=9 216位。对应子块行数，共需16个此类存储模块。③译码结果存储模块，用于存储译码结果。每一子块列对应的译码数据长度为128位，对应子块列数，共需64个此类存储空间。同样，为了提高吞吐量，译码数据输出模块也采用乒乓操作，当一个存储器进行译码结果更新的时候，另一个存储器中的译码结果向外设输出。

(3)校检节点更新模块(Parity-Check Update Block，PCUB)

校检节点模块是译码器的核心处理单元，完成迭代更新过程。共有16个PCUB模块进行并行处理，一次更新16组数据。每一组相关的12个变量节点信息串行输入PCUB中的FIFO寄存器，并逐次进行比较，寻找该组数据中的最小值与次最小值。当一组数据输入完成后，最小值与次最小值得以确定，再从FIFO寄存器中依次读出数据同最小值与次最小值比较，更新数据，PCUB的结构如图3所示。由PCUB的结构图可以看出，迭代译码过程主要被划分为2个阶段:变量节点信息输入FIFO阶段，变量节点信息输出FIFO阶段。这样的结构很适合采用二级流水线，当一组已输入的变量节点信息从FIFO中读取的时候，将下一组变量节点信息输入FIFO。通过二级流水线处理，提高了近一倍的数据吞吐率。

图3 译码器PCUB结构示意图

(4)地址生成模块

地址生成模块中包含一个保存伴随矩阵中所有子块位置和子块偏移量信息的只读寄存器(ROM)。通过从ROM中调取信息，分别产生Lmem和Rmem的读写地址。

(5)校检模块

校检模块在每一次迭代结束后，对所有校检方程进行验证，若全部满足则停止迭代，否则进行下一次迭代过程，直到达到设定的最高迭代次数为止。

(6)控制模块

控制模块中设置整个译码器的状态机，控制译码器各子模块有序运行。

3.2 译码器内存读取中的问题与改进

在介绍PCUB模块时已经了解，每一个校检节点对应的12个变量节点信息串行加入迭代过程，而这些节点信息存储在与子块列相对应的64个Lmem中。由于伴随矩阵的列权重为3，因此当16个PCUB并行从Lmem中读取数据时，如果按照伴随矩阵原本的结构，顺序读取变量节点信息时可能从某一子块列对应的Lmem中读取1～3个数据。图4为校验节点更新时PCUB读取Lmem顺序。

在图4(a)中列出了16个PCUB读取不同子块对应的Lmem的顺序。从中可以看到，在每组变量节点信息输入迭代译码的第1时刻。第2、9、11子块行对应的PCUB模块同时从第1子块列对应的Lmem中共读取3个数据，第8、15子块行对应的PCUB模块则同时从第2子块列对应的Lmem中共读取2个数据。这样不同的读取情况，会对Lmem的硬件设计引入更多的复杂度。

图4 校检节点更新时PCUB读取Lmem顺序

由于变量节点信息加入迭代过程的先后顺序并不影响译码结构，因此对变量节点信息的读取顺序稍作改进，如图4(b)所示，将原有的读取顺序重新排列，使得在同一时刻不同的PCUB从不同的子块列对应的Lmem中读取数据，即每一时刻Lmem最多提供一个数据，这就大大降低了Lmem的设计复杂度，提高了硬件的通用性。

4 FPGA实现

选用Altera公司的CycloneⅢ系列中的EP3C120器件，设置最大迭代次数为 5次，在QuartusⅡ10.0下完成综合和布局布线，硬件资源的消耗如表1所示。

表1 译码器硬件资源消耗统计

在译码过程中，首先花费128个时钟进行Lmem的初始化过程，完成后开始迭代译码。在每一次迭代过程中，核心的PCUB模块进行128次更新，由于是采用流水线结构，每次更新实际仅花费12个时钟，再加上第1组数据进入流水线花费的额外12个时钟，5次迭代共花费12×(128×5)+12=7 692个时钟。因此整个译码过程最多花费7 692+128=7 820个时钟。完成布局布线后，译码器的最高时钟频率可以达到45.44 MHz。此时译码器的吞吐量达到:(45.44 ×8 129)/7 820=47.60 Mbps。

由于仅有16个PCUB模块，译码器的并行度相对于普通的部分并行译码结构还比较低，因此数据的吞吐量还有限。可以通过将子层进一步划分，增加PCUB模块来提升并行度，以达到更好的译码吞吐速度。

通过图5中的性能曲线可以看到，将图1的不可分层QC-LDPC码用改进后的分层译码器处理后，在最大迭代次数同为5次的情况下，较采用传统部分并行结构译码具有更好的译码性能表现。

图5 部分并行结构与分层译码结构的译码性能曲线比较

5 结束语

基于PLBP算法，针对码长8 192，码率3/4的(3，12)规则不可分层QC-LDPC码设计了一种分层译码器。突破了不可分层LDPC码不能应用分层译码算法的局限，较传统的部分并行结构具有了更好的收敛性，降低了迭代次数要求。设计在Altera公司的CycloneⅢ系列FPGA上得以实现，达到了较高的译码吞吐量，且具有很强的通用性，仅需要修改部分参数就可以适用不同的不可分层LDPC码。

［1］GALLAGER R G.Low-density parity-check codes［J］.IRE Trans.on Inf.Theory，1962，IT －8(1)：21 －28.

［2］LDPC coding for OFDMA PHY.802.16REVe sponsor ballot recirculation comment［S］.IEEE C802.16e － 04 2004，7：639.

［3］Digital video broadcasting(DVB)，second generation［S］.ET-SI EN 302 307 v.1.1，2005.

［4］MARJAN K，JOSEPH R C.Semi-parallel reconfigurable architectures for real-time LDPC decoding ［C］∥Proceedings of the International Conference on Information Technology：Coding and Computing(ITCC04)Orleans，USA，2004，1(4)：579 －585.

［5］MANSOUR M M，SHANBHAG N R.High-Throughput LDPC Decoders［J］.IEEE Transaction on Very Large Scale Integration Systems，2003(11)：976 －978.

［6］郭琨，黑勇，周玉梅，等.一种应用于不可分层LDPC码的并行分层译码算法［J］.电子与信息学报，2010，32(8)：1956 －1960.

［7］SHIH Xin-yu，ZHAN Cheng-zhou，LIN Cheng-hung，et al.An 8.29 mm252 mW multi-mode LDPC decoder design for mobile WiMax system in 0.13 μm CMOS process［J］.IEEE Journal of Solid-state Circuits，2008，43(3)：672－683.