一种基于码字估计值的极化码早期迭代停止方法及装置

摘要

本发明公开了一种基于码字估计值的极化码早期迭代停止方法及装置，包括如下步骤：S1)预设BP译码的最大迭代次数；S2)利用BP译码算法对极化编码信息进行译码；S3)在每一次迭代过程中，均对当前迭代所得到的码字估计值

说明书

技术领域

本发明涉及一种极化码处理方法及装置，尤其涉及一种基于码字估计值的极化码早期迭代停止方法及装置。

背景技术

2008年在国际信息论ISIT会议上，Arikan首次提出了信道极化的概念，基于该 理论，他给出了人类已知的第一种能够被严格证明达到信道容量的信道编码方法， 并命名为极化码(Polar Code)。极化码基于信道极化进行设计。通过一个特殊的递 归编码过程对足够多个信道进行信道变换后，即N足够大时，会出现一部分极化信 道的容量趋于1，其余极化信道容量趋于0的现象。使用信道容量趋于1的子信道传 递有用信息，使用信道容量趋于0的子信道传递确定信息。

在极化码的实际译码中，串行抵消(Successive Cancelation,SC)算法与置信度传播(Belief Propagation,BP)算法是常见的两种算法。SC算法的计算复杂度较小。 通过列表译码策略或堆栈译码策略，改进的SC算法可以实现比原始SC和BP算法 更好的译码性能。但由于串行译码结构，导致其受到高译码延迟O(L)的影响，其 中L是码长。高译码延迟阻碍了极化码的广泛应用，特别是对于高速场景。

与SC译码不同，BP译码是一种迭代算法，是并行的。BP算法的计算复杂度为 O(I_aveN>ave为平均迭代次数。由此可知，对于BP译码器，其译码延迟>max。在达到最大迭代次数之前，BP译码将不会终止。这种终止方案缺乏灵活>

发明内容

本发明所要解决的技术问题是提供一种基于码字估计值的极化码早期迭代停止方法及装置，能够大大降低译码的计算复杂度和译码延时，同时便于硬件实现。

本发明为解决上述技术问题而采用的技术方案是提供一种基于码字估计值的极化码早期迭代停止方法，包括如下步骤：S1)预设BP译码的最大迭代次数；S2)利 用BP译码算法对极化编码信息进行译码；S3)在每一次迭代过程中，均对当前迭代 所得到的码字x估计值的变化率进行判断；如果连续多次迭代过程中的均未发生 变化，则停止迭代并输出当前迭代所得到的译码结果，否则，继续进行迭代，直至 达到预设的最大迭代次数。

上述的基于码字估计值的极化码早期迭代停止方法，其中，所述步骤S3)使用 码字估计值的变化率作为判断标准，若判断出在连续多次迭代过程中码字估计值均 未发生变化，则停止迭代并输出当前迭代所得到的译码结果。

上述的基于码字估计值的极化码早期迭代停止方法，其中，所述步骤S3)中使 用的码字估计值的计算如下：对于参数为(N，K)的极化码，其对应因子图由n＝log₂N>对最右端的 第n+1列节点中的软信息进行硬判决可得到码字x的估计值(i,j)表示从左起第i 行，第j列的节点；每个节点从右到左传递通过节点(i,j)的软信息记为L_i,j，从左到>i,j；所述步骤S2)先向左传播更新节点中的L_i,j，>i,j；迭代终止后，如果不是信息位则该位>i,1的符号判断信息位是0还是1。

上述的基于码字估计值的极化码早期迭代停止方法，其中，所述步骤S3)通过 组合使用硬判决、相等检测器与阈值比较器实现早期迭代停止机制；每次迭代中更 新到因子图第n+1列节点，即从BP译码器的PE中获得R_i,n+1，对R_i,n+1进行硬判决得>所述相等检测器从存储器中获取t-1次迭代的码字估 计值从硬判决模块获得所述相等检测器比较与是否相同，相同时输 出C＝1，否则输出C＝0；所述阈值比较器由加法器、寄存器与比较器构成，寄存器 中存储连续相同次数，若C＝1则加1，C＝0则清零；比较器比较存储器中存储的连 续相同次数与预设参数X的大小，若相等则输出D＝1，否则输出D＝0；D＝1则BP 译码器停止迭代输出译码结果，D＝0则BP译码器继续迭代直到达到预设的最大迭代 次数。

上述的基于码字估计值的极化码早期迭代停止方法，其中，所述预设参数X为 1～10，所述最大迭代次数预设为15～80。

本发明为解决上述技术问题还提供一种基于码字估计值的极化码早期迭代停 止装置，包括：BP译码器，采用迭代方式对极化编码信息进行译码，并预设最大迭 代次数；硬判决装置：取出每次迭代后的软信息符号位，获得当前迭代中码字的估 计值相等检测器：从存储器中获取上一次迭代的码字估计值比较与是 否相同，相同时输出C＝1，否则输出C＝0；阈值比较器：由加法器、寄存器与比较 器构成，寄存器中存储连续相同次数，若C＝1则加1，C＝0则清零；比较器比较存 储器中存储的连续相同次数与预设参数X的大小，若相等则输出D＝1，否则输出D＝0； D＝1则BP译码器停止迭代输出译码结果，D＝0则BP译码器继续迭代直到达到预设 的最大迭代次数。

上述的基于码字估计值的极化码早期迭代停止装置，其中，所述预设参数X为 1～10，所述最大迭代次数预设为15～80。

本发明对比现有技术有如下的有益效果：本发明提供的基于码字估计值的极化码早期迭代停止方法及装置，在每一次迭代过程中，均对当前迭代所得到的码字估 计值的变化率进行判断实现早期迭代停止机制。测试结果显示，与迭代次数固定为 40次的传统BP译码器相比，当信噪比为3.5dB时迭代次数可减少84.35％，从而大 大降低译码的计算复杂度和译码延时。综合结果显示，与已有的三种常见早期迭代 停止机制相比逻辑资源消耗可降低63.25％～96.88％，有效降低硬件资源消耗。已有 的早期迭代停止标准均依赖L_i,1或会造成额外译码延迟，本发明依赖不会造成 额外的延迟。

附图说明

图1为本发明参数为(8，4)的极化码因子图；

图2为本发明极化码因子图的基本单元示意图；

图3为本发明的硬件架构实现示意图；

图4为相等检测器硬件结构；

图5为阈值比较器硬件结构；

图6位本发明提出的早期迭代停止计算流程；

图7为本发明参数为(1024，512)的极化码，最大迭代次数为40的BP译码方 法与原始BP译码器的译码性能比较示意图；

图8为本发明参数为(1024，512)的极化码，最大迭代次数为40的BP译码方 法与原始BP译码器在不同信噪比信道下的平均迭代次数比较示意图。

具体实施方式

下面结合附图和实施例对本发明作进一步的描述。

在实践中，迭代译码器经常可以在迭代过程的早期阶段收敛或者不会收敛。也 就是说，在迭代次数达到I_max之前，译码可能已经成功。早期迭代停止算法是指在译>

本发明提供的基于码字估计值的极化码早期迭代停止方法，包括如下步骤：

S1)预设BP译码的最大迭代次数；

S2)利用BP译码算法对极化编码信息进行译码；

S3)在每一次迭代过程中，均对当前迭代所得到的码字估计值的变化率进行判断；如果连续多次迭代过程中的码字估计值均未发生变化，则停止迭代并输出当前 迭代所得到的译码结果，否则，继续进行迭代，直至达到预设的最大迭代次数。

本发明的基于码字估计值的极化码早期迭代停止方法，利用BP译码算法对极 化编码信息进行译码，信息更新公式如下：

f(x,y)≈α*sign(x)sign(y)min(|x|,|y|) (2)

使用码字的估计值的变化率作为标准，若在连续X次迭代过程中均未发生变化，则可认为此时的输出足够可靠，称为x辅助(x-aided)早期迭代停止标准。具 体公式如下：

即当满足上式时即可停止迭代。若不满足公式(3)，则继续进行迭代，直至达到 预设的最大迭代次数。相比现有技术方案，本发明能够在不造成译码性能损失的情 况下显著减小译码迭代次数，尤其在高信噪比信道中效果更为明显；并且该方法可 靠性强，硬件实现简单。

下面采用参数为(1024，512)的Polar码进行实施测试，码长为N＝1024，K＝512，码率为0.5。使用高斯近似方法在信噪比为1.5dB下仿真结果作为位置信息，调制方 式为二进制相移键控(Binary Phase Shift Keying，BPSK)，信道为加性高斯白噪声信 道(Additive White Gaussian Noise，AWGN)。码字由长度为1024的与生成 矩阵G相乘得到。生成矩阵表示矩阵的log₂1024＝10次克罗>1^N使用对数似然比(Log-likelihood>

参数为(1024,512)的极化码的因子图由log₂1024＝10阶处理单元(Processingelement,PE)和11列节点构成(码长为8的因子图如图1所示)，其中每阶由N/2＝512>的估计值对最右端的第11列节点中的软 信息进行判决可得到码字的估计值(i,j)表示从左起第i行，第j列的节点。 每个节点都有两种信息，本发明将从右到左传递通过节点(i,j)的信息记为L_i,j，将从>i,j，这些信息以LLR形式相互传递更新。

在译码过程中，预设迭代最大迭代次数为40次，先对R_i,1和L_i,11进行初始化。L_i,11初始化为信道接受值Y_i，R_i,1根据位置信息分别初始化为0和7位量化方案能表示的>

L_i,11＝Y_i>

公式中的A指的是信息位的集合。然后按照式(1)先向左传播更新节点中的L_i,j，到达最左侧后开始向右传播更新节点中的R_i,j。式(2)中的α设置为0.9，具体如公>

f(x,y)≈0.9*sign(x)sign(y)min(|x|,|y|) (6)

每次迭代过程中可依据以下两式得到码字估计值

为降低译码的计算复杂度和译码延时，同时便于硬件实现，本发明的思路是利 用码字的估计值的变化作为标准，参数X设置为1，若在连续1次迭代过程中未发生变化，则可认为此时BP译码器的输出足够可靠。具体公式如下：

若满足等式(9)，则此时的译码输出就可以认为是可靠的译码输出，迭代终止。 如果不满足条件，判断译码次数是否达到40次，若达到最大迭代就终止迭代；如果 没有，则继续更新信息，进行下一次迭代。

迭代终止后，如果不是信息位则该位译码为0，否则依照最左端的对数似然比 L_i,1(下标1表示第一列节点，即因子图最左侧的一列节点，i表示第i位)的符号判断信>

图3为本发明的硬件架构实现示意图，主要由相等检测器与阈值比较器构成。 每次迭代中更新到因子图第11列节点即可从BP译码器的PE中获得R_i,11，对R_i,11进>相等检测器从存储器中获取t-1次迭代的 码字估计值从硬判决模块获得相等检测器比较与是否相同，相同时 输出C＝1，否则输出C＝0。阈值比较器由加法器、寄存器与比较器构成，寄存器中 存储连续相同次数，若C＝1则加1，C＝0则清零；比较器比较存储器中存储的连续 相同次数与预设参数X＝1的大小，若相等则输出D＝1，否则输出D＝0。D＝1则BP 译码器停止迭代输出译码结果，D＝0则BP译码器继续迭代直到达到预设的最大迭代 次数。图4为图3中相等检测器的详细硬件结构，图5则为阈值比较器的详细结构。

图6为本发明在(N，K)极化码译码过程中的计算流程。已有的早期迭代停止 标准均会造成额外延迟，无法在获得之前判断是否进行下一次迭代，因为这些标准 都依赖于或者对进行硬判决后获得的如图6所示，t次迭代中的第n个时 钟后通过对进行判决可获得随后本发明只需要两个时钟即可完成早期迭代 停止判决，若满足本发明的早期迭代停止标准则计算对进行硬判决后获得译 码结果，随后停止迭代；若不满足本发明的早期迭代停止标准则进行下一次迭代。

图7显示了多种早期迭代停止标准与传统极化码BP译码器在高斯加性白噪声信道中的测试结果。图中横坐标Eb/N0为信噪比，图中FER为误帧率，图中BER为 误比特率，constant iterations表示迭代次数为常数，x-aided表示使用了本发明提出 的BP早期迭代停止译码方法。根据图7可看出本发明能在迭代次数显著少于传统 BP译码器的情况下，达到和传统BP译码器同样的译码性能。

图8显示了多种早期迭代停止标准与传统极化码BP译码器在不同信噪比信道中的平均迭代次数。图中Eb/N0为信噪比，Average number of iterations表示平均迭代 次数，x-aided表示使用了本发明提出的BP早期迭代停止译码方法。当最大迭代次 数为40且Eb/N0＝3.5dB时，与迭代次数固定为40次的原始BP译码器相比本发明的 平均迭代次数减少了84.35％。

下表为本实施的x-aided机制与另外三种已提出的早期迭代停止机制在StratixV 5SGXEA7N2F455C2中综合的结果，其中Q为LLR量化位数。

由表中可看出，在硬件资源消耗方面，与G-Matrix机制相比，Logic utilization与Registers的消耗分别减少63.25％与99.9％。与minLLR和LMA相比，Logic utilization的消耗分别减少72.44％和96.88％。

虽然本发明已以较佳实施例揭示如上，然其并非用以限定本发明，任何本领域 技术人员，在不脱离本发明的精神和范围内，当可作些许的修改和完善，因此本发 明的保护范围当以权利要求书所界定的为准。