基于CA-GA的Polar码构造算法研究

Research on Polar Code Construction Algorithm Based on CA-GA Algorithm

摘要: 针对满足低信噪比下信息可靠传输需求的问题，本文提出了一种基于优化遗传算法CA-GA的polar码构造方法。将polar码的信息子信道选择映射成N维二进制向量的优化问题，首先通过先验知识生成初始种群，再将贪婪算法引入选择过程中，然后在变异过程中引入柯西变异算子，最后根据种群适应度值自适应计算变异概率和交叉概率。进一步，以最小化误码率为目标，更新迭代生成适应度较高的种群，选取当前种群中最优秀的个体作为信息子信道索引向量，通过子信道索引向量、码长、码率以及信息位构造polar码。仿真结果表明，本文提出算法随着码长增加具有更低的误块率，在码长256、误块率为10⁻²时与GA构造法、蒙特卡洛构造法相比分别具有0.4 dB、0.5 dB的净增益，与传统遗传算法构造法相比约有0.05 dB的净增益，在码长512、误块率为10⁻²时和巴氏参数法、GA构造法、蒙特卡洛构造法相比分别具有0.5 dB、0.1 dB、0.15 dB的净增益。

Abstract: To meet the requirement of reliable information transmission under low signal-to-noise ratio, this paper proposes a polar code construction method based on an optimized genetic algorithm. The optimization problem of mapping the information sub-channel selection of polar codes into N-dimensional binary vectors involves first generating an initial population through prior knowledge, then introducing a greedy algorithm into the selection process, and finally introducing the Cauchy mutation operator in the mutation process. Finally, the mutation probability and crossover probability are adaptively calculated based on the population fitness value. Furthermore, with the goal of minimizing the bit error rate, the population with higher fitness is iteratively generated and updated. The best individual in the current population is selected as the information subchannel index vector. Using this subchannel index vector, along with the code length, code rate, and information bits, the polar code is constructed. The simulation results demonstrate that the algorithm proposed in this paper exhibits a lower block error rate as the code length increases. When the code length is 256 and the block error rate is 10⁻², it achieves a net gain of 0.4 dB and 0.5 dB compared to the Genetic Algorithm (GA) construction method and Monte Carlo construction method, respectively, and approximately 0.05 dB compared to the traditional Genetic Algorithm construction method. For a code length of 512 and a block error rate of 10⁻², it offers net gains of 0.5 dB, 0.1 dB, and 0.15 dB over the Bhattacharyya parameter method, GA construction method, and Monte Carlo construction method, respectively.

1. 引言

作为无线通信中最关键的一项技术，信道编码是一种有效的抗干扰方法，其编码质量直接影响着整个网络的覆盖范围和用户的数据传输率。第五代移动通信(5G)是近几年来国际上最热门的研究方向之一，而极化码编码作为5G无线信道的标准之一，也是目前国际上的研究热点。

E. Arikan等学者基于极化理论提出的极化码[1]，其基本思想是：在编码端，通过特定的编码方式，使各子信道具有完全不同的可靠度，随着编码长度的增大，部分分子信道的信道容量将达到Shannon极限，其余的子通道被转换成一个纯噪音通道，其容量接近0，最终达到与极大似然译码算法相当的解码性能，在有噪信道中实现无损传输。针对极化码的构建问题，提出了巴氏参数构建法[2]、GA (高斯)近似法[3]、蒙特卡洛(Monte Carlo)逼近法[4]、密度进化法[5]等多种方法来选择适合不同信道的信息比特。上述构造策略不仅拓宽了polar码可适应的信道范围，还降低了运算的复杂性，从而促进了polar码在实际应用场景中的有效实施与利用。

近几年，编码构造改进算法被广泛研究。文献[6]提出了一种灵活且可并行化的系统极化码编码算法，通过非系统的编码器和预处理器改变冻结位的位置和数量，并证明了其高速率、高吞吐量的准确性。文献[7]提出了一种循环冗余校验码辅助PC-polar码的编码算法，用奇偶校验比特和高汉明权重的冻结比特替换低汉明权重的信息比特并且优化了PC码的校验函数，显著提升了polar码的纠错能力。文献[8]研究了面向包含常态和干扰态的混合信道的多目标强化学习算法，提出了一种适应强干扰环境的polar码构造优化算法，通过优化编码过程中的信息位比特信道序列、初始化预处理和理论计算回报值，实现了降低算法复杂度的需求，相比于传统编码方案有了一定的增益。文献[9]研究了极化码的权重结构，利用三角仿射变换、RM码构建了低速率和高速率极化码构造方案，实现了高速代码的实际应用。文献[10]提出了一种深度极化码，利用一系列不同大小的多层极性变换来实现极化码的构造，该编码算法具有复杂度低、显著增强了码权重分布和更灵活的速率分布的优点。

上述各类编码方案通过改进编码机理在码速率、误块率、时间复杂度、空间复杂度方面取得了性能的提升。随着智能编译码技术的不断发展，智能优化算法的发展和创新过程日渐增多。然而现阶段很少有学者将智能优化算法应用到polar码编码构造过程。为提高编码性能、降低误块率，本文将遗传算法引入polar码编码构造过程，通过加入柯西变异算子和贪婪算法，根据先验条件生成初始种群，自适应改进交叉概率和变异概率，实现降低误块率的效能。

2. Polar码编码原理分析

2.1. 信道极化原理

学者E. Arikan依据信道极化的理论，首次提出了Polar码，这种线性分组码是首个能够从理论上证实其能够抵达任意二进制输入下离散无记忆对称信道容量极限的编码方式。

Polar码的核心思想是信道极化效应，信道极化是一种将信道容量进行转移的操作，将多个子信道合并成一个等效信道，然后将等效信道分裂成多个信道容量呈两极分化(信道容量接近0或者1)的子信道，在这些子信道中，相互之间存在依赖性，且其传输能力的分布呈现两极化特征。其中，一部分子信道趋向于噪声极低的信道，另一部分则趋向于噪声满载的信道。传输过程中，信息主要通过传输容量接近于1的可靠子信道进行，而在传输容量接近于0的不稳定子信道上，则传输已知的信息比特，以此增强信息传递的可靠性。信道极化过程涉及信道组合与信道分裂两个阶段，信道组合是将N个性质相似的信道合并为一个的过程，而信道分裂则是将合并后的信道再拆分为N个子信道的步骤。

2.1.1. 信道组合

信道组合就是指把N个具有相同特性的信道合成一个信道的过程。假设信道$W:X\to Y$ 代表的是二进制离散无记忆信道(BDMC)，其中X表示信道输入，Y表示信道输出，信道转移概率用W (y|x)表示，N个信道组合而成的合成信道为$W_N:X^N\to Y^N$ ，W^N表示信道的N次使用，则$W^N:X^N\to Y^N$ 信道的转移概率公式如式(1)所示：

$W^N\left(y_1^N|x_1^N\right)={\displaystyle \prod }_{i=1}^{N}W\left(y_i|x_i\right)$ (1)

例如，当N = 2时，代表两个信道组合成$W_2:X^2\to Y^2$ ，信道组合过程如图1所示，其转移概率如式(2)所示：

$W_2\left(y_1,y_2|u_1,u_2\right)=W\left(y_1|u_1\oplus u_2\right)W\left(y_2|u_2\right)$ (2)

Figure 1. Channel joint diagram of W₂

图1. W₂的信道联合图

以此类推，信道W_N的转移概率可表示如式(3)所示：

$W_N\left(y_1^N|u_1^N\right)=W^N\left(y_1^N|u_1^N{G}_N\right)$ (3)

W_N的信道联合图如图2所示，其中R_N是一种比特置换结构，用于把奇数索引的元素重新打乱排列成偶数索引元素。

Figure 2. Channel joint diagram of W_N

图2. W_N的信道联合图

2.1.2. 信道分裂

信道分裂是指把合成的信道拆分为N个子信道的过程。信道$W_N$ 分裂成N个子信道的过程可用$W_N^{\left(i\right)}:X\to Y^N\times X^{i-1},1\le i\le N$ 来表示，其信道转移概率为式(4)所示。

$W_N^{\left(i\right)}\left(y_1^N,u_1^{i-1}|u_i\right)\triangleq {\displaystyle \sum }_{u_{i+1}^N\in X^{N-i}}\frac{1}{2^{N-1}}\ast W_N\left(y_1^N|u_1^N\right)$ (4)

式中，$\left(y_1^N,u_1^{i-1}\right)$ 代表$W_N^{\left(i\right)}$ 的输出，$u_i$ 是输入，表示的含义是当输入是$u_i$ ，输出是$y_1^N$ 、$u_1^{i-1}$ 时信道的转移概率。

2.2. Polar码编码原理

在经过信道的整合与拆分操作后，比特信道展现出了容量的两极分化效应，部分子信道几乎不含噪声，而其余的则充满了干扰。基于这一特性，Polar码将数据单元分布在较为清澈的子信道中，而将剩余的信道用于放置收发双方都知晓的比特(通常为比特0)，这些位置被称作冻结位，实质上并未进行信息的传输。那些收发双方都了解的比特被称作冻结比特。Polar码的编码机制可以通过公式(5)来描述：

$x_1^N=u_1^N{G}_N$ (5)

其中，$u_1^N$ 表示原始发送比特添加冻结比特后的向量，$x_1^N$ 是经由polar编码后的比特序列，$G_N$ 表示的是生成矩阵。

$G_N=B_N{F}^{\otimes n}$ (6)

其中$F^{\otimes n}$ 指$F=\left[\begin{array}{cc}1& 0\\ 1& 1\end{array}\right]$ 的n次克罗内克积，$B_N$ 是排序矩阵，通过重新排列索引矩阵，可以将各个子

信道的索引以二进制形式表示，并将其倒序排列以生成一个新的序列，通过这种交换方式，将原序列中的索引与生成的索引进行位置对调，从而构建出最终的输出序列，具体过程如下式(7)所示：

$B_N=R_N\left(I_2\otimes B_{\frac{N}{2}}\right)$ (7)

假定polar码的总长度为N，待传输的信息比特总数为K，已知信息子信道的索引集合记作A，其元素数量与K相等，polar码的信息位用$u_A$ 表示。基于这四个要素，便可以明确一个polar码的结构，再通过公式(5)进行编码，即可得到polar编码的比特序列。

在现实的无线传输场景中，信道状况极具变化性，这就导致没有一种普适性强的子信道可靠性评估公式适用于大部分信道环境。因此，开发一种能够适应多种信道条件，且在应用不同接收算法时都能保持优异性能的通用polar码设计显得尤为重要。

3. 基于CA-GA算法的Polar码构造算法

3.1. 算法思路

针对上述问题，本文提出了一种基于遗传算法的polar码编码构造方案，在计算信道可靠度和从极化信道$W_N^{\left(i\right)}$ ，($1\le i\le N$ )中选取K个最可靠的极化信道的过程中引入遗传算法，本文中遗传算法计算的适应度值即传统构造方法计算的可靠度，信道集合可看作种群，通过计算适应度值(可靠度)来寻找最适合的种群个体(传输信道)，寻找具有最小的成本函数的最优信息集[11]。此算法在短极化码极化不充分的情况下可以较为准确地计算信道可靠度并寻找信息比特序列集合中的冻结位上的冻结比特，更准确的构造极化码，具有更好地编码性能[12]。针对提高低信噪比下信息传输可靠性的问题，本文选择了误码率作为成本函数，以高斯白噪声信道为例进行仿真实验[13]。

polar码构造的优化模型目标函数为：

$A_{\text{opt}\cdot }=\text{arg}\underset{A}{\min }\text{BER}\left(A\right)\text{or}\text{BLER}\left(A\right)$ (8)

约束条件为：

(9)

算法流程图如下图3所示：

Figure 3. Flow chart of polarity code design based on genetic algorithm

图3. 基于遗传算法的极性码设计流程图

3.2. 改进遗传算法

3.2.1. 初始种群生成

与传统的遗传算法随机生成个体不同，本文采用先验知识引导初始化，初始种群先验知识指的是在遗传算法中为了提高算法的效率和准确性，可以利用已知的相关知识来构建初始种群。在搜索空间较大的情况下，遗传算法很容易陷入局部最优解，引入先验知识可以使算法更快地跳出局部最优解。而本文正是采用GA构造法、巴氏参数法和蒙特卡洛构造法这三种传统构造方法来计算信息子信道索引向量从而获取初始种群。

3.2.2. 改变交叉变异概率

传统遗传算法中变异概率(p_c)和交叉概率(p_m)是固定不变的，通常来说，前期变异概率与交叉概率需要稍大一点来更好地进行寻优，而后期则不需要太大的变异和交叉概率，若一直用较大的交叉概率，则容易陷入局部最优。

本文采用交叉点动态变化的两两交叉，首先，利用rand()函数生成一个在区间(0,1)内的随机数，当随机值小于交叉概率时进行交叉操作，在自适应动态遗传算法中，交叉概率和变异概率是根据个体的适应度值动态调整。这一调整机制基于个体的适应度与种群中平均适应度及最大适应度的相对关系，当适应度越接近最大适应度时，交叉概率根据线性关系逐渐递减，但是交叉概率和变异概率不能为零，因为若为零会导致较优个体不会发生变化[14]，公式如下式(10)、(11)所示。

$p_c=\{\begin{array}{l}{k}_1\frac{fi{t}_{max}}{fi{t}_{max}-fi{t}_{min}},\frac{fi{t}_{ave}}{fi{t}_{max}}>a,\frac{fi{t}_{min}}{fi{t}_{max}}>b\\ k_1,其它\end{array}$ (10)

$p_m=\{\begin{array}{l}{k}_2\frac{fi{t}_{max}}{fi{t}_{max}-fi{t}_{min}},\frac{fi{t}_{ave}}{fi{t}_{max}}>a,\frac{fi{t}_{min}}{fi{t}_{max}}>b\\ k_2,其它\end{array}$ (11)

式中，$fi{t}_{max}$ 代表当前种群最大适应度值，$fi{t}_{min}$ 代表当前种群最小适应度值，$fi{t}_{ave}$ 代表种群平均适应度

值，其中参数$0.5<a<1$ ，$0.1<b<1$ ，当$\frac{fi{t}_{min}}{fi{t}_{max}}>b$ 时，认为个体集中，此时交叉率和变异率根据群体集中

程度进行自适应变化，使算法自行调整自然选择机制；不满足该条件时，判断为群体分散，交叉率和变异率则保持原始值。

3.2.3. 精英保存

自适应遗传算法存在一个实际问题，虽然该算法自适应调整交叉率和变异率，但二者可能会不断变大，这样就会造成优良个体被淘汰，本文采用最优保存策略来避免这一现象。基本思想为将当代群体中的最高适应值个体与上一代群体最高适应值个体相比较，如果上一代群体最高适应值较高，则随机淘汰掉当代群体中的一个个体，然后将上一代最高适应值个体加到当代中来。通过这种最优保存策略，保证了改进后自适应遗传算法可以很好地收敛。自适应动态遗传算法确保算法在搜索过程中不断探索新的解空间区域，避免陷入局部最优解；同时，它还能有效地防止算法过早收敛，确保遗传算法的收敛过程稳定[15]。精英保存公式如式(12)所示：

$X\left(t+1\right)=\{\begin{array}{l}X\left(t+1\right)\text{if}F\left(X\left(t+1\right)\right)<F\left(X\left(t\right)\right)\\ X\left(t\right) \text{other}\end{array}$ (12)

式中，$F\left(X\left(t+1\right)\right)$ 代表本次迭代的个体适应度值，$F\left(X\left(t\right)\right)$ 代表上一次迭代的个体适应度值。

3.2.4. 加入柯西变异算子

接着本文通过加入柯西变异算子利用柯西分布来得到两个变异位置，如图4所示，柯西分布在垂直方向上峰值相对较小；在水平方向上，当接近横轴附近时变化更加缓慢。柯西分布更容易产生远离原点的随机数，并且随机数分布范围广泛，这使得遗传算法在初始时可以产生更加丰富多样的个体，容易跳出局部最优或平坦地带。克服了传统遗传算法的缺点，这样能更好地找到当前最优值，防止局部搜索出现早停现象[16]。

柯西分布概率密度函数为：

$f\left(x;x_0,\gamma \right)=\frac{1}{\pi }\left[\frac{\gamma }{{\left(x-x_0\right)}^2+{\gamma }^2}\right]$ (13)

高斯分布概率密度函数为：

$f\left(x\right)=\frac{1}{\sqrt{2\pi }\sigma }\text{exp}\left(-\frac{{\left(x-\mu \right)}^2}{2{\sigma }^2}\right)$ (14)

将柯西随机变量产生的随机扰动来得到两个变异位置，1变异为0，0变异为1。柯西变异的局部能力搜索较好，相比固定的变异概率值，在一定程度上会产生较好的变异幅度，因此会使算法具有较好的全局搜索能力。

Figure 4. Comparison of probability density function distributions between Gaussian distribution and Cauchy distribution

图4. 高斯分布和柯西分布的概率密度函数分布对比图

4. 仿真验证

为验证本文提出的基于CA-GA算法的polar码构造方案的性能，通过Matlab平台和以下参数对不同码长的poalr码的误块率进行仿真实验(表1)。

Table 1. Simulation parameters

表1. 仿真参数

系统参数	参数设置
信噪比	0.5:0.5:2.5
种群最大迭代次数	50
SCL译码保留路径数量	8
种群大小	60
蒙特卡洛仿真次数	100,000
仿真次数	10,000

如图5和图6所示，在不同码长条件下对CAGA算法构造和SCL译码算法进行误块率分析。在迭代次数为30次，在SNR达到2.5 dB时，码长128和码长256情况下的误块率分别达到0.0072和0.00197。在迭代50次和迭代70次，在SNR达到2.5 dB时，码长128情况下的误块率达到0.0068、0.0063，码长256情况下的误块率达到0.0015、0.0014，可见随着码长和迭代次数的增加，性能逐渐变优，综合运行时间、复杂度和性能三方面，本文选择折中的迭代次数为50次。

Figure 5. Performance comparison of block error rate under different iteration times under the condition of code length 128

图5. 码长128条件下不同迭代次数误块率性能对比

Figure 6. Performance comparison of block error rate under different iteration times under the condition of code length 256

图6. 码长256条件下不同迭代次数误块率性能对比

Figure 7. Comparison of error block rate performance of different construction methods under the condition of code length 128

图7. 码长128条件下不同构造方法误块率性能对比

图7展示了码长N为128时，在不同构造方法下采用SCL译码算法的误块率对比。当信噪比大于1.5 dB时，巴氏参数构造法性能最差，蒙特卡洛构造法稍优于高斯逼近法。而本文提出的算法要明显优于传统的三种构造方法，该算法构造Polar码在误块率为10⁻¹时，与蒙特卡洛构造法相比约有0.4 dB的净增益，在误块率为10⁻²时，与传统遗传算法构造方法相比约有0.1 dB的净增益。

Figure 8. Comparison of error block rate performance of different construction methods under the condition of code length 256

图8. 码长256条件下不同构造方法误块率性能对比

图8展示了码长N为256时，在不同构造方法下采用SCL译码算法的误块率对比。从图中可见巴氏参数构造法性能最差，当信噪比大于1.5 dB时，蒙特卡洛构造法稍优于高斯逼近法。而本文提出的算法要明显优于传统的三种构造方法，该算法构造的Polar码在误块率为10⁻²时，与传统的构造方法相比分别有0.4 dB、0.5 dB的净增益，与传统遗传算法构造法相比约有0.05 dB的净增益。

Figure 9. Comparison of error block rate performance of different construction methods under the condition of code length 512

图9. 码长512条件下不同构造方法误块率性能对比

图9展示了码长N为512时，在不同构造方法下采用SCL译码算法的误块率对比。可以看出巴氏参数构造法性能最差，当信噪比处于0.5~1.6 dB时，蒙特卡洛构造法性能稍差一些；而当信噪比大于1.6 dB时，蒙特卡洛构造法稍优于高斯逼近法；本文提出算法也优于传统三种构造方法，在误块率为10⁻²时，与传统的构造方法相比分别有0.1 dB、0.15 dB的净增益，与传统遗传算法构造法相比约有0.02 dB的净增益。

Figure 10. Comparison of error block rates for code lengths of 128, 256, and 512

图10. 码长128、256、512的误块率对比

图10展示了不同码长情况下采用优化遗传算法的误块率性能对比，可以看出在信噪比处于0.5~1.2 dB之间时，码长为128时的误块率最好，码长256次之，码长512的最差，而当信噪比大于1.2 dB时，码长为512时的性能最好，误块率较低，码长256情况下次之，而码长128的性能最差，由此可见，随着信噪比的增加，码长越长，性能越好。

5. 总结

本文提出了一种基于优化遗传算法的polar码构造方案。结合巴氏参数构造法、GA构造法以及蒙特卡洛构造法，形成的信息子信道的索引向量作为先验知识，形成初始群体。融合精英保存算法与柯西变异机制于遗传算法之中，通过种群更新与迭代操作，培育适应度优异的群体和个体。通过对遗传算法的优化升级，有效减少误码率。但算法存在因复杂度提升而导致译码时间增加的问题，后续将从降低复杂度角度对算法进行优化和完善。