SCL译码器下的基于普遍偏序和遗传算法的极化码构造方法

摘要

本发明提出了一种新的极化码构造方法，包括：根据改进的普遍偏序UPO算法，挑选出可靠的比特通道，不可靠的比特通道，以及不确定比特通道；对遗传算法进行改进，通过引入汉明距离初始化、精英个体保护机制等措施，加快传统遗传算法的收敛速度和精度；根据改进的遗传算法寻找不确定比特通道中的最优解，即其中的信息位；其中，种群通过自身的误码性能不断的进化，最终向误码率最低所对应的比特集收敛。本方法的优点在于，相对于传统的极化码构造方法，该算法获得的比特集误码性能更优。

说明书

技术领域

本发明涉及数据传输以及5G移动通信技术领域，具体是一种SCL译码器下的基于普遍偏序和遗传算法的极化码构造方法。

背景技术

在信道编码技术领域，追求香农极限容量一直都是通信学者们的目标。早期的Turbo码和LDPC码已经十分接近这一目标，但是没能得到严格的数学证明，目前唯一能达到香浓极限的信道编码技术也只有极化码技术。极化码是一种基于信道极化现象而产生的一种信道专属编码，关于极化码的理论研究可以可以划分为极化码的构造方法以及极化码译码算法的研究。研究极化码构造方法的主要目的是在信道产生极化之后精准的挑选出信道容量趋于“1”的比特信道来传送有用的信息位，而研究极化码译码算法的目的则是在信息接收端以最精确的方式还原发送端所传过来的信息。

极化码是在信道极化理论基础上，使用N个信道中的K个可靠信道来传输信息并且在其余的不可靠信道上使用收发双方都已知的固定信息(通常为0)填充。在接收端，最初使用串行抵消(SC)算法进行译码。由于SC译码的误码性能并不够理想，学者们提出了置信度传播(BP)译码算法、线性规划(LP)译码算法等。这些算法取得了一定的编码增益，但增益仍然不够明显。

关于极化码构造方法的研究相对较少，但是通过改进编码构造方法可以有效的提升极化码的性能。Density evolution方法和高斯近似方法是经典的极化码构造方法。密度演进算法的精度虽然非常高，但是该方法在计算过程中涉及到卷积计算，这对硬件的要求十分苛刻。高斯近似方法存在极化速率过低的问题。最近极化权重算法用于极化码的构造，该算法虽然能够快速的构造出比特集，但是误码性能相对较差。

发明内容

本发明要解决的技术问题在于，针对如何精准的挑选出信道容量趋近于“1”的比特信道来传送有用的信息位，采用了一种SCL译码器下的基于普遍偏序和遗传算法的极化码构造方法解决上述问题。

一种SCL译码器下的基于普遍偏序和遗传算法的极化码构造方法，包括以下步骤：

S1、根据改进的UPO算法，挑选出可靠的比特通道、不可靠的比特通道以及不确定比特通道；

S2、通过引入包括汉明距离初始化和精英个体保护机制措施，改进传统的遗传算法；

S3、根据S2改进的遗传算法，寻找不确定比特通道中的最优解；

S4、将S3求得的最优解用于高斯信道下的SCL译码器。

本发明提供的技术方案带来的有益效果是：本发明改进后的遗传算法加快了传统遗传算法的收敛速度和精度，且相对于传统的极化码构造方法，该本发明获得的比特集误码性能更优。

附图说明

图1为本发明一种SCL译码器下的基于普遍偏序和遗传算法的极化码构造方法流程图；

图2为本发明一种SCL译码器下的基于普遍偏序和遗传算法的极化码构造方法中码长N＝32时的部分可靠性排序图；

图3为本发明一种SCL译码器下的基于普遍偏序和遗传算法的极化码构造方法中码长N＝32时的基于组的可靠性偏序图；

图4为本发明一种SCL译码器下的基于普遍偏序和遗传算法的极化码构造方法中码长N＝32时I、F和U的选取图；

图5为本发明一种SCL译码器下的基于普遍偏序和遗传算法的极化码构造方法汉明距离初始化流程图；

图6为本发明一种SCL译码器下的基于普遍偏序和遗传算法的极化码构造方法寻找不确定比特通道中的最优解的流程图；

图7为本发明求得的比特集(N＝32)与PW算法求得比特集在高斯信道下SCL(L＝8)译码的误码性能对比图；

图8为本发明求得的比特集(N＝64)与PW算法求得比特集在高斯信道下SCL(L＝8)译码的误码性能对比图；

图9为本发明求得的比特集(N＝128)与PW算法求得比特集在高斯信道下SCL(L＝8)译码的误码性能对比图。

具体实施方式

为了对本发明的技术特征、目的和效果有更加清楚的理解，现对照附图详细说明本发明的具体实施方式。

如图1所示为本发明一种SCL译码器下的基于普遍偏序UPO和遗传算法的极化码构造方法示意图，该方法根据改进的UPO算法，挑选出可靠的比特通道(信息位)，不可靠的比特通道(冻结位)，以及不确定比特通道(可能为信息位也可能为冻结位)；对遗传算法进行改进，通过引入汉明距离初始化和精英个体保护机制，加快传统遗传算法的收敛速度和精度；根据改进的遗传算法寻找不确定比特通道中的最优解，即最优的极化码构造。其中，种群(比特集)通过自身的误码性能不断的进化，最终向误码率最低所对应的比特集收敛。

步骤S1中，改进的UPO算法挑选出可靠的比特通道，不可靠的比特通道以及不确定比特通道具体步骤如下：

S11、UPO算法主要包括两个基本内容：addition和left-swap，给定任意一对合成信道的索引值(x,y)，它们的可靠性可以根据以下两个规则来进行判断：

Addition：如果一个合成信道索引值的二进制表示为(a,b,1,c)，那么它的靠性一定要比二进制表示为(a,b,0,c)信道的可靠性要高，这种0→1的特征不仅适用于单比特也适用于多比特，如：

2(0，1，0)→3(0，1，1)

9(1，0，0，1)→15(1，1，1，1)

它们表示的意思分别为索引值为2的比特通道的可靠性要小于比特通道3，索引值为9的比特通道可靠性要小于比特通道15。

Left-swap：如果一个合成信道索引值的二进制表示为(a,0,b,1,c)，那么它的可靠性一定要比二进制表示为(a,1,b,0,c)信道的可靠性要低；这种0..1→1..0的特征可以在可靠性对比中发生多次，并且0和1可以不相邻，如：

2(0，1，0)→4(1，0，0)

12(0，1，1，0，0)→24(1，1，0，0，0)

它们表示的意思分别为索引值为2的比特通道的可靠性要小于比特通道4，索引值为12的比特通道可靠性要小于比特通道24。

另外提出UPO的两个重要性质：nested和symmetric，可以使我们在码长较长的情况下能够较快速的得到可靠性的部分排序。

Nested：在码长为N时的可靠性排序在码长为2N时仍保持不变；

Symmetric：假如码长为N，如果索引值为x的比特通道的可靠性小于比特通道y，那么索引值为N-1-x的比特通道的可靠性要大于比特通道N-1-y。

如码长N＝32时的部分可靠性排序如图2所示.

S12、将所有子比特通道划分为不同的组，每个组用GR

便可以知道该比特通道所属的组数，如码长N＝32时的基于组的可靠性偏序如图3所示。

设M个组中的中间组为GR

深灰色的为可靠比特通道，即I＝{15,22,23,25,26,27,28,29,30,31}，浅灰色的为不可靠比特通道，即F＝{0,1,2,3,4,5,6,8,9,16}，白色的则是不确定比特通道，即U＝{7,10,11,12,13,14,17,18,19,20,21,24}。

其中I+F+U＝N，I的大小取决于r值的选取，U的大小取决于l值的选取，U的大小则由r值和l值共同决定；U值不易过大，太大的话会导致计算复杂度较高，U值也不宜过小，太小的过可能会找不到最优的比特集。

S13、把可靠的比特通道直接作为信息位1，不可靠的比特通道直接作为冻结位0；

S14、根据步骤S11，S12和S13，可以得到码长分别为N＝8,16,32，64，128，256，512，1024时所对应的可靠比特通道，不可靠比特通道以及不确定比特通道；如N＝64时，不确定比特通道的索引值为{14,15,21,22,23,24,25,26,27,28,35,36,37,38,39,40,41,42,48,49}，N＝256时，不确定比特通道的索引值为{55,58,59,60,61,79,86,87,89,90,91,92,101,102,103,104,105,106,112,113,142,143,149,150,151,152,153,154,163,164,165,166,168,169,176,194,195,196,197,200}。

步骤S2中，改进的遗传算法具体步骤如下：

S21、等长的两个字符串之间的汉明距离是指将其中一个字符串改成另一个字符串所需要改变的位的总数，在改进遗传算法中，种群中不同个体之间的汉明距离必须大于等于设定的最小值，即假设种群大小为T，染色体长度为N(即码长)，那么最小汉明距离D可以计算为：

D≤2N-T+1

使用汉明距离初始化方法，就可以在不失去随机性的情况下使初始种群中的个体尽可能的分散，达到使用有限的个体数量尽可能详细的描述解空间的目的；

S22、在每次挑选下一代种群之前，计算出每个个体的适应度值，然后找出该种群中适应度值最小的个体，记录下该个体以及它所对应的适应度值；

S23、采用冒泡排序算子选择执行挑选操作，挑选出下一代个体，并对挑选出来的种群进行交叉和突变，其中，只有当种群中的个体大于设定的交叉概率和突变概率才进行交叉和突变操作；

S24、循环执行步骤S22和步骤S23，直到达到设定的遗传算法最大循环次数M；

S25、在达到遗传算法最大循环次数M时，记录下M个个体和它们所对应的适应度值；

S26、对比步骤S25中M个个体的适应度值，找到这M个个体中适应度值最小的个体A，然后再将个体A的适应度值与最终收敛结果对应的适应度值进行对比，找出适应度值最小的个体即是求得的最优解。

步骤S3中，采用改进的遗传算法挑选出不确定比特通道中的信息位步骤如下：

S31、执行步骤S14，得到I个信息位比特通道，F个冻结位比特通道以及U个不确定比特通道，对不确定比特通道进行汉明距离初始化，如N＝32时，对索引值为{7,10,11,12,13,14,17,18,19,20,21,24}的比特通道进行汉明距离初始化，假设初始化得到了L个信息位比特通道；

S32、进行自适应操作，使得由步骤S31初始化得到的信息位个数L+I＝K，K为设定的值；

S33、对初始化的种群进行适应度值计算，即求种群中每个个体的误码率，然后执行步骤S22；

S34、采用冒泡排序算子选择执行挑选操作，挑选出来下一代个体，并对挑选出的种群进行交叉和突变，但是交叉和突变都只是针对不确定比特通道，如N＝32时，只对种群中个体索引值为{7,10,11,12,13,14,17,18,19,20,21,24}的比特通道进行交叉和突变操作。并且交叉和突变后，都要执行自适应操作，使得信息位的个数始终为K；

S35、执行步骤S24，S25和S26，找到适应度值最小的个体即是求得的最优比特集。

图5为本发明改进遗传算法中的汉明距离初始化流程图。

图6为极化码构造方法寻找不确定比特通道中的最优解的流程图；

如图7所示为本发明所得比特集(N＝32)与PW算法求得比特集在高斯信道下SCL(L＝8)译码的误码性能对比图。

其中如图7中“○”线条所示为本发明所构造的比特集误码性能曲线。如图7中“□”线条所示为PW算法构造的比特集的误码性能曲线。

从图中可以看出，基于普遍偏序和遗传算法构造的比特集具有更好的误码性能。

随着信噪比的不断增大，这种基于普遍偏序和遗传算法构造的比特集在误码性能上的优势越来越明显，当信噪比大于等于1dB时，本发明构造的比特集误码率有了将近0.3dB的增益，当信噪比大于等于2dB时，本发明构造的比特集误码率有了将近0.5dB的增益。

如图8所示为本发明所得比特集(N＝64)与PW算法求得比特集在高斯信道下SCL(L＝8)译码的误码性能对比图。

其中如图8中“○”线条所示为本发明所构造的比特集误码性能曲线。如图8中“□”线条所示为PW算法构造的比特集的误码性能曲线。

从图中可以看出，基于普遍偏序和遗传算法构造的比特集具有更好的误码性能。

随着信噪比的不断增大，这种基于普遍偏序和遗传算法构造的比特集在误码性能上的优势越来越明显，当信噪比大于等于2dB时，本发明构造的比特集误码率有了将近0.2dB的增益。

如图9所示为本发明所得比特集(N＝128)与PW算法求得比特集在高斯信道下SCL(L＝8)译码的误码性能对比图。

其中如图9中“○”线条所示为本发明所构造的比特集误码性能曲线。如图9中“□”线条所示为PW算法构造的比特集的误码性能曲线。

从图中可以看出，基于普遍偏序和遗传算法构造的比特集具有更好的误码性能。

随着信噪比的不断增大，这种基于普遍偏序和遗传算法构造的比特集在误码性能上的优势越来越明显，当信噪比大于等于2dB时，本发明构造的比特集误码率有了将近0.1dB的增益。

对所公开的实施例的上述说明，使本领域专业技术人员能够实现或使用本发明。对这些实施例的多种修改对本领域的专业技术人员来说将是显而易见的，本文中所定义的一般原理可以在不脱离本发明的精神或范围的情况下，在其它实施例中实现。因此，本发明将不会被限制于本文所示的这些实施例，而是要符合与本文所公开的原理和新颖特点相一致的最宽的范围。