基于码根信息差熵和码根统计的BCH码识别方法

杨晓静,闻年成

(电子工程学院,安徽合肥 230037)

0 引言

BCH码是能够纠正多个随机错误的循环码,具有较强的纠错能力和严格的代数结构,同时具有构造方便、编码简单的优点。因此,BCH码在现阶段有着较为广泛的应用。在截获BCH码序列后,为侦获信息,需对编码方式和编码参数进行盲识别。

目前,此领域的研究主要集中于卷积码的盲识别和提高各种信道编码方式的编译码性能,而在编码方式识别及参数识别方面的相关研究很少。在目前编码方式识别的算法中,快速双合冲算法[1]实现了对1/2码率的卷积码的识别,但其模型不能应用于其他高码率的卷积码的盲识别;欧几里德算法[2]在低码率方面实现了对卷积码的盲识别,但没有考虑误码条件下的识别处理方法。文献[3]提出了一种新型数据矩阵模型,实现了对线性分组码的盲识别,并且该方法可推广到对系统卷积码的盲识别,但其也没有考虑误码条件下的识别处理方法。文献[4]提出了一种对低码率二进制线性分组码的识别方法,由码重分布函数提取码长参数 n的方法在4.71×10-3误码率条件下仍有效,并在此基础上通过矩阵变换获得生成矩阵,实现对二进制线性分组码的盲识别,但该方法不能解决高码率分组码的识别问题。与此同时,这些编码识别方法都采用了大量的矩阵运算,且对误码率的要求比较高,有的方法甚至要求无误码情况下,才能获得良好的性能。因此,在实际较高误码率条件下,如何正确识别BCH码成为一个难点问题。

本文针对本原BCH码的盲识别问题,提出了一种基于码根信息差熵和码根统计的识别方法。

1 BCH码识别基础

对于BCH码的盲识别问题,就是在不知道编码先验信息的情况下,通过对码字序列的分析处理,从而估计出其生成多项式,其数学模型为:

式中,m(x)表示信息输入多项式,c(x)表示信息编码输出多项式,g(x)表示编码生成多项式。实际中,c(x)是通过对接收或侦察信号解调处理得到。因此,BCH码的盲识别问题就是在仅知道c(x)的前提下如何获得生成多项式 g(x),进而完成对信息的还原。

定义1:给定有限域GF(q)及其扩域GF(qm),其中q=2,m为某一正整数。若码元取自GF(q)上的循环码,其生成多项式g(x)的根集合R中含有δ-1个连续根:

时,则由g(x)生成的循环码称为二进制本原BCH码,码长为n=2m-1,其生成多项式根的性质如下:

1)该生成多项式的根在GF(qm)中,且包含一组m个共轭根{a,a2,a4,…,a2m-1}[5],a是本原根。

2)该生成多项式的偶数个根是其本原根a的连续幂。

本文在BCH码盲识别中,提出的码根信息差熵的概念如下:

定义2:实际测得的码根分布信息熵与均匀分布的码根分布信息熵的差值,即为码根信息差熵函数,其计算公式如下:

这里需要对p作一下扩展,将p中的零元素改为元素“1”,剔除元素“0”对码根信息差熵函数的影响,因为对于对数函数log(x)要求其自变量x＞0,而log(1)=0可以剔除“0”元素的影响。

2 码根信息差熵和码根统计的识别原理

当截获 BCH码序列后,通过遍历m对本原BCH码进行分组,得到分组数N。对每个码字求取整数码根并进行统计,得到不同码根出现的次数N 0{1,2,…,n},进而得到所有码根出现的总次数S=sum(N0)。

2.1 基于码根信息差熵的码长识别

由有限域多项式根的性质[5],对于码长为n的循环码码字,其码根个数为n-1,范围为0～n-1,并且其分布具有一定的规律,即生成多项式的根在每个码字中均会出现,而每个码字中其他的码根是随机出现的。若估计的码长不是真实循环码的码长,那么码字之间的相关性和码根分布的特征便不存在,则统计得到的码根是随机出现的。假设其码根分布为均匀分布,不同码根的出现概率均为:

对于码根在域GF(2m)上、码长为n的BCH码而言,信道的误比特率Pe与码块正确率Ps具有如下的关系

由此可以看出,码块出现错误时,码块的根不会出现BCH码的根特征。在随机错误或突发错误的条件下,每个码块中出现错误的位置是随机的,因此码块的码根也将是随机出现的。在数据量足够大的条件下,码块数足够多,其正确码块的数目就多,那么正确码块的码根中满足的性质1和性质2的根将会在每次正确码块的码根统计中出现。下节将对在足够多的数据量条件下实现BCH码的正确识别进行可行性证明。

若实际测得的码根分布为 p=p{p 1,p2,…,p n}=N0{1,2,…,n}/S,利用定义2的码根信息差熵的函数可以实现对BCH码的码长识别。

2.2 基于码根统计的生成多项式识别

在码字整数根中,生成多项式根的分布是最大的且随本原多项式的变化而变化,仅在整数分布中发生位置的变化,而大小不变。这给利用码根信息差熵函数识别码长提供了的条件,简化了识别过程。在识别码长的基础上,利用统计得到的码根分布p=p{p 1,p 2,…,p n}=N0{1,2,…,n}/N,寻找概率接近1的码根即为生成多项式的整数根Z 。

接下来,遍历本原多项式,然后将这些整数根Zroot转换为符号码根Sroot。若Sroot满足 BCH码码根的性质,则可同时完成对本原多项式和生成多项式根a=(a1,a2,…,al)的识别。利用有限域乘法,可以知道该生成多项式为:g(x)=(x-a1)(xa2)…(x-al)。

最后经过化简处理后,得到系数为0和1的表达式,实现对生成多项式的识别。

对BCH码的识别流程如图1所示。

图1 BCH码的识别流程图Fig.1 Recognition flow of BCH codes

3 可行性证明

上节指出了在足够的数据量条件下可以实现BCH码的正确识别,下面对其可行性进行证明。

证明:鉴于编码信息的随机性,在码长为n的条件下,正确码块出现的码根中包含生成多项式确定的n0个根,其余的根是随机出现的;同时由于信道比特错误位置的随机性,错误码块的所有根也是随机出现的。

令H0表示码块正确事件,H 1表示码块错误事件,D 0表示出现包含生成多项式n0个根的事件,D1表示出现其他根的事件。由概率论每个码块中出现生成多项式n0个根的概率为:

其余根的出现概率为:

因此,在一定的码块正确率条件下,生成多项式每个根的出现概率由公式(1)可知

其余每个根的出现概率由公式(2)可知

由式(3)和式(4)可以得到:

所以,通过统计可实现对BCH码的正确识别,而且若得到BCH码长不正确,则每个码块都会产生随机的错误,导致根的统计分布接近等概率的分布。

4 仿真验证

在上述的识别方法基础上,误码率设定为pe=1×10-3和p e=1×10-2,利用Matlab软件对不同编码参数的BCH码进行了盲识别仿真。大量的仿真实验表明识别效果较好。

下面以(63,51)BCH码为例进行盲识别的仿真实验。

该仿真模拟的信道是二进制对称信道(BSC),其特点是通过保留二进制符号每一比特出现的概率来破坏信息传输,且与二进制符号序列传输过程中前后出现的错误无关。

4.1 码长识别验证

图2和图3是BSC分别为p e=1×10-3和pe=1×10-2情况下BCH码码根信息差熵的仿真验证图。当遍历的码长不是真实码长时,码组的线性关系被破坏,故进行分组后的得到的码根也是随机产生,其码根信息差熵相对于以真实的码长进行分组时较小。图2中在m=6位置码根信息差熵的值大于2,其余的位置码根信息差熵均小于1。图3中在m=6的位置码根信息差熵的值大于1,其余位置码根信息差熵均小于1。所以从图2和图3可以明显地看出,在m=6的位置出现峰值。故可以识别该BCH码的码长为n=2m-1=63。

图2 p e=1×10-3的某BCH码码长识别Fig.2 Code length recognition of BCH codes when p e=1×10-3

图3 p e=1×10-2的某BCH码码长识别Fig.3 Code length recognition of BCH codes when p e=1×10-2

从图2和图3看出在一定的数据量条件下,通过遍历码长,利用码根信息差熵函数完成对BCH码的码长识别时,误码率对该码根信息差熵函数存在着影响。若假设码长不是真实的码长,那么误码率对该函数的值几乎无影响,且该值较小,不超过1;若假设的码长是真实的码长,那么随着误码率的增加,该函数的值变小,而且这些函数值大小是超过1的。

4.2 生成多项式识别验证

在识别出码长的基础上,利用统计码根分布p=p{p 1,p2,…,p n}=N0{1,2,…,n}/N,寻找概率接近1的码根即为生成多项式的整数根Z root,转化为符号码根Sroot。遍历本原多项式,若Sroot满足BCH码码根的性质,则可以同时完成对本原多项式和生成多项式根a=(a,a,…,a)的识别。利用有限域乘法,可以知道该生成多项式为:g(x)=(xa1)(x-a2)…(x-al)。化简处理后最终将是系数为0和1的表达式,完成对生成多项式的识别。

图4和图5分别是在不同误码率条件下对识别码长为n=63的BCH码的整数码根分布图。可以看出随着误码率的增加,码根统计概率均降低,且生成多项式的根仍保持着概率相等。

图4 p e=1×10-3,n=63的BCH码的整数码根分布Fig.4 Integral code root statistic of BCH codes of n=63 when p e=1×10-3

图5 p e=1×10-2,n=63的BCH码的整数码根分布Fig.5 Integral code root statistic of BCH codes of n=63 when p e=1×10-2

从图4和图5可以看出,概率较近且分布概率较高的码根为:2,3,4,5,8,9,12,13,16,17,18,19。遍历该码长对应的本原多项式,并结合BCH码生成多项式的码根t特征,进一步识别可以得到该序列本原多项式为:p(x)=x6+x+1;上述的整数码根对应的符号码根为:a1,a6,a2,a12,a3,a32,a8,a48,a4,a24,a33,a16,其中a为p(x)对应的本原根。利用有限域的乘法原理可以知道,该码序列的生成多项式为:g(x)=(x-a1)(x-a6)…(x-a33)(x-a16)=x12+x10+x8+x5+x4+x3+1。

在获取码长后,通过遍历本原多项式对生成多项式的整数根Z root转换为符号根S root,完成对本原多项式的识别,同时获得对应的符号码根,利用有限域乘法恢复生成多项式,完成BCH码的识别。

5 结论

本文提出的基于码根信息差熵和码根统计的BCH码的识别方法,首次定义了码根信息差熵函数,利用该函数实现了BCH码的码长识别;采用码根统计的方法完成了BCH码的生成多项式识别,进而实现了对BCH码的盲识别。仿真验证分析表明:该方法能够在较高的误码率条件下对二进制本原BCH码进行有效的盲识别,且具有较好的容错性能。

[1]邹艳,陆佩忠.关键方程的新推广[J].计算机学报,2006,29(5):711-718.ZOU Yan,LU Peizhong.A new generalization of key equation[J].Chinese Journal of Computers,2006,29(5):711-718.

[2]WANG Fenghua,HUANG Zhitao.A method of blind recognition of convolution code based on euclidean algorithm[C]//IEEE Inter Conference on Wireless Com Networking and Mobile Computing.Shanghai,China:IEEE,2007:1 414-1 417.

[3]薛国庆.系统卷积码的盲识别[J].信息安全与保密通信,2009(2):57-60.XUE Guoqing.Blind identification of system convolutional codes[J].Information Security and Communications Privacy,2009(2):57-60.

[4]昝俊军.低码率线性分组码的盲识别[J].无线电技术,2009,39(1):19-22.ZAN Junjun,LI Yanbin.Blind recognition of low coderate binary linear block code[J].Radio Engineering,2009,39(1):19-22.

[5]王新梅.纠错码-原理与方法[M].西安:西安电子科技大学出版社,2002.