基于游程间隔特征的线性分组码码长识别方法

李歆昊，张 旻，陆 凯，吕全通

（1.解放军电子工程学院，安徽 合肥230037；2.安徽省电子制约技术重点实验室，安徽 合肥230037）

0 引言

为了实现通信的可靠性，并提高通信的效率，信道编码在现代通信中得到了普遍的应用。如在智能移动通信、多点广播通信、认知无线电和认知通信领域，都需要接收方仅根据接收的未知数据快速识别出信道编码参数；此外，在非合作的通信条件下，信道编码识别可以准确获取编码参数从而完成信息的还原，因此在通信侦察和网络对抗领域也有着迫切的军事需求。信道编码识别已经成为目前国内外研究的热点问题［1］。

信道编码主要分为线性分组码和卷积码，其中线性分组码被广泛应用在数字通信系统和卫星通信系统中［2］。但目前对信道编码识别的研究还主要集中在卷积码上，对线性分组码的识别偶有涉及，且深度远远不够［1］。而且信道编码的识别分析主要停留在有限先验知识的情况下进行［3-9］，真正的全盲识别分析还不多。如在已知码字起点的基础上，通过码重分布距离的方法完成对线性分组码的盲识别［3］；在码长已知的前提下利用高斯解方程和综合分析法，实现线性分组码的盲识别［1］。文献［8］虽然利用线性分组码对偶码字的统计特性和Walsh-Hadamard变换实现了全盲识别，但算法对误码率要求过高，距离实际应用还有较大差距。可见，目前有效的信道编码盲识别是在已知码长或码字起点的基础上完成对生成矩阵或生成多项式的识别，而实际分组序列的码字起始点往往难以获得，因此获取码长后再对码字进行盲识别就具有十分重要的意义。

本文针对现有识别算法中存在的对接收序列误码率要求高和需要一定先验知识的不足，提出了基于游程间隔特征的码长识别方法。算法通过统计接收序列的游程间隔分布实现了对码长的识别，与现有的单位化矩阵求秩相比，本文算法可以极大地降低计算量且提高了识别效率和算法的鲁棒性，具有较好的抗误码性能。

1 线性分组码的基本概念

1.1 线性分组码的定义

定义1：将信息码元分组，为每组信息码附加若干监督码的编码称为分组码。若每个监督码元都是由码组中某些信息码元线性相加得到的，则称这样的分组码为线性分组码［9］。

定义2：GF（q）上的n维线性空间Vn中的k维子空间Vn，k构成的码字称为（n，k）线性分组码［10］。

显然，在二进制下，2n个n维组成了一个GF（2）上的n 维线性空间，2k个码字集合构成了一个k 维线性子空间。而这2k个码字完全可由k 个相互独立码字构成的一组基线性表示出来，如果把这个基写成矩阵形式G，即称为（n，k）码的生成矩阵，它的秩是k，k／n就是编码码率。

1.2 线性分组码码长的定义

对于线性分组码的码长识别问题，首先要了解码字的产生方式，然后通过对码字序列的分析处理，从而估计出码长。其数学模型描述为：

式中，M = ｛M1，M2，…，Mi，…｝表示以k比特为分组单位的输入，Mi= ｛m1m2…mk｝表示第i时刻输入的k个比特信息；C=｛C1，C2，…，Ci，…｝表示以n比特为分组单位的编码输出序列，Ci= ｛c1c2…cn｝表示第i时刻输出的n 个比特信息；G 表示生成矩阵。实际中，C 是通过对接收或侦察信号解调处理得到。因此，线性分组码的码长识别问题就是在仅知道比特流的前提下如何获得编码输出序列C中每个时刻输出比特信息Ci的长度n 问题。

2 基于游程间隔的码长识别

2.1 游程的基本概念

定义3：设a是GF（2）上周期为v的周期序列，将a的一个周期a= （a0，a1，a2，…，av-1）依次按循环排列，使av-1与a0相邻，则把如100…001 和011…110的一连串两两相邻的项分别称为a的一个周期中的一个0游程和1游程。0游程中的0的个数或1游程中1的个数称为这个游程的长［1］。

2.2 游程间隔的基本概念

定义4：相同游程长度下前后相邻的两两0游程或1游程之间间隔的码元数称为游程间隔［1］。

对长度为L 的（n，k）线性分组码编码序列，定义码字C 的游程间隔H（C）是x（x ＜L）个整数的集合H（C）=｛Ni，1≤i≤x｝，Ni表示C 中游程间隔为i的数目。

2.3 线性分组码的游程间隔特性

定理1：（n，k）线性分组码的k位信息生成的n位码字集v是n 维空间V 的子集，且每组码字的校验位由该组的信息位唯一确定［1］。

对于（n，k）线性分组码，生成的码字集大小为2k≪2n，k位信息生成的n位码字的集合必定隶属于n位码字组成的码字集合。其中k位信息码元共有2k个不同组合，输出的码字矢量也应当有2k种，如图1（a）所示；长度为n的二元随机序列共有2n个可能的码字矢量，如图1（b）所示。可见（n，k）编码有2n-2k个禁用码字，破坏了线性分组码的随机特性，导致线性分组码的随机性能变差。

图1 码字分布图Fig.1 Code word distribution

由于游程长度t与信息位长度k 的关系直接影响到游程间隔的分布，而游程间隔的分布对于码长的识别又起到了关键的作用。因此，分析游程长度t与信息位长度k 之间存在以下三种可能：

t＜k

当游程长度小于信息位长度时，游程长度为t的0游程或1游程可能在一个码字的信息位和监督位中都出现，如图2（a）所示（此时t=1）；还可能在多个码字中同时出现，如图2（b）所示（此时t=3）。此时的游程间隔分布没有周期性且比较随机；

n＞t≥k

由于游程长度大于等于信息位长度、小于码长时的监督位很难出现多个连续的0和1，所以仅在t≈k时，游程长度为t的0游程或1游程才会在某两个码字首尾相接处出现，如图2（c）所示（此时t=6）。此时的游程间隔呈现周期分布特征，且在码长整数倍的位置上，游程间隔分布取得峰值。

3）t＞n

当游程长度大于码长时，随着游程长度的增加，此时游程长度为t的0游程或1游程出现的次数极少甚至不出现，即便是在两个码字首尾相接处，因为信息位和监督位很难出现连续的0和1，所以满足条件的0游程和1游程也很难出现。

图2 游程间隔分布Fig.2 Run interval distribution

由以上分析可知，仅在游程长度大于等于信息位长度时，游程间隔才呈现周期分布的特征，而且周期长度等于码长。

2.4 游程间隔的码长识别

对于接收到的一串长度为L，码长为n 的二进制线性分组码编码序列，将其按照游程长度t划分，统计1游程的游程间隔分布。从编码序列的第一位开始，寻找游程长度为t的1游程，记录下满足条件的游程起点，并继续搜寻下一起点，计算两点之间的间隔码元数。按照以上方法，依次遍历每个码元位置，计算所有可能的间隔码元数，统计相同间隔码元数出现的次数，得到1游程的游程间隔分布。按照同样的方法统计0游程的间隔分布，最后绘制图形识别码长。具体识别步骤如下：步骤1）初始化游程长度t，提取编码序列的0 游程和1 游程的游程间隔H（C）；步骤2）利用步骤1）得到的游程间隔H（C）绘制游程间隔分布图，并进行周期峰值检测，如未检测到周期峰值，游程长度加1，返回步骤1）；步骤3）继续提取相应游程长度下的游程间隔H（C），直到出现周期性峰值；步骤4）当检测到周期峰值时，此时对应的周期即为码长n，完成识别。

3 仿真实验

为了验证算法的有效性，使用matlab软件进行仿真实验。按照上文的算法，本文针对线性分组码分别产生了10万组四种不同的码字进行游程间隔的仿真对比实验，并选取其中三种码字在不同误码率的情况下作了抗误码性能的分析，实验结果验证了本文算法的有效性和鲁棒性。

3.1 线性分组码的码长识别

3.1.1 游程间隔的周期特性

选取（6，3）线性码10万组，统计游程长度为2、3、4且无误码情况下的游程间隔分布情况，结果如图3所示。

当游程长度为2小于信息位长度时，游程间隔分布集中在间隔长度为4处，且随着间隔长度的增加，游程间隔数量的取值越来越少，没有出现周期性特征，如图3（a）所示；当游程长度为4和3大于等于信息位长度时，游程间隔分布在码长整数倍的位置上都取得峰值，游程间隔分布出现周期性特征，如图3（b）、图3（c）所示。当游程长度继续增加，游程间隔分布的周期性特征也逐渐消失，与上文分析结果一致。

图3 （6，3）线性分组码游程间隔特征Fig.3 Run interval feature of（6，3）linear block code

3.1.2 码长的识别

选取（7，4）、（8，4）和（15，5）线性码各10万组，统计游程长度为4、4、5且无误码情况下的游程间隔分布情况，（7，4）码和（8，4）码的游程间隔取前50位值，（15，5）码的游程间隔取前200位，结果如图4所示。

游程长度分别为4、4和5，此时三组码字的游程长度都等于信息位长度。图4（a）中，在间隔长度为14、21、28等7的整数倍位置上游程间隔分布取得峰值；图4（b）中，在间隔长度为16、24、32等8的整数倍位置上游程间隔分布取得峰值；图4（c）中，在间隔长度为30、45、60等15的整数倍位置上游程间隔分布取得峰值。三组图片中，游程间隔分布都周期性的出现了峰值，而此周期的长度即等于待识别序列的码长。

图4 三组线性分组码游程间隔特征Fig.4 Run interval feature of 3different linear block code

图5 误码影响Fig.5 BER impact

3.2 误码性能分析

3.2.1 误码影响

选取（6，3）、（7，4）和（8，4）线性码各10万组，在不同误码率情况下各进行50的蒙特卡洛仿真实验。图5所示的是三种码字在误码率不断升高的情况下，能够成功识别的概率图。可以看出，在误码率小于3%的情况下，三种码长成功识别的概率都在50%以上，其中（6，3）线性码的最高。随着误码率的不断升高，成功识别的概率有所下降。

3.2.2 性能比较

选取（6，3）线性码10万组，分别利用单位化矩阵求秩算法和游程间隔分析法在不同误码率的情况下各进行50次的蒙特卡洛仿真实验。由图6可知，在误码率等于1%时，游程间隔分析法成功识别的概率达到了100%，而单位化矩阵求秩算法成功识别的概率在65%左右。随着误码率的升高，当误码率达到2%时，单位化矩阵求秩算法成功识别的概率接近0，已无法保证正确识别，而游程间隔分析法在误码率达到6%时仍然保持了90%的高识别率。可以看出，本文算法具有更好的容错性能和更高的实际应用价值。

图6 性能比较Fig.6 Performance comparison

4 结论

本文提出了基于游程间隔的线性分组码盲识别方法。该方法根据线性分组码的结构特征和理论分析，得到了隐藏在0-1序列内的游程间隔在游程长度大于等于信息位长度时会呈现周期性的特征。利用上述特征，通过统计不同游程长度下游程间隔的数量得到游程间隔的周期分布并从中提取出周期长度，实现对线性分组码码长的识别。由于信息位长度较短，所以算法无需完全遍历，计算复杂度低。仿真实验表明，在误码率一定的情况下，以上的方法仍可以很好地识别出线性分组码，具有一定的工程应用价值。在后续的研究中，我们将对算法进行改进，并尝试将其应用在其他码型的参数识别中。

［1］张永光，楼才义.信道编码及其识别分析［M］.北京：电子工业出版社，2010.

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

［3］昝俊军，李艳斌 .低码率二进制线性分组码的盲识别［J］.无线电工程，2009，39（1）：19-22.

［4］王甲峰，岳旸，权友波.二进制BCH 码的一种盲识别方法［J］.信息与电子工程，2011，9（5）：591-595.

［5］王兰勋，李丹芳，汪洋.二进制本原BCH 码的参数盲识别［J］.河北大学学报，2012，32（4）：416-428.

［6］杨晓静，闻年成.基于码根信息差熵和码根统计的BCH码识别方法［J］.探测与控制学报，2010，32（3）：69-73.

［7］Cluzeau M，Finiasz M.Recovering a code length and synchronization from a noisy international［C］／／Symposium on Information Theory.Seoul：ISIT，2009：1-5.

［8］杨晓炜，甘露.基于Walsh-Hadamard变换的线性分组码参数盲估计算法［J］.电子与信息学报，2012，34（7）：1643-1646.

［9］WANG F H，HUANG Z T，ZHOU Y Y.A method for blind recognition of convolution code based on Euclidean algorithm［C］／／IEEE International Conference on Wireless Communications.Shanghai：IEEE Press，2007：1414-1417.

［10］王新梅，肖国镇.纠错码——原理与方法［M］.西安：西安电子科大出版社，2001.