基于比特翻转串行消除列表算法的极化码译码方法

摘要

本发明公开了一种基于比特翻转串行消除列表算法的极化码译码方法，解决了现有SCL算法有较高的时间复杂度的问题。本发明实现方法的步骤：(1)通信终端接收待译码序列；(2)对接收的待译码序列进行SC译码；(3)判断SC译码序列是否通过CRC校验；(4)初始化列表宽度和比特翻转次数；(5)选取判决出错位置集；(6)从判决出错位置集中选出一个元素；(7)利用比特翻转串行消除列表算法进行译码；(8)判断是否选取完判决出错位置集中的元素；(9)译码成功；(10)译码失败。本发明通过先进行SC译码，在译码失败时，将比特翻转与列表译码相结合重新译码，提高了译码性能，降低了译码算法的时间复杂度。

说明书

技术领域

本发明属于通信技术领域，更进一步涉及信道编码技术领域中一种基于比特翻转串行消除列表算法的极化码译码方法。本发明可用于对遥感图像传输、通信卫星传输以及第五代移动通信等各种通信系统中，对要发送的信源信息进行极化码编码，然后用本发明中的极化码译码方法解码，以纠正由于信道噪声造成的传输差错。

背景技术

极化码因其在理论上被证明可以达到香农极限,并且具有较低的编译码计算复杂度,有确定性的构造方法，使其可以用于上述通信系统中信道编码方案，以此解决信息在无线信道中传输差错问题。

现有极化码的串行消除SC(Successive Cancellation)译码方法是基于似然比(likelihood ratio,LR)逐比特顺序译码。虽然串行消除SC译码在码长N很长的情况下能够获得很好的渐近性能，逼近香农限。但是当码长N较短或者中等长度的时，由于Polar码仍然还有部分没极化的信道，在这些没极化的信道传输信息比特，很容易导致译码出错。其次，串行消除SC译码方法在译码过程中会产生错误传播，使其性能没有超过Turbo码和低密度奇偶校验LDPC(Low-density Parity-check)码的性能，还需要进一步提高译码性能。

ORION A,BALATSOUKAS-STIMMING A,ANDREAS B.在其发表的论文“A Low-complexity Improved Successive Cancellation Decoder for Polar Codes”([C]//Proceedings of IEEE 48th Asilomar Conference on Signals,Systems andComputers.Pacific Grove:IEEE,2014:2116-2120.)中公开了一种极化码译码方法。该译码方法首先进行串行消除SC译码，在串行消除SC译码算法输出结果不能通过循环冗余校验CRC(Cyclic Redundancy Check)时，该译码方法根据信息位对应的对数似然比的绝对值来选取T个最小判定位以此作为不可靠信息位的估计，并将这些位对应的索引值构成集合M。每次从集合M中取出一个值，然后重新执行串行消除SC算法译码，并对判定序列中该索引标志对应的不可靠的信息位进行比特翻转，将翻转结果作为该索引位置的译码结果。如果新的码字估值v₁^N通过循环冗余校验，则译码成功，否则选择M集合中下一位索引值，继续进行上述过程。遍历集合M后如仍未得到有效码字，则译码失败。该译码方法在译码性能上得到了一定程度的提升，相比于串行消除列表SCL(Successive>

西安电子科技大学在申请的专利文献“一种基于比特翻转的串行列表译码算法”(申请公布日：2016年9月28日，申请公布号：CN 105978557 A)中公开了一种基于比特翻转的串行列表译码算法。该发明实施例针对极化码，提出了一种新的基于比特翻转的串行列表译码算法。该算法针对循环冗余校验辅助的串行抵消列表CA-SCL译码算法(CyclicRedundancy Check Aid Successive Cancellation List)中的错误传播问题，把原错误路径上第一次出现的错误比特进行翻转，使之变为正确的路径。和循环冗余校验辅助的串行抵消列表CA-SCL算法相比，该译码算法在性能上有了较大的提升，保证安全性的同时，提高了便利性。但是，该方法仍然存在的不足之处是，该译码算法是以增加译码复杂度为代价来提升译码性能，即使在高信噪比环境下，该译码复杂度仍然很高，无法用于实际的通信系统中。

发明内容

本发明的目的在于针对上述已有技术的不足，提出一种基于比特翻转串行消除列表算法的极化码译码方法，提高了极化码的译码性能，同时具有相对较低的复杂度，在高信噪比环境下，本发明的译码方法的时间复杂度逐渐趋于串行消除SC算法的复杂度。

为实现上述目的，本发明的技术思路是：首先对极化码进行串行消除SC译码，若译码结果能够通过循环冗余校验，则直接输出正确结果。否则利用判决层中信息位对应的极化信道的对数似然比LLR(Log Likelihood Ratio)的绝对值找出判决可能出错的位置。然后开始进行比特翻转的串行消除列表译码，当译码进行到判决可能出错位置处时，直接将SC译码序列中该判决出错位置对应的比特进行反转来作为此次该位置的译码结果，继续进行余下的译码直至进行到译码树中的叶子节点处，当候选路径中有一个能通过循环冗余校验时，则译码结束，否则重新从判决可能出错位置集中选出下一个元素重新执行比特翻转的串行消除列表译码。

本发明的实现步骤如下：

(1)从通信终端接收待译码序列：

(2)对待译码序列先进行串行消除SC译码：

(2a)计算极化信道的对数似然；

(2b)根据译码结构判决层中信息位对应的每一个极化信道的对数似然比值的正负对通信终端收到的序列进行判决，若为正，判决为0，为负则判决为1，对于通信终端收到的序列中每一个非信息位对应的位置比特，直接判决为0；

(2c)判断当前译码序列的序号是否大于极化码的码长，若是，则将当前译码序列作为串行消除SC译码序列后执行步骤(3)，否则，将当前译码序列的序号加1后执行步骤(2a)；

(3)判断串行消除SC译码序列是否通过循环冗余CRC校验，若是，则执行步骤(9)，否则，执行步骤(4)：

(4)用一个2的整数次方的值，初始化串行消除列表算法的列表宽度和比特翻转次数；

(5)选取判决出错的位置集：

按照从小到大的排序方法，依次从未通过循环冗余CRC校验的串行消除SC译码序列中，选取信息位集所对应的译码判决出错的位置，将所有出错的位置构成串行消除SC译码判决出错的位置集；

(6)依次从串行消除SC译码判决出错的位置集中选出一个元素；

(7)利用比特翻转串行消除列表算法进行译码：

(7a)判断当前译码序列的序号是否等于所选出错位置集元素的值，若是，则执行步骤(7b)，否则，执行步骤(7c)；

(7b)按照下式，按照下式，使用惩罚因子计算译码树中每一个译码序号等于译码判决出错的位置集中的元素值处的每一个扩展路径的度量值，以间接实现比特翻转；

其中，表示译码树中由第1位译码比特u₁到第i位译码比特u_i，所构成的扩展路径的度量值，表示译码树中由第1位译码比特u₁到第i-1位译码比特u_i-1，所构成的扩展路径的度量值，u_e表示串行消除SC译码序列中第e位所对应的比特值，e表示从串行消除SC译码判决出错位置集中选出的元素值，L_i表示译码结构判决层中第i位极化信道对数似然比值的绝对值，α表示惩罚因子，其取值范围为100≤α≤2000；

(7c)按照下式，计算译码树中每一个译码序列的序号处的每一个扩展路径的度量值；

其中，表示译码树中由第1位译码比特u₁到第i位译码比特u_i，所构成的扩展路径的度量值，表示译码树中由第1位译码比特u₁到第i-1位译码比特u_i-1，所构成的扩展路径的度量值，∈表示属于操作，Λ表示编码时选出的信息位集，b表示正确的冻结比特值，其值为0，L_i表示判决层中第i位极化信道的对数似然比值的绝对值；

(7d)判断扩展路径值是否小于等于串行消除列表算法的列表宽度值，若是，则执行步骤(7e)，否则，执行步骤(7f)；

(7e)保留所有扩展路径；

(7f)对扩展路径的度量值进行从大到小排序，将排序中的前M条扩展路径作为候选路径，其中M取值等于串行消除列表算法的列表宽度值；

(7g)判断当前译码序列的序号是否大于极化码的码长，若是，则执行步骤(7h)，否则，将当前译码序列的序号加1后执行步骤(7a)；

(7h)判断Q条候选路径中是否有通过循环冗余校验的路径，若是，从通过循环冗余检验的候选路径中选取路径度量最大的一条路径作为译码序列后执行步骤(9)，否则，执行步骤(8)，其中Q取值等于串行消除列表算法的列表宽度值；

(8)判断是否选取完串行消除SC译码判决出错的位置集中的所有元素，若是，则执行步骤(10)，否则，执行步骤(6)；

(9)译码成功，输出译码成功的序列；

(10)译码失败，输出串行消除SC译码序列。

本发明与现有技术相比具有以下优点：

第一，由于本发明使用惩罚因子，计算译码树中每一个译码序号等于译码判决出错的位置集中的元素值处的每一个扩展路径的度量值，以间接实现比特翻转，克服了现有技术中的单比特翻转串行消除译码算法每次只尝试翻转一次不可靠信息位，译码性能不好，无法用于性能要求高的通信系统的问题，使得本发明通过使用串行消除列表译码算法，明显提高了译码的纠错性能。

第二，由于本发明对待译码序列先进行串行消除SC译码，当串行消除SC译码序列没有通过循环冗余CRC校验时，再利用比特翻转串行消除列表算法进行译码，克服了现有技术中的基于比特翻转的串行列表译码算法以增加译码复杂度为代价来提升译码性能，即使在高信噪比环境下，该译码复杂度仍然很高，无法用于实际的通信系统中的问题，使得本发明实现了在高信噪比下，译码复杂度逐渐趋于串行消除SC的复杂度，明显降低译码算法的时间复杂度。

附图说明

图1为本发明的流程图；

图2为改进的译码算法SFSCL与现有串行消除SC、循环冗余校验辅助的串行消除列表CRC-SC、基于单比特翻转串行消除SFSC译码方法的误帧率曲线对比图；

图3为改进的译码算法SFSCL与现有SC，CRC-SCL，SFSC译码方法的归一化的平均译码复杂度曲线对比图。

具体实施方式

下面结合附图对本发明做进一步描述。

参照附图1，对本发明的具体步骤做进一步描述。

步骤1，从通信终端接收待译码序列。

步骤2，对待译码序列进行串行消除SC译码。

计算极化信道的对数似然。

根据极化信道序号的奇偶分别计算译码结构判决层中极化信道的对数似然比：

按照下式，计算译码结构判决层中每个序号为奇数的极化信道的对数似然比值；

其中，表示极化码编码后的码字长度为N的译码结构判决层中第k个奇数序号的极化信道输入为的极化信道对数似然比值，k表示译码结构判决层中极化信道的序号，其取值为2j-1，且1≤j≤N/2，N表示极化码编码后的码字长度，表示该极化信道的输入，y表示通信终端收到的序列,表示已经译出的前k-1位码字序列，sign(·)表示一个当L₁与L₂的乘积为正数时，函数值为1,当L₁与L₂的乘积为负数时，函数值为-1的函数，L₁表示译码结构邻近层中上分支的极化信道对数似然比，L₂表示译码结构邻近层中下分支的极化信道的对数似然比，min(·)表示求两个实数中最小值的函数，|·|表示求绝对值操作。

按照下式，计算译码结构判决层中每个序号为偶数的极化信道的对数似然比值。

其中，表示极化码编码后的码字长度为N的译码结构判决层中第m个偶数序号的极化信道输入为的极化信道对数似然比值，m表示译码结构判决层中极化信道的序号，其取值为2j，且1≤j≤N/2，N表示极化码编码后的码字长度，表示该极化信道的输入，y表示通信终端的接收端收到的序列，表示已经译出的前m-1位码字序列，表示已经译出的第m-1位码字。

根据译码结构判决层中信息位对应的每一个极化信道的对数似然比值的正负对通信终端收到的序列进行判决，若为正，判决为0，为负则判决为1，对于通信终端收到的序列中每一个非信息位对应的位置比特，直接判决为0。当译码进行到最后一位时，最终得出串行消除SC译码序列。

其中，对于信息位对应的比特，按照下式进行判决。

其中，表示译码序列中第i位译码比特值，表示判决层中第i位极化信道的对数似然比值，Λ表示信息位集。

信息位集Λ按下面的方式进行选取：

根据高斯近似计算极化信道的均值

对于(N,k)极化码从N个信道中挑选出k个信道用于信息传输，信息位的选取是极化码的关键。本发明采用高斯近似来对极化信道进行可靠性估计。即在BAWGN信道下，可以将密度进化中的LLR值的概率密度函数用一簇方差为均值2倍的高斯分布来去近似。对噪声方差为σ²高斯白信道AWGN，接收端获取的接收信号为y：

y＝(1-2x)+z

其中，y表示接收端接收到的序列，x表示发送比特，x∈{0,1}，z表示均值为0，方差为σ²高斯白噪声，信源比特序列采用BPSK调制，其概率密度函数为：

其中，p(y|x)表示发送端发送x，接收端收到y的概率密度函数，σ²表示高斯白噪声的方差。

假设发送的比特为全零序列，则对应的LLR值为

其中，LLR(y)表示信道层的极化信道的对数似然比值，ln(·)表示自然对数操作，p(·|·)表示信道层的转移概率，y表示接收端接收到的序列，σ²表示高斯白噪声的方差。

根据密度进化中的设定，令表示的概率密度函数，那么也是服从的高斯分布。再根据高斯近似的构造理论，将密度进化的计算转化为对均值的递归计算：

当判决层中极化信道的序号为奇数时，按下式计算其均值

其中，表示判决层中第2i-1个极化信道的概率密度函数的均值，表示邻近层中极化信道的概率密度函数的均值，表示的反函数，定义如下：

当判决层中极化信道的序号为偶数时，按下式计算其均值

其中，表示判决层中第2i个极化信道的概率密度函数的均值，表示邻近层中极化信道的概率密度函数的均值。

递归终止时，其均值为：

其中，表示信道层中概率密度函数的均值，σ²表示高斯白噪声的方差。

根据下式，计算极化子信道的错误概率

其中，表示判决层中第i个极化信道的错误概率，表示判决层中第i个极化信道的均值，Q(x)函数定义如下：

对极化子信道的错误概率进行升序排序，选出信息位集Λ；

将得到的各极化子信道的错误概率进行升序排序，选出极化信道错误概率最小的k个子信道用于传输比特信息，该集合记为Λ，该集合即是信息位的索引位置，其余子信道用于传输冻结比特，该集合记为Λ^c，冻结比特集通常传输为全零比特集。

步骤3，判断串行消除SC译码序列是否通过循环冗余CRC校验，若是，则执行步骤9，否则，执行步骤4。

步骤4，用一个2的整数次方的值初始化串行消除列表算法的列表宽度和比特翻转次数。

步骤5，选取判决出错的位置集。

对判决层中信息位所对应的极化信道的对数似然比值绝对值，利用从小到大的次序进行排序，依次选出前T个判决层中极化信道对数似然比值的绝对值所对应的极化信道索引位置，构成串行消除SC译码判决出错位置集，其中T是一个等于比特翻转次数的值。

步骤6，依次从串行消除SC译码判决出错的位置集中选出一个元素。

步骤7，利用比特翻转串行消除列表算法进行译码。

根据当前译码序列的序号是否等于所选出错位置集元素的值分两种情况计算每一个扩展路径的度量值。

情况一：当前译码序列的序号等于所选出错位置集元素的值时，按照下式，使用惩罚因子计算译码树中每一个译码序号等于译码判决出错的位置集中的元素值处的每一个扩展路径的度量值，以间接实现比特翻转。

其中，表示译码树中由第1位译码比特u₁到第i位译码比特u_i，所构成的扩展路径的度量值，表示译码树中由第1位译码比特u₁到第i-1位译码比特u_i-1，所构成的扩展路径的度量值，u_e表示串行消除SC译码序列中第e位所对应的比特值，e表示从串行消除SC译码判决出错位置集中选出的元素值，L_i表示译码结构判决层中第i位极化信道对数似然比值的绝对值，α表示惩罚因子，其取值范围为100≤α≤2000；

情况二：当前译码序列的序号不等于所选出错位置集元素的值时，按照下式，计算译码树中每一个译码序列的序号处的每一个扩展路径的度量值；

其中，表示译码树中由第1位译码比特u₁到第i位译码比特u_i，所构成的扩展路径的度量值，表示译码树中由第1位译码比特u₁到第i-1位译码比特u_i-1，所构成的扩展路径的度量值，∈表示属于操作，Λ表示编码时选出的信息位集，b表示正确的冻结比特值，其值为0，L_i表示判决层中第i位极化信道的对数似然比值的绝对值。

当扩展路径值是否小于等于串行消除列表算法的列表宽度值，则保留所有扩展路径，否则，对扩展路径的度量值进行从大到小排序，将排序中的前M条扩展路径作为候选路径，其中M取值等于串行消除列表算法的列表宽度值。

继续进行以上过程，直至译码进行到译码树中的叶子节点，最终得到Q条候选路径，判断Q条候选路径中是否有通过循环冗余校验的路径，若是，从通过循环冗余检验的候选路径中选取路径度量最大的一条路径作为译码序列后执行步骤9，否则，执行步骤8，其中Q取值等于串行消除列表算法的列表宽度值。

步骤8，判断是否选取完串行消除SC译码判决出错的位置集中的所有元素，若是，则执行步骤10，否则，执行步骤6。

步骤9，译码成功，输出译码成功的序列。

步骤10，译码失败，输出串行消除SC译码序列。

下面结合仿真实验对本发明的效果进一步说明。

1.仿真条件：

本发明的仿真实验是在MATLAB 16.0软件下进行的。在本发明的仿真实验中，为了真实地模拟加性高斯白噪声信道，采用伪随机序列模拟高斯白噪声和使用BPSK对信号进行调制，信源输出端的信息序列采用随机数生成，码率为0.5，码长为1024，极化码的信息位的选取采用高斯近似的方法。

2.仿真内容与结果分析：

仿真实验1：

本发明的仿真实验1是采用本发明的极化码译码方法与三种现有极化码译码方法(串行消除SC方法、循环冗余校验辅助的串行消除列表CRC-SCL方法、基于单比特翻转串行消除SFSC方法)的误帧率对比实验。

图2是本发明的极化码译码方法与三种现有的极化码译码方法(串行消除SC算法、循环冗余校验辅助的串行消除列表CRC-SCL算法、基于单比特翻转串行消除SFSC算法)的误帧率曲线对比图。图2中的横轴表示信噪比，纵轴表示误帧率。图2中以空心圆标示的曲线表示采用现有的串行消除译码算法的极化码译码方法的误帧率曲线。图2中以正方形标示的曲线表示，采用现有技术的基于单比特翻转串行消除SFSC算法，且翻转次数等于4的极化码译码方法的误帧率曲线。图2中以菱形标示的曲线表示采用现有技术的基于单比特翻转串行消除SFSC算法，且翻转次数等于8的极化码译码方法的误帧率曲线。图2中以三角形标示的曲线表示采用现有技术的循环冗余校验辅助的串行消除列表CRC-SCL算法，且列表宽度等于2的极化码译码方法的误帧率曲线。图2中以五角星标示的曲线表示采用本发明的方法，且列表宽度等于2、翻转次数等于4的极化码译码方法的误帧率曲线。图2中以星号标示的曲线表示采用本发明的方法，且列表宽度等于2、翻转次数等于8的极化码译码方法的误帧率曲线。

从图2中的星形曲线与菱形曲线、三角形曲线对比可知，在信噪比相等的情况下，星形曲线的误帧率低于菱形曲线和三角形曲线的误帧率，可见，本发明的译码方法相比于基于单比特翻转串行消除译码算法和循环冗余校验辅助的串行消除列表算法的译码方法在性能上都有很大的提升。

仿真实验2：

本发明的仿真实验2是采用本发明的极化码译码方法与三种现有极化码译码方法(串行消除SC方法、循环冗余校验辅助的串行消除列表CRC-SCL方法、基于单比特翻转串行消除SFSC方法)的归一化的平均复杂度对比实验。

图3是本发明的极化码译码方法与三种现有的极化码译码方法(串行消除SC算法、循环冗余校验辅助的串行消除列表CRC-SCL算法、基于单比特翻转串行消除SFSC算法)的归一化的平均复杂度对比图。图3中的横轴表示信噪比，纵轴表示归一化的平均译码复杂度，图3中以空心圆标示的曲线表示采用现有技术的串行消除方法的极化码方法的归一化的平均译码复杂度曲线。图3中以正方形标示的曲线表示采用现有技术的基于单比特翻转串行消除SFSC译码算法，且翻转次数等于4的极化码译码方法的归一化的平均译码复杂度曲线。图3中以菱形标示的曲线表示采用现有技术的基于单比特翻转串行消除SFSC译码算法，且翻转次数等于8的极化码译码方法的归一化的平均译码复杂度曲线。图3中以三角形标示的曲线表示采用现有技术的循环冗余校验辅助的串行消除列表CRC-SCL算法，且列表宽度等于2的极化码译码方法的归一化的平均译码复杂度曲线。图3中以五角星标示的曲线表示采用本发明的方法，且列表宽度等于2、翻转次数等于4的极化码译码方法的归一化的平均译码复杂度曲线。图3中以星号标示的曲线表示采用本发明的方法，且列表宽度等于2、翻转次数等于8的极化码译码方法的归一化的平均译码复杂度曲线。

从图3中的星形曲线与圆形曲线对比可知，在高信噪比情况下，星形曲线逐渐与菱形曲线重叠，因此本发明改进的方法，随着信噪比的提升，译码方法的复杂度逐渐趋近于串行消除SC的译码的复杂度，译码复杂度明显降低。