Pipeline Design of LDPC Decoder Based on Frame-Interleaving

5G 标准采用准循环LDPC（Quasi-cyclic Low Density Parity Check, QC-LDPC）码，其校验矩阵可以用一个基图（Base Graph, BG）和相应的移位因子Z来表示，即基图中每个元素都展开为Z×Z大小的单位矩阵的循环矩阵，移位大小由Z和该元素值确定。特别地，元素“−1”展开为Z×Z的全零矩阵。3GPP会议确定5G LDPC由一个高码率校验矩阵进行码字扩展得到，根据基图可对校验矩阵进行划分，如图1所示。

图中A是维度4×k_b的密集矩阵，对应信息比特，B是维度4×4的双对角矩阵，对应校验比特，O是维度4×(m_b−4)的全零矩阵，D是维度(m_b−4)×(k_b+4)的稀疏矩阵，E是维度(m_b−4)×(m_b−4)的单位矩阵。[A,B]构成校验矩阵的核心H_core。5G标准的校验矩阵通过H_core扩展得到。

考虑到应用场景的多样性，5G给出了两个基图BG1和BG2以实现不同的码长和码率。表1列出了这两个基图的基本参数。从表中可以看出，两个矩阵的节点度分布不均匀，导致实际实现中存在内存访问冲突问题。

传统的LDPC迭代译码算法是基于全并行的泛洪调度^[13]，这种调度方式是以较大的资源消耗来换取较高的吞吐量。为了实现吞吐量和硬件资源的折中，文献[14]提出了分层译码算法，其基本思想是将校验矩阵按行分层，依次更新每层节点的信息，上一层更新的节点信息可以立即用于下一层的更新，其收敛速度是全并行调度的两倍。

在硬件实现中通常以Z行作为一层，由于准循环特性，层内变量节点具有完美的正交性，因此能实现Z个节点并行译码。为了便于表述，本文以一行作为一层，表2对译码过程出现的符号做了详细说明，调制方式为BPSK，在高斯信道下，译码过程如下。

在第一次迭代时，变量节点的后验概率信息根据信道接收的似然信息进行初始化，校验节点信息初始化为零：

初始化完成后开始译码迭代，逐层更新。

1）逐行更新第l层变量节点向校验节点传递的信息：

2）逐行更新第l层校验节点向变量节点传递的信息：

3）更新第l层后验概率：

4）译码结果判决：

令$ {\boldsymbol{r}} = {[{r_0},{r_1}, \cdots ,{r_n}]^{\rm{T}}} $，如果$ {\boldsymbol{Hr}} = 0 $，退出迭代，输出r为译码结果，否则返回步骤1）继续迭代，直到达到最大迭代次数。

上述译码过程中，最复杂的是步骤2），在实现中通常采用查表法，需要消耗大量硬件资源，因此一般采用低复杂度的归一化最小和算法（Normalized Minimum Sum, NMS）：

其中，

$\alpha \in [0.5,1]$称为归一化因子。相比于和积译码算法，NMS仅需计算最小值和次小值，在硬件设计中容易实现。

传统分层译码结构如图2所示，节点地址存储单元根据校验节点存储变量节点和校验节点的索引值，最小和计算单元和节点更新单元对应上述译码步骤2）和3），判决模块负责对译码结果进行检验，对应步骤4）。

为了提高译码吞吐量，通常采用流水线设计，然而流水线设计常常会导致内存访问冲突问题，主要发生在以下两个方面。

1）当前层在读取节点信息时，上一层的LLR值尚未更新和写入到存储器中，因此当前层无法获得最新的LLR值，即式(3)参与运算的实际是$ L_j^{(t)}(l - 2) $而非$ L_j^{(t)}(l - 1) $。节点更新采用了错误的LLR值。

2）当前层节点更新还没有完成，下一层的节点最小值就已经准备好，此时节点更新用的是下一层的最小值，即式(7)参与运算的实际是${M^{(t)}}(i + 1)$而非${M^{(t)}}(i)$。节点更新采用了错误的最小值。

本文提出的帧交错译码结构如图3所示，与传统译码结构相比，该结构主要有以下4点改进。

1） 插入一个帧控制单元，在多帧之间来回切换，根据帧索引信号选择进行译码的存储单元。

2） 采用一个FIFO作为多级缓冲结构，可以缓存多个最小值，当上层节点更新完成时，再将下层最小值从FIFO读出。该操作需要一个时钟周期，相应地增加一个流水阶级。

3） 插入一个译码输出选择器，使译码器可以在进行初始化时同时读出前一帧的译码结果，与传统结构相比，节省了额外用于存储译码结果的资源。

4） 采用乒乓式缓存机制，即将存储器分为两组，分别用于预存初始化信息和当前帧的译码，工作时交替使用，节省初始化信息需要的时间。

通常节点更新顺序是按照其在矩阵的位置逐个进行，若同一变量节点在连续两层中出现，其间距太小很容易发生访问冲突，因此有必要对节点进行层内重排序，使得同一变量节点间距足够长，且同一层的节点进行重排序不会影响译码性能。

若一个节点在连续两层中同时出现，称它在上一层的节点为父节点，在下一层的节点为子节点。一个节点可以同时是父节点和子节点。动态规划的基本思想是父节点提前更新，子节点推迟读取，使得父节点有足够的时钟周期完成更新。具体规划如算法1所示。

节点的位置关系着该节点在硬件实现中读写的先后顺序，即同一层位置靠左的节点优先读写，图4给出了一个具体的例子，图中黄色标识的节点代表符合移动条件的节点。以序号为7的节点为例，在进行重排序之前，该节点在层1到层2 的间距为6，在层2到层3的距离为4。经过重排序后间距都为8，足够的间距能够有效避免内存访问冲突。

算法 1　层内节点动态规划

for 校验节点每一层 do

　for 从右到左每个节点 do

　　if 该节点同时是父节点和子节点 then

　　　移动该节点至最左端

　　end if

　end for

　for从右到左每个节点do

　　if 该节点是父节点且非子节点 then

　　　移动该节点至最左端

　　end if

　 end for

　for从左到右每个节点do

　　if 该节点是子节点且非父节点 then

　　　移动该节点至最右端

　　end if

　 end for

end for

图5展示了在校验矩阵行重高度不对称的情况下，不同译码结构的时序分析。图中主要展示的是节点信息的读和写过程，整个流水结构包括5个流水阶级，在读取完一层节点的5个时钟周期后开始逐个写入节点信息。

可以看到，在没有采用帧交错结构的情况下，传统译码结构完成一次译码迭代需要插入11个空闲周期。文献[16]提出了简单的帧交错结构，但在行重高度不对称的情况下仍然存在内存访问冲突问题。本文在此基础上做了改进，插入了必要的空闲周期，平均每一帧插入两个空周期，相比传统结构提升了吞吐量。

除了以上对于帧交错结构的改进，结合本文提出节点动态规划问题，能够进一步减少空闲周期的插入，极大地提高吞吐量。

本实验选择长度为2176，速率为1/3，基图为BG1的LDPC码，交错帧数为3。根据上述推导，本结构的吞吐量Th为：

式中，F_clk代表译码器工作频率；n代表码字长度；n_c代表一次迭代所需要的周期，即基图的非零元数目；$ {\bar n_l} $代表平均迭代次数。为了实验更具有可比性，采用归一化吞吐量进行对比，有：

表3对比了本文提出的结构与已有文献在资源利用率和归一化吞吐量的比较，表中量化等级（6,8,6）表示6位初始LLR值，8位变量信息，6位校验信息；HUE表示单位资源的归一化吞吐量。从表中可以看到，虽然现有文献能够实现比本结构更高的吞吐量，但消耗了大量的资源。与已有文献相比，本文提出的结果能显著提高单位资源利用率。

本文针对5G LDPC码中行重高度不均匀导致的内存访问冲突问题，提出了一种多帧交错译码结构，结合了节点多级缓冲机制、乒乓机制和节点动态规划算法。该结构能很好地解决内存访问冲突问题，提高吞吐量。未来，将继续优化帧交错译码器结构，主要集中于提高译码器的灵活性和兼容性，支持5G LDPC更多矩阵更多并行度的译码。