循环码参数的全盲识别算法

循环码参数的全盲识别算法

王兰勋，熊政达，佟婧丽

(河北大学 电子信息工程学院，河北 保定071002)

摘要：为有效解决高误码率下高码率循环码的全盲识别，根据实际序列与随机序列最高公因式阶数分布之间的差异性特征，提出基于标准差率差值的最高公因式阶数的循环码全盲识别算法，该算法可以同时识别码长和码字同步点．在此基础上，通过循环码的循环特性，识别生成多项式，实现了循环码的全盲识别．理论分析及仿真实验表明基于标准差率差值的最高公因式阶数的循环码识别方法简单易行，计算量较少，容错性强，且在误码率为0.023条件下，对中短码识别效果明显．

关键词：循环码；全盲识别；标准差率差值；高码率

DOI：10.3969/j.issn.1000-1565.2015.05.011

中图分类号：TN911.22文献标志码：A

收稿日期：2015-03-14

基金项目：河北省自然科学基金资助项目(F2013201170)

Blind identification algorithm of cyclic code parameters

WANG Lanxun, XIONG Zhengda, TONG Jingli

(College of Electronic and Informational Engineering, Hebei University, Baoding 071002,China)

Abstract：In order to solve the blind identification for cyclic code with high BER or high code rate effectively，according to the most notable differences between the highest common factor order distribution of the actual sequence and the random sequence, proposed the blind identification algorithm of cyclic code based on standard error rate difference of the highest common factor order was proposed. The algorithm could identify code length and codeword synchronization point.And through the characteristics of cyclic codes, identified the generator polynomial was identified, a blind identification of cyclic codes was achieved. The theoretical analysis and simulation experience showed that the method was simple and had less computation as well better error-tolerance . And the effect was obvious in the short-code recognition,in the BER of 0.023 conditions.

Key words: cyclic code; blind recognition; standard error rate difference; high code rate

第一作者：王兰勋(1956-)，男，河北安平人，河北大学教授，主要从事数字通信与信息编码方向研究．

E-mail:wanglanxun56@163.com

循环码是目前应用最广泛的一类特殊的线性分组码，在纠错编码理论中具有重要地位．循环码识别技术已经应用于协作通信、智能通信等诸多领域中，具有重要的现实意义[1]．据现有公开发表的文献知，循环码盲识别研究的文献相对较少．其中，文献[2]提出一种利用码重分布概率方差识别循环码的码长，容错性较好，但未考虑截获序列非同步的情况．文献[3]利用码重分布距离估计码长、同步点，仅适用于低误码率下低码率的系统循环码．文献[4]对较高误码条件下的循环码盲识别未提出可行性解决方案．文献[5]在码字同步点已知下，通过秩统计识别码长，码根特征识别生成多项式，该方法更适用较低误码率的情况．文献[6]提出对偶空间法，将对偶空间候选向量同截获矩阵内积的结果与判决门限进行比较，增加了算法的抗误码性能，但计算量大，且所选门限使得误判率较大．文献[7]利用文献[6]的对偶空间法，通过“3倍标准差”准则制定判决门限，该算法虽可以完成对码长和同步点的识别，但需进行多次迭代，导致计算量较大．文献[8]提出一种译码匹配的二进制BCH码参数估计法，此方法能够识别码长和本原多项式，但需已知同步点．文献[9]提出基于矩阵秩信息熵与码重分布识别码长和同步点，误码适应能力较强，但需进行多次构造矩阵，计算量较大．文献[10]提出改进秩准则法识别参数，但计算量较大，且在高误码率条件下性能不稳定．

上述这些算法，低误码率下才能达到识别效果,计算量较大或不能达到全盲识别.针对以上方法的不足，通过欧几里德算法分别计算实际码字与随机码字循环移位前后码字多项式的最高公因式，根据实际序列与随机序列最高公因式阶数分布之间的差异性，本文提出标准差率差值的最高公因式阶数的循环码全盲识别算法，并利用循环码特性，识别生成多项式．

1基础知识

定义1[11]一个n重子空间Vn,k∈Vn，若对任一个V=(an-1,an-2,…,a0)∈Vn,k，总有V1=(an-2,an-3,…,a0,an-1)∈Vn,k，则称V为循环码或循环子空间．

性质[11]任意一个(n,k)循环码均是由唯一的1个r=n-k生成的多项式g(x)生成，因此每个码字及其循环移位后的码字之间的最高公因式是g(x)或其倍式，即g(x)是循环码中次数最低的多项式，且为最高公因式中阶数最低的多项式(全零码字除外)．

定义2[11]同时除尽多项式a(x),b(x),…,l(x)(不全为0)的正整数，称为a(x),b(x),…,l(x)的公约数，其中最大者称为最大公约数，记为GCD(a(x),b(x),…,l(x))，简记为GCD．若系数不为零的x的最高次数是多项式t(x)的阶数，记为deg(t(x))，则最高公因式阶数简记为deg(GCD)．设Lv是(n,k)循环码中每一个码字与其循环移位码字的最高公因式阶数(deg(GCD))为v的码字个数，则deg(GCD)分布为{L0,L1,…，Ln-1}，其分布概率是deg(GCD)为v的码字个数占码字总数的比率．

欧几里德算法[12]任意2个码多项式m(x),n(x)，有下面一系列的运算：

m(x)=n(x)s1(x)+t1(x);

n(x)=t1(x)s2(x)+t2(x);

t1(x)=t2(x)s3(x)+t3(x);

t2(x)=t3(x)s4(x)+t4(x);

⋮

ti-2(x)=ti-1(x)si(x)+ti(x);

ti-1(x)=ti(x)si+1(x)+ti+1(x).

在上述除法过程中，不可能无止境地进行下去，而必然进行到某一个(i+1)而结束，直到ti+1=0为止.其中degti(x)>degti+1(x)，则m(x),n(x)的最高公因式为ti(x)．

2识别方法

2.1　同步点和码长识别

循环码的码元之间具有严格线性约束关系，每个码字与其循环移位后的码字的最高公因式是g(x)或其倍式，导致码字deg(GCD)分布不平衡，其deg(GCD)概率分布与随机序列的deg(GCD)概率分布之间差异很大．本文根据deg(GCD)分布的差异性，提出基于标准差率差值的deg(GCD)的循环码全盲识别算法．

在概率论和统计中，标准差率(CV)定义为标准差与平均值之比，即CV=σ/μ，只有μ≠0时，才有意义，文中μ>0，因为平均值μ是针对最高公因式阶数概率分布而言．CV是反映概率分布离散程度的一个归一化量度，比方差、标准差更能反映离散度．当CV较大时，说明概率的分布相对集中，相反，说明概率的分布相对分散．而真实序列的deg(GCD)分布相对集中，CV较大；随机序列的deg(GCD)分布相对分散，CV较小．因此，本文利用标准差率差值来衡量真实与随机序列deg(GCD)分布的差异性．

设(n,k)循环码的最高公因式阶数概率分布为Z1={a0,a1,…,an-1}，记为实际序列分布．设随机序列的最高公因式阶数概率分布为Z2={b0,b1,…,bn-1}，记为随机序列分布．

定义标准差率差值：实际序列的deg(GCD)分布概率的CV与随机序列的deg(GCD)分布概率的CV之间的差值定义为最高公因式阶数标准差率差值，即

(1)

其中σ实，σ随表示Z1，Z2的标准差，μ实，μ随表示Z1，Z2的均值，即

将式(2)—(5)带入式(1)，即得

(6)

经上述分析，当识别为非真实码长、同步点时，实际序列与随机序列deg(GCD)概率几乎在n个阶数位置有分布，且较分散，ΔCV较小；当识别为真实值时，实际序列deg(GCD)概率只在某阶数(阈值即生成多项式次数)位置以上有分布，在阈值以下有少许分布，但相对于随机序列deg(GCD)分布较集中，特性相差较大，ΔCV最大．

基于ΔCV的循环码识别码长、同步点方法的步骤概括如下.

1)初始化识别参数：码长n取值范围5~s，s为最大可能码长；同步点e，取值范围1~n；

5)求出每种假设(n,e)下的实际与随机分布的deg(GCD)分布概率，利用式(6)求ΔCV，找出ΔCV最大时对应的(n,e)，即为真实码长、同步点．

2.2　生成多项式识别

循环码的每个码字与其循环移位后的码字之间最高公因式是g(x)或其倍式，所以deg(GCD)均大于等于g(x)的次数．用上述方法识别出码长和同步点后，统计正确码长和同步点对应的deg(GCD)分布，找出分布中个数最多的一个deg(GCD)，以其对应的所有最高公因式作为研究对象，统计公因式系数分布概率，选择出现概率最大的公因式系数作为g(x)系数，即完成识别．

3仿真验证及分析

3.1　码长和同步点的识别

当BSC信道无误码时，采用(15,5)循环码为研究对象，参数设置如下：选取3×104bit码元作为测试样本序列，码字同步点设为6，仿真结果如图1所示.

ab

a.码长同步点识别;b. 图a的局部放大.

图1Pe=0时(15,5)循环码识别

Fig.1(15,5) cyclic code identification whenPe=0

由图1 a三维图可见，ΔCV最大时对应的码长和同步点分别为n=15,e=6，即为真实值．由于图1a中的点过于密集，不易观察，为了使其更清晰，将a图进行局部放大，得到b图，可以看出坐标在(15,6)处对应Z轴值最大．图1分析知，当识别码长、同步点不为真实值时，码字内不具有完整的线性约束关系，选取的待测矩阵与其循环移位矩阵之间的deg(GCD)分布相对分散，与随机序列分布相接近，ΔCV较小；相反，当识别为真实值时，选取的待测矩阵与其循环移位矩阵之间的deg(GCD)分布相对集中，与随机序列分布相差最大，此时ΔCV最大．经仿真分析该方法能正确识别码长和同步点．

当BSC信道有误码时，仍采用(15,5)循环码为研究对象，参数设置如下：选取3×104bit码元作为测试样本序列，码字同步点设为6，误码率Pe=0.03，仿真结果见图2.

ab

a.码长同步点识别;b.图a的局部放大.

图2Pe=0.03时(15,5)循环码识别

Fig.2(15,5) cyclic code identification whenPe=0.03

图2为有误码下识别仿真图，b是a的局部放大图，由图a,b看出，坐标(15,6)处ΔCV取得峰值，而在其他坐标(n,e)处对应ΔCV均小于坐标(15,6)处，可知，在码长15、同步点6时为真实码长、同步点．同图1比较知，利用ΔCV的最高公因式阶数分布识别码长、同步点，误码率对识别方法存在影响．图2中，正确(n,e)处的ΔCV相对图1无误码时，其值变化相对平缓，但依然可以判断出循环码的码长和同步点．因此，该识别方法可以识别高误码下循环码的码长、同步点．

3.2　生成多项式识别

经上述方法正确识别出码长、同步点，仍以(15，5)循环码为例，统计在(n,e)=(15,6)处对应的最高公因式，取1 000组(15，5)循环码作为研究对象，其最高公因式阶数分布如表1.

由表1知，十进制数10的位置对应的分布个数最多为261，即生成多项式的次数为10，以此次数对应的所有最高公因式为研究对象，统计不同公因式对应的个数概率，如表2.

由表2知，十六进制537对应的公因式系数的概率最大为246/261，此时的最高公因式系数对应的二进制即为所求生成多项式的系数，即(10 100 110 111)，对应生成多项式为g(x)=x10+x8+x5+x4+x2+x+1，完成识别．

表1　最高公因式阶数分布

表2　次数为10的公因式个数分布

4容错性分析

4.1　码长、同步点容错性分析

下面以(7,3)，(15,11)，(31,26)3种循环码为实验对象讨论该方法的容错性．对不同码长均取1 001组码字，在不同误码率下进行200次蒙特卡洛仿真实验，统计出不同误码率条件下的正确识别率，识别曲线如图3所示.

图3　识别率仿真 Fig.3　Recognition rate simulation diagram

由图3可见，较低码率的(7,3)循环码在误码率为0.053下，该方法识别码长、同步点的正确识别率达90%以上，高码率的(15,11)在误码率为0.028下，正确识别率达90%以上，且该算法对于识别高码率(31,26)循环码仍有较好的容错性，在误码率为0.023下，识别率超过了90%．分析以上3种码字，可以看出随着识别码长的增加，误码适应能力下降．从图3可以明显看出，该方法在误码率为0.023下，对中短循环码识别率达90%以上．

以(15,11)循环码作为截获数据的编码参数，本文算法与文献[6]，[7]，[9]，[13]分别比较识别码长、同步点的容错性，仿真结果如图4所示．图4a、b是进行200次蒙特卡洛仿真实验得出，经图4a分析知，选择相同码字种类时，本文算法在误码率为0.028时的码长识别正确率可达到90%以上，而其他4种方法均不如本文算法,由图4b分析可知，本文算法在误码率为0.028时的同步点识别正确率可达到90%以上，均强于其他4种算法．且由图4a、b均可以看出，随着误码增加，正确识别率是下降的．因此本文提出的基于标准差率差值的最高公因式阶数识别算法比以往算法的误码适应能力强．

ab

a.码长识别率;b.同步点识别率.

图4不同方法比较

Fig.4Comparison of different methods

4.2　复杂度分析

比较文献[7]，[13]和本文提出识别码长、同步点算法的模2加计算量．

截获N个数据码元，设码长为ni，码长遍历为nmin~nmax，码字同步点为e,为1~ni，1个码字与其循环移位后的码字的最高公因式长度为L，L小于码长．本文利用欧几里德算法，1个码字求其最高公因式需进行niL次加法运算，对于N/ni个码字，遍历不同码长，则对应ni个不同码字同步点．

本文方法识别码长、同步点，进行模2加运算次数为

文献[7]Walsh-Hadamard变换的线性分组码参数盲估计算法，进行模2加运算次数为

文献[13]改进的二进制循环码盲识别码长、同步点的方法进行模2加运算次数为

去除上述3个运算公式的相同项，很明显本文算法相比于文献[7]、[13]，所需模2加计算量小．下面通过表格形式比较3种算法的运算量，参数设定：码长为7,15,31,63，截获序列N=1 000个码元，将其分别带入2×ni×N，(N/ni)×(ni-1)×(2ni-1)，((ni-1)/2)×N×(ni+1)，如表3所示.

表3　3种算法所需模2加计算量

由表3所示，文献[7]所需运算量最多，并且随着码长增加计算量成指数增加，文献[13]相对运算量较少，本文算法所需模2运算量最少，从而提高了识别效率．

5结论

本文根据循环码最高公因式阶数(deg(GCD))分布的不平衡性，以及同随机序列相比，循环码deg(GCD)分布相对分散，利用此差异性，提出了基于标准差率差值的deg(GCD)分布的识别算法，同时识别码长、同步点．在此基础上，利用循环码特性，识别生成多项式．本文方法简单易行，对先验信息要求较少，仅需知道编码方式是否是循环码即可．最后进行仿真分析，讨论其容错性及模2计算量，通过仿真实验表明，在误码率为0.023时，该方法也能有效识别高码率的中短循环码，然而，在软件无线电通信中，误码率一般在10-4~10-6范围内.可见，本文识别算法适合应用在软件无线电通信的场合．

参考文献:

[1]解辉,黄知涛,王丰华.信道编码盲识别技术研究进展[J].电子学报,2013,41(6):1166-1176.

XIE Hui,HUANG Zhitao,WANG Fenghua. Research progress of blind recognition of channel coding[J].Acta Electronica Sinica,2013,41(6):1166-1176.

[2]郑瑞瑞，汪立新.基于码重分布概率方差的循环码识别方法[J].太赫兹科学与电子信息学报，2013,11(5)：792-796.

ZHENG Ruirui,WANG Lixin.Recognition method of cyclic codes based on code weight distribution probability variance[J].Journal of Terahertz Science and Electronic Information Technology,2013,11(5):792-796.

[3]王磊,胡以华,王勇，等.基于码重分布的系统循环码识别方法[J].计算机工程与应用,2012,48(7):150-153.

WANG Lei, HU Yihua, WANG Yong, et al. Recognition method of system cyclic code based on code weight distribution[J].Computer Engineering and Applications,2012,48(7):150-153.

[4]闫郁翰.循环码的盲识别方法[J].电子科技，2011,24(3)：112-114.

YAN Yuhan.Blind recognition method for the cyclic code[J].Electronic Science and Technology,2011,24(3):112-114.

[5]闻年成,杨晓静.采用秩统计和码根特征的二进制循环码盲识别方法[J].电子信息对抗技术，2010,25(6)：26-29.

WEN Niancheng, YANG Xiaojing. Blind recognition of cyclic codes based on rank statistic and codes roots characteristic[J].Electronic Warfare Technology,2010,25(6):26-29.

[6]VALEMBOIS A. Detection and recognition of a binary linear code [J]. Discrete Applied Mathematics, 2001,111(1-2):199-218.

[7]杨晓炜，甘露.基于Walsh-Hadamard变换的线性分组码参数盲估计算法[J].电子与信息学报，2012,34(7):1642-1646.

YANG Xiaowei,GAN Lu.Blind estimation algorithm of the linear block codes parameters based on WHT[J].Journal of Electronics & Information Technology,2012,34(7):1642-1646.

[8]周攀.循环码参数盲估计与识别[D].成都：电子科技大学.2013.

ZHOU Pan.Blind recognition and parameter estimation of cyclic codes[D].Chengdu:School of Electronic Engineering,2013.

[9]陈金杰，计同钟，杨俊安.高误码条件下线性分组码的盲识别[J].应用科学学报，2013,31(5):459-467.

CHEN Jinjie,JI Tongzhong,YANG Junan.Blind recognition of linear block code under high error rate condition[J].Journal of Applied Science, 2013,31(5):459-467.

[10]BARBIER J, SICOT G, HOUCKE S. Algebraic approach for the reconstruction of linear and convolutional error correcting codes[J]. International Journal of Applied Mathematics and Computer Sciences, 2006, 2(3): 113-118.

[11]王新梅,肖国镇.纠错码—原理与方法[M].西安电子科技大学出版社,2001.

[12]WANG Lanxun, LI Danfang. A new method for BCH codes of blind recognition[Z]. 2nd International Conference on Materials Engineering for Advanced Technologies, Xiamen, 2012.

[13]朱联祥，李荔.改进的二进制循环码盲识别方法[J].计算机应用，2013,33(10)：2762-2764.

ZHU Lianxiang,LI Li.Improved blind recognition method for binary cyclic code[J].Journal of Computer Application,2013,33(10)：2762-2764.

(责任编辑：王兰英)