基于强度统计算法的混沌序列复杂度分析*
2011-09-28孙克辉贺少波盛利元
孙克辉 贺少波 盛利元
(中南大学物理科学与技术学院，长沙 410083)
基于强度统计算法的混沌序列复杂度分析*
孙克辉贺少波 盛利元
(中南大学物理科学与技术学院，长沙 410083)
(2010年4月8日收到;2010年5月28日收到修改稿)
为了分析混沌序列的复杂度，文中采用强度统计复杂度算法分别对离散混沌系统(TD-ERCS)和连续混沌系统(简化Lorenz系统)进行复杂度分析，计算了混沌序列随参数变化的复杂度，分析了连续混沌系统产生的伪随机序列分别进行m序列和混沌伪随机序列扰动后的复杂度.研究表明，强度统计复杂度算法是一种有效的复杂度分析方法，离散混沌序列复杂度大于连续混沌序列复杂度，但对连续混沌系统的伪随机序列进行m序列和混沌伪随机序列扰动后可大大增加复杂度，为混沌序列在信息加密中的应用提供了理论依据.
强度统计复杂度算法，TD-ERCS系统，简化Lorenz系统，序列扰动
PACS:05.45.-a，05.45.Tp
1.引 言
混沌序列复杂度是指其接近随机性的程度，越接近随机序列，复杂度越大.随着混沌科学的发展，混沌系统中的复杂性引起了越来越多人的关注，实用的混沌伪随机码应具有尽可能大的序列复杂度，以保证扩频通信的最大通信容量.目前计算序列复杂度的算法主要有四种，都是建立在Kolmogorov复杂度［1］基础上，前三者分别是1976年由Lempel和Ziv提出的 Limpel-Ziv算法［2］、1991年由 Steven和Pincus提出的复杂性近似熵(ApEn)算法［3］和2002年由 Bandt和 Pompe提出的复杂性度量排列熵(PE)算法［4］.这三种算法都能在一定程度上正确反映出混沌序列的复杂度，但 Limpel-Ziv算法只是在一维时间尺度上对系统的复杂度进行统计，涉及的只有序列的长度，而ApEn算法体现了不同嵌入维变化时情况，但是计算过程中涉及嵌入维和分辨率参数的选择，其结果随主观因素而有所变化，对于PE计算结果也要进行嵌入维的选择［5］.第四种是强度统计复杂度算法，强度统计算法最早由 López-Ruiz，Mancini和Calbet(LMC)提出［6］，原理是用统计复杂度测度(SCM)作为时间序列内模型结构程度的量化器.对给定的系统状态，统计复杂度测度是测度熵(H)乘以到平衡状态(Q)距离的积，对完全随机过程其值是零.对比前面三种算法，强度统计算法可以看成是对PE算法的进一步改进，因为其考虑了到平衡状态(Q)距离这一因素，反映了序列内模型结构.文献［7］进一步改进了强度统计复杂度算法，使之具有强度特性.强度统计复杂度测度更方便应用于序列随机性的度量，同时能呈现序列的相关结构，反应序列的随机本质.
本文在讨论了强度统计复杂度算法原理的基础上，以TD-ERCS系统和简化Lorenz系统为例，分别分析了离散混沌系统和连续混沌系统产生的混沌序列的复杂度，讨论了混沌序列复杂度随系统参数、分数阶数而变化的规律，计算了连续混沌系统伪随机序列在m序列和混沌序列扰动下的复杂度，为混沌序列在保密通信和信息安全方面的应用提供了理论依据.
2.复杂度算法原理与描述
强度统计复杂度测度CJ［P］是一个和动态系统产生的时间序列的概率分布P相联系的物理量，其计算公式为［8］
其中
且有Smax=S［Pe］=lnN(0≤HS≤1)，N代表系统在相空间中总的状态数目;Pe表示均匀分布，即Pe= {1/N，…，1/N}，S为Shannon熵.QJ是根据 Jensen-Shannon分歧定义的不均衡，有［8］
Q0是归一化常数，其计算式为
可见，0≤QJ≤1，且不均衡QJ为能反映序列结构的强度量，同样CJ［P］也能呈现序列的相关结构，对没有任何结构的完全随机序列，CJ［P］=0.复杂度测度值越小，则系统复杂度越大，反之亦然.
概率分布P采用Bandt-Pompe提出的方法进行计算［4］.给定时间序列{xt，t=1，…，T}和一个嵌入维d>1，对每一时刻i(i=1，2，…，T-d+1)，其d阶顺次模式是由时刻(i，i+1，…，i+d-1)的值组成的d维向量
显然，d越大，向量提供的信息越多.通过和时刻 i联系的“顺次模式”，定义(0，1，…，d-1)的一个排列π=(r0，r1，…，rd-1)为
若 xi+ri=xi+ri-1，则 ri 符号#代表“数目”.强度统计复杂度通过这种“排列”概率分布来计算. 值得指出的是，按此种排序方法得来的概率对于周期序列，特别是短周期序列会产生错误，如序列{1，2，3，4，1，2，3，4，1，2，3，4，…}，当d=3时，P ={1/2，1/4，1/4}，当d=4时，P={1}，当d=5时，P={1/4，1/4，1/4，1/4}，代入(1)式，当d=3时，复杂度CJ［P］=0.0427，当d=4时复杂度不存在，当d=5时复杂度CJ［P］=0，但显然序列不是完全随机的. 下面以基于切延迟的椭圆反射腔离散混沌系统(TD-ERCS系统)［9］，Logistic系统和耦合映像格子系统［10］为例，证明强度统计复杂度算法的有效性和分析离散系统的复杂度特性. TD-ERCS系统映射关系为 其中 其中，参数(u，x0，α，m)为系统的种子参数，确定了系统种子参数，系统特性也就随之确定，且有u(0< u≤1)，x0(-1≤x0≤1)，α(0<α<π)，m=0，1，2，3，….当m=0时系统为ERCS系统，当m=1，2，3，….时系统为 TD-ERCS系统，并处于混沌状态.对(8)式进行迭代就能分别得到两个实值序列{xm+1，xm+2，xm+3，xm+4，…}和{km+1，km+2，km+3，km+4，…}. 取系统初值x0=0.7654，α=0.9876，系统参数u=0.7123，迭代次数N=10000，嵌入维d分别为3，4，5.对系统的不同切延迟 m情况进行强度统计复杂度计算，结果如表1所示. 表1 TD-ERCS系统的强度统计复杂度 由表1可见随着嵌入维d的增加，即子序列反映的信息增加，总的趋势是复杂度有所增大，但相差不大.当m=0时，系统复杂度最小，比m=1时小一个数量级;当m=2时，系统的复杂度又增大了一个数量级;m=3时与m=2时的系统复杂度基本一样.这说明强度统计复杂度算法是一种很有效的方法，能很好地识别出系统复杂度. 为了进一步分析系统复杂度，这里考察系统参数u，m变化时复杂度的变化情况.系统复杂度随参数变化的情况如图1所示，嵌入维为d=3. 图1 TD-ERCS系统复杂度随系统参数变化情况 (a)m=2，u变化，(b)u=0.7123，m变化 如图1(a)所示，随着u值的增加系统复杂度增加，最后趋于稳定，从u的物理意义来看，u越接近1则椭圆反射腔越接近圆，其反射效果也越接近圆的反射效果，系统复杂度也就越大;从图1(b)可以看出，当m=0时，系统复杂度最小，此时系统为ERCS系统，但随着m的增加，系统复杂性增大并处于基本稳定状态，保持在0—0.005之间，可见当 m≥2后，切延迟操作对系统复杂度影响不是很大.综上可知TD-ERCS系统是一个广域高复杂性混沌系统. Logistic系统和耦合映像格子系统迭代方程参见文献［10］，系统相图也参见该文献中的图2(a)和(b).可见耦合映像格子系统相图比Logistic系统相图“混乱”，其复杂度应该比Logistic系统大很多.这里用强度统计算法计算这两者的复杂度如表2所示. 表2 Logistic和耦合映像格子复杂度 计算结果与实际情况符合，耦合映像格子序列复杂度比Logistic大2个数量级，可见，强度统计复杂度算法灵敏性很好.文献［10］中的表2，两系统产生的8进制伪随机序列的复杂度，计算方法采用的是ApEn算法，Logistic的为0.692左右，而耦合映像格子的为2.00左右，相比强度统计算法的计算结果区分度小很多，虽然计算的不是同一种序列. 下面取以上三个系统在不同迭代次数N情况下，计算序列强度统计复杂度与长度 N的关系.这里嵌入维d=5，各系统参数的选择与上面的基本一致，其中TD-ERCS系统的切延迟(m=3)，计算结果如表3所示. 表3 复杂度随序列长度的变化情况 由表3可知，系统产生的序列的长度对复杂度的影响不大.这点明显优于 Limpel-Ziv算法，因Limpel-Ziv算法涉及长度N的选择，复杂度随 N的增大有减小的趋势［5］.另外，对比表1，2，3可知，耦合映像格子系统复杂度比TD-ERCS系统的高，因为耦合映像格子系统为6维系统，而TD-ERCS系统是2维的，TD-ERCS系统复杂度小一点，但其运算量相对较小. 对离散系统的复杂度分析可以看出强度统计算法是一种非常有效的复杂度分析方法，从前面的计算结果来看，当只改变嵌入维d或序列长度N时，序列的复杂度改变不是很大，且复杂度对比结果不改变，也就是说在比较序列复杂度时只要选取一样的嵌入维d和序列长度N，按照强度统计算法计算复杂度值，就可以了，在这里，考虑到计算量问题，我们给出两者的参考值，嵌入维d取3即可，或4和5也可以，但再大就没必要了，因为当d≥6时，d!就比较大了，这样概率分布P的获取将非常繁杂，而序列长度N的选择根据具体情况而定，一般1000≤N≤10000都可以满足条件，再大也没太多意义;另外就是离散系统的复杂度是比较高的，复杂度值最大可以达到10-4数量级. 图2 简化Lorenz系统吸引子相图 (a)分数阶，(b)整数阶 Lorenz系统族是著名的混沌系统，在文献［11］中将其归为一类，并以统一的形式表达，而简化Lorenz系统［12］为 Lorenz系统族的一员.这里，选取简化Lorenz系统为例，研究连续混沌系统的复杂性特点. 简化Lorenz系统方程为 其中c为系统参数，α，β，γ为微分阶数，当α=β=γ =1时，系统为整数阶简化Lorenz系统;当0<α，β，γ<1时，系统为分数阶简化 Lorenz系统.图2为简化Lorenz系统的吸引子图，参数选择为分数阶α=β =γ=q=0.98，c=5，整数阶α=β=γ=q=1，c=5，可见此时系统都处于混沌状态. 当系统处于混沌态时，分别选取系统产生的三个序列，利用强度统计复杂度算法计算在不同嵌入维下的复杂度，其结果如表4所示. 表4 不同嵌入维下简化Lorenz系统强度统计复杂度 从表4可以看出不管系统是处于整数阶状态还是分数阶状态，其产生的序列复杂度都不是很大，且差别很小.对于同一系统中各序列的复杂度相差也不大.从图2吸引子图可以看出 x，y，z三个序列值并没有分布于整个坐标平面，而在有限空间相互成一定的规律，不是很“混乱”，所以复杂度不会很大.进一步，从计算结果表 4，图 2可以得出简化Lorenz系统(q=0.98，1时)复杂度并不是很大.为了证明这一点，接下来考察系统参数对复杂性影响，如图3所示. 图3中系统选取为分数阶简化Lorenz系统.图3(a)中，当参数c由小到大变化时，对x，y，z序列复杂度影响不大，其值在0.262到0.274之间变化，复杂度比较小.图3(b)中，α=β=γ=q，c=5，可以看出系统复杂度在q比较小(比如q≤0.5)时比较大，但这只是一种“假象”，根据文献［12］可知，此时系统处于非混沌态，之后当q接近1时系统处于混沌态，但复杂度变小了.由上面分析可知，简化Lorenz混沌系统的复杂度不如离散混沌系统. 图3 分数阶简化Lorenz系统强度统计复杂度随参数c和q变化情况 (a)q=0.98，c变化，(b)c=5，q变化 连续混沌系统由于约束比较多，其产生的混沌序列复杂度并不一定会很高，如简化Lorenz系统(q =0.98，1时).在应用中，连续系统由于其参数较多，系统关系复杂，经常被采用，但是往往也需要复杂性高的序列，另外就是实际应用中用得很多的是伪随机序列.针对这种情况，下面将分别采用m序列和混沌伪随机序列扰动的方法增加序列的伪随机序列复杂度.这种方法同样适用于离散混沌系统. 混沌伪随机序列是由混沌迭代产生的序列{xn}，归一化后，经过量化和判决得到的，判决公式为［13］ 可得到二进制的伪随机序列{Xn}.对于伪随机序列复杂度的分析的算法由文献［13］可知，最常用的是Berlekamp-Massey线性复杂度算法，但文章指出该算法并不能有效地区分出序列的复杂度.这里采用强度统计复杂度算法对伪随机序列进行测度，只是在计算过程中，p(π)的π获取方法参照文献［14］. 将分数阶简化 Lorenz系统产生的伪随机序列按强度统计算法进行计算，得到的结果如表5所示. 计算结果可看出生成的伪随机序列复杂度大小与原始序列的差不多，也不是很大.在实际应用中是序列的复杂度越大越好，所以，下面分别用 m序列［15］和混沌伪随机序列扰动的方法提高序列的复杂度.扰动模型见图4，扰动序列与待扰动序列对应位进行异或运算，得到结果后输出. 表5 分数阶Lorenz系统二进制伪随机序列的复杂度 图4 序列扰动原理示意图 m序列又叫伪随机序列、伪噪声(PN)码或伪随码，是一种常用的扩频序列，在扩频通信中有着广泛的应用.m序列的生成可用移位寄存器序列发生器的本原多项式决定.本文将分别采用4阶和10阶本原多项式来产生m序列. 根据m序列定义，产生m序列进行扰动实验.表6和表7是将上面的分数阶简化Lorenz系统的伪随机序列进行m序列扰动，进而得到的复杂度结果，从中可以看出这种方法的特性. 可以看出序列复杂度明显变大了，分别至少提高了1和2个数量级.可见这种方法对于提高伪随机序列复杂度是很有效的.进一步分析表6和表7可以看出随着d的增加强度统计复杂度值增加，说明序列复杂度在减少，且成倍数变化.原因可能是生成的m序列是一个周期序列，这里周期分别是24-1和210-1，随着 d增大，m序列的周期性影响越突出.可见m序列扰动能够大大提高序列的复杂度，是一种很实用的方法;缺点就是m序列是一种周期性序列，其周期性可能会对原序列造成影响. 表6 m序列(4阶)扰动后分数阶Lorenz系统二进制伪随机序列复杂度 表7 m序列(10阶)扰动后分数阶Lorenz系统二进制伪随机序列复杂度 表8 TD-ERCS伪随机序列扰动后的分数阶Lorenz系统伪随机序列复杂度 接下来利用混沌伪随机序列对简化 Lorenz伪随机序列进行扰动，混沌伪随机序列采用的是TDERCS系统产生的伪随机序列，其种子参数(u，x0，α，m)为(0.7123，0.7654，0.9876，3)，扰动后伪随机序列的复杂度如表8所示. 对比表5和表8可见，利用TD-ERCS系统产生的混沌伪随机序列对 Lorenz系统伪随机序列进行扰动后序列的复杂度至少提高了一个数量级，且没有m序列扰动后的明显周期性影响.表8最后一行是相应TD-ERCS系统的伪随机序列复杂度，扰动后的序列复杂度也比其大. 利用m序列扰动可以得到更高复杂度的混沌伪随机序列，但有周期性影响;而混沌伪随机序列扰动后，没有周期性的影响，但得到的序列复杂度没有利用m序列扰动后的高.总的来说两种方法各有所长，得到的高复杂度混沌伪随机均可应用于保密通信. 本文利用强度统计复杂度算法分别对离散混沌系统和连续混沌系统的复杂度进行了分析.对离散系统的分析表明强度统计复杂度算法是一种有效的复杂度测度算法，且具有灵敏度高和对参数嵌入维d和序列长度N的选择要求不严格等特点;在对TD-ERCS等系统分析后，可知该离散系统复杂度大;对连续混沌系统的复杂度分析表明，连续混沌系统复杂度没有离散混沌系统的大，但经m序列和混沌伪随机序列扰动后，序列复杂度能有效地增大.m序列扰动后，复杂度随嵌入维 d的增大而变小，原因可能是m序列本身存在周期性，而混沌伪随机序列扰动无此现象，但复杂度提高程度相对较小，显然这两种方法都可以提高混沌伪随机序列的复杂度，为混沌序列应用于信息加密提供了理论依据. ［1］Li M，Vitanyi P M B 1990 Amsterdam:Elsevier Science A 187 ［2］Lempel A，Ziv J 1976 IEEE Trans IT-22 75 ［3］Steven M，Pincus S 1991 Mathematics 88 2297 ［4］Bandt C，Pompe B 2002 Phys.Rev.Lett.88 174102 ［5］Sun K H，Tan G Q，Sheng L Y 2008 Acta Phys.Sin.57 3359 (in Chinese)［孙克辉、谈国强、盛利元 2008物理学报 57 3359］ ［6］López-Ruiz R，Mancini H L，Calbet X 1995 Phys.Lett.A 209 321 ［7］Larrondo H A，González C M，Martin M T，Plastino A，Rosso O A 2005 Physica A 356 133 ［8］González C M，Larrondo H A，Rosso O A 2005 Physica A 354 281 ［9］Sheng L Y，Sun K H，Li C B 2004 Acta Phys.Sin.53 2871(in Chinese)［盛利元、孙克辉、李传兵2004物理学报53 2871］ ［10］Xiao F H，Yan G R，Han Y H 2004 Acta Phys.Sin.53 2877 (in Chinese)［肖方红、阎桂荣、韩宇航 2004物理学报 53 2877］ ［11］Lü J H，Chen G R，Zhang S C，ˇCelikovsky＇S 2002 Int.J. Bifurc.Chaos 12 2917 ［12］Sun K H，Sprott J C 2009 J.Bifurcation and Chaos 19 1357 ［13］Wang L，Wang F P，Wang Z J 2006 Acta Phys.Sin.55 3964(in Chinese)［王 蕾、汪芙平、王赞基 2006物理学报 55 3964］ ［14］Luo S J，Qiu S S，Chen X 2010 Journal of South China University of Technology 38 18(in Chinese)［罗松江、丘水生、陈 旭2010华南理工大学报38 18］ ［15］Fan X Q 2009 Computer Engineering＆ Science 31 20(in Chinese)［范雪琴2009计算机工程与科学31 20］ PACS:05.45.-a，05.45.Tp Complexity analysis of chaotic sequence based on the intensive statistical complexity algorithm* Sun Ke-HuiHe Shao-Bo Sheng Li-Yuan 8 April 2010;revised manuscript 28 May 2010) To analyze the complexity of the chaotic sequences，based on the intensive statistical complexity algorithm，the complexities of the discrete TD-ERCS and continuous simplified Lorenz chaotic systems were investigated respectively，and the complexities of the chaotic sequences with different system parameters were calculated.The complexities of pseudorandom sequences of the continuous chaotic systems disordered by m-series and chaotic pseudo-random sequences were analyzed.The results indicate that the intensive statistical complexity algorithm is an effective method for analyzing the complexity of the chaotic sequences，and the complexity of the discrete chaotic systems is larger than that of the continuous ones.However，after disordering by m-series or chaotic pseudo-random sequences，the complexities of the pseudo-random sequences can be increased significantly.This study provides a theoretical basis for the applications of chaotic sequences in the field of secure communication and information encryption. intensive statistical complexity algorithm，TD-ERCS，simplified Lorenz system，sequence disorder *国家自然科学基金(批准号:60672041)资助的课题. *Project supported by the National Natural Science Foundation of China(Grant No.60672041).
3.离散混沌系统的复杂度分析
4.连续混沌系统的复杂度分析
4.1.简化Lorenz系统模型
4.2.简化Lorenz系统复杂度分析
4.3.伪随机序列生成及序列扰动后复杂度
5.结 论
(School of Physics Science and Technology，Central South University，Changsha 410083，China)
