基于粒子群算法的(n,1,m)卷积码盲识别

占 超，何显鹏

(中国人民解放军92515部队，辽宁 葫芦岛 125001)

0 引言

现代数字通信系统中一般采用信道编码技术，以避免噪声和干扰的影响，实现信息的可靠传输。(n,1,m)卷积码是一种常见的编码方式，它具有编码易于实现以及纠错性能强等优点，在深空探测、数字通信等领域应用广泛。因此，对(n,1,m)卷积码的盲识别进行研究，具有十分重要的意义[1-6]。

目前，卷积码盲识别方法主要有高斯解方程法[7-8]、欧几里德法[9-12]和矩阵分析法[13-16]。其中，高斯解方程法无法容错，且必须预先知道码字起点等先验信息；欧几里德法相比高斯解方程法大大降低了计算量，但只适于无记忆的卷积码识别；矩阵分析法利用接收序列建立分析矩阵，然后初等变换并从中提取码长及检验序列等信息，但误码适应性较差。因此，针对以上不足，本文提出了一种新的基于粒子群算法的(n,1,m)卷积码盲识别方法。

1 问题描述

卷积码常记为(n,k,m)，其中n称为码长，k称为信息分组长度，m称为编码记忆长度。对于本文的(n,1,m)卷积码，它表示编码器每输入1路信息序列u(x)，则输出n路编码序列V(x)，其中：

u(x)=u0+u1x+…+uixi+…，

(1)

C(x)=[c1(x)c2(x) …cn(x)]，

(2)

cj(x)=cj,0+cj,1x+…+cj,lxl+…,j=1,2,…,n。

(3)

设生成多项式矩阵为G(x)，则编码过程可表示为：

C(x)=u(x)G(x)，

(4)

其中，

G(x)=[g1(x)g2(x) …gn(x)] ，

(5)

gi(x)=gi,0+gi,1x+…+gi,mxm,i=1,2,…,n。

(6)

令H(x)表示校验矩阵，则

(7)

(8)

根据文献[17]，有：

G(x)HT(x)=0。

(9)

由式(4)和式(9)，得：

C(x)HT(x)=u(x)·G(x)·HT(x)=0。

(10)

因此，(n,1,m)卷积码盲识别就是利用已接收的编码序列识别码长n和信息分组长度k，然后恢复校验多项式矩阵H(x)，并利用式(9)得到生成多项式矩阵G(x)。

2 识别方法介绍

2.1 模型建立

将式(10)展开，得：

(11)

(12)

为了便于直接利用编码序列构建方程，将上式转换为：

(13)

2.2 基于粒子群算法的校验矩阵识别

粒子群算法通过模拟鸟群飞行觅食的行为方式，基于鸟个体之间的集体协作使群体达到最优[18]。该算法具有概念简明、实现方便、收敛速度快以及参数设置少等特点，是一种高效的群智能算法。在粒子群算法中，每个个体被称为一个“粒子”，而每个粒子的所在位置代表着一个潜在的解。每个粒子按一定规则运动，并估计自身位置的适应值，同时记住自己目前找到的最佳位置，此外还要记录所有粒子达到的最佳位置。所有粒子都逐渐向最佳位置靠近，最终达到收敛状态。

令D=n(M+1)，粒子群群体规模为q，zi=(zi1,zi2,…,zid,…,ziD)为第i个粒子(1≤i≤q)当前所在位置。每次迭代中，根据所设定的适应值函数计算zi当前的适应值，即可衡量粒子位置的优劣。设vi=(vi1,vi2,…,vid,…,viD)为粒子i的飞行速度，pi=(pi1,pi2,…,pid,…,piD)为粒子i迄今为止所搜索到的最佳位置，pg=(pg1,pg2,…,pgd,…,pgD)为整个粒子群迄今为止搜索到的最佳位置。

在每次迭代中，每个粒子按下式更新速度：

(14)

式中，a1和a2为学习因子，也称加速因子，它使粒子具有自我总结和向群体中其他优秀个体学习的能力；r1和r2用来保持群体的多样性；w称为惯性权重。a1,a2在[0, 4]上，一般选取a1=a2=2。r1,r2是[0, 1]上的随机数。惯性权重w起着权衡局部最优能力和全局最优能力的作用，实际问题中，往往希望先采用全局搜索，使搜索空间快速收敛于某一区域，然后采用局部精细搜索已获得高精度的解。因此，将其设定为一个随时间线性减少的函数，并表示为：

(15)

在不同速度下，粒子的位置得到如下更新，

(16)

式中，ρ为[0, 1]之间的随机数，且

(17)

由于粒子群算法中，没有实际的机制来控制粒子速度，因此有必要对速度的最大值进行限制，当速度超过这个阈值时，将其设定为vmax。通常选取vmax=6，此时Sigmoid(·)的取值范围为[0.002 5, 0.997 5]。

下面对适应值函数的选取进行说明。当zi是方程组(13)的根时，该线性方程组中方程成立的个数达到最多。反之，方程成立与否的概率各为0.5。令cl=[c1,l…cn,lc1,l+1…cn,l+1…c1,M+l…cn,M+l]，并计：

(18)

2.3 生成多项式求解

在得到校验多项式矩阵H(x)，将根据式(9)展开，有：

(19)

式中，包含n(m+1)个未知数，而通过待定系数法可以列出(n-1)(m+M+1)个方程，要保证有解，则必须满足(n-1)(m+M+1)≤n(m+1)，即m≥n(M-1)-1。以此可以计算得到生成多项式矩阵G(x)。

综上，(n,1,m)卷积码识别步骤可总结如下：

输入：接收序列c；

输出：码长n，编码记忆长度m，生成多项式矩阵G(x)；

识别步骤：

步骤1：设定码长取值范围2≤n≤8，校验多项式最高次数取值范围2≤M≤6，取n和M的初值为2；

步骤2：设定粒子群算法的种群规模q=50，算法最大迭代次数kmax=⎣22m+1/q」，其中⎣·」表示向下取整；

步骤3：按式(13)建立方程组，并采用粒子群算法计算bi值；

步骤4：判断bi值是否大于门限T。如果是，则记录对应的M值和向量zi，并将其转为校验多项式矩阵H(x)。反之，判断M是否大于6，如果是，则n自加1，并重复步骤3、4；如果否，则M自加1，并重复步骤3、4；

步骤5:设定m初值为n(M-1)-1，根据式(19)计算生成多项式矩阵G(x)。

3 仿真分析

选取(4,1,5)卷积码进行仿真，其生成多项式用8进制可表示为G(53,67,71,75)，即G(x)=[1+x2+x4+x51+x+x3+x4+x51+x+x2+x51+x+x2+x3+x5]。首先生成2 000 bit卷积码编码数据，然后随机加入误码率为0.01的误比特，按2.3节步骤进行识别，通过对参数进行遍历，当n=4,M=2时，结果如图1所示。此时，方程共有15个解，分别为(000011000110),(001101010011),(001110010101),(010100011100),(010111011010),(011001001111),(011010001001),(100101111100),(100110111010),(101000101111),(101011101001),(110001100000),(110010100110),(111100110011)和(111111110101)。

图1 (4,1,5)卷积码识别结果

选取第1、第2和第4个解，可得：

(20)

令m=5，带入式(19)，可以建立如下方程组：

(21)

解方程，最终得到解向量为(101011110111111001111101)，因此G(x)=[1+x2+x4+x51+x+x3+x4+x51+x+x2+x51+x+x2+x3+x5]，与前面设置的参数相同，识别正确。

将本文方法、文献[13]中基于矩阵分析的方法和文献[16]中基于欧几里得的识别方法进行抗误码性能对比。选取(3,1,5)卷积码作为研究对象，生成1 000组码字，加入错误比特后按不同方法进行识别。在每组误比特率和识别方法组合下分别进行500次蒙特卡洛仿真，结果如图2所示。可以看出，本文识别方法性能明显优于其他2种方法。

图2 不同识别方法抗误码性能对比图

4 结束语

针对传统(n,1,m)卷积码盲识别方法对误码适应性较差的问题，基于粒子群算法提出了一种新的识别方法。该方法能有效完成各参数的识别，并具有较好的容错性能。仿真结果表明，该方法在误码率低于10-2时能有效实现对常用卷积码生成多项式的估计，且性能明显优于传统方法，能有效满足通信侦察和自适应调制编码等不同应用领域的要求。后续将针对其他码率的卷积码进行进一步的研究。