0 概述

低密度奇偶校验码(Low Density Parity-check Codes, LDPC)是线性分组码, 其译码简单、性能接近容量限^[1]。文献[2-4]通过分层译码算法构造LDPC译码器, 使其无需存储变量节点信息, 降低了存储资源耗费, 且译码收敛速度比最小和(Min-Sum, MS)算法快。文献[5-6]提出一种双修正型最小和积译码算法, 该算法译码复杂度较低, 但吞吐量有一定的损失。文献[7-8]提出的交替译码框架, 能在同一时刻同时更新一帧校验消息和一帧变量消息, 两帧交替更新, 提高了吞吐量, 但需消耗较多的存储资源。本文在分层MS译码算法的基础上, 提出校验节点自更新译码算法, 并采用一种新的QC-LDPC码分层译码器结构, 以降低存储资源消耗和提高吞吐量。

1 分层译码算法

QC-LDPC码具有准循环特性, 其校验矩阵可表示为分块矩阵^[9]。

$ {\boldsymbol{H}}=\left[\begin{array}{cccc}{\boldsymbol{Q}\left(p_{11}\right)} & {\boldsymbol{Q}\left(p_{12}\right)} & {\cdots} & {\boldsymbol{Q}\left(p_{1 t}\right)} \\ {\boldsymbol{Q}\left(p_{21}\right)} & {\boldsymbol{Q}\left(p_{22}\right)} & {\cdots} & {\boldsymbol{Q}\left(p_{2 t}\right)} \\ {\vdots} & {\vdots} & {} & {\vdots} \\ {\boldsymbol{Q}\left(p_{s 1}\right)} & {\boldsymbol{Q}\left(p_{s 2}\right)} & {\cdots} & {\boldsymbol{Q}\left(p_{s t}\right)}\end{array}\right]_{s B \times t B} $

(1)

其中, B表示分块矩阵Q(p_ij)的阶数, 0≤p_ij≤B, i=1, 2, …, s, j=1, 2, …, j。当p_ij=0时, Q(p_ij)表示一个B阶全零矩阵; 当1≤p_ij≤B时, Q(p_ij)表示B阶单位矩阵I_B循环右移p_{i, j}位后得到的矩阵, 特别地, Q(B)=I_B。因此, 每个子块列重最大为1。H是一个sB×tB矩阵, 列重最大为s, 码长为n=tB, 设计码率为R=(t－s)/t。

根据每个子块的列重量分布, 可校验矩阵H按上述分块形式划分为s层, 每层对应B个校验节点c_{i, h}(i=1, 2, …, s, h=1, 2, …, B)。令x=(x₁, x₂, …, x_t)表示一个码字, x_j=(x_{j, 1}, x_{j, 2}, …, x_{j, B})表示由B个变量节点x_jl(j=1, 2, …, t, l=1, 2, …, B)构成的子码。根据分层方式, 可推得各个节点的相邻校验节点集为:

$ \begin{array} [c]{l} c_{i, h}=\left\{x_{j, l} : j=1, 2, \cdots, t ;\right. p_{i j}>0; \\ \qquad \qquad l=\left(p_{i j}+h-1\right) \bmod B+1 \} \end{array} $

(2)

第i层对应B个校验方程如下:

$ \boldsymbol{Q}\left(p_{i 1}\right) \boldsymbol{x}_{1}^{\mathrm{T}}+\boldsymbol{Q}\left(p_{i_{2}}\right) \boldsymbol{x}_{2}^{\mathrm{T}}+\cdots+Q\left(p_{i t}\right) \boldsymbol{x}_{t}^{\mathrm{T}}={\bf{0}}_{B \times 1} $

(3)

其中, 码字x的每个变量节点每层只出现在一个校验方程中。

分层最小和算法^[10]描述如下:基于第一层子方程组, 更新校验消息, 然后把校验消息代入到变量节点中更新变量消息。当完成第一层的变量消息更新后, 代入下一个分层校验消息和更新变量消息。每一层消息更新过程使用上一层发送的变量信息和初始校验信息。当所有分层都完成消息更新后, 一轮迭代译码更新完成。

分层最小和算法的特点是利用后验信息和校验信息来表示变量信息, 使变量信息无需储存, 降低了资源的消耗。但是分层最小和算法仍需要存储大量的校验信息以及后验信息, 且后验信息值的范围随着迭代次数的增加会慢慢变大, 需要花费更多比特去储存才能得到合理的性能。为减少存储资源的消耗, 提出校验节点自更新方法, 该方法基于分层最小和算法, 将后验信息融合到校验信息中, 避免了后验信息的储存, 从而减少译码器资源的开销。

在第k≥1次迭代中, 令q_{i, j}^k表示第i层的变量节点x_j接收的更新校验信息, γ_{i, j}^k是变量节点x_j从第i层发往第i+1层的更新变量信息, γ^k是第k次迭代更新的后验概率信息, i指层序号, n_i指与第i层校验节点相连的变量节点, n_i′∈N(i)\n_i是指除n_i外, 与第i层校验节点相邻的变量节点的集合, λ_i指信道信息初始值, α表示校正因子, 一般取α=0.75, 便于硬件实现。校验节点自更新译码算法的具体步骤如下:

步骤1  LDPC码初始化。初始化结果为:

$ \gamma^{0}=\lambda_{i} $

(4)

$ r_{i}^{0}=0 $

(5)

步骤2  LDPC码迭代过程(第k次迭代, 第i层更新)包括分层更新和译码判决, 具体分析如下:

1) 分层更新计算公式如下:

$ q_{i, j}^{k}=\gamma^{0}+\sum\limits_{c_{i^{\prime}} \in m\left(v_{j}\right), i^{\prime}>i} r_{i}^{k-1}+\sum\limits_{c_{i^{\prime}} \in m\left(v_{j}\right), i^{\prime}<i} r_{i}^{k} $

(6)

$ r_{i, j}^{k}=\alpha \prod\limits_{v_{j} \in N\left(c_{i}\right) \backslash v_{j}} \operatorname{sgn}\left(q_{i, j}^{k}\right) \times \min\limits _{v_{j} \in N\left(c_{i}\right) \backslash v_{j}}\left(\left|q_{i, j}^{k}\right|\right) $

(7)

$ \gamma^{k}=\gamma^{0}+\sum\limits_{{\text{c}}_{i} \in m\left(v_{j}\right)} r_{i}^{k} $

(8)

2) 译码判决。设译码码字c={c₁, c₂, …, c_t}, 若γ^k < 0, 则c_m=1;否则c_m=0。

步骤3  校验结果。若译码序列满足c×H^T=0或者译码次数已经达到最大迭代次数, 则停止译码; 否则重新执行步骤2。

2 高吞吐量译码架构设计

译码器的最大吞吐量表达式为:

$ T=\frac{f \times N \times R}{C \times I_{\max }} $

(9)

其中, f是工作频率, 单位是Hz, N是码长, 单位是bit, R是指码率, C是译码器每次迭代所花费的时钟周期数, 单位是s, I_max是最大迭代次数, T是吞吐量, 单位是bit·s^-1·Hz^-1。由于长码相对于短码性能更加优越, 因此在设计过程中, 一般采用长码。为提高吞吐量, 采用并行更新的方式更新数据, 但会增加输入输出的延迟, 导致译码过程不同步。在这段时间内, 译码模块处于等待状态无法更新, 使得吞吐量变低。式(9)中分母实际应该为(C×I_max+D), 因为D为额外时钟延迟, 所以达不到最大吞吐量。本文提出一种新的译码器结构, 通过改进输入、译码、输出3个模块, 可最大化减少D值, 实现3个模块的连续工作, 使译码器可达到最高吞吐量。

根据文献[11], 针对1/2码率的(2 304, 1 152)QC-LDPC码, 如图 1所示, 2 304为码长, 1 152为信息位长度, 每个子矩阵大小为96×96, 每个数字代表单位矩阵偏移量, 空白的地方表示零矩阵。实现连续译码的过程是:在输入过程中, 1个时钟周期输入2位信息, 传输1帧信息需要1 152个时钟周期, 传输2帧信息需要2 304个周期。在输出过程中, 1帧信息总长度为1 152位, 1个时钟周期输出1位信息, 输出2帧信息则需要2 304个时钟周期。在译码过程中, 2帧信息并行更新, 每次迭代更新要96个时钟周期, 将I_max和每次迭代更新所消耗的时钟数相乘, 结果为消耗的时钟m。当I_max取校验矩阵行数的值时, 时钟m值就是信息位长度1 152, 即译码消耗了1 152个时钟周期。输入和输出采用的是双倍频率时钟周期, 其耗费2 304个双倍频率时钟周期, 译码采用单倍频率时钟周期, 其耗费1 152个单倍频率时钟周期, 2 304个双倍频率时钟周期在时间上等同于1 152个单倍频率时钟周期, 即输入、输出、译码这3个过程所花费一样的时钟周期数, 因此可实现连续译码。

如果要完成上述译码框架, 那么矩阵某一列的偏移量相邻2个数值之差要比每一分层更新所消耗时钟周期数大, 否则无法完成一次完整的迭代。笔者采用修正偏移量的方法解决该问题。修正偏移量后的矩阵如图 2所示。

以修正偏移量后的检验矩阵H的第一列为例, 在译码过程中消息传递路径如图 3所示, 可以看出, 每行消息更新完成后传给偏移量偏小的行, 而偏移量最小的一行传递给偏移量最大的一行, 即73→48→33→27→12→73。

为增加吞吐量, 根据文献[12], 将原始框架拆分成3份, 拆分后的消息传递路径如图 4所示, 在相同时刻译码器可更新3个变量信息, 减少译码所花费的时间, 增加吞吐量, 但该框架的译码器存在一个问题, 那就是原先的子矩阵对应一个RAM, 而一个子矩阵变成3个矩阵之后, 相当于只需花费1个RAM的存储资源变成了花费3个RAM的存储资源, 因此增加了RAM的资源消耗, 这种框架是以增加存储资源的消耗为代价来达到提高吞吐量的目的。

为减少RAM资源消耗, 且能够在相同时间更新3个变量信息, 需要把相同偏移量所对应的变量信息的值储存到相同RAM中, 为了满足这一条件, 必须保证校验矩阵中同一列的偏移量模3结果相同, 才能使得并行更新的3个数据位于RAM相同地址。

3 译码器设计与实现

本文选择CCSDS标准的(2 304, 1 152)LDPC码来设计部分并行分层译码器, 该译码器的主要特点是:采用流水线设计方法, 能够有效增加解码器的工作频率。

3.1 译码器总体架构

译码器设计采用校验节点自更新算法, 提出高吞吐率的QC-LDPC码译码器框架, 该框架支持部分并行分层译码, 如图 5所示。本文方法由接收信道信息、信息存储器、校验信息处理、硬判决以及迭代译码控制等主要部分组成。迭代译码控制模块是译码器的核心, 各个子模块之间通过不同的时序进行控制, 每个存储器的读写地址、使能信号由地址生成器提供, 且初始化信息、外信息也是由不同的时序控制。

3.2 接收信道信息模块

接收信道信息模块是对信道似然比信息进行初始化, 初始化为接收到量化过后的译码信息。在接收信道信息模块中, 对信道似然比信息存储器的写入顺序操作与子矩阵偏移量大小有关系, 令偏移量为16, 似然比信息储存器对应的初始化操作如图 6所示, 0地址存入的值是偏移量对应第16个已更新校验信息的数据, 1地址存入的值是对应第17个已更新校验信息的数据, 2地址存入的值对应第18个已更新校验信息的数据。地址按顺序存入相应的数据, 不一样的偏移量对应不一样的接收信道信息模块, 共96个不一样的偏移量, 对应96个接收信道信息板块。

3.3 信息存储模块

信息储存模块包括校验信息和后验信息这2个储存模块, 校验矩阵H被分成12个分层, 且每个分层有一个专门的校验节点单元(Check Node Unit, CNU), 后验信息储存模块存储后验概率信息, 校验信息储存模块存储校验节点信息。每层的非零子矩阵对应一个后验信息储存模块和一个校验信息储存模块。在分层译码过程中, 每一个后验信息存储模块向CNU输出一个后验信息, 并从其他分层CNU中获取一个新的后验信息。同时, 每个校验信息储存模块向CNU输出校验信息, 并且从同一层CNU得到新的校验信息。本文采用单端口同时进行读写操作。因为校验矩阵H中有96个非零子矩阵, 所以后验信息储存模块和校验信息储存模块包含了96个单端口存储单元。

3.4 校验信息处理单元模块

校验信息处理单元模块是校验节点自更新算法中的核心单元, 对于校验信息的更新来说, 每一层采用一个CNU去执行一系列的功能, 主要包括加法、比较等, CNU成为最长的延迟路径。在新的译码算法中, 每个CNU需要对比8个信息, 找出其中的最小值、次小值及各自的地址。因此, 对比装置成了CNU中最关键的元素。2输入的比较器包含一个加法器和一个复用器, 3输入的比较器包含3个加法器、5个复用器和一些基础逻辑门。一个8输入的比较器是由多个2输入和3输入比较器构成。为减少关键路径延迟和提高工作频率, CNU被分割成3级流水寄存器。CNU的3级流水线结构如图 7所示。由式(6)可知, 在第1级中, 第一个加法器组将初始信道信息、前一次迭代得到的校验信息和本次迭代得到的校验信息相加得到VTC信息q₁~q₈。由式(7)可知, 在第2级中, 将第1级得到的VTC信息进行符号分离、比较选取最小值等操作, 重新合并端口的最小值与符号, 得到新的校验信息r₁~r₈。由式(8)可知, 在第3级中, 加法器将初始信道信息与第2级得到的校验信息r_i相加, 得到新的后验概率信息APP_new。

3.5 硬判决单元

LDPC译码器输出比特位由后验信息的符号位决定。在传统分层译码中^[13], 变量节点一般更新到最底层才开始进行硬判决。而部分并行分层译码却使用一种不同的方法来进行更新, 会使每一个分层在每次迭代过程中产生一个后验概率信息, 并且不同的分层之间同时工作。以修正偏移量后的校验矩阵的第1列为例, 第4层CNU从第13行开始更新, 第9层CNU从第1行开始更新, 第12层CNU从第81行开始更新, 根据修正偏移量后的校验矩阵, 分别对应第74行、第13行、第28行。第1列后验概率信息传递的路径是从第4层到第12层、第12层到第9层、第9层到第4层。在每次迭代结束之后, 第13列最后的后验概率信息储存在第12层, 第28列最后的后验概率信息储存在第4层, 第74列最后的后验信息储存在第9层。因此, 第1列的硬判决比特储存在3个不同分层的存储器中。

4 译码器性能

在译码器硬件实现中, 文献[14-16]以及本文提出的译码器均采用altera公司StratixIV系列的EP4SGX530, 由QuartusⅡ10.0综合后, 本文提出译码器的最高工作频率可达308.2 MHz。根据式(9)译码器吞吐量的计算, 当最大迭代次数为10时, 译码器的吞吐量为516.8 Mb/s。本文提出的译码器和其他译码器之间性能比较如表 1所示。

由表 1可以看出, 与文献[14-16]译码器相比, 本文译码器吞吐量较大, 且消耗的存储资源较小。因此, 本文译码器同时具有高效、复杂度低、吞吐量高、收敛速度快等性能, 有效解决了吞吐量与资源消耗的矛盾。

5 结束语

基于分层MS译码算法, 本文提出一种高吞吐量、低存储量译码器, 实现了(2 304, 1 152)LDPC码。通过修正偏移量提高译码器的吞吐量。同时, 将后验信息和变量信息融合到校验信息中, 从而减少译码器的存储资源消耗。仿真结果显示, 该译码器吞吐量较大, 且收敛速度较快。