基于FIFO分段存储的QC-LDPC码部分并行译码方法

摘要

本发明公开了一种基于FIFO分段存储的QC-LDPC码部分并行译码方法，主要解决现有技术在QC-LDPC译码硬件实现中存在的大量地址控制逻辑的问题。其技术要点是：根据校验矩阵H的准循环特性，确定独立的译码单元，并对其分块；将译码更新过程转化成了独立译码单元的行更新和列更新；利用一组FIFO建立形成CFU存储空间和VFU存储空间，将存储单元进行连接，并加入切换信号；在独立译码单元的行更新和列更新时，通过切换信号对CFU存储空间和VFU存储空间进行选择，并通过对CFU存储空间或者VFU存储空间的内部循环移位完成。该译码方法操作简单，取消了硬件实现中的大量地址控制逻辑操作，便于在工程上实现QC-LDPC码的高速并行译码，可用于QC-LDPC码部分并行译码器的硬件实现。

说明书

技术领域

本发明属于通信技术领域，具体涉及一种基于先进先出FIFO的分段存储的准循环低密度奇偶校验QC-LDPC码部分并行译码方法，可用于高速QC-LDPC译码器的实现。

技术背景

LDPC码最早由Gallager于1962年首次提出，并与上个世纪90年代重新被研究。LDPC码是一种具有稀疏校验矩阵的线性分组码，具有以下特点：能够逼近香农限的性能特性，在许多场合下性能优于Turbo码；而且由于校验矩阵的稀疏性，译码的复杂度低，并可实现并行操作，便于硬件实现；具有较大的灵活性和较低的差错平层特性；描述简单，对严格的理论分析具有可验证性；具有简单的二分图编码的数学模型。LDPC码是近年信道编码领域的研究热点，目前已广泛应用于深空通信、光纤通信、卫星数字视频和音频广播等领域。

QC-LDPC码是一类特殊的LDPC码，其校验矩阵由一系列相同大小的稀疏矩阵组合而成，也就是说，其H校验矩阵具有准循环的特性。QC-LDPC码的校验矩阵表示形式如下：

$>H_{\mathrm{bM}\times \mathrm{bN}}=\left(\begin{array}{cccc}{A}^{\mathrm{1,1}}& A^{1,2}& \Lambda & A^{1,N}\\ A^{\mathrm{2,1}}& A^{\mathrm{2,2}}& \Lambda & A^{2,N}\\ M& M& O& M\\ A^{M,1}& A^{M,2}& \Lambda & A^{M,2}\end{array}\right)$>

A^i，j是大小为b×b的循环方阵，是由ω个单位阵循环右移的方阵相加而成，则A^i，j的行重和列重为ω，是中第一行“1”的位置。其中

LDPC码的译码算法主要包括和积算法SPA，最小和算法MS和改进最小和算法NMS。其中：

和积算法中，存在大量的tanh和它的反函数运算，这对于硬件实现来说，算法的复杂度依然很高；

最小和算法以及改进的最小和算法，其主要思想是对函数进行简化，把复杂的三角函数求取的过程简化为最小值和次小值的选取，且最小和以及改进算法，不用对信道噪声进行估计。现在在硬件实现时，LDPC译码运算中一般应用最小和或者其改进算法。下面给出在加性高斯白噪声信道下最小和算法的译码步骤：

1、初始化

Lui＝y_i＝m_vi

2、校验节点更新

计算每个校验节点将要传递给变量节点的值m^l_cji。在实际运算中，可以分为如下两个步骤执行：

(1)校验节点从与之相连的变量节点的信息中选取最小值和次小值，同时计算校验和，即

$>m_{\min \_j}^l=\underset{i\in \mathrm{Vcj}}{\min }\left(\right|m_{\mathrm{vij}}^l\left|\right)$>

$>m_{\min \_2\mathrm{nd}\_j}^l=2\mathrm{nd}\_\underset{i\in \mathrm{Vcj}}{\min }\left(\right|m_{\mathrm{vij}}^l\left|\right)$>

$>{\mathrm{sign}}_j^l=\underset{i\in \mathrm{Vcj}}{\Pi }\mathrm{sgn}\left(\right|m_{\mathrm{vij}}^l\left|\right)$>

(2)计算校验节点传递给变量节点的信息

如果是最小值，则

否则的话，有

3、变量节点更新

计算每个变量节点需要传递给校验节点的值

$>m_{\mathrm{vij}}^l=m_{\mathrm{vi}}+\underset{j^{\prime }\in \mathrm{Cvj}j}{\Sigma m_{c{j}^{\prime }i}^l}$>

4、判决

计算后验概率：

$>L_i=m_{\mathrm{vi}}+\underset{j^{\prime }\in \mathrm{Cvj}}{{\mathrm{\Sigma m}}_{c{j}^{\prime }i}^l}$>

然后对后验概率进行判决：当L_i＜0时，C_i＝1；当L_i≥0时，C_i＝0。

5、校验

最后对判决的输出进行判断：如果满足则结果满足校验方程，认为迭代结束；如果不满足上面的方程，表示结果错误，需要进一步迭代，返回步骤2。

QC-LDPC码的译码是根据H矩阵完成的，译码过程主要是变量节点更新VFU和校验节点更新CFU，它们分别按照H矩阵的行列进行更新。根据H矩阵的准循环特性，每一个A^i，j是一个独立的单元，A^i，j中每一条线对应一个存储空间每个存储空间包含b个存储单元。CFU和VFU更新，相当于更新每个中b个存储单元中的信息。中b个存储单元与A^i，j中每个非零位置节点一一对应。

进行CFU更新时，将ω个中每一行校验节点的非零位置对应存储空间的存储单元中的信息取出，连同H矩阵中其他位于同一行的(N-1)个A^i，j的一共ω×N个值进行CFU运算，将运算结果作为外信息存到原来的存储单元中，从而实现了校验节点对应的存储信息更新。CFU更新，是按照H矩阵的行进行的。

进行VFU更新时，将ω个中每一列变量节点的非零位置对应存储空间的存储单元中的信息取出，连同H矩阵中其他位于同一列的(M-1)个A^i，j的一共ω×M个值进行VFU运算，将运算结果作为先验信息存到原来的存储单元中，从而实现了变量节点对应的存储信息更新。VFU更新，是按照H矩阵的列进行的。

CFU和VFU更新采用同一个共享存储空间，由于A^i，j中ω个各不相同，在CFU更新时，存储空间的存取从第个存储单元开始；而在VFU更新时，存储空间的存取从第0个存储单元开始。CFU和VFU更新过程，存储空间的起始位置并不相同，这导致硬件实现中需要一定的控制逻辑，实现不同存取位置的对应。

LDPC译码器实现结构主要分为串行、并行和部分并行三种。完全并行结构，具有高的数据吞吐率，可以实现高速译码，但是这种方法占用的资源会随着数据块长度的增加而快速增加，导致资源消耗的代价过大，布局困难，而最终难以实现。串行结构，不会有资源消耗过高的问题，但当码长增加时，一次译码迭代所需时钟周期数也随之增加，这会导致数据吞吐率的急速下降。部分并行结构，是前两种结构的折中，达到了译码器数据吞吐率和资源占用的平衡。由于QC-LDPC校验矩阵具有准循环的特点，所以功能单元可以通过复用来减少资源的耗用，根据码字结构及实际系统的要求，有针对性的调整并行度的大小，兼顾资源消耗和速度问题，同时不以牺牲译码性能为代价。现在的QC-LDPC译码器一般采用部分并行译码。QC-LDPC采用共享存储的迭代译码结构如图1。

然而即使在采用部分并行译码方法的QC-LDPC译码器实现中，依然存在以下问题，导致译码的控制逻辑操作过于复杂：校验节点更新和变量节点更新时，存储空间的起始地址不同，这样对于不同的校验矩阵结构，当进行校验更新和变量更新时，需要对不同的存储空间分别进行读写地址初值写入操作，导致硬件实现中需要大量的控制逻辑进行地址控制。

发明内容

本发明的目的在于针对现有QC-LDPC译码器中地址控制逻辑操作复杂的缺点，提出一种基于FIFO分段存储的QC-LDPC码部分并行译码方法，减少对存储空间的读写地址初值的写入操作，取消硬件实现中的控制逻辑和地址控制，实现工程上的高速QC-LDPC译码。

为实现上述目的，本发明的一种基于FIFO分段存储的QC-LDPC部分并行译码方法，包括如下步骤：

(1)已知校验矩阵H_bM×bN由M×N个大小为b×b的循环方阵A^i，j构成，其中A^i，j由ω个b×b的单位阵循环右移次的方阵相加而成，这些方阵记为并以作为独立的译码单元，下标d的取值范围为1～ω，是方阵第一行中“1”的位置，称为起始地址，的取值范围为0～(b-1)；

(2)将独立的译码单元分成均匀的块，设块的大小为J×J，分成的块数K＝b/J，该块数K称为译码并行度，中第m行第n列的块用表示，并以作为最小的译码单元，中下标m和n的取值范围都为1～K；

(3)设起始地址的表达式为其中a是被J整除的最大整数，a称为空间起始位置，a的可能取值为0～(K-1)，β是除以J的余数，β称为偏移地址，β的可能取值为0～(J-1)；

(4)将一共K个最小译码单元合并成一个大块，记为则每个包含J行，b列，则把每一个作为译码时校验节点更新的最小更新单元，根据每个构建对应的一个CFU存储空间R’_m，下标m的取值范围是1～K，在每个周期内完成对K个最小更新单元中同一行的更新，经过J＝b/K个周期，完成对独立译码单元的行更新；

(5)将一共K个最小译码单元合并成一个大块，记为则每个包含b行，J列，则把每一个作为译码时变量节点更新的最小更新单元，根据每个构建对应的一个VFU存储空间R”_n，下标n的取值范围是1～K，在每个周期内完成对K个最小更新单元中同一列的更新，经过J＝b/K个周期，完成对独立译码单元的列更新；

(6)设译码过程的迭代次数为N，重复步骤(4)和步骤(5)N次，得到译码结果为C，直到满足译码终止条件时完成QC-LDPC码部分并行译码。

本发明具有以下优点：

(1)本发明由于根据实际要求适当改变独立译码单元均匀分块的块大小J，从而可以提高译码并行度，实现工程上的高速QC-LDPC译码。

(2)本发明由于把译码更新过程转化成了独立译码单元的行更新和独立译码单元的列更新，并在独立译码单元的行更新和独立译码单元的列更新过程中应用了CFU存储空间和VFU存储空间，从而减少了对读写地址初值的写入操作，并且取消了硬件实现中的控制逻辑和地址控制。

附图说明

图1是现有采用共享存储的QC-LDPC整个迭代译码结构；

图2是本发明的译码流程图；

图3是本发明在β＝0时构建的CFU存储空间示意图；

图4是本发明在β≠0时构建的CFU存储空间示意图；

图5是本发明用CFU存储空间重新组合构建形成的VFU存储空间示意图；

图6是本发明对CFU存储空间和VFU存储空间的初始化结果图。

具体实施步骤

下面参照附图，具体说明本发明的实施步骤。

参照图2，本发明的译码步骤如下：

步骤1，确定独立的译码单元。

QC-LDPC码的校验矩阵H_bM×bN具有准循环特性，校验矩阵H_bM×bN的表达形式如下：

$>H_{\mathrm{bM}\times \mathrm{bN}}=\left(\begin{array}{cccc}{A}^{\mathrm{1,1}}& A^{1,2}& \Lambda & A^{1,N}\\ A^{\mathrm{2,1}}& A^{\mathrm{2,2}}& \Lambda & A^{2,N}\\ M& M& O& M\\ A^{M,1}& A^{M,2}& \Lambda & A^{M,2}\end{array}\right)$>

A^i，j是校验矩阵H_bM×bN中大小为b×b的循环方阵，其中i的取值范围为1～M，j的取值范围为1～N，该A^i，j由ω个b×b的单位阵循环右移次的方阵相加而成，这些方阵记为并以作为独立的译码单元，下标d的取值范围为1～ω，是方阵第一行中“1”的位置，称为起始地址，的取值范围为0～(b-1)；

步骤2，对独立译码的单元分块，并确定最小译码单元。

将独立的译码单元分成均匀的块，设块的大小为J×J，分成的块数K＝b/J，该块数K称为译码并行度，中第m行第n列的块用表示，并以作为最小的译码单元，中下标m和n的取值范围都为1～K。

步骤3，将最小译码单元合并。

3a)将一共K个最小译码单元合并成一个大块，记为则每个包含J行，b列，则把每一个作为译码时校验节点更新的最小更新单元，每个对应一个CFU存储空间R’_m，下标m的取值范围为1～K；

3b)将一共K个最小译码单元合并成一个大块，记为则每个包含b行，J列，则把每一个作为译码时变量节点更新的最小更新单元，每个对应一个VFU存储空间R”_n，下标n的取值范围是1～K，在每个周期内完成对K个最小更新单元中同一列的更新，经过J＝b/K个周期，完成对独立译码单元的列更新，下标n的取值范围为1～K。

步骤4，计算起始地址a和偏移地址β。

起始地址的表达式为其中a是被J整除的最大整数，a称为空间起始位置，a的取值为0～(K-1)，β是除以J的余数，β称为偏移地址，β的取值为0～(J-1)。

步骤5，利用一组FIFO构建CFU存储空间和VFU存储空间。

5a)构建CFU存储空间

CFU存储空间R’_m，它由1～2个FIFO根据偏移地址β的不同取值和空间起始位置a构建：

参照图3，当β＝0时，构建的CFU存储空间为：每个CFU存储空间R’_m由一个深度为J的FIFO构成，每个FIFO包含J＝b/K个存储单元，并将来自信道的第(j-1)×b+{a×J+(u-1)×J+X}mod b个的待译码值存入CFU存储空间R’_u的第X个存储单元中，其中j为A^i，j中的上标中的j，j的取值范围为1～N，u表示第u个CFU存储空间，取值范围为1～K，X表示第X个存储单元，取值范围为1～J。每个存储单元都连接数据输入和数据输出线，数据输出线与相邻的前一个存储单元数据输入线连接，第1个存储单元的数据输出线与译码器中的校验节点更新单元的数据输入线连接，校验节点更新单元的数据输出线与第J个存储单元的数据输入线连接，这样构建形成CFU存储空间R’_m；

参照图4，当β≠0时，构建的CFU存储空间为：每个CFU存储空间R’_m由深度分别为J-β和β的两个FIFO组合而成，即SC1_m和SC2_m，其中SC1_m包含J-β个存储单元，SC2_m包含β个存储单元，则每个CFU存储空间R’_m包含J个存储单元。将来自信道的第(j-1)×b+{a×J+β+(u-1)×J+Y-1}mod b个的待译码值存入CFU存储空间R’_u中SC1_u的第Y个存储单元，且将来自信道的第(j-1)×b+{[(a+1)×J+(u-1)×J+Z-1]mod b}个的待译码值存入CFU存储空间R’_u中SC2_u的第Z个存储单元，其中j为A^i，j中的上标中的j，j取值范围为1～N，u表示第u个CFU存储空间，取值范围为1～K，Y和Z表示第Y个存储单元和第Z个存储单元，Y的取值范围为1～J-β，Z的取值范围为1～β。SC1_m和SC2_m中的每个存储单元都连接数据输入和数据输出线，数据输出线与相邻的前一个存储单元数据输入线连接，SC1_m中第1个存储单元的数据输出线与译码器中的校验节点更新单元的数据输入线连接，SC2_m中的第1个存储单元的数据输出线与SC1_m中第J-β个存储单元的数据输入线连接，校验节点更新单元的数据输出线与SC2_m中第β个存储单元的数据输入线连接，这样的构建形成CFU存储空间R’_m；

5b)构建VFU存储空间

VFU存储空间R”_n，它是根据偏移地址β的不同取值和空间起始位置a，通过对K个CFU存储空间R’_m调整顺序或重新组合构建：

当β＝0，调整K个CFU存储空间R’_m的顺序构建形成K个VFU存储空间R”_n，设第s个CFU存储空间R’_s为第t个VFU存储空间R”_t，s，t之间的关系为：

$>t=\left(\begin{array}{cc}s+a,& 1\le s\le K-a\\ s+a-K,& K-a+1\le s\le K\end{array}\right),$>

则每个VFU存储空间为一个深度为J的FIFO，每个FIFO包含J＝b/K个存储单元，每个存储单元都连有输入输出数据线，数据输出线与相邻的前一个存储单元的数据输入线连接，第1个存储单元的数据输出线与变量节点更新单元的数据输入线连接，变量节点更新单元的数据输出线与第J个存储单元的数据输入线连接，这样构建形成VFU空间R”_n；

参照图5，当β≠0，用CFU存储空间重新组合构建形成的VFU存储空间R”_q由SC2_p和SC1_p+1组成，其中SC2_p是CFU存储空间R’_p的一个FIFO，SC1_p+1是CFU存储空间R’_p+1的一个FIFO，下标p表示第p个CFU存储空间，下标q表示第q个VFU存储空间，p和q之间的关系为：

$>q=\left(\begin{array}{cc}p+a,& 1\le p\le K-a\\ p+a-K,& K-a+1\le p\le K\end{array}\right),$>

SC2_p包含β个存储单元，SC1_p+1包含J-β个存储单元，则VFU存储空间R”_q一共包含J个存储单元，SC2_p和SC1_p+1中的每个存储单元都连接数据输入线和数据输出线，数据输出线与相邻的前一个存储单元数据输入线连接，SC2_p的第1个存储单元的数据输出线与译码器中的变量节点更新单元的数据输入线连接，SC1_p+1的第1个存储单元的数据输出线与SC2_p中第β个存储单元的数据输入线连接，变量节点更新单元的数据输出线与SC1_p+1中第J-β个存储单元的数据输入线连接，这样构建形成VFU存储空间R”_q。

步骤6，对CFU存储空间和VFU存储空间初始化。

参照图6，对CFU存储空间和VFU存储空间的初始化过程为：完成FIFO之间的全部连接，并且在每个FIFO的末单元前加入一个二选一选择器和空间切换控制信号SW，其中SW信号用来对CFU存储空间和VFU存储空间进行选择，当空间切换控制信号SW＝1时，选择CFU存储空间的连接方式，在图6中虚线显示，此时形成CFU存储空间；当空间控制信号SW＝0时，选择VFU存储空间的连接方式，在图6中实线显示，此时形成VFU存储空间。

步骤7，独立译码单元的行更新。

在每个周期内完成对K个最小更新单元中同一行的更新，经过J＝b/K个周期，完成对独立译码单元的行更新，此过程是通过CFU存储空间R’_m的内部循环移位实现的。令空间切换控制信号SW＝1，选择CFU存储空间，从每个CFU存储空间的第1个存储单元取出存储信息送入校验节点计算单元，同时将每个CFU存储空间中的第2～J个存储单元中的存储信息逐个上移到第1～(J-1)个存储单元，并将校验节点计算单元的计算结果送入每个CFU存储空间的第J个存储单元，完成一次CFU存储空间R’_m的内部循环移位，重复上述操作J次后停止。

步骤8，独立译码单元的列更新。

在每个周期内完成对K个最小更新单元中同一列的更新，经过J＝b/K个周期，完成对独立译码单元的列更新，此过程是通过VFU存储空间R”_n的内部循环移位完成的，即令空间切换控制信号SW＝0，选择VFU存储空间，从每个VFU存储存储空间的第1个存储单元取出存储信息送入变量节点更新单元，同时将每个VFU存储空间中的第2～J个存储单元中的存储信息逐个上移到第1～(J-1)个存储单元，并将变量节点更新单元的计算结果送入每个VFU存储空间的第J个存储单元，完成一次VFU存储空间R”_n的内部循环移位，重复上述操作J次后停止。

步骤9，迭代译码完成。

设译码过程的迭代次数为N，重复步骤7和步骤8共N次，得到译码结果为C，直到满足译码终止条件时完成QC-LDPC码部分并行译码。