Parallel Decoding Method with Multiple Sub-Decoders for Specific LDPC Code

MBBP算法是一个多个子译码器构建的并行译码系统^[6]，它的子译码器是由使用不同校验矩阵的BP译码模块构成。图1是MBBP算法的结构，其中子译码器${D_0}$中的基础译码模块使用基础校验矩阵${{{\mathit{\boldsymbol{H}}}}_0}$对输入进行BP译码，子译码器${D_i}(i = 1,2, \cdots ,N)$中扩展译码模块则使用了扩展校验矩阵${{{\mathit{\boldsymbol{H}}}}_i}$进行BP译码。

MBBP算法对信道接收序列${{y}}$的向量LLR值${{{\mathit{\boldsymbol{L}}}}_{{\rm{ch}}}}$同时做$N{\rm{ + }}1$个子译码处理，并获得候选的双极性表示码字${{{\mathit{\boldsymbol{\hat c}}}}_0},{{{\mathit{\boldsymbol{\hat c}}}}_1}, \cdots ,{{{\mathit{\boldsymbol{\hat c}}}}_N}$，即码元取值为“+1”或“−1”；最终输出的码字${{\mathit{\boldsymbol{\hat c}}}}$由LMS模块获得，即对平稳信道：

式中，$d({{\mathit{\boldsymbol{a}}}},{{\mathit{\boldsymbol{b}}}})$是向量${{\mathit{\boldsymbol{a}}}}$和${{\mathit{\boldsymbol{b}}}}$的欧几里得距离。

MBBP算法的性能取决于子译码器输出候选码字的误字率及其等价的误码率，进一步地，依赖于各个子校验矩阵的环结构。

mRRD算法与MBBP类似，由$N{\rm{ + }}1$个完全相同的子译码器${D_0},{D_1}, \cdots ,{D_N}$并行构成，但每个子译码器的内部构造与MBBP算法不同。mRRD算法的子译码器结构如图2所示。

mRRD算法第$i$个子译码器${D_i}$的译码流程是：

1)初始化：令$\theta $为单位置换；令$t = 0$；记BP译码输入为$ {{{\mathit{\boldsymbol{L}}}}}^{(0)}={{{\mathit{\boldsymbol{L}}}}}_{{\rm{ch}}}$；最大迭代次数为t₀。

2)第$t$次译码时：以${H_t}$对${{{\mathit{\boldsymbol{L}}}}^{(t)}}$进行BP译码，并输出软信息${{{\mathit{\boldsymbol{L}}}}^{(t + 1)}}$和硬判决码字${{\mathit{\boldsymbol{\hat c}}}}_i^{(t + 1)}$。

3)若${{{\mathit{\boldsymbol{H}}}}_0} {\left( {{{\mathit{\boldsymbol{\hat c}}}}_i^{(t + 1)}} \right)^{\rm{T}}} = 0$或$t + 1 = t_0$，则输出候选码字${{{\mathit{\boldsymbol{\hat c}}}}_i} = {{\mathit{\boldsymbol{\hat c}}}}_i^{(t + 1)}$并结束算法。

4)随机选取置换$\gamma \in {\rm{Per}}(C)$，令$\theta = \theta \gamma $；将$\theta $作用于基础矩阵${{{\mathit{\boldsymbol{H}}}}_0}$得到校验矩阵并记为${{{\mathit{\boldsymbol{H}}}}_{t + 1}} = g(\theta ,{{{\mathit{\boldsymbol{H}}}}_0})$；令$t = t + 1$，回到步骤2)。

由于自同构群中的置换作用于基础矩阵后得到的扩展矩阵具有和基础矩阵一样的环结构，因此可以保证每个子译码器的误码率没有结构性恶化。显然，mRRD算法构建的关键是找到码的自同构群。

对于构造LDPC码的扩展校验矩阵的许多方法而言，不经意的方法会导致矩阵中的短环更短也更多，将其用于子译码器中的BP处理时，难以有效改善译码性能。为获得适于多子译码器的扩展矩阵序列，本节首先分析短环导致译码性能恶化的机理和消除短环影响的途径，然后再给出一种可改善译码性能的扩展译码模块级联基础译码模块的子译码器结构。

BP算法是在校验矩阵的等效Tanner图上，计算变量节点的似然值并计算校验节点的信道外信息产出值，并在两类节点之间交换信息后再进行迭代计算的过程。若Tanner图中存在由某个变量节点至校验节点再至其他变量节点并最终回返至原变量节点自身的较短连接回路(即短环)，则环中各节点的信息难以在足够多的节点中遍历足够的交互与平滑处理，从而导致变量节点的似然值估计存在较大误差。因此，短环较多的校验矩阵通常无法获得良好的译码性能。

图3展示了Tanner图中短环的信息流动情况，其中图3a与3b分别是4环和6环的情况。实线代表第一次迭代时候的信息传递，段状虚线和点状虚线分别代表第2次和第3次迭代时候的信息流。

以图3a为例，第一次迭代的信息通过校验节点${c_1}$传给了${v_2}$。第二次迭代的时候，${v_2}$把信息经${c_2}$传回给了${v_1}$，完成了一次循环。图3b通过3次迭代完成了一次循环。

从图3可以看出，若迭代次数是短环环长的一半，则短环中流动的信息将不会再次流入原始起点，从而消除了由短环引起的节点信息估计存在误差的问题。

虽然，将BP算法的迭代次数设置为校验矩阵的最短环长的一半，可有效消除短环在译码中的影响。但是，此时BP算法无法输出有效码字。为了解决这个问题，本文提出一种在扩展BP之后级联基础译码模块的组合并行译码方法，其译码结构如图4所示。

由图4可见，本文设计的子译码器${D_i}$，$i = 1, $$ 2, \cdots ,N$，可以分为两类。第一类子译码器由一个扩展BP模块和一个基础译码模块级联构成。基于扩展校验矩阵${{{\mathit{\boldsymbol{H}}}}_i}$的扩展BP模块对信道输入${{{\mathit{\boldsymbol{L}}}}_{{\rm{ch}}}}$进行BP算法处理并获得外信息${{\mathit{\boldsymbol{L}}}}_{{\rm{ex}}}^i$。然后，${{\mathit{\boldsymbol{L}}}}_{{\rm{ex}}}^i$与${{{\mathit{\boldsymbol{L}}}}_{{\rm{ch}}}}$合并后由基于基础校验矩阵${{{\mathit{\boldsymbol{H}}}}_0}$的基础译码模块进行BP译码并输出候选码字${{{\mathit{\boldsymbol{\hat c}}}}_i}$。其中，扩展译码模块的迭代次数被设置为${{{\mathit{\boldsymbol{H}}}}_i}$中最短环长的一半。因此，${{\mathit{\boldsymbol{L}}}}_{{\rm{ex}}}^i$不受${{{\mathit{\boldsymbol{H}}}}_i}$中环结构的影响。第二类子译码器${D_0}$仅由基础校验矩阵${{{\mathit{\boldsymbol{H}}}}_0}$确定的译码模块构成，输入信道信息${{{\mathit{\boldsymbol{L}}}}_{{\rm{ch}}}}$并输出码字${{{\mathit{\boldsymbol{\hat c}}}}_0}$。这两类子译码器输出的候选码字${{{\mathit{\boldsymbol{\hat c}}}}_0},{{{\mathit{\boldsymbol{\hat c}}}}_1}, \cdots ,{{{\mathit{\boldsymbol{\hat c}}}}_N}$均通过一个LMS最大后验概率选出系统译码输出码字${{\mathit{\boldsymbol{\hat c}}}}$。

本文提出的并行组合译码方法的步骤如下：

1)初始化：设候选码字集合$S = \emptyset $；将信道接收值序列${{y}}$的向量LLR值${{{\mathit{\boldsymbol{L}}}}_{{\rm{ch}}}}$分别输入到$N{\rm{ + }}1$个子译码器。

2)子译码${D_i}$输出候选向量${{{\mathit{\boldsymbol{\hat c}}}}_i}$，若有${{{\mathit{\boldsymbol{H}}}}_0}{{\bf{\hat c}}_i}^{\rm{T}} = $$ 0$，则$S = S \cup \{ {{{\mathit{\boldsymbol{\hat c}}}}_i}\} $，$i = 0,1, \cdots ,N$。

3)当$N + 1$个子译码器译码结束后，若$S = \emptyset $，则译码结束并宣称译码失败。

4) LMS选出${{\mathit{\boldsymbol{\hat c}}}} = \arg {\min _{{{{{\mathit{\boldsymbol{\hat c}}}}}_i} \in S}}d({{\mathit{\boldsymbol{y}}}},{{{\mathit{\boldsymbol{\hat c}}}}_i})$为译码输出码字。

以本原多项式作为连接多项式的产生的线性序列是m序列，m序列的截段可以等价为一个LDPC码的码字。这种LDPC码可称为m序列码^[13]。由于m序列产生器是一个线性移位反馈寄存器，因此m序列码的编码开销极低。为了将并行组合译码方法应用于m序列编码上，本节先介绍该码的编码方法，然后分析其采样序列的约束关系，最后给出用这种约束关系构造扩展校验矩阵的方法。

记二元域上本原式为$f(x) = {x^k} + {x^p} + 1$，其中正整数$k\text{、}p$有$k > p$。再记迹函数${\rm{tr}}_1^k( \cdot )$是从域${\rm{GF}}({2^k})$到域${\rm{GF}}(2)$的映射^[14]。设$\alpha $是$f(x)$的根，$\beta $是$f(x)$确定的线性反馈移位寄存器的初始相位，则由该寄存器生成的m序列$({a_i})$可被描述为：

序列$({a_i})$的$n$长片段$({a_i})_{i = 0}^{n - 1}$能被由$f(x)$确定的约束关系所校验，即：

由此可以定义此序列片段$({a_i})_{i = 0}^{n - 1}$为一个分组码的码字。进一步，由于$f(x)$是三项式，由式(3)等价构成的校验矩阵是稀疏的，从而，可认为m序列片段$({a_i})_{i = 0}^{n - 1}$是LDPC码的码字。

由于${\rm{GF}}({2^k})$可表示为本原元$\alpha $的幂指数形式：

因此，${\alpha ^q} \in {\rm{GF}}({2^k})$是该有限域的本原元的充分必要条件为${\rm{gcd}}(q,{2^k} - 1) = 1$，其中${\rm{gcd}}(a,b)$是$a$和$b$的最大公约数^[14]。而且新找出的本原元${\alpha ^q}$能代替$\alpha $重新表示整个有限域，即：

记本原元${\alpha ^q}$是$k$阶本原式${f_q}(x)$的根，那么本原式${f_q}(x)$的形式为：

与$f(x)$生成序列$({a_i})$类似，以${f_q}(x)$为连接多项式的线性反馈移位寄存器通过初始相位$\,\beta $，可生成m序列$(a_i^{(q)})$：

比较式(3)可见，式(7)中的序列$(a_i^{(q)})$受到${f_q}(x)$的约束，即约束关系为：

事实上，序列$(a_i^{(q)})$是序列$({a_i})$的采样间隔为$q$的采样序列，即：

于是，码字序列$({a_i})_{i = 0}^n$的采样间隔为$q$的采样序列$({a_{qj + s}})_{j = 0}^{Q - 1}(s = 0,1, \cdots ,q - 1,{\rm{ }}Q = \left\lfloor {n/q} \right\rfloor )$同样满足${f_q}(x)$的约束关系。这些约束关系是：

根据以上分析，本文设计了一种构造扩展校验矩阵的方法。为满足${\rm{gcd}}(q,{2^k} - 1) = 1$的采样间隔$q$，构造扩展校验矩阵的步骤为：

1)生成$f(x)$约束下的m序列$({a_i})$。

2)通过采样间隔$q$对m序列进行采样，获得采样序列$(a_i^{(q)})$。

3)通过Berlekamp-Massey算法^[15]获得约束$(a_i^{(q)})$的本原式${f_q}(x)$。

4)通过式(9)将${f_q}(x)$对$(a_i^{(q)})$的约束关系转化为$({a_i})$的约束。

5)依照式(10)，将${f_q}(x)$对应向量做循环位移生成扩展校验矩阵。

由向量做循环位移生成的矩阵一定存在许多短环。因此，尽管该扩展校验矩阵不适合MBBP算法中的子译码器，但是能用于本文提出的并行组合译码方法中的子译码器。

在深空通信和极低信噪比等场合，必须利用极低码率纠错码的极限纠错能力。为示范这类应用，本节构造一个极低码率m序列LDPC码，选择本原多项式为$f(x) = {x^{89}} + {x^{38}} + 1$，设计码长为3000，码率约0.03。仿真性能指标为误码率，对比对象为该码的单译码器译码算法^[13]。

为验证子译码器个数对于误码率的影响，本文通过第3节提出的方法，以采样间隔$q = 3,5,7,9, $$ 11,13$构造出6个扩展校验矩阵，对应的本原式${f_q}(x)$分别如下：

不同信噪比下误码率仿真结果如图5所示。可见，译码性能随着子译码器个数增加而改善，但是子译码器个数大于5后，译码性能趋于稳定。

图6展示了不同译码方法下m序列码的误码率曲线，从图中可以看出，本文提出的并行组合译码方法比原单译码器译码算法有更好的性能，当误码率为${10^{ - 5}}$时，本文的方法比原单译码器译码算法提升约0.4 dB。

研究和设计适用于分组码译码的并行译码系统是提高分组码纠错性能的又一条有效途径，适用于编码复杂度低但译码复杂度可宽容的，例如深空探测信息回传地球等通信场合。

本文提出了一种新的多子译码器并行组合译码系统，消除了子译码器中BP译码模块里校验矩阵的短环对译码的影响，降低了构造适合的扩展校验矩阵的难度。针对m序列编码，本文提出了一种构造扩展译码矩阵的方法，以适用于本文提出的并行组合译码方法。仿真实验显示，在误码率为${10^{ - 5}}$时，本文提出的并行组合译码方法比原单译码器译码方法提升约0.4 dB。