CN105680883B - 一种极化码和多比特奇偶校验码级联的纠错编码方法 - Google Patents

Abstract

本发明公开了一种极化码和多比特偶校验码级联的纠错编码方法，该方法发送端编码器采用多比特偶校验码作为外码，极化码作为内码；接收端译码器采用修正的SCL译码算法进行译码。在纠错性能上，相对于采用SCL译码算法的中短码长非级联极化码，本发明可以显著提升系统的误帧率性能，并可明显突破后者不可突破的最大似然界限(ML Bound)；在工程实现上，本发明外码采用多比特偶校验码，编码简单，译码采用修正的SCL译码算法，译码过程中比特判决与偶校验联合进行，相对于原始SCL译码算法无译码复杂度的提升，有利于工程实现。

Description

一种极化码和多比特奇偶校验码级联的纠错编码方法

技术领域

本发明属于纠错编码领域，更具体地，属于一种提升极化码SCL译码算法纠错性能的级联系统设计方案，具体为一种极化码和多比特奇偶校验码级联的纠错编码方法。

背景技术

极化编码作为一种新型的接近香农限的编码方案提出后，由于理论完善、并且具有较低复杂度的编译码算法，有利于工程实现而被广泛研究。极化码SCL(SuccessiveCancellation List，连续消除列表)译码算法提出后，仿真结果表明该译码算法在较低复杂度O(L·N log(N))(L为路径数量，N为码长)下，译码纠错能力可以达到最大似然译码器的纠错能力。但是对于采用SCL译码算法的中短码长非级联极化码，其纠错性能仍然与香农极限存在较大差距，并且这个差距无法单独从增大路径数量进行弥补。因此，可以从级联极化码的角度，来提升极化码的SCL译码算法的纠错性能。

传统的极化码级联方案中，部分方案(例如级联LDPC(Low Density ParityCheck，低密度奇偶校验)码)由于得到的级联码的特性不适合SCL译码算法，因此相对于采用SCL译码算法的极化码而言，其纠错性能无明显提升；部分方案(例如级联CRC(CyclicalRedundancy Check，循环冗余校验)码)需要额外的CRC校验电路，因此带来一定的硬件开销。

发明内容

针对现有技术的以上缺陷或改进需求，本发明提出一种极化码和多比特奇偶校验码级联的纠错编码方法，目的在于降低编码复杂度，便于工程实现，并且在无明显提升译码复杂度和存储复杂度的情况下，显著提升极化码在SCL译码算法下的纠错性能，并且该性能明显优于最大似然译码器译码性能。

本发明提供的一种极化码和多比特奇偶校验码级联的纠错编码方法，该方法的编码过程如下：

步骤1 外编码器编码：信息比特序列在外编码器进行多比特偶校验编码，得到外码码字；

步骤2 外码码字映射：外码码字第一个至最后一个比特依次映射到极化码第一个至最后一个非固定比特；

步骤3 内编码器编码：对步骤2中极化码的非固定比特序列进行极化码编码，得到级联码码字。

作为上述技术方案的改进：步骤1中，外码码字中的校验比特可以集中于外码码字尾部，设码长为N，信息比特数量为M，校验方程数量为K，校验比特位置序号集合为P＝{M+1，M+2，M+3，...，M+K}，集合P中的元素表示在外码的这些比特位置上为校验比特，也即外编码器编码码字中，比特序列为信息比特，为校验比特。

上述步骤1中，外码码字中的校验比特也可以在外码码字中等间隔分布，设码长为N，信息比特数量为M，校验方程数量为K，外码码长为M+K，相邻校验比特的间距为其中，表示取x的下整数，校验比特位置序号集合为

上述步骤1中，外码码字中的校验比特还可以在外码码字中不等间隔分布，即越靠近外码码字前部，校验比特分布越分散，越靠近外码码字尾部校验比特分布越集中，按照校验比特位置分布的这种特征，得到校验比特位置序号集合P。

上述技术方案中，设码长为N，信息比特数量为M，校验方程数量为K，假设集中在尾部的校验比特的数量为K₁，则前面等间隔分布的校验比特的数量为K-K₁，在不等间隔分布下，校验比特的位置序号集合为：

所述多比特偶校验编码时，校验比特仅校验该比特之前的比特，而与之后的比特无关。

外码还可以替换为多比特奇校验码。

上述编码方法的译码采用修正的SCL译码算法进行译码，即译码信息比特时根据SCL译码算法进行比特判决，译码校验比特时，根据校验比特所在的偶校验方程中信息比特的判决结果进行校验得到。

总体而言，通过本发明所构思的以上技术方案与现有技术相比，具有以下有益效果：

1、本方案显著提升极化码纠错性能

采用SCL译码算法的中短码长非级联的极化码，其纠错性能趋近于最大似然译码器译码性能，纠错能力有限，并且即使增大SCL译码算法路径数量，误帧率性能不会明显改善，另外增大路径数量会线性增大算法存储复杂度和译码复杂度，不利于工程实现。在相同路径数量的SCL译码算下，本发明提出的级联方案与非级联的极化码相比，本方案的纠错性能提升显著，并且本方案的纠错性能可以明显突破最大似然译码器的纠错性能。

2、本方案无明显译码复杂度和存储复杂度的提升

本方案采用修正的SCL译码算法，相对于原始SCL译码算法而言，其主要区别在于：算法译码校验比特时，直接通过该校验方程信息比特的判决结果校验得到。因此虽然译码校验比特时需要进行偶校验，但是省略了原始SCL译码算法在译码这一类比特时产生的路径度量值排序、路径删减、路径复制等操作。本方案在存储复杂度上存在微弱的提升，也即需要在编码器和译码器上分别存储外码对应的校验方程等信息，K个校验方程的信息比特和校验比特位置信息的存储量相对于整个系统而言是微弱的。

3、本方案外码编码简单，易于实现

本方案外码采用多比特奇偶校验码，相对于其它级联的外码方案，本发明方法可以使外编码器的硬件电路设计简单，有利于工程实现。

附图说明

图1为原始的SCL译码算法示意图；

图2为本发明给出的级联方案的编译码流程图；

图3为本发明给出的三种确定偶校验码校验比特位置的示意图；

图4为本发明给出的修正的SCL译码算法示意图。

具体实施方式

由于奇校验码和偶校验码具有相同的性质和检错能力，因此本发明中级联的多比特偶校验码可以替换为多比特奇校验码，为了便于对本方案进行说明，本文外码均以多比特偶校验码为例进行说明。

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。此外，下面所描述的本发明各个实施方式中所涉及到的技术特征只要彼此之间未构成冲突就可以相互组合。

对于码长为N，发送信息比特数量为M的极化码，极化编码技术是通过一个极化电路将N个独立同分布的信道极化为N个比特信道(bit channel)，在这N个比特信道中，信道容量最大的M个比特信道上发送极化码信息比特，该比特信道称为非固定比特信道(unfrozen bit channel)，非固定比特信道上发送的比特也称为非固定比特(unfrozenbit)；其它N-M个比特信道称为固定比特信道(frozen bit channel)，固定比特信道上发送的比特称为固定比特(frozen bit)。

设极化码极化电路输入端输入序列为比特u₁到u_N依次在第1个到第N个比特信道上发送，极化码非固定比特信道序号集合为固定比特信道序号记为A^c，集合A中的元素满足当1≤i＜j≤M时，a_i＜a_j.则非固定比特序列记为极化码固定比特在收发两端已知，固定比特序列设置为全0。当已知M个信息比特时，可确定非固定比特序列u_A，从而确定极化电路输入端输入序列极化码编码为G_N为极化码生成矩阵。

极化码SCL译码算法是SC(Successive Cancellation，连续消除)译码算法的改进。SCL译码算法译码时从比特u₁到u_N依次进行判决，得到输入序列的译码结果。SCL算法译码过程中最多可保留L(L为SCL译码算法的参数)条译码路径，在译码u_i时，每条路径上已经译码出的序列唯一表征该路径。原始SCL译码算法步骤如下：

初始化输入：i＝1，路径数量L；

Step1：判断i是否小于等于N，是，则进入Step2；否，则进入Step5；

Step2：判断u_i是否为固定比特，是，则进入Step3；否，则进入Step4；

Step3：将当前每条路径上u_i的判决值设置为0；i＝i+1；返回Step1；

Step4：统计当前路径数量L′，当前每条路径在u_i处可取值0或1，从而得到2L′条备选路径，2L′条路径的度量值分别为该路径在u_i处取值0或1的概率：或若2L′≤L，保留2L′条路径；若2L′＞L，保留L条度量值最大的路径；i＝i+1；返回Step1；

Step5：从L条路径中输出路径度量值最大的一条路径上对应的判决序列判决序列中的非固定比特序列即为极化码信息比特序列译码结果；

Step6：结束。

如图1为码长为4的极化码采用SCL译码算法示意图，其中u₂为固定比特，(u₁，u₃，u₄)为非固定比特，路径数量L＝2，译码时，每条路径上在固定比特u₂处判决为0，其它非固定比特则根据路径度量值进行判决。

本发明提供一种极化码和多比特奇偶校验码级联的纠错编码方法，如图2所示，具体包括如下步骤：

步骤1 外编码器编码

对于码长为N，信息比特数量为M，校验方程数量为K的级联系统，则外码输入端信息序列的长度为M，输出的外码码字长度为M+K。设外编码器编码得到的码字为包含M个信息比特和K个偶校验比特。如图3所示，根据外码码字中K个偶校验比特的位置分布，本发明提供三种确定校验比特位置的方法：

方法一：校验比特集中于外码码字尾部。如图3(a)所示，校验比特位置序号集合为P＝{M+1，M+2，M+3，...，M+K}，集合P中的元素表示在外码的这些比特位置上为校验比特，也即外编码器编码码字中，比特序列为信息比特，为校验比特。

方法二：校验比特在外码码字中等间隔分布。如图3(b)所示，外码码长为M+K，相邻校验比特的间距为其中，表示取x的下整数，校验比特位置序号集合为

方法三：校验比特在外码码字中不等间隔分布。如图3(c)所示，方法三中，校验比特不等间隔分布的特征为：越靠近外码码字前部，校验比特分布越分散；越靠近外码码字尾部校验比特分布越集中。按照校验比特位置分布的这种特征，得到校验比特位置序号集合P。

具体实施中，方法三可采用上述方法一和方法二的一个联合形式，也即一部分检验比特集中于尾部，另一部分校验比特等间隔分布。假设集中在尾部的校验比特的数量为K₁，则前面等间隔分布的校验比特的数量为K-K₁，可知在不等间隔分布下，校验比特的位置序号集合为：

。当K₁＝0时，集合P₁为空集，此时方法三等效于方法一；当K₁＝K时，集合P₂为空集，此时方法三等效于方法二。

假设根据上述三种方法之一确定的校验比特位置集合记为p_j表示第j(j＝1，2，3，...，K)个校验比特在外码码字比特中的序号，校验比特所在方程中的信息比特位置将从集合S_j＝{1，2，3，...，p_j-1}中挑选构成集合T_j，从而保证校验比特仅校验该比特之前的比特而与该比特之后的比特无关。则校验比特的取值为：完成外码编码。

步骤2 外码码字映射

外码码字映射是指将外码码字中的各个比特通过该映射关系作为极化码编码输入的比特。设极化码的非固定比特信道序号集合为固定比特信道序号集合为A^c，极化码极化电路输入端输入序列记为极化码的非固定比特序列为固定比特取值为全0。外码码字映射到非固定比特序列u_A的方式为：外码码字的第一个比特x₁至最后一个比特x_M+K依次映射到非固定比特序列的第一个比特至最后一个比特也即满足或者

通过映射后可知，非固定比特信道a_P＝{a_i|i∈P}上发送为外码的校验比特；非固定比特信道上发送为外码第j，(j＝1，...，K)个校验比特；非固定比特信道上发送为外码第j个校验方程的信息比特。

步骤3 内编码器编码

通过步骤2得到内码极化码非固定比特序列极化码固定比特序列为全0，从而可知极化码极化电路输入端输入序列根据极化码编码公式，从而可得级联系统编码的码字为其中G_N为极化码生成矩阵。

步骤4 接收端译码

级联系统译码器采用修正的SCL译码算法。主要修正的是：译码校验比特时，根据校验比特所在的偶校验方程中信息比特的判决结果进行校验得到，而不是根据原始SCL译码算法中的概率进行判决。

具体译码步骤如下：

初始化输入：i＝1，路径数量L；

Step1：判断i是否小于等于N，是，则进入Step2；否，则进入Step7；

Step2：判断u_i是否为固定比特，是，则进入Step3；否，则进入Step4；

Step3：将当前每条路径上u_i的判决值设置为0；i＝i+1；返回Step1；

Step4：判断u_i是否为校验比特，是，则进入Step5；否，则进入Step6；

Step5：当前每条路径上u_i的判决值通过该路径上判决的信息比特校验得到：i＝i+1；返回Step1；

Step6：统计当前路径数量L′，当前每条路径在u_i处可取值0或1，从而得到2L′条备选路径，2L′条路径的度量值分别为该路径在u_i处取值0或1的概率：或若2L′≤L，保留2L′条路径；若2L′＞L，保留L条度量值最大的路径；i＝i+1；返回Step1，表示接收序列，表示在译码u_i时，每条路径译码出的序列，其上角标^表示判决值；

Step7：从L条路径中输出路径度量值最大的一条路径上对应的判决序列

Step8：结束。

在译码结果中，即为外码码字译码结果，令集合则即为发送的信息比特译码结果。

图4所示为本方案一个码长为4的级联码，校验方程为采用修正的SCL(路径数量L＝2)进行译码的示意图，由图可知，两条路径在译码u₃比特时，该比特的判决值直接根据的校验结果得到，而不根据SCL译码算法的路径度量值进行判决。

下面以一个实施例来说明本发明方法，具体如下。

实施例：

本发明实施例为，级联码码长为N＝512，信息比特数量为M＝240，校验方程的数量为K＝16，从而可知内码极化码非固定比特信道的数量为256，固定比特信道的数量为256，在2dB下进行极化码构造，分别得到非固定比特信道的序号集合和固定比特信道序号的集合A^c.接收端译码器采用修正的SCL译码算法，路径数量设置为L＝32。

步骤1外编码器编码

信息比特数量为240，校验方程数量为16，则外码码长为256，记外码码字为根据上述说明的校验比特位置序号集合P确定的三种方法并结合实施例，依次得到集合P如下：

方法一，校验比特集中于外码码字尾部。这表明在外码的比特中，后16个比特，也即为偶校验比特；前240个比特，也即为信息比特，则集合P＝{241，242，243，244，245，246，247，248，249，250，251，252，253，254，255，256}。

方法二，校验比特在外码码字中等间隔分布。这表明在外码的比特中，x_1×16，x_2×16，x_3×16，...，x_16×16为校验比特，其余240个比特为信息比特，则集合P＝{16，32，48，64，80，96，112，128，144，160，176，192，208，224，240，256}。

方法三，校验比特在外码码字中不等间隔分布。假设在不等间隔分布中，集中在尾部的校验比特的数量K₁＝8，前面等间隔分布的校验比特数量为K-K₁＝8，这表明在外码的比特中，x_1×31，x_2×31，x_3×31，...，x_8×31，x₂₄₉，x₂₅₀，x₂₅₁，...，x₂₅₆为校验比特，其余240个比特为信息比特，结合本例，则集合P＝{31，62，93，124，155，186，217，248，249，250，251，252，253，254，255，256}。

以方法二得到的集合P为例说明每个校验方程中信息比特位置的确定，以及每个偶校验方程的编码。

已知P＝{16，32，48，64，80，96，112，128，144，160，176，192，208，224，240，256}，也即第一个校验方程的校验比特为x₁₆，该方程中信息比特的位置将从集合S₁＝{1，2，3，...中挑选，集合S₁中的元素按照概率α＝0.5选择是否参与该校验方程，从而得到第一个校验方程信息比特位置集合为T₁＝{6，8，10，11}，因此第一个校验比特x₁₆的编码公式如下：

按照上述方式可以确定另外15个校验比特的取值，从而完成外码编码。

步骤2外码码字映射

已知外编码器得到的码字为极化码非固定比特信道集合为A＝{a₁，a₂，a₃，...，a₂₅₆}，将码字的第1个至256个比特依次映射到极化码第1个至256个非固定比特，则极化码非固定比特序列为

映射后可知，非固定比特信道a_P＝{a_i|i∈P}上发送外码的校验比特；非固定比特信道上发送为外码第j，(j＝1，...，16)个校验比特；非固定比特信道上发送为外码第j个校验方程的信息比特。以方法二得到的P＝{16，32，48，64，80，96，112，128，144，160，176，192，208，224，240，256}为例，则a_P＝{a_i|i∈P}＝{a₁₆，a₃₂，a₄₈，a₆₄，a₈₀，a₉₆，a₁₁₂，a₁₂₈，a₁₄₄，a₁₆₀，a₁₇₆，a₁₉₂，a₂₀₈，a₂₂₄，a₂₄₀，a₂₅₆，}，发送外码校验比特；非固定比特信道上发送外码第1个校验比特；非固定比特信道上发送外码第1个校验方程的信息比特。依次可以得到等情况。

步骤3内编码器编码

通过步骤2得到内码极化码非固定比特序列极化码固定比特序列为全0，从而可知极化码极化电路输入端输入序列根据极化码编码公式，从而可得级联系统编码的码字为其中G_N为极化码生成矩阵。

步骤4级联系统的译码

级联系统的译码采用修正的SCL译码算法，该算法与原始SCL译码算法的主要区别在于，译码校验比特时，校验比特判决值直接根据该校验方程的信息比特判决值进行校验得到。以第一个校验方程为例，当32条路径译码到比特时，对于比特的判决则根据第一个校验方程中信息比特的判决值进行校验得到，具体公式如下：

而对于集合P之外的非固定比特信道上的比特判决，则根据SCL译码算法的译码原理进行判决。按照这种修正的SCL译码算法，从而可以得到级联码的译码结果在译码结果中，即为外码码字译码结果，令集合则即为发送的信息比特译码结果。

本领域的技术人员容易理解，以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。

Claims (6)

1.一种极化码和多比特奇偶校验码级联的纠错编码方法，该方法的编码过程如下：

步骤1外编码器编码：信息比特序列在外编码器进行多比特偶校验编码，得到外码码字，当所述信息比特序列在外编码器进行多比特偶校验编码时，每个校验比特仅校验该校验比特之前的比特，而与之后的比特无关，所述校验比特集中于外码码字尾部、在外码码字中等间隔分布或在外码码字中不等间隔分布；

步骤2外码码字映射：外码码字第一个至最后一个比特依次映射到极化码第一个至最后一个非固定比特；

步骤3内编码器编码：对步骤2中极化码的非固定比特序列进行极化码编码，得到级联码码字，其中，译码采用修正的SCL译码算法进行译码，即译码信息比特时根据SCL译码算法进行比特判决，译码校验比特时，根据校验比特所在的偶校验方程中信息比特的判决结果进行校验得到；

所述译码的具体过程为：

初始化输入：i＝1,路径数量L；

Step1:判断i是否小于等于N，N为码长，是，则进入Step2；否，则进入Step7；

Step2:判断u_i是否为固定比特，u_i为输入序列中的比特，是，则进入Step3；否，则进入Step4；

Step3:将当前每条路径上u_i的判决值设置为0；i＝i+1；返回Step1；

Step4:判断u_i是否为校验比特，是，则进入Step5；否，则进入Step6；

Step5:当前每条路径上u_i的判决值通过该路径上判决的信息比特校验得到：返回Step1，为外码第j个校验方程的信息比特；

Step6:统计当前路径数量L′，当前每条路径在u_i处可取值0或1，从而得到2L′条备选路径，2L′条备选路径的度量值分别为该路径在u_i处取值0或1的概率：或若2L′≤L，保留2L′条备选路径；若2L′＞L，保留L条度量值最大的路径；i＝i+1；返回Step1，表示接收序列，表示在译码u_i时，每条路径译码出的序列，其上角标＾表示判决值；

Step7:从L条路径中输出路径度量值最大的一条路径上对应的判决序列

Step8:结束。

2.如权利要求1所述的极化码和多比特奇偶校验码级联的纠错编码方法，其特征在于，步骤1中，外码码字中的校验比特集中于外码码字尾部，设码长为N，信息比特数量为M，校验方程数量为K，校验比特位置序号集合为P＝{M+1,M+2,M+3,...,M+K}，集合P中的元素表示在外码的这些比特位置上为校验比特，也即外编码器编码码字中，比特序列为信息比特，为校验比特。

3.如权利要求1所述的极化码和多比特奇偶校验码级联的纠错编码方法，其特征在于，步骤1中，外码码字中的校验比特在外码码字中等间隔分布，设码长为N，信息比特数量为M，校验方程数量为K，外码码长为M+K，相邻校验比特的间距为其中，表示取x的下整数，校验比特位置序号集合为

4.如权利要求1所述的极化码和多比特奇偶校验码级联的纠错编码方法，其特征在于，步骤1中，外码码字中的校验比特在外码码字中不等间隔分布，即越靠近外码码字前部，校验比特分布越分散，越靠近外码码字尾部校验比特分布越集中，按照校验比特位置分布的这种特征，得到校验比特位置序号集合P。

5.如权利要求4所述的极化码和多比特奇偶校验码级联的纠错编码方法，其特征在于，设码长为N，信息比特数量为M，校验方程数量为K，假设集中在尾部的校验比特的数量为K₁，则前面等间隔分布的校验比特的数量为K-K₁，在不等间隔分布下，校验比特的位置序号集合为：

6.如权利要求1至5中任一所述的极化码和多比特奇偶校验码级联的纠错编码方法，其特征在于，外码替换为多比特奇校验码。