一种基于提前终止迭代策略的极化码改进BP译码方法

技术领域

本发明属于计算机译码领域，特别涉及一种基于提前终止迭代策略的极化码 改进BP译码方法。

背景技术

极化码具有以较低的编译码复杂度达到香农限的能力，因此，在最近的几年 中引起了人们的关注。为了说明极化码的性能，Arikan给出了第一个译码算法 ——连续消除译码算法，即SC。之后，又有人又提出了一些改进的SC译码算 法。由于SC译码算法的本质，以上提出的算法都有较高的译码延迟以及较低的 输出等缺点，因此，在实际生活中的应用受到了影响。

BP作为一种并行译码算法，在Polar上的应用引起了人们很大的关注。 然而，这种算法需要大量的迭代次数，使得译码时需要计算大量的数据，具有较 高的计算复杂度。

发明内容

基于以上技术问题，本发明公开了一种基于提前终止迭代策略的极化码改进 BP译码方法，所述方法使用极化码的信息比特似然比的收敛情况作为BP译码算 法停止迭代的准则；所述方法包括以下步骤：

S100、输入：接收矢量r，最大迭代次数Max_iter，信道可靠度L_C，收敛 阈值ε，{ε|0＜ε＜1}；

S200、初始化：如果位于因子图中(i，1)的是信息比特，则F_i，1＝0， 否则$R_{i,1}^t=-\infty ,$t＝0，p＝0，$L_{i,n+1}^t=L_C*r_i;$

其中，表示在第t次迭代过程中，位于因子图中(i，j)处节点从左向右传递的 信息，即右信息；F_i，1表示因子图中第i行，第一列的节点收敛标记；t表示迭代 次数；p表示信息比特计数变量；i为因子图中的行索引；j为因子图中的列索 引；表示在第t次迭代过程中位于因子图中(i，j)处节点从右向左传递的信息， 即左信息；

S300、更新：根据下式(1)对因子图中每个节点先从右向左进行更新，然后 从左向右进行更新；

$L_{i,j}^t=g(L_{i,j+1}^{t-1},L_{i+N/2^j,j+1}^{t-1}+R_{i+N/2^j,j}^t)$

$L_{i+N/2^j,j}^t=L_{i+N/2^j,j+1}^{t-1}+g(L_{i,j+1}^{t-1},R_{i,j}^t)---\left(1\right)$

$R_{i,j+1}^t=g(L_{i+N/2^j}^{t-1}+R_{i+N/2^j}^t,R_{i,j}^t)$

$R_{i+N/2^j,j+1}^t=R_{i+N/2^j,j}^t+g(L_{i,j+1}^{t-1},R_{i,j}^t)$

其中g(x，y)＝-2arctan h(tanh(x/2)tanh(y/2))，tanh(x)为双曲正切函数， arc tanh(x)为反双曲正切函数。

S400、迭代：对于位于因子图中(i，1)的信息比特，判断该信息比特的收敛标 记F_i，1＝0是否成立，如果成立转至步骤S401；如果不成立，转至步骤S403；

S401、判断信息比特的与是否满足下式(2)，

$0.5*\left(\right|L_{i,1}^t-L_{i,1}^{t-1}|+|L_{i,1}^{t+1}-L_{i,1}^t\left|\right)<ϵ---\left(2\right)$

如果该信息比特的与满足上式(2)，则转至步骤S402；如果不满 足，则转至步骤S403；

S402、设置p＝p+1，F_i，1＝1，此时判断p＝K是否成立，K表示信息比特个 数；

如果p＝K成立，停止迭代；

如果p＝K不成立，转至步骤S403

S403、继续判断下一个信息比特；如果位于因子图中(i，1)位置的所有信息比 特作同样处理后，则t＝t+1，如果t＝Max_iter，停止迭代，否则转至步骤S300； 如果位于因子图(i，1)位置的信息比特没有处理完，则处理下一个信息比特，转至 S400；

S500、判决：停止迭代后，如果码字中第i比特的硬判结果否 则输出译码比特。

本公开改进的BP译码算法与原始BP译码算法相比，性能没有损失，并且 大大降低了译码复杂度；对于同一个码长，随着信噪比的增加，减少的迭代次数 逐渐增加，最终趋于平稳；对于不同的码长，随着码长的增加，在相应信噪比条 件下平均迭代次数是减少的。

附图说明

图1(a)参数为(8，4)的极化码的因子图，图1(b)处理元，其中表示在第t 次迭代过程中，位于因子图中(i，j)处节点从左向右传递的信息，即右信息；表示在第t次迭代过程中位于因子图中(i，j)处节点从右向左传递的信息，即左信 息；t表示迭代次数；i为因子图中的行索引；j为因子图中的列索引；N为码 长；

图2(a)为参数为(512，256)的极化码，改进的BP译码算法与原始BP译码算 法的比特错误率曲线比较，图2(b)为参数为(512，256)的极化码，改进的BP译码 算法与原始BP译码算法的平均迭代次数的曲线比较；其中红色曲线表示原始的 BP译码算法；蓝色表示改进的BP译码算法；

图3(a)为参数为(1024，512)的极化码，改进的BP译码算法与原始BP译码算 法比特错误率曲线比较，图3(b)为参数为(1024，512)的极化码，改进的BP译码算 法与原始BP译码算法的平均迭代次数的曲线比较；其中红色曲线表示原始的 BP译码算法；蓝色表示改进的BP译码算法；

图4(a)为参数为(2048，1024)的极化码，改进的BP译码算法与原始BP译码 算法的比特错误率曲线比较，图4(b)为参数为(2048，1024)的极化码，改进的BP 译码算法与原始BP译码算法的平均迭代次数的曲线比较。其中红色曲线表示原 始的BP译码算法；蓝色表示改进的BP译码算法；

具体实施方式

下面根据附图结合实施例对本公开进行具体的说明：如图1～4所示，参数为 (N，K)的极化码的因子图由n阶段、N(n+1)节点构成(n＝log₂N)(当N＝8， K＝4时，其中N为码长，K表示信息比特个数，因子图如图1(a)所示)，其中每 个阶段有N/2处理元(如图1(b)所示)，每个节点有两种信息：从左向右传递的信 息和从右向左传递的信息；为了防止BP译码过程中计算的溢出，所有传递的信 息都采用对数域的似然比。

我们现在对极化码的BP译码算法中出现的符号做出定义。

定义1：

●Max_iter：最大迭代次数，{Max_iter|Max_iter＞0，Max_iter∈Z}。

●t：迭代次数，{t|0≤t≤Max_iter，t∈Z}。

●i：因子图中的行索引，{i|1≤i≤N，i∈Z}。

●j：因子图中的列索引，{j|1≤j≤n+1，j∈Z}。

●在第t次迭代过程中，位于因子图中(i，j)处节点的信息：从右 向左传递的信息，即左信息。

●在第t次迭代过程中，位于因子图中(i，j)处节点的信息：从左 向右传递的信息，即右信息。

●码字中第i比特的硬判结果。

●r：码字通过信道后的接收矢量，r_n为其第n分量。

●L_C：信道可靠度，2/σ²，其中σ²为噪声方差。

极化码BP译码算法更新公式[6][7]：

$L_{i,j}^t=g(L_{i,j+1}^{t-1},L_{i+N/2^j,j+1}^{t-1}+R_{i+N/2^j,j}^t)$

$L_{i+N/2^j,j}^t=L_{i+N/2^j,j+1}^{t-1}+g(L_{i,j+1}^{t-1},R_{i,j}^t)---\left(1\right)$

$R_{i,j+1}^t=g(L_{i+N/2^j}^{t-1}+R_{i+N/2^j}^t,R_{i,j}^t)$

$R_{i+N/2^j,j+1}^t=R_{i+N/2^j,j}^t+g(L_{i,j+1}^{t-1},R_{i,j}^t)$

其中g(x，y)＝-2arctan h(tanh(x/2)tanh(y/2))，tanh(x)为双曲正切函 数，arc tanh(x)为反双曲正切函数。

极化码的原始BP译码算法步骤如下：

输入：接收矢量r，最大迭代次数Max_iter，信道可靠度L_C。

初始化：如果码字的第i分量为信息比特，则否则t＝0， $L_{i,n+1}^t=L_C*r_i.$

更新：以处理元为信息更新基本单位，根据(1)式对每个节点先从右向左进行更 新，然后从左向右进行更新。

判决：如果t＝Max_iter，停止更新；如果否则

我们从极化码的BP译码算法中看出，只有当译码迭代次数达到预先设置的 最大迭代次数时，译码才会终止，并且在译码过程中需要计算大量数据，因此译 码的复杂度很高，对此，本发明提出了一种提前终止迭代的策略。

在极化码的原始BP译码过程中，由于没有提前终止迭代的条件，每个节点 需要不停的更新，只有达到预先设置的最大迭代次数时，更新才能停止，此过程 中需要计算大量的数据，具有较高的计算复杂度，基于此，我们提出一种提前终 止策略，使译码可以提前终止，减少了计算复杂度。

我们知道在LDPC码的BP译码过程中，许多变量在很少的迭代次数后达到 很高的可靠度，在以后的迭代过程中，它们的符号和极性就不再改变。随着BP 译码的收敛，节点信息在更新前后的差值逐渐趋于零。由于极化码和LDPC码的 BP译码算法很相似，因此，根据极化码的信息比特的似然比收敛情况，当似然 比达到收敛时，可以停止迭代。在本文中，我们规定当极化码的信息比特的似然 比信息变化很小时，该信息比特已达到收敛。

在描述提前终止迭代策略之前，我们对下面的符号做出定义。

定义二：

●p：信息比特计数变量，{p|0≤p≤K，p∈Z}。

●ε：收敛阈值，[ε|0＜ε＜1}。

●F_i，1：因子图中第i行，第一列的结点收敛标记，F_i，1∈{0，1}。

对于参数为(N，K)的极化码，在BP译码过程中，我们规定：对于位于因子图 中(i，1)的信息比特，当与满足下面的(2)式时，该信息比特收敛。

$0.5*\left(\right|L_{i,1}^t-L_{i,1}^{t-1}|+|L_{i,1}^{t+1}-L_{i,1}^t\left|\right)<ϵ---\left(2\right)$

在每一次迭代译码过程中，判断信息比特收敛阈值F_i，1是否为0，如果不为0， 判断下一个F_j，1(j＞i)是否为0，如果F_j，1为0，判断该信息比特是否满足(2)式， 如果满足(2)式，则p＝p+1，F_j，1＝1，此时判断p＝K是否成立，如果成立，停 止迭代，否则继续判断下一个信息比特。当所有信息比特作同样的处理后，p＝K 仍不成立，则进行下一次迭代，t＝t+1。

极化码的改进BP译码算法具体步骤如下：

S100、输入：接收矢量r，最大迭代次数Max_iter，信道可靠度L_C，收敛 阈值ε，{ε|0＜ε＜1}；

S200、初始化：如果位于因子图中(i，1)的是信息比特，则F_i，1＝0， 否则$R_{i,1}^t=-\infty ,$t＝0，p＝0，$L_{i,n+1}^t=L_C*r_i;$

其中，表示在第t次迭代过程中，位于因子图中(i，j)处节点从左向右传 递的信息，即右信息；F_i，1表示因子图中第i行，第一列的节点收敛标记；t表示 迭代次数；p表示信息比特计数变量；i为因子图中的行索引；j为因子图中的 列索引；表示在第t次迭代过程中位于因子图中(i，j)处节点从右向左传递的 信息，即左信息；

S300、更新：根据下式(1)对因子图中每个节点先从右向左进行更新，然后 从左向右进行更新；

$L_{i,j}^t=g(L_{i,j+1}^{t-1},L_{i+N/2^j,j+1}^{t-1}+R_{i+N/2^j,j}^t)$

$L_{i+N/2^j,j}^t=L_{i+N/2^j,j+1}^{t-1}+g(L_{i,j+1}^{t-1},R_{i,j}^t)---\left(1\right)$

$R_{i,j+1}^t=g(L_{i+N/2^j}^{t-1}+R_{i+N/2^j}^t,R_{i,j}^t)$

$R_{i+N/2^j,j+1}^t=R_{i+N/2^j,j}^t+g(L_{i,j+1}^{t-1},R_{i,j}^t)$

其中g(x，y)＝-2arctan h(tanh(x/2)tanh(y/2))，tanh(x)为双曲正切函数， arc tanh(x)为反双曲正切函数。

S400、迭代：对于位于因子图中(i，1)的信息比特，判断该信息比特的收敛 标记F_i，1＝0是否成立，如果成立转至步骤S401；如果不成立，转至步骤S403；

S401、判断信息比特的与是否满足下式(2)，

$0.5*\left(\right|L_{i,1}^t-L_{i,1}^{t-1}|+|L_{i,1}^{t+1}-L_{i,1}^t\left|\right)<ϵ---\left(2\right)$

如果该信息比特的与满足上式(2)，则转至步骤S402；如果不满 足，则转至步骤S403；

S402、设置p＝p+1，F_i，1＝1，此时判断p＝K是否成立，K表示信息比特个 数；

如果p＝K成立，停止迭代；

如果p＝K不成立，转至步骤S403

S403、继续判断下一个信息比特；如果位于因子图中(i，1)位置的所有信息比 特作同样处理后，则t＝t+1，如果t＝Max_iter，停止迭代，否则转至步骤S300； 如果位于因子图(i，1)位置的信息比特没有处理完，则处理下一个信息比特，转至 S400；

S500、判决：停止迭代后，如果码字中第i比特的硬判结果否 则输出译码比特。

实施例1

在最大迭代次数为60，收敛阈值ε＝0.01的情况下仿真了参数为(512，256)的 极化码的改进的BP译码算法与原始BP译码算法的比特错误率曲线以及各个信 噪比下的平均迭代次数的曲线；结果如图2所示；图中曲线表明，参数为(512，256) 的极化码的改进BP译码算法与原始BP译码算法相比，性能没有损失，平均迭 代次数大大减少，在信噪比3dB时，平均迭代次数大约减少了80％，随着信噪 比的增加，平均迭代次数逐渐减少，最终趋于平稳。

实施例2

在最大迭代次数为60，收敛阈值ε＝0.01的情况下仿真了参数为(1024，512) 的极化码的改进的BP译码算法与原始BP译码算法的比特错误率曲线以及各个 信噪比下的平均迭代次数的曲线；结果如图3所示；图中曲线表明，参数为 (1024，512)的极化码的改进BP译码算法与原始BP译码算法相比，性能没有损失， 平均迭代次数大大减少，在信噪比3dB时，平均迭代次数大约减少了80％，随 着信噪比的增加，平均迭代次数逐渐减少，最终趋于平稳。

实施例3

在最大迭代次数为60，收敛阈值ε＝0.01的情况下仿真了参数为(2048，1024) 的极化码的改进的BP译码算法与原始BP译码算法的比特错误率曲线以及各个 信噪比下的平均迭代次数的曲线；结果如图4所示；图中曲线表明，参数为 (2048，1024)的极化码的改进BP译码算法与原始BP译码算法相比，性能没有损 失，平均迭代次数大大减少，在信噪比3dB时，平均迭代次数大约减少了80％， 随着信噪比的增加，平均迭代次数逐渐减少，最终趋于平稳。

改进的BP译码算法与原始BP译码算法相比，性能没有损失，并且大大降 低了译码复杂度；对于同一个码长，随着信噪比的增加，减少的迭代次数逐渐增 加，最终趋于平稳；对于不同的码长，随着码长的增加，在相应信噪比条件下平 均迭代次数是减少的。对于不同的收敛阈值ε，译码复杂度降低的程度也不相同， 随着ε的减小，平均迭代次数越来越多，复杂度越高；仿真结果表明，在ε＝0.01 时，效果较好，因此本文中的仿真曲线都是在ε＝0.01的条件下获得的。

本发明提出的一种基于提前终止策略的极化码的改进BP译码算法，通过比 较信息比特的似然比信息变化值与收敛阈值的大小，判断信息比特是否达到收 敛，当所有信息比特达到收敛时，停止迭代。仿真结果表明，该算法减少了平均 迭代次数。

本说明书中的各个实施例均采用递进的方式描述，每个实施例重点说明的 都是与其他实施例的不同之处，各个实施例之间相同相似的部分互相参见即可。 对于系统实施例而言，由于其与方法实施例基本相似，所以描述的比较简单，相 关之处参见方法实施例的部分说明即可。

以上对本发明所提供的方法，进行了详细介绍，本文中应用了具体个例对 本发明的原理及实施方式进行了阐述，以上实施例的说明只是用于帮助理解本发 明的方法及其核心思想；同时，对于本领域的一般技术人员，依据本发明的思想， 在具体实施方式及应用范围上均会有改变之处，综上所述，本说明书内容不应理 解为对本发明的限制。