（物理电子学专业论文）离散混沌系统的复杂性算法研究.pdf

中南大学硕士学位论文 摘要 摘要 混沌在信息安全领域的应用已成为非线性科学研究的热点，而混 沌系统复杂性分析是系统安全性能的一个非常重要研究方面。混沌系 统的复杂性大小，直接关系到该系统的密码学性能。本文采用多种方 法研究和分析了离散混沌系统产生的时间序列的复杂性，探讨其复杂 性变化规律，特别是对新型离散混沌系统一t d - e r c s 系统进行了详细 的讨论，并与一些常用离散混沌系统进行了对比分析。首先，采用相 空间观测直接观察法研究了多个混沌系统的相空间结构，对这些混沌 系统的复杂性大小有一个直观了解。然后，分别从行为复杂性和结构 复杂性两方面对离散混沌系统的复杂性大小进行计算与分析。在行为 复杂性中，以k o l m o g o r o v 复杂性为基础，应用经典的l i m p e l z i v 算 法、a p e n 算法和p e 算法，从单维时间序列和多维相空间重构两方 面计算了l o g i s t i e 系统、t e n t 系统、h e n o n 系统、分段线性映射系统 和t d e r c s 系统的复杂性数值大小，计算结果表明，t d - e r c s 系统 的行为复杂性明显高于其它离散混沌系统，而且该系统的复杂性大小 随参数改变的变化范围很小，是一个复杂性非常稳定的全域混沌系 统。在结构复杂性方面，运用傅立叶变换和小波变换两种变换方法， 以信号变换域的谱熵和小波熵特征量来估计原混沌系统的复杂性大 小，研究结果表明，t d - e r c s 系统的频域复杂度与其它离散混沌系 统相当，结构复杂性也非常大。最后，通过三种复杂性研究方法的对 比和讨论，得出t d e r c s 不仅在行为复杂性方面具有明显优势，在 结构复杂性方面也可以与其它离散混沌系统相媲美，符合混沌系统复 杂性性能指标，是一个可用于密码学应用的离散混沌系统，在信息安 全领域有着广阔的应用前景。 关键词混沌，复杂性，t d - e r c s ，熵，行为复杂性，结构复杂性 中南大学硕士学位论文 a b s t r a c t a b s t r a c t t h e a p p l i c a t i o no f c h a o si nf i e l do fi n f o r m a t i o ns e c u r i t yh a sb e c o m ea h o tt o p i c t h ec o m p l e x i t ya n a l y s i so fc h a o t i cs y s t e m si sav e r yi m p o r t a n t a s p e c to fs y s t e ms e c u r i t yp e r f o r m a n c e t h e r ei s ac l o s er e l a t i o n s h i p b e t w e e nt h ec o m p l e x i t ya n dt h es y s t e m sc r y p t o g r a mp e r f o r m a n c e t h e c o m p l e x i t yo ft i m es e r i e sg e n e r a t e db yd i s c r e tc h a o t i cs y s t e mi sa n a l y z e d a n ds t u d i e db yu s i n gd i f f e r e n tm e t h o d s ，e s p e c i a l l y , t h en e wt d e r c s d i s c r e tc h a o t i cs y s t e mi sd i s c u s s e di nt h ep a p e r , a n di t sc o m p l e x i t yi s c o m p a r e dw i t ht h eo t h e rc o m m o n d i s c r e tc h a o t i cs y s t e m s f i r s t ，t h es p a c e s t r u c t u r ec o m p l e x i t yo fe a c hc h a o t i cs y s t e mi so b s e r v e db yp h a s es p a c e o b s e r v a t i o nm e t h o d ，t h em a g n i t u d eo ft h ec o m p l e x i t yi sa p p r o x i m a t e l y g a i n e d ，t h e n ，t h ec o m p l e x i t y i sm e a s u r e dt h r o u g ht h em e t h o d so f b e h a v i o rc o m p l e x i t ya n ds t r u c t u r ec o m p l e x i t y i nt h em e t h o do fb e h a v i o r c o m p l e x i t y , b a s e d o n k o l m o g o r o vc o m p l e x i t y , c l a s s i cl i m p e l z i v a l g o r i t h m ，a p e na l g o r i t h ma n dp ea l g o r i t h ma r eu s e dr e s p e c t i v e l yi n s i n g l ed i m e n s i o na n dm u l t i p l i e dd i m e n s i o n sa p p r o a c h t h ec o m p l e x i t y v a l u eo fs o m es y s t e m si sc a l c u l a t e d ，i n c l u d i n gl o g i s t i cs y s t e m ，t e n t s y s t e m ，h e n o ns y s t e m ，s e c t e dl i n e a rr e f l e c t i o ns y s t e ma n dt d e r c s s y s t e m n er e s u l t ss h o wt h a t t h eb e h a v i o rc o m p l e x i t yo ft d e r c s s y s t e mi sg r e a t e rt h a no t h e rc h a o t i cs y s t e m s ，a n dt h ec o m p l e x i t yv a l u e c h a n g e sal i t t l ea st h ec h a n g eo fi t sp a r a m e t e r s i nt h ea s p e c to fs t r u c t u r e c o m p l e x i t y , t h ef o u r i e rt r a n s f o r ma n dw a v e l e tt r a n s f o r m a r eu s e dt og e t t h es p e c t r a le n t r o p ya n dw a v e l e te n t r o p y , w h i c ha r eu s e dt od e s c r i b et h e c o m p l e x i t yo ft h ed i s c r e tc h a o t i cs y s t e m s n er e s u l t si n d i c a t et h a tt h e f r e q u e n c ys p e c t r a lc o m p l e x i t yo ft d e r c ss y s t e m i sa b o u tt h es a m e w i t ho t h e rd i s c r e tc h a o t i cs y s t e m ，a n dt h es t r u c t u r ec o m p l e x i t yi sa l s o v e r yg r e a t i nac o n c l u s i o n ，t h eh e h a v i o u rc o m p l e x i t yo ft d e r c s s y s t e mi sb e t t e rt h a nt h a to fo t h e rc h a o t i cs y s t e m s a n di th a st h es a m e s t r u c t u r ec o m p l e x i t ya so t h e rd i s c r e tc h a o t i cs y s t e m s i ti sa na p p l i c a b l e c h a o t i cs y s t e mw h i c hc a l lb eu s e df o rc r y p t o g r a p h ya p p l i c a t i o na n dh a s b r o a da p p l i c a t i o nf o r e g r o u n di nt h ef i e l do fi n f o r m a t i o ns e c u r e k e yw o r d s c h a o s ，c o m p l e x i t y , t d e r c s ，b e h a v i o rc o m p l e x i t y , s t r u c t u r ec o m p l e x i j i i 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在在论文中作了明确的说 明。 作者签名：豳i 玺日期：塑年月竺日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位 论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论 文；学校可根据国家或湖南省有关部门规定送交学位论文。 作者签名：邀导师签名 中南大学硕士学位论文 第一章绪论 第一章绪论 世界的本质是非线性的，日月星辰的运行，草木鱼虫的繁衍，股市的起落， 天气的阴晴变化都蕴含了大量的非线性现象。混沌是非线性确定性系统的一种内 在的随机现象，对混沌现象的研究有助于人们对客观世界的正确认识和把握。本 章回顾了混沌的发展历史，阐述了混沌的定义、特点，以及在信息领域中的一些 应用情况，介绍了系统复杂性的定义、研究方法以及对混沌复杂性研究的重要性。 最后，概述了该课题所需要研究的内容，思路和意义。 1 1 混沌及其特点 近年来，随着混沌科学和非线性动力学的不断深入和发展，混沌理论已经逐 步发展成为了一门专门的理论和学科【1 4 1 。混沌属于2 0 世纪三大科学革命之一 如果说相对论排除了绝对时空观的牛顿幻觉，量子论排除了可控测量过程中的牛 顿迷梦，那么混沌则捧除了拉普拉斯可预见性的狂想。在2 l 世纪里，混沌理论 将开创科学思想上又一次新的革命。 1 1 混沌研究的发展历史 混沌学的研究热潮始于2 0 世纪7 0 年代，但对混沌的研究可以追溯到1 9 世 纪人们公认的真正发现混沌的第一位学者是法国数学家、物理学家h p o i n c a r e 早在1 8 9 2 年，他在研究天体运动时发现，即使是三个非常简单的天体，由于引 力相互作用有可能产生非常复杂的动力学行为( 混沌行为) 。他同时也发现某些 系统具有初值敏感依赖性和行为不可预见性。1 9 0 3 年，庞加莱把动力学和拓扑 学结合起来，提出了著名的。庞加莱猜想”，预测了混沌存在的可能性，从而成 为世界上最先研究混沌的人与他同时代的另一位科学家l y a p u n o v 则提出了动 力系统中的l y a p u n o v 指数的概念，直到目前为止l y a p u n o v 指数还仍然是衡量混 沌的重要指标之一但受到数学发展水平的限制，无法进行深入研究，这些成果 并没有立即在科学界引起重视。 真正使人们开始关注混沌现象的是1 9 6 3 年美国气象学家e n l o r e n z 在 j o u r n a lo f t h ea t m o s p h e r i cs c i e n c e s ) 杂志上发表的一篇论文确定性的非周期 流) 嘲文章中提出和解释了著名的蝴蝶效应( 初始条件的极其敏感性) ，人们 开始认识到复杂系统的长期行为是不可预测的同时，他是最先在计算机上采用 数值方法研究混沌的人，也是第一个发现奇异吸引予( l o r e n z 吸引子) 的人，因 中南大学硕士学位论文 第一章绪论 此，l o r e n z 被誉为“混沌之父”。1 9 7 0 年，美国科学家t s k u h n 出版的科学 革命的结构一书则将混沌理论的研究推向了新的高潮。 1 9 7 5 年，j a y o r k e 和李天岩在美国数学月刊上发表周期3 意味着混 沌嘲一文，首次采用c h a o s 一词来描述混沌现象，它明确表示混沌动力学的特 征，成为混沌本身的代名词。1 9 7 7 年，第一次国际混沌会议在意大利召开，标 志着混沌科学理论的正式诞生。 1 9 7 8 年，美国物理学家m f e i g e n b a u m 发现倍周期分叉现象中的普适常数 - q 他计算出相邻两次倍周期分岔所对应的参数间距的收敛速度为常数， 万= 4 6 6 9 2 ，这就是著名的f e i g e n b a u m 常数。该常数将混沌理论研究从定性分 析推进到定量计算的阶段，从而使混沌在现代科学中打下坚实的理论基础。 1 9 8 4 年，中国科学院郝柏林院士从众多的参考文献中筛选出至为重要的研 究成果编辑成混沌 嘲一书出版，对混沌科学的发展起到了一定的推动作用 1 9 8 6 年，中国第一届混沌学术会议在桂林召开，为我国广泛开展混沌学研 究起到了积极的促进作用 自上世纪8 0 年代以来的二十多年问，混沌理论得到了迅速发展，混沌学与 其它学科相互渗透、相互促进，在进一步完善其理论体系的过程中，各种混沌现 象不断被发现，各种分析方法和判据也相继提出。在物理学【9 ，l o l 、化学【1 、生物 学f 1 2 , 1 3 1 、天文学i 埘、气象掣嘲、信息科学【垌、甚至音乐、艺术【1 刀等众多领域的 研究中均产生了重大的影响。混沌现象的发现，揭示了自然界及人类社会普遍存 在的复杂性，如有序和无序的统一，确定性与随机性的统一，整体与局部的统一 混沌学的创立，在确定论和概率论这两大科学体系之间架起了桥梁，它将揭开物 理学、数学乃至整个现代科学发展的新篇章 1 1 2 混沌的定义 无论从物理学的角度还是数学角度，研究混沌动力学理论的首要问题是如何 给出混沌的科学定义然而由于混沌系统的奇异性和复杂性尚未被人们彻底了 解，因此，迄今为止，关于混沌还没有一个准确、完整、科学的定义，不同领域 的科学家对其也有不同的理解。 从物理学的角度上来讲，混沌是非线性系统在远离平衡的状态下，由于运动 轨道高度不稳定，经多次分岔而得到的一种运动状态，是一种具有某种统计规律 的“序”；数学家则从映射、不变集、拓扑学的角度来定义混沌在给出混沌数 学定义之前，先定义两个动力学概念【1 8 1 。 定义1 1 拓扑传递f r o p o l e g i e a u yt r a n s i t i v e ) 设，为拓扑空间，映射厂：，- ，如果对任意的开集u j ，v ，存在 中南大学硕士学位论文第一章绪论 七 0 ，七e z ，使 f ( t o n y 西( 1 1 ) 则称：，：j 专，为拓扑传递的 拓扑传递意味着任一点的邻域在厂的作用之下将“遍历”整个度量空间， 这说明不可能分解成为两个在，下不互相影响的子系统。 定义1 2 初值敏感性( s e n s i t i v ed e p e n d e n c eo ni n i t i 龇c o n d i t i o n s ) 对给定的万 0 ，对任何的x - ，和在工的任何邻域u 上，都存在y e u 和 万0 ，一ez ，使得 矿“( 一，“( 州 艿 ( 1 - 2 ) 直观上，映射对初始条件的敏感依赖性是指，对于任意接近工的点，在，的 有限次迭代之后，它和x 的分离程度可以大于任意给定的万 定义1 3 混沌( c h a o s ) 1 ) l i - y o r k e 定义：最早提出混沌定义的是由李天岩和j a y o r k e 在1 9 7 5 年发表 的一篇周期3 意味着混沌的论文中提出来的，该定义被称为l i - y o r k e 定义 6 1 ： 设，：z 啼厂是闭区间，c 且上的连续映射，如果满足下列条件：。 、? 1 厂周期点的周期无上界； ” 2 存在不可数集s c ，s 不含周期点，且满足 对任意x , y s 。工j ，有 。 l i m 叫，。( 功- f ”洲 0 ( 1 3 ) 对任意的童，y e s ，有 熙i n f l f 。( 功一f 。酬= o 对任意x s 及周期点y eo r ，有 ( 1 4 ) l i m s 叫厂“( x ) - f 。训 0 ( 1 - 5 ) 则称厂：，一，在s 上是混沌的 。根据l i - y o r k e 的定义，一个混沌系统应该存在所有阶的周期轨道，存在一 个互不趋近的混沌周期轨道的不可数集合，并且周期轨道具有高度的不稳定性。 他指出了“有界”和。非周期”是混沌的本质特征【1 9 1 。 。 2 1 d e v a n c y 定义鳓 一 。 1 9 8 9 年，d e v a n c y 提出一个为多数人接受、影响较大的混沌定义设y 为一 集合，如果满足下列三个条件，则称厂：y 寸y 在y 上是混沌的 1 ，对初始条件的敏感依赖性； 2 厂是拓扑传递的i 中南大学硕士学位论文 第一章绪论 3 状态点在v 中是稠密的。 d e v a n c y 的定义说明混沌具有不可预测、不可分解和规律性三个要素。其中， 对初始条件的敏感依赖性导致该系统是不可预测的：拓扑传递性导致该系统不能 分解称为两个互不影响的子系统；在“混乱”的形态中，规律性的因素导致有稠密 的周期点。 3 1l o r e n z 定义 2 l l 被誉为“混沌之父”的美国科学家l o r e n z 曾经给混沌一个通俗的说法：一个 真实的物理系统，在排除了所有的随机性影响之后仍有貌似随机的表现，那么这 个系统就是混沌的。l o r e n z 的定义表明混沌具有如下两个主要特征。 1 混沌是系统固有的。系统所表现出来的复杂性是系统自身的、内在的因 素造成的，并不是在外界的干扰下所产生的，是系统内随机性的表现。 2 混沌是具有确定性的。混沌的确定性分为两个方面：首先，混沌系统是 确定的系统，是一个真实的物理系统；其次，混沌的表现是貌似随机，而并不是 真正的随机。系统的每一时刻状态都受前一状态的影响，是确定出现的。混沌系 统的状态是完全可以重现的，这与随机系统不同 已有的这些定义从不同的侧面反映了混沌的性质简单的来说，混沌是由确 定的动力学系统产生的复杂的动力学行为。 1 1 3 混沌的特点 混沌是一种貌似随机的现象，概括来说，混沌具有以下几个特征圆； 1 对初始条件的极端敏感性。 。 混沌系统对其初始条件具有极端的敏感性，这是混沌区别于其它运动形态的 本质特征这一特征意味着混沌的不可预测性。 2 有界性。 混沌是有界的。它的运动轨迹始终局限于一个确定的区域，这个区域称为混 沌吸引域。无论混沌系统内部状态多么不稳定，它的轨迹都不会走出混沌吸引域。 所以，从整体上来说，混沌系统是稳定的。 3 遍历性。 混沌运动在其混沌吸引域内是各态历经的，即混沌轨迹将经过混沌吸引域内 的每一个状态点。 4 内随机性。 虽然混沌系统的动力学方程是确定的，但其运动形态却具有某种“随机”性 这种随机性是在系统自身演化的动力学过程中由于内在非线性机制作用而自发 产生出来的。因此，混沌的随机性是确定性系统的内在随机性。混沌的内随机性 说明混沌系统是局部不稳定的 中南大学硕士学位论文 第一章绪论 5 分维性 混沌不等同于随机运动，它在局部区域和空间中具有丰富的内涵。表现为混 沌运动轨迹在某个有限的区域内做无限次的折叠，运动状态具有丰富的层次和自 相似结构，从而形成了奇异吸引子。混沌的这种行为特征用分维性来表示。 6 非周期定常态特性。 非周期性是混沌运动的一个重要特征。可以说，混沌没有通常意义下的定常 态，或者说混沌的定常态就是这一非周期性过程。但是，混沌不是任意一种非周 期运动，而是确定性的非周期性运动。这里的“确定性”，一是指混沌是由确定 性动力学方程产生的非周期运动，不是外部扰动引起的；二是指混沌是一种定常 态行为，不是系统在过渡过程中呈现的非周期性。 7 统计特征和混合性 混沌运动具有某种统计确定性，即统计特性。混合性则指初始条件的选取不 影响混沌轨道的统计学特性。所以，可以用信号统计的各种工具来分析混沌。佣 如，正的李雅普诺夫( l y a p u n o v ) 指数以及连续功率谱等，都是在这两种特性下的 分析结果。 ， 1 2 混沌在信息领域中的应用研究 二十一世纪是信息的时代，目前发展起来的多项混沌技术是在适应当前信息 时代的发展战略需要的基础上发展起来的，混沌在信息领域主要有以下几个方面 的应用 ， 1 2 1 混沌在密码学中的应用 一 ， 加密技术是现代信息安全的一项重要技术传统的加密技术主要利用数论、 代数及算法复杂性等理论。目前，由于密码分析方法的研究和攻击手段的不断进 步，传统密码学理论一不能满足安全需要；计算机运行速度的不断提高，使得新 的密码种类出现，如量子密码嘲和混沌密码等捌。经研究发现，传统的密码学 与混沌系统存在着密切的联系一个密码系统要求对密钥敏感依赖，对明文敏感 依赖，加密、解密变化是一个一一映射。相应的，混沌也具有敏感性，对初值敏 感，当初值有一个微小差别，其相轨迹呈指数发散；具有拓扑传递性，即任一点 的邻域在混沌映射的作用下将扩散到整个度量空间，相当于密码系统的扩散密 码系统要求对明文充分混合，才能达到保密的作用，而这一点，正好是混沌系统 所具备的遍历性，混沌系统能够把状态之间充分混合，达到内在的随机性。因此， 混沌为加密技术注入了新的活力 5 中南大学硕士学位论文第一章绪论 1 2 2 混沌在保密通信中的应用 1 9 9 0 年，p e c o r a 和c a r r o l l 发现了混沌可以实现同步瞄】，并且用电路实现 了混沌同步之后，混沌用于保密通信成为信息安全领域研究的热点问题。混沌用 于保密通信，主要有两种方式，一是利用混沌系统同步进行保密通信田1 ，二是 利用混沌映射自身的特性构造密码圆，以达到对信息的加密目的。利用混沌同 步进行保密通信，属于信道加密范畴；利用混沌构造密码，属于信源加密范畴。 近些年来，混沌同步和混沌控制理论日趋成熟，为混沌保密通信的发展铺平了道 路。目前已经构造出的混沌通信系统，大致可以分为以下几类【凹l ：混沌掩蔽 ( c h a o t i cm a s k i n g ) 、混沌键控( c h a o t i cs h i t tk e y i n g ) 、混沌调制( c h a o t i c m o d u l a t i o n ) 、混沌扩频通信( c h a o t i cs p r e a d - s p e c t r u mc o m m u n i c a t i o n ) 。 1 2 3 混沌在信号处理中的应用 混沌信号处理包括噪声背景下混沌信号的处理和混沌背景下有用信号的提 取两个方面刚噪声背景下混淹信号的处理是指抑制混沌信号中的噪声，这是 一项非常有应用价值的课题。对于混沌信号，如果采用传统的线性滤波的方法， 如f i r 、i i r 等，并不能很好的解决混沌信号与噪声分离的问题。由于混沌具有 宽频特性，对某些频率的抑制可能改变滤波后的输出信号的动力学特性。因此， 对于混沌信号，必须采用非线性动力学的方法进行处理才能获得良好的降噪效 果。自上个世纪9 0 年代开始，出现了许多特定的混沌去噪方法【3 ，如f a r m e r 方法、影子法等第二个方面是在混沌背景下提取出有用的信号人们发现，很 多场合的噪声背景具有混沌的特点，这样，当有用信号淹没在具有混沌行为的噪 声背景中时，如果采用常规的统计检测方法，就把的混沌信号看为随机噪声，从 而不能取得良好的检测效果。随着人们对混沌认识的不断深入，人们发现混沌是 由确定机制所确定的，并且，由这种确定机制发现了许多规律，从而发现了一系 列的检测方法，如相空间重构法p 2 l 、相关维计算法口3 1 等等。 1 3 复杂性的概念及其物理意义 随着混沌在密码学，保密通信等信息领域中应用的展开，系统安全性和复杂 程度成为了一个重要的研究课题。系统安全性是否符合检测标准，决定了混沌能 否成功应用于这些领域。因此，在混沌系统应用于信息领域的同时，系统复杂性 研究也不断的深入。研究复杂性的根本目的，是要为认识自然界中各种复杂现象 提供统一的方法和工具。由于复杂性的研究内容多种多样，就目前的研究成果来 6 中南大学硕士学位论文 第一章绪论 看，对复杂性的研究还没有形成统一的共识，对复杂性的研究是一个非常有挑战 性的课题人们对复杂度的研究，也只能从某一个方面、某一个领域着手，来探 讨事物的复杂性 3 4 1 1 3 ：1 复杂性的概念 复杂性问题的探索涉及到自然、思维和社会的各个角落，复杂性本身包含 了多个方面，因此，对复杂性的理解没有形成统一的认识，更谈不上统一的科学 定义，不同的领域对复杂性也有着不同的认识英语中复杂性。c o m p l e x i t y ”的 含义为：难以理解或解释的，错综复杂的中文词典中的“复杂”一词的含义为； 事物的种类、头绪等的多而杂。但这种字面的解释和科学研究。复杂性”的含义 截然不同。科学家为了描述事物的复杂性，正在寻找一种有效的衡量事物复杂性 的方法 ， 对复杂性的最早的数学描述，可追溯到k o l m o g o r o v 对随机性的理解 3 5 1 与 二，s h a n n o n 等对信息的概念和对信息量的估计阁按照k o l m o g o r o v 的描述，一个 对象的复杂性就是一段产生该对象的最短计算机程序长度。产生一个周期序列所 需计算机程序短，所以其k o l m o g o r o v 复杂性小，产生一个随机序列所需的计算 机程序长，故其k o l m o g o r o v 复杂性大s h a n n o n 信息熵是指一段信源所包含的 平均信息量信源概率分布均匀，熵越大；概率分布越不均匀，熵越小。因此， 一个过程越随机，熵越大，复杂性程度就越高在此基础上，人们发现了一系列 新的复杂性算法【3 7 - 弼 符号序列出现在众多的各个科学领域中，经常出现的一个问题是对于一个给 定的序列，如何分析它的复杂性本文主要研究单个序列的复杂性，即对单个混 沌序列的复杂性进行有效的度量，主要从单个序列的行为复杂性和结构复杂性两 方面进行研究分析 行为复杂性，是指序列与随机序列的相似程度，单个序列的复杂性概念与随 机性是分不开的要指出的是，这里的随机概念与概率论中的随机性是不同的两 个概念为了描述这种表面复杂却内含规律的现象，人们提出了复杂性测度 “一( c o m p l e x i t ym e a s u r e ) 概念网，对时间序列的复杂性因状态空间采用不同的分 割方法和不同的结构测度方法获得不同的复杂性测度本文所用到的一些行为复 杂性的算法也都是在基于k o h n o g o r o v 复杂性的基础上，对序列的测度熵进行计 算 结构复杂性，是指序列的组成频率成分的复杂性嗍这种分析主要是分析 序列在频率组成成分上具有的复杂性，以此来衡量整个序列的复杂性，这也是序 列复杂性的一个重要方面。混沌信号的频谱具有连续、均匀分布的特性，而这种 7 中南大学硕士学位论文第一章绪论 连续程度和均匀程度又可以衡量整个序列的复杂程度。在该种复杂性描述中，用 变换域内的特征量来讨论事物的组成频率的复杂程度。针对混沌信号的宽频特 性，计算了各种频率段下的序列复杂程度。 1 3 2 复杂性与随机性 单个序列的复杂性反映了序列的复杂程度，然而，单个序列的复杂性的刻划 与概率论中的随机性的概念却没有直接关系。概率论中的随机性是基于多次重复 试验得到的独立随机变量序列，它是一种简单的随机过程，有完整的数学理论 每次试验得到的序列只是这个随机过程的一个样本，在概率论中并没有对一个样 本是否随机下定义。而我们研究的复杂性由确定的系统产生，与该序列的生成没 有直接关系。动力系统的一个重要发现是，一个完全是确定性的简单系统可以产 生完全随机的输出。 1 3 3 复杂性研究进展 事物复杂性的研究，已经不是一个新的课题，国外的科学家在对复杂性问题 的研究起步较早，很多科学家从哲学的理性角度思考，认为事物的复杂性是随着 人们对事物的认识的逐渐深入而变化的，因此，不可能有一个完整的法则来确定 和衡量序列的复杂程度1 9 世纪6 0 年代以前，并没有科学家提出复杂性测度方 法，对事物的复杂性的理解也没有共识1 9 世纪6 0 年代以后，人们对复杂性的 研究重点转移到了时间序列复杂性的度量上 1 9 世纪6 0 年代中差不多同时，有三个人分别独立地提出了相同的方法，他 们是k o l m o g o r o v 3 5 4 l l 、g d c h a i t i i l 【4 2 1 和r j s o l o m o n o 茁4 3 1 ，在许多资料中，都简 称这种复杂性方法为k o h n o g o r o v 方法该方法的提出，为以后科学家们的复杂 性概念奠定了基础和铺平了道路。人们在用此法则的基础上，不断改进和发现新 的算法来衡量序列的复杂性。 k o l m o g o r o v 复杂性只对序列的复杂性的概念进行了阐述，实际上在计算当 中是难以实现的。直到1 9 7 6 年，由i 抽p - z i v m 及k a s p e r 和s c h u s t e r l 4 5 】提出了著 名的l i m p - z i v 算法，使k o l m o g o r o v 算法得以实现。从此，l i m p - z v 复杂性的 应用深入到了生物医学、天气预测、自然灾害预测和密码学应用等领域。直到今 天，l i m p - z i v 算法也还是一种非常经典和适用的复杂性研究算法。 随着复杂性算法的不断改进，国外一些科学家也提出了其它不同的算法。比 较有代表性和应用比较广泛的有近似熵( a p e n ) 算法m 7 】和捧列熵( p e ) 算法【鹌栅 近似熵算法是s m p i n c u s 于1 9 9 1 年提出来的一种复杂性的度量方法，该方法计 算更为简单，因此立即得到了广泛的应用。2 0 0 2 年，由c b a n d t 和b p o m p e 提 l 中南大学硕士学位论文 第一章绪论 出了排列熵算法，该算法改进了a p e n 算法中存在的一些问题，因此，也得到了 广泛的推广和应用。除此之外，还有很多科学家提出了各自对复杂性的理解和算 法 4 9 - 5 3 3 在序列行为复杂性发展的同时，本文也从另外一个角度结构复杂性的观 点来分析了系统的复杂性 5 4 , s 5 1 。通过对变换后的信号进行特征量分析，来衡量原 序列的复杂性，这方面的研究还不非常成熟，许多学者正朝着这个方向在进一步 的努力 随着对序列复杂性研究的不断展开，我国科学家对复杂性的研究也已经逐步 展开1 9 8 1 年，钱学森提出了三个崭新的科学技术领域：系统科学、思维科学 和人体科学通过对这三个领域作出的大量创新性工作，于8 0 年代末总结和提 炼出来。开放的复杂巨系统”的概念。1 9 9 0 年1 月，自然杂志发表了钱学森、 于景元、戴汝为合写的一篇论文；一个科学新领域开放的复杂巨系统及其 方法论，首次向世人公布了这一新领域。1 9 9 2 年，钱学森提出了“综合集成研 讨厅方法构想，用于分析复杂巨系统；戴汝为研究了认知复杂性问题并与于景 元、王浣尘等合作承担综合集成研讨厅的理论、方法及应用研究的重点课题，有 望创立有我国独立知识产权的成果 1 9 9 1 年1 月，在中国科学院张熹同志的倡议下，由周光召院长主持，中科 院举行了一次“复杂性科学学术研讨会”；1 9 9 4 年9 月，在香山举行了一次题为 “开放的复杂巨系统方法论”的学术会议。这两次会议对推动复杂性的研究起到 了积极的推动作用，复杂性的研究有了明显的进展 1 9 9 9 年3 月1 8 , - - 2 0 日在北京举行了题为。复杂性科学”的第1 1 2 次香山科 学会议。来自国内从事经济管理复杂性，生物复杂性及其它复杂性研究的4 0 余 位专家一起讨论复杂性科学问题。 对于序列的复杂性的探讨也随着复杂性理论的研究而不断深入我国科学家 也运用已经比较成熟的算法，应用到各个领域当中特别是近些年来，在医学、 自然灾害预报、经济学中的复杂性和密码学应用等领域的发展日新月异，特别是 在某些方面也取得了重大突破。当然，对复杂性的研究也期待更加深入 1 4 课题研究背景及研究意义 混沌是一个极具潜力的领域。然而，人们对混沌科学的研究还很不完善，对 混沌学的研究也极具挑战性。非线性系统特别是混沌系统受到了国内外越来越多 的学者的关注。国内外许多学者纷纷提出了不同的混沌系统，试图以多种角度和 方法来揭开混沌系统的本质特征人们正以吸引子、l y a p u n o v 指数、分数维等 一系列指标来刻画和描述混沌系统。混沌系统的复杂性研究是对混沌系统特性的 9 中南大学硕士学位论文第一章绪论 另外一种有效的刻画方法，通过对混沌系统复杂性的度量，可以更好地认知混沌 系统。 随着混沌学研究的不断深入，混沌在许多领域得到广泛的应用。特别是在安 全性领域，随着信息科学的飞速发展，信息安全t 通信保密显得尤为重要，而混 沌在安全性领域表现出巨大的应用潜力和应用价值。混沌系统的复杂性是混沌系 统密码学性能的一个重要指标。混沌系统复杂性的大小，直接关系到该混沌系统 能否用于安全性领域。所以，混沌系统复杂性研究成为了一个重要的课题。混沌 系统复杂性的研究目前还不是很完善，对复杂性的研究也没有达成统一的认识， 因此，对混沌系统复杂性的研究具有重要的意义。 1 5 论文的层次和结构 本课题研究对象为离散混沌系统的产生的时间序列。第一章为总结，概述混 沌的发展过程，在信息领域的应用，以及复杂性的概念和国内外发展概况。在第 二章中，阐明了一些常用离散混沌系统的动力学方程及其参数意义，描述了混沌 系统的相空间结构及序列散布点分布情况，为定性分析离散混沌系统的复杂性作 出铺垫。在第三章中，在k o l m o g o r o v 复杂性的基础上，应用l i m p - z i v 算法、 p e n 算法和p e 算法对序列的行为复杂性进行定性分析，从数值上度量了序列的行为 复杂性，并与第二章中的相空间直接观测法得到的结论进行比较和验证在第四 章中，运用傅立叶变换的谱熵算法和小波变换后的小波熵算法对序列进行结构复 杂性进行分析，用变换域内的特征量来描述原系统的复杂性最后，第五章是对 离散混沌系统复杂性研究结果的结论和展望 文章以复杂性为主线，从不同角度、不同的方法讨论复杂性研究算法，并 且应用对比分析的思想比较和分析各种方法，得出的结论基本一致。整篇文章的 大致思路如图卜1 所示。 图i - i 本文的研究思路和研究方法 l o 中南大学硕士学位论文第二章离散混沌系统的空问复杂性分析 第二章离散混沌系统的空间复杂性分析 目前，许多离散混沌系统已经应用于混沌密码学、混沌保密通信和混沌伪随 机序列发生器等。本章介绍了目前常用于信息安全领域的离散混沌系统的数学模 型及其空间结构特征，直观观测了其相空间的复杂程度，并且对混沌伪随机序列 的构造方法进行了描述 2 1l o g i s t i c 映射系统 2 1 1l o g i s t i c 映射方程 l o g i s t i c 系统是目前应用最广泛的一类非线性动力学混沌系统【2 ”，其映射方 程为 e ；o 一) 一“一= l ，2 ，3 ( 2 - 1 ) 其中，参数e ( o ，4 】，( o ，1 ) ，当3 5 6 9 9 s 4 时，系统处于混沌状态。 当系统参数变化时，系统的复杂性随之变化，具体体现在如下几方面： ( 1 ) ( o j 】时，系统存在_ o 的不动点； ( 2 ) 【l ，3 ) 时，系统存在斗0 和矗专l - l i p 的不动点，此为周期l 解； ( 3 ) 陵止) 时，此时，厄= 3 5 6 9 9 4 5 6 7 2 ，依次出现轨道周期变化 l 哼2 - 9 4 8 ，即倍周期分岔现象 ( 4 ) 当阪，4 ) 时，系统出现混沌现象。 其倍周期分岔图如图2 1 所示。 田2 - 1h 面础系统分岔图 中南大学硕士学位论文第二章离散混沌系统的空间复杂性分析 在图2 1 中，迭代初始值 g o = o 1 ，迭代次数n = 1 0 0 0 0 ，省略前2 0 0 个点， 参数z 7 的变化步长为0 0 0 5 由图2 1 可以看出，当时间序列依次经历稳定不动 点寸不稳定不动点专周期寸混沌四个不同的演化阶段时，系统复杂性依次明显 增大。当a ；4 0 时，l o g i s t i c 系统复杂性最大。这一点也可以通过l o g i s t i c 系统 的l y a p u n o v 指数体现。当= 4 0 时，l o g i s t i c 系统的l y a p u n o v 指数也达到最大 值0 6 9 。 2 1 2l o g i s t i c 系统空间结构 图2 - 2 和图2 - 3 分别描述了- - 4 0 时其相空间结构图和各点分布情况。其 中，系统参数u 7 = 4 0 ，初x 0 = 0 1 ，迭代次数n = 1 0 0 0 0 ，省略前2 0 0 个点。 图2 - 2l o g i , q d c 映射相空间结构 o 砌0 n6 0 0 0 舢1 0 0 0 0 圈2 - 3l o g i s 蝴代点空间分布蟹 。 由图2 2 可见，l o 豇i c 映射的相空间结构图为一个单峰，这也是l o g i s t i c 映射有时候又称为单峰映射的原因。由图2 - 3 可看出，_ = 4 o 时，系统的各点 几乎布满整个区域，并且所有的点都分布在( o ，1 ) 的范围内，这正是混沌系统的遍 历性和有界性特点的体现。 2 2t e n t 映射系统 2 2 1t e n t 映射方程 t e n t 系统是另外一种应用比较广泛的混沌系统，目前，由t e n t 构成的混沌 序列已经广泛应用于混沌扩频码的产生、混沌加密系统构造和混沌优选算法的实 现等领域中冈。t e n t 系统映射方程为 = 群一舅黑 ， 。1 ( 1 一) ( 1 一g ) g 以 l 1 2 ， ( u 并 眈 o 中南大学硕士学位论文 第二章离散混沌系统的空问复杂性分析 其中，系统参数q ( o 1 ) ，e ( o ，1 ) ，它与l o g i s t i c 为一个拓扑共轭映射。当g 在 ( o ，1 ) 变化时，系统处于混沌状态。特别值得注意的是，当q = 0 5 时，系统呈现短 周期状态，如( o 2 ，0 4 , 0 3 ，0 4 ) ，由于短周期的存在，系统的结构比较简单，其 复杂性比较小；另外，对于t e n t 系统，系统初值不能选取和系统参数g 相同，如 果相同，那么系统将演化成为一个周期系统。因此，在应用t e n t 系统时，应合 理选用系统参数g 和系统初值而 2 2 1t e n t 系统空问结构 t e n t 系统的相空间结构图和迭代点分布分别如图2 - 4 ，2 - 5 所示。其中，系 统参数g = 0 4 ，初值 g o = 0 2 ，迭代次数= 1 0 0 0 0 ，省略前2 0 0 个点 图2 4 t e a t 系统相空间结构图 02 0 0 0 4 0 0 0n8 0 0 0 e 0 0 01 0 0 0 0 圈2 4 t e n t 迭代点分布图 在图2 4 中，系统相空问轨线形状类似一个帐篷”因此，该系统有时也 称为。帐篷映射”当g 变化时，该轨线的最高点也相应变化。经研究发现，该 轨线最高点对应的横坐标值即为g 值与l o 蓟f 如比较，该系统仍为一个单峰映 射，而且是为一个直线单峰，系统在理论上应该具有相近的复杂性图2 - 5 是 t e n t 映射的迭代点分布图，与l o g i s t i c 系统类似，该系统的迭代点布满整个平面 区域，且值都均匀分布在( 0 ，1 ) 的范围内 2 3h e n o n 映射系统 ：， 2 3 1h e n o n 系统映射方程 h e n o n 映射是1 9 7 6 年由h e n