基于遗传算法的（n，n-1，m）卷积码盲识别*

张 岱，张 玉，杨晓静，樊斌斌

（电子工程学院，合肥 230037）

基于遗传算法的（n，n-1，m）卷积码盲识别*

张 岱，张 玉，杨晓静，樊斌斌

（电子工程学院，合肥 230037）

针对信息截获领域中（n，n-1，m）卷积码盲识别问题，提出基于遗传算法的盲识别方法。该方法在矩阵分析得到编码参数之后，利用遗传算法的全局搜索能力实现对基本校验多项式矩阵的精确识别，进而实现对基本生成多项式矩阵的识别。仿真表明：该方法能够在高误码条件下实现对（n，n-1，m）卷积码的盲识别，且运算量相对于以往的高容错识别方法得到降低。

信息截获，卷积码，盲识别，遗传算法

0 引言

在现代数字通信系统中普遍采用信道编码技术以提高信息传输的安全可靠性，其中，卷积码作为信道编码中一种典型的纠错编码方式，广泛应用于卫星通信、深空通信等领域中。因此，卷积码盲识别研究在非合作环境下的信息截获等领域具有重要意义［1］。（n，n-1，m）卷积码具有较高的编码效率，故本文将针对（n，n-1，m）卷积码的盲识别展开研究。

卷积码盲识别技术的重要性受到了国内外越来越多研究人员的关注［2-8］，目前的识别方法主要有基于欧几里德算法的识别方法［3］、Walsh-Hadamard分析法［4］、基于校验统计的识别方法［5-6］、基于BM的快速合冲法［7］和基于矩阵分析的识别方法［8］等。其中基于欧几里德算法的识别方法适用于1/n码率卷积码，运算量小但容错性能差；Walsh-Hadamard分析法和基于校验统计的识别方法同样只适用于1/n码率卷积码，具有较好的容错性，但运算量巨大；基于BM的快速合冲法运算量小且具备一定容错性，但该方法只适用于1/2码率卷积码的识别；基于矩阵分析的识别方法可对不同码率卷积码进行全盲识别，其中在对卷积码编码参数识别时具有较高容错性，但对基本校验矩阵进行识别时容错性差。

综上所述，现有的卷积码识别方法主要针对1/n码率卷积码进行识别，对（n-1）/n码率卷积码识别研究少，且容错性能差。为此，本文提出一种基于遗传算法的卷积码盲识别方法，可实现对高误码（n，n-1，m）卷积码的盲识别。

1（n，n-1，m）卷积码盲识别问题描述

记u和c分别为（n，n-1，m）卷积码的信息序列和码字序列，在F2（x）上，二者满足如下关系：

式（1）中，G（x）为（n，n-1，m）卷积码的生成多项式矩阵。同时，存在校验多项式矩阵H（x），并满足以下关系［9］：

对于（n-1）/n码率卷积码，其基本校验多项式矩阵可表示如下：

通过矩阵分析法对卷积码编码数据进行处理可得到如下结果［7］：

通常情况下，当接收数据中存在误码时仅会使校验序列P1i发生错误，而不影响对卷积码编码参数的识别结果，由式（6）可直接识别得到原卷积码码长n。记P1i所在列数为p，则码字约束度K+1估计如下：

利用式（6）、式（7）识别得到的卷积码参数n、K，对截获的含错码字序列r={r1，0，r2，0，…，rn，0，…，r1，NK+N-1，r2，NK+N-1，…，rn，NK+N-1}构建编码矩阵如下：

结合式（1）、式（2）可得编码矩阵R与基本校验序列之间有如下校验关系：

由此，对（n，n-1，m）卷积码基本校验多项式矩阵的识别问题转化为求F2上含错线性方程组式（9）最优解的问题。

2 基于遗传算法的（n，n-1，m）卷积码盲识别

遗传算法由美国密歇根（Michigan）大学教授John H.Holland于20世纪70年代初提出，该算法运行原理基于模仿生物进化的过程，是一种概率性的自适应迭代寻优算法。它从某一随机产生的或是特定的初始群体（父体）出发，按照一定的操作规则，如选择、交叉、变异等，不断地迭代计算，并根据每一个个体的适应度，保留优良品种，淘汰次品，引导搜索过程向最优解逼近。因此，遗传算法是一种能在复杂空间中进行鲁棒搜索的方法，能够解决许多传统的优化方法难以解决的优化问题［10］。

2.1 算法适应度函数及判决门限分析

由第1节可知，对（n，n-1，m）卷积码基本校验多项式矩阵的识别问题即为求式（9）的最优解问题。任取F2上非零n（K+1）×1向量hk，则有：

上式bk中0的数目表示R的行向量中与hk满足校验关系的数目，线性含错方程组式（9）的最优解即为使得bk中0数目最多的行向量hk。对于（n，n-1，m）卷积码，其基本校验序列h唯一，因此，可求解如下：

综合以上分析，将适应度函数确定如下：

对于F2上n（K+1）×1向量空间中任意元素hk，若hk≠h，则对bk中的每个元素bkj，j=1，2，…，N，有：

即bkj～b（1，1/2），有E（bkj）=1/2，D（bkj）=1/4。当编码矩阵行数N取足够大时，有：

φ（x）为标准正态分布函数。设定识别虚警概率为pfa=1×10-5，令：

可查表求得f（k）的取值范围为：

因此，设定适应度判决门限为：

2.2 基于遗传算法的（n，n-1，m）卷积码识别

利用第1节原理识别积码参数n、K，进而采用遗传算法对（n，n-1，m）卷积码的基本校验矩阵进行识别。算法实现的具体步骤如下：

1）利用识别得到的参数n、K，选取一较大数N，将接收序列按式（8）形式构建编码矩阵RN×n（K+1）；

2）设定染色体长度L=n（K+1），群体规模M（每代处理的染色体数目）；设定进化代数上限Gen、选择概率Ps、交叉概率Pc和变异概率Pm，使得Ps+Pc+ Pm=1，以确保每代染色体的完备；根据式（12）、式（20），确定适应度函数f（k）和适应度判决门限λ；

3）随机从F2上n（K+1）×1向量空间中选择初始染色体hk（1≤k≤M），并构造初始群体集H0= {h1，h2，…，hM}；

4）遍历选取H0中元素hk（k=1，2，…，m），计算RN×n（K+1）·hkT=bk，得到群体中M个个体的适应度值：{f（k）|k=1，2，…，M}，此时进化代数gen设置为0；

5）判断max{f（k）|k=1，2，…，M}是否大于适应度判决门限λ，若条件满足则结束进化，输出最优解h={hi|f（i）=max（f（k）），i，k=1，2，…，M}，结束算法运行；若不满足判决条件则进行遗传进化：选取Hgen中适应度最高的M·Ps个个体直接复制；选取适应度最高的M·Pc个个体，将其两两配对在随机位置上进行交叉；选取适应度适中的M·Pm个个体，对每个个体选择随机位置进行突变，处理后传递给下一代；

6）令gen=gen+1，计算新一代群体中M个个体的适应度值：{f（k）|k=1，2，…，M}，返回步骤5）；若gen=Gen，则识别失败，结束算法运行。

利用遗传算法识别得到的基本校验序列h可根据式（3）、式（4）还原出原卷积码的基本校验多项式矩阵h（x）。对于（n，n-1，m）系统卷积码其基本生成多项式矩阵g（x）与基本校验矩阵之间存在严格的相似转换关系，因此，可由h（x）直接变换得到。对于（n，n-1，m）非系统卷积码基本生成多项式矩阵的识别原理如下：

解多项式方程组式（20）时将得到多解，这些解均是基本多项式矩阵行向量的线性组合，因此，可通过对解向量进行初等变换使其化到最简，最终完成原卷积码基本生成多项式矩阵g（x）的识别［11］。

3 仿真分析

以（2，1，6）和（3，2，4）非系统卷积码识别为例验证本文算法的可行性。其基本生成多项式矩阵分别表示如下：

仿真生成误码率为0.05的（2，1，6）和（3，2，3）两种卷积码序列，利用第1节原理对其进行识别，可得到如下结果：对（2，1，6）卷积码含错序列，码长n1=2，码字约束度为7，即K1=6；对（3，2，3）卷积码含错序列，码长n2=3，码字约束度为7，即K2=6。

随后基于遗传算法对（n，n-1，m）卷积码的基本校验序列进行识别，设置仿真条件：编码矩阵R行数N=400，对两种卷积码识别的染色体长度分别设定为：L1=14、L2=21；群体规模M=60，进化代数上限Gen=2 000，选择概率Ps=0.2，交叉概率Pc=0.4，变异概率Pm=0.4；适应度函数f（k）=400-weight（bk），适应度判决门限λ=242。分别对两种卷积码含错编码序列进行识别仿真，其识别情况如图1所示。

由图1知，利用遗传算法进行识别时，对（2，1，6）卷积码，当进化到350代时，群体最高适应度值达到245，对（3，2，3）卷积码，当进化到1 526代时，群体最高适应度值达到249，均搜索到满足条件的染色体，即所要识别的基本校验序列。由仿真还可得到，识别进化代数随基本校验序列长度的增加而逐渐增多，这是由搜索空间的扩张所致。利用遗传算法识别得到两种卷积码的基本校验序列分别为h1=11100011110111和h2=111000110111000111101。由此，h1（x）和h2（x）可分别表示如下：

对（2，1，6）卷积码，在F2（x）上其基本校验多项式矩阵与基本生成多项式之间有如下关系：

又gcd（g1，1（x），g1，2（x））=0，且一般卷积码编码器不存在反馈逆［8］，可得：

最终识别得到（2，1，6）卷积码含错编码序列的原基本生成多项式矩阵为：

对（3，2，3）卷积码含错编码序列，根据式（21），设基本生成多项式矩阵的最高阶数（编码记忆长度）为m，建立F2（x）上的多项式方程如下：

对多项式方程式（27）分析可得，其最高阶次为m+6，未知项系数有3（m+1）个，由此，将式（27）按阶次提取系数可构建F2上方程个数为m+7、未知数个数为3（m+1）的线性方程组。又基本生成多项式矩阵的行数即为方程式（24）最大线性无关解的个数，即解空间维数。对线性方程组维数进行分析可得如下关系：

解得卷积码编码记忆长度为m=3。求解由多项式方程式（27）系数提取构造的线性方程组，得到基础解向量为：p1=111101101101，p2=111111011010。表示成多项式矩阵形式如下：

对p（x）作行初等化简，使其行最高阶次最小（即使编码矩阵结构最简）［11］，得到：

式（26）和式（27）识别结果均与原卷积码基本生成多项式矩阵相同，验证了本文算法在高误码环境下对（n，n-1，m）卷积码盲识别的可行性。

当前对（n，n-1，m）卷积码识别主要采用矩阵分析法，此外采用校验统计的方法也可对（n，n-1，m）卷积码进行识别，但由于需对2n（K+1）个F2上向量进行逐个检验，运算量较大，因此，不具有实用性［5］。现在卷积码参数n和K准确识别的基础之上，对3 000 bit不同误码率的（3，2，3）卷积码序列，分别采用矩阵分析法［8］和本文算法（为保证实时性，设置进化代数上限Gen=2 000）识别其基本校验序列，通过蒙特卡罗方法统计识别概率如图2所示。

由图2可以看出，采用矩阵分析法对（n，n-1，m）卷积码进行识别，当误码率达到0.02时，对卷积码基本校验序列的识别率将降低到50%以下，而采用本文算法进行识别时，当误码率在0.07左右时，对基本校验序列的准确识别率仍能达到50%以上，识别率取得了明显提高。同时，由于本文算法与基于校验统计的识别算法均是通过在F2上向量空间中寻找编码约束方程组最优解向量实现对基本校验序列的识别，因此，本文算法与基于校验统计识别算法的识别概率接近，然而在运算量对比上，基于校验统计识别算法识别运算量为N（2nK+2n-1）（2n（K+1）-1），本文算法在进化到进化代数上限Gen时运算量为Gen·M·N（2nK+2n-1）。当对（3，2，3）卷积码进行识别时，基于校验统计识别算法运算量在1010量级，本文算法运算量在108量级，运算量得到了明显降低。

4 结束语

本文提出了基于遗传算法的卷积码盲识别方法。该方法通过矩阵分析识别卷积码参数，利用遗传算法的全局搜索能力实现对高误码（n，n-1，m）卷积码基本校验多项式矩阵的准确识别，进而通过与基本生成多项式矩阵间的校验关系实现对基本生成多项式矩阵的识别。仿真结果表明，与矩阵分析法［7］相比，本文方法具有较好的容错性，同时，和校验统计的方法［5］相比，极大地降低了运算量，在非合作信号处理及智能通信等领域具有重要应用意义。

［1］解辉，黄知涛，王丰华.信道编码盲识别技术研究进展［J］.电子学报，2013，41（6）:1166-1176.

［2］Marazin M，Gautier R，Burel G.Blind Recovery of k/n Rate Convolutional Encoders in a Noisy Environment［J］.EURASIP Journal on Wireless Comunications and Networking，2011:168.

［3］刘建成，杨晓静，张玉.基于改进欧几里德算法的（n，1，m）卷积码识别［J］.探测与控制学报，2012，34（1）:64-68.［4］刘健，王晓君，周希元.基于Walsh-hadamard变换的卷积码盲识别［J］.电子与信息学报，2010，32（4）:884-888.

［5］解辉，王丰华，黄知涛.基于最大似然检测的（n，1，m）卷积码盲识别［J］.电子与信息学报，2013，35（7）:1672-1676.

［6］张东，陈格顺，王格芳，等.一种新的高误码（2，1，m）卷积码盲识别方法［J］.火力与指挥控制，2013，38（11）:69-72.

［7］Peizhong L，Yan Z.Fast Computations of Grobner Bases and Blind Recognitions of Convolutional Codes［J］.Lecture Notes in Computer Science，2007，4547:303-317.

［8］杨晓静，刘建成，张玉.基于求解校验序列的（n，k，m）卷积码盲识别［J］.宇航学报，2013，34（4）:568-573.

［9］Marazin M，Gautier R，Burel G.Some Intresting Dual-code Properties of Convolutional Encoder for Standards Self-recognition［J］.IET Commun，2012，8（6）:931-935.

［10］王耀南.智能信息处理技术［M］.北京：高等教育出版社，2003.

［11］Cote M，Sendrier N.Reconstruction of Convolutional Codes from Noisy Observation［C］//ISIT 09，Seoul，Korea，2009: 546-550.

Blind Recognition of（n，n-1，m）Convolutional Code Based on Genetic Algorithm

ZHANG Dai，ZHANG Yu，YANG Xiao-jing，FAN Bin-bin
（Electronic Engineering Institute，Hefei 230037，China）

Considering blind recognition of（n，n-1，m）convolutional code in information interception，a recognition method based on genetic algorithm is proposed.After obtaining coding characters through matrix analysis，this method achieves accurate recognition of the basic check polynomial matrix by utilizing global searching ability of the genetic algorithm.Then，recognition of basic generator polynomial matrix is realized.The simulation shows that this method can blindly recognise（n，n-1，m）convolutional code in a high BER environment，while its computing efforts get lower compared with high fault-tolerant methods before.

information interception，convolutional code，blind recognition，genetic algorithm

TP309

A

1002-0640（2015）09-0031-04

2014-08-12

2014-09-18

国家自然科学基金（61201379）；安徽省自然科学基金资助项目（1208085QF103）

张 岱（1993- ），男，安徽太和人，硕士研究生。研究方向：信道编码识别分析。