（电子科学与技术专业论文）基于浮点格式的数字混沌系统周期研究.pdf

硕士学位论文 a b s l r a c t a bs t r a c t t h ep e r i o d sa n dt h e i rd i s t r i b u t i o no fad i g i t a lc h a o t i cs y s t e m ， e s s e n t i a lc o n t e n to fc h a o t i cd e g r a d a t i o na n da n t i - d e g r a d a t i o nm e c h a n i s m r e s e a r c h ，i sa ni m p o r t a n ti n d i c a t o ro fa s s e s s i n gt h ec a p a c i t yo fa n t i - d a g r a d a t i o na n d t h es a f e t yo fac h a o t i ce n c r y p t i o na l g o r i t h m t h ee x i s t i n g c o n c l u s i o n sa b o u te m p i r i c a lr e l a t i o no f1 一dc h a o t i cs y s t e m sa v e r a g e p e r i o da n dt h ed i s t r i b u t i o nr a n g eo fp e r i o d sa r ea l lb a s e do nf i x p o i n t f o r m a t s i fu s i n gt h e ma st h eq u a n t i t a t i v ea s s e s s m e n tc r i t e r i ao fc h a o t i c a n t i d a g r a t i o n ，t h e o r e t i c a lb a s i si sn o ts u f f i c i e n t t og e ta ne m p i r i c a lr e l a t i o nw i t hm o r et h e o r e t i c a la n da p p l i c a t i v e v a l u e ，t h ep e r i o d sa n dt h e i rd i s t r i b u t i o no fd i g i t a lc h a o t i cs y s t e m sb a s e d o nf l o a t i n g p o i n tf o r m a t sa r es t u d i e di nt h i sp a p e r b e c a u s es t a n d a r d f l o a t i n g p o i n tf o r m a t s a r en o ts u f f i c i e n t ，n o n s t a n d a r d f l o a t i n g p o i n t f o r m a t sm a t c h i n gw i t ht h es t a n d a r do n e sa r ec o n s t r u c t e d ，b yp u t t i n g p r e c i s i o n v a r i a b l e si n t o f l o a t i n g p o i n t f o r m a t sa n du s i n gs t a n d a r d f l o a t i n g - p o i n tf o r m a t sf o rs t o r i n gn o n - s t a n d a r do n e s af a s ts e a r c h i n g a l g o r i t h mi sd e s i g n e d ，m a k i n gi tp o s s i b l et of i n do u tt h ec h a o t i cp e r i o d s u n d e rd i f f e r e n t f l o a t i n g - p o i n tp r e c i s i o n s u s i n gv i s u a lc + + 6 0 ，t h e p e r i o d so fe l e v e n1 一d c h a o t i cs y s t e m s ，f o u r2 一dc h a o t i cs y s t e m sa n d t d e r c s ( t a n g e n t - d e l a ye l l i p s er e f l e c t i n gc a v i t ym a ps y s t e m ) a r e m e a s u r e d ，b yc o n d i t i o no fd i f f e r e n ti n i t i a li t e r a t i n gv a l u e s ，d i f f e r e n t s y s t e mp a r a m e t e r s ，o rd i f f e r e n tf l o a t i n g p o i n tc o m p u t i n gp r e c i s i o n s f a c t o r si m p a c t i n gp e r i o d sa r ef i g u r e do u t u s i n gal i n e a rf i t t i n gm e t h o d ， t h ed i s t r i b u t i o nr e l a t i o n s h i pb e t w e e np e r i o d sa n dn u m e r i c a lp r e c i s i o n si s o b t a i n e d ，w h i c hc o r r e c t st h eo n eb a s e d o nf i x e d - p o i n tf o r m a t s m o r e o v e r ， i t g i v e sar a t i o n a l c r i t e r i o nf o r t h es t u d yo fc h a o t i ca n t i d e g r a d a t i o n m e c h a n i s m t h i sp a p e ra l s os h o w st h a tf o rc h a o t i cs y s t e m s ，c o n c l u s i o n s b a s e do nf i x e d p o i n tf o r m a t sc a nn o tb es i m p l ye x t e n d e dt oo n e sb a s e do n f l o a t i n g - p o i n tf o r m a t s k e y w o r d s c h a o s ，f l o a t i n g - p o i n t ，p e r i o d ，a n t i d e g r a d a t i o n h 硕士学位论文 第一章绪论 1 1 研究背景 1 1 1 混沌的基本概念 第一章绪论 在计算机等现代科技的辅助下，混沌学科迅速得到发展，其在信息安全的应 用更成为近年来的研究热点。科学家认为，混沌现象无处不存在于现代的物质世 界中，其打破了不同学科之间的分界线，是- - f l 涉及系统总体本质的新兴学科【1 1 。 混沌的研究起源于十九世纪末，科学家p o i i l c a r 6 【2 1 在研究太阳、地球和月亮 三天体的相对运动时，提出系统在某类不动鞍点附近存在异常运动，三体问题在 一定范围内其解是随机的，这实际上是一种保守系统的混沌现象。2 0 世纪6 0 年 代，保守系统中k a m 定理的提出和耗散系统中l o r e n z 吸引子的发现使混沌学 研究取得了重大突破【3 】。但是，混沌( c h a o s ) 概念于1 9 7 5 年才被科学家李天岩 和y o r k e l 4 1 首次提出，二人同时给出了混沌的一种数学定义。1 9 7 7 年，第一届混 沌国际会议于意大利召开，标志了混沌科学的正式诞生。f e i g e n b a u m t 5 】在1 9 7 9 年发表了混沌的普适性研究论文，由此奠定混沌在科学界的地位蔡少棠【6 】于 1 9 8 3 年设计出蔡氏电路，首次利用模拟电路产生混沌振荡及混沌分岔现象，为 混沌研究提供了实验模型，成为混沌学研究的又一里程碑事件。1 9 9 0 年，p c c o r a 和c a r r o l l l 7 1 提出了混沌系统应用于通信时的一种同步方案，并首次在硬件电路上 实现混沌同步，由此揭开了混沌的应用研究序幕。 混沌系统的奇异性和复杂性至今难以完全揭示，于是不同领域的研究学者从 多个角度对混沌进行了定义。混沌的几种常见数学定义如下： l 、l i y o r k e 定义【4 】 l i y o k e ( 李天岩约克) 定义是从区间映射的角度对混沌进行定义的。 定义1设一连续自映射函数厂：i - - 4 ，c 尺，i 是r 中的一子区间。如果存 在不可数的集合sci ，满足以下条件： ( 1 ) s 不包含有周期点； ( 2 ) 对于任意的x 。，x ：s ( x n 五) ，有 三砌s u p f ( z 1 ) 一厂( x 2 ) i 0 砌i n f l f 。( x i ) - f ( x 2 ) i - 0 其中厂( ) = f ( f ( ( ) ) ) 表示进行t 次函数厂运算； 硕士学位论文 第一章绪论 ( 3 ) 对于任意的x s 及厂上任意的周期点p i ，有 l i ms u p l f ( 五) - f ( 尸) | 0 则称厂在集s 上是混沌的。 l i y o r k e 定义刻画了三个重要现象： ( 1 ) 混沌运动存在可数的多个稳定周期轨道； ( 2 ) 混沌运动存在至少一个不稳定非周期轨道； ( 3 ) 混沌运动存在不可数的多个稳定非周期轨道。 2 、d e v a n e y 定义嘲 d e v a n e y 定义是从拓扑的角度对混沌进行定义的。 定义2 设度量空间v 中有一映射：y 寸v ，如果满足以下条件： ( 1 ) 存在万 0 ，对于任意的s 0 和x v ，在x 的s 邻域，内有自然数刀 和y 矿，使得d ( f “( x ) ，f ”( y ) ) 万； ( 2 ) 存在k 0 ，对于y 中任意的开集x 和】，有厂( a o n r ； ( 3 ) 映射厂的周期点在y 中是稠密的。 则称厂在y 上是混沌的。 d e v a n e y 定义表明混沌映射应具有拓扑传递性、不可分解性、长期不可预测 性和全局规律性。混沌系统对初始条件的敏感性，使得其演化轨道不可预测，不 同初始条件对应的系统轨道可能完全偏离，但由于存在拓扑传递性，系统轨道又 无法分解为两个或多个在厂下相互影响的子系统，然而事实上混沌行为宏观上仍 表现出一定的规律性，即存在稠密的周期点。 除l i y o r k e 定义和d e v a n e y 定义外，学界还提出了混沌的其它定义，如符 号动力系统、拓扑混合、s m a l e 马蹄理论、横截同宿点和m e l n i k o v 定义等。实 际上，不同研究领域的学者定义的混沌会存在差异，其描述内容可关于奇怪吸引 子、正拓扑熵、或正l y a p u n o v 指数等，因此目前仍没有存在统一的普遍适用的 精确混沌定义。尽管如此，综合大多数文献的叙述，可以这样不严格地简单理解 混沌的概念：混沌是一种类随机现象，指在确定的非线性系统中，不需要外界施 予任何因素，由于系统内部存在的非线性相互作用，而阵发产生的无规则运动【9 】。 混沌是确定的非线性动力系统中特有的复杂运动状态。以相空间的有限域为 整体，其表现为不稳定的有限定常运动，即在某种意义上运动状态是不随时间变 化的，运动区域局限于有限空间，而轨道永不重复，总结为全局稳定而局部不稳 定特征。一般地，混沌具有以下特性： l 、内随机性 一般地，确定性动力系统只有当输入是随机性时，输出才随机。混沌系统是 确定性动力系统，但其输入是确定性时，仍可产生类随机输出。由于此随机输出 2 硕士学位论文第一章绪论 来自于系统内部，故称混沌具有内随机性。混沌的内随机性是因系统的初值敏感 性引起的，因而异于通常所说的随机性。混沌系统对初值敏感，加上系统的非线 性不稳定机制，初值的差异迅速扩大，使得系统运动在宏观上变得不确定。 2 、有界性 混沌轨道始终限于某一确定区域( 混沌吸引域) ，混沌系统内部虽不稳定， 其轨道却永远不会超越混沌吸引域，即混沌是有界的。 3 、遍历性 在有限时间内，混沌运动遍历混沌吸引域内的所有状态点。 4 、分维性 混沌运动的轨道，在相空间中的某个有限区域内经过无限次折叠后，形成一 条特殊的曲线。曲线的维数是分数，而不是整数，故称混沌具有分维。分维性表 明了混沌的内部结构是无限层次自相似的，即混沌运动具有一定的规律性，这成 为混沌运动区别于随机运动的重要因素之一。 5 、普适性 普适性是指趋向混沌时，不同系统均表现出的共同特性，它不依赖于系统方 程或具体的系统参数。一般地，普适性分两种：结构普适性和测度普适性。结构 普适性是指系统在趋向混沌过程中，轨道的定量特征与分叉情况只与系统的数学 结构相关；测度普适性是指同一映射在不同测度层次间的嵌套结构是相同的，结 构的形态只与系统方程按幂次级数展开后的幂次相关。 1 1 2 数字混沌的退化 使用计算机等数字设备模拟混沌时，混沌系统在时间和空间上均被离散化， 则变成定义在有限精度的离散时间和空间网格上的、具有离散时间和离散变量的 混沌系统【1 0 1 ，它可被理解为受迭代过程中的量化噪声扰动的占一离散化混沌系 统，其中g 表示离散网格中相邻单元间的最大距离。在计算精度为尸的计算机迭 代下，离散网格为二进制数字化空间，s = 2 ，此离散化混沌系称作数字混沌 系统( d i g i t a lc h a o t i cs y s t e m s ) 1 l , 1 2 】。 混沌数字化( 离散化) 后会产生以下的问题： 1 、误差问题 实现数字混沌系统的器件精度有限，系统的迭代值存在有限精度效应引起的 舍入、截尾或者进位误差。在确定计算精度和确定迭代运算下，运算误差虽为确 定性的，但仍难以预测数字混沌系统在迭代中所产生的误差。这是因为，混沌系 统具有初值敏感性，迭代初始值有误差，对应的迭代轨道会以一种不可预测的方 3 硕士学位论文第一章绪论 式完全偏离原轨道。 2 、周期问题 在二进制数字化空间中，数值被网格化，网格个数有限。设实现数字混沌系 统器件的有限精度为p ，混沌系统是d 维的，系统的迭代值被限制于仅包含2 肿 个元素的网格空间中，系统的演化轨道最终不可避免地退化成周期性的，则演化 成一个循环，该循环的周期必然不大于2 d 。尸。设一维混沌系统的迭代方程为 x 川= f ( x 疗) ， ( 1 一1 ) 其中j c 。r ，力= 0 ，l ，2 ，图1 1 给出了其数字化后的典型演化轨道。轨道包括 两个连通的部分：x o 、x i 、x l - l 和吒、屯n l ，本文中它们 分别被称为过渡态和循环态，三和丁则分别被称为过渡态长度和循环周期， 工+ 丁称为轨道长度。 溉+ 1 、 x o - - x l + x 2 札l x l x l 仆 图1 - 1数字混沌系统的典型演化轨道 在混沌系统的吸引子中，内嵌有无穷多个不稳定的周期轨道，但系统在某一 特定时刻只表现为一种周期态，此周期态只是系统的一个不稳定解，当系统未受 任何外界干扰时，混沌轨道只能无限地靠近不稳定的周期轨道，而不会真正到达， 并随机地由一种不稳定周期态演化到另一种不稳定周期态。同时，因混沌吸引子 存在各态遍历性，在有限演化时间内，混沌系统会遍历性地经过吸引子内的每条 不稳定的周期轨道1 1 3 1 。然而，限于有限的计算精度，数字混沌系统的周期不可 能大于2 肿，则数字混沌系统的所有轨道最终均收缩成长度不大于2 肿的周期轨 道。轨道的收缩显然会破坏连续混沌的遍历性，导致系统丧失连续混沌时具有的 如复杂性、随机性等优良特性。 1 1 3 数字混沌应用于信息安全的研究现状 利用混沌系统的特性，可实现信息的安全性。信息论的奠基人s h a n n o n 指 出，任一加密算法须满足扩散原则和扰乱原则【1 4 1 。混沌系统的初值敏感性和轨 道长期不可预测性可满足扩散原则；混沌吸引子的混合性、拓扑传递性及系统参 4 硕士学位论文 第一章绪论 数敏感性可满足扰乱原则。理论上，将混沌应用于信息加密，加密信息难于分析、 破译，可防范穷举攻击、频率分析攻击等常见解密方法。混沌信号具有初值敏感、 长期不可预测等特性，使加密信息具备抗截获能力；混沌信号具有宽频谱、非周 期等特性，使加密信息具备隐蔽性；混沌信号由系统方程、系统参数及系统初始 值完全决定，其确定性保证了加密的易实现性。 目前，混沌在信息安全方面的主要应用有混沌保密通信技术【坫2 2 l 和混沌密码 技术 2 3 - 3 9 1 ，前者基于混沌同步技术，按实现方法可分为扩频、参数调制、脉冲定 位调制和混沌掩盖等，按同步方法可分为广义同步、相同步、滞后同步、藕合同 步、投影同步和完全同步等；后者按传统密码学的分类方法可分为混沌分组密码 和混沌流密码，按加密算法可分为基于动态s 盒的混沌密码、基于公钥的混沌密 码和基于搜索机制的混沌密码。混沌保密通信技术和混沌密码技术可合称为混沌 加密技术。 参照美国国家标准与技术协会( n i s t ) 评判标准，评估混沌加密技术的性 能包括三方面：安全性、实现特性和实现代价【4 0 】。安全性评估是分析混沌系统 本身是否安全，方法分为定量和定性两类，定量方法包括重构相空间分析法、分 维分析法、l y a p u n o v 指数分析法和k o l m o g o r o v 熵分析法等；定性方法包括庞卡 莱截面法和直接观测法。实现特性评估针对混沌加密的实现平台，分软件、硬件 两方面。实现代价评估是分析加密的时间代价和空间代价，时间代价分为准备时 间和加密时间，准备时间表示生成子密钥所需的时间，加密时间表示在子密钥控 制下变换明文数据所需的时间；空间代价分为静止空间和运行空间，静止空间是 指加密算法实现部分占用整个程序的空间，一般为加密执行代码的总长度，运行 空间是指在加密过程中执行算法所需分配的临时空间。 混沌加密技术的关键是混沌序列，而混沌序列又是基于数字设备产生的，因 而不可避免地发生退化现象。密码学界普遍怀疑混沌加密技术存在因混沌退化而 引起的安全性隐患t 4 1 1 ，短周期意味着弱密钥【4 2 】。虽然目前仍然没有可用的系统 框架从理论层面上克服数字混沌系统的动力学特性退化，但许多可能的改善混沌 性能的方法已提出，主要分三种： l 、扰动混沌系统【4 ”l j 扰动的目的是为了增强混沌的特性，延长系统的周期。其基本思想是在相应 的离散空间中，利用伪随机数发生器，如m 序列发生器，产生一个伪随机扰动 信号，以某种扰动函数比如异或的方式叠加到原混沌轨道，叠加操作每隔一定次 数的混沌迭代后执行一次。扰动是最常用的一种混沌抗退化策略，按照扰动对象 的不同，扰动方法主要分三类：扰动系统变量、扰动系统参数、同时扰动系统变 量和系统参数。虽然理论和实验结果表明此方法只需付出较小的代价便可较好地 5 硕士学位论文 第一章绪论 改善有限精度下混沌迭代输出序列的不均匀现象，延长混沌序列的周期【5 0 , s l 】，但 是加密的效果受扰动信号周期的影响，且不能从理论上证明加密时不存在由于混 沌退化而引起的安全性隐患，因而无法完全满足加密性能评估中的安全性要求。 2 、级联多个混沌系统【5 2 5 4 】 使用多个混沌系统代替单一混沌系统，能够增强混沌加密系统的安全性。特 别是当级联的混沌系统具有不同的迭代方程和不同的初始条件时，系统轨道的叠 加更能有效地掩盖密钥信息，降低密文与混沌轨道的相关性，使得加密信息难以 破译。有理论和实验分析表明，使用两个混沌系统可提供足够的安全性【5 2 】。但 是，级联多个混沌系统的方法，需要增加系统资源，加大实现难度，减慢加密速 度，难以满足加密性能评估中的实现特性和实现代价要求。 3 、提高计算精度【5 5 】 采用更高的计算精度能够延长混沌序列的平均周期，但是由于硬件设备的限 制，计算精度无法无限地提高，且有实验表明，此方法亦不能真正有效地增加所 有拟混沌轨道的长度，空间中仍大量存在长度远短于平均值的拟混沌轨道。对于 逐段线性混沌系统，文献【4 2 】指出提高计算精度的方法不可有效改善弱密钥的 不均匀分布，原精度下的弱密钥在高精度下并没有得到加强。文献 5 6 】使用不 同类型的计算机，对l o g i s t i c 混沌系统在单精度和双精度下的迭代结果统计分 析表明，提高计算精度并不能明显改善l o g i s t i c 混沌系统的动力学特性退化。 采用更高的计算精度，不仅增n t 软件和硬件实现的成本，也不能有效地改善某 些混沌系统的动力学特性退化，实用性不强。 6 硕士学位论文 第一章绪论 1 2 研究意义 混沌数字化后不可避免地发生退化，而现有的改善混沌密码安全性能的方法 均存在不足。好的密码特性是通过确定性的密码系统产生的伪随机混乱状态保证 的，因此好的混沌系统是确保密码系统安全性的关键，寻找一种安全的混沌系统 ( 称之为“安全混沌 ) 有可能成为保证混沌加密安全性的根本解决方法，直 接将其应用于加密可满足混沌加密的性能评估要求。安全混沌除了具有一般混沌 系统的特性外，内部还应存在抗退化机制，在退化的同时本身进行不断的抗退化， 表现为“长周期”特性。此机制存在的定量评估为：多数混沌符合周期分布的普 遍规律，周期限于某一经验分布范围，安全混沌的周期分布异常，相同计算精度 下存在周期超越经验分布范围的上限。 数字混沌系统的周期个数有限，但由于遍历性理论匮乏【埘，难于严格测算 系统周期的所有值及其个数。刻画数字混沌系统的轨道的一种有效措施是使用标 度律( s c a l i n gl a w ) ，通过统计实验和随机映射理论在宏观上研究混沌动力学特 性退化现象及规律【5 7 】设户为计算精度，令占= 2 一，标度律揭示了： 1 、过渡态长度以及循环周期的平均值和最大值均服从指数规律0 ( 6 叫) ， 其中d 0 ，由混沌系统的方程唯一确定。一般地，有占一“2 ，但对于h a m i l t o n 映射，关系式不一定成立。 2 、循环周期的个数满足数量级o ( 1 n e - 1 ) = d ( 尸) 。 3 、随着循环周期的增大，周期不同值的出现频率呈指数衰减【5 8 , 5 9 ，则在混 沌轨道中存在大量的具有短循环周期的演化轨道。 但是，标度律只在一般意义下成立，对于某些特殊的数字混沌系统，规律并 不适用【1 0 l 。为找寻混沌周期分布的普遍规律，j c e m a k 6 0 l 测得一维混沌系统的周 期分布范围 0 ，2 暑】，其中尸为b i t 位表示的计算精度，占= 0 6 8 + 0 0 5 ；c b e c k 和q r o e p s t o r f f1 6 l j 观察到类似结果，一维混沌系统的平均周期正比于( 1 广一， 其中1 n 为计算精度，r l 与f 相当。这些结论均基于定点格式，虽沿用至 今【6 2 】，却只有定性意义，实际意义有限，特别是要作为混沌抗退化机制研究的 定量评估标准，理论依据不充分。因为定点数定义在部分实数域上，表示范围有 限，当计算对象中存在一个或多个变量( 包括中间变量) 超出定点数的定义域时， 定点格式计算失效。另外，在给定精度下，定点格式的最小单元是常数，浮点格 式的最小单元是数的指数函数，两者功能上存在显著差别，计算对象必然受影响。 虽然定点数的编码格式和运算算法简单，但此优点随着硬件技术的发展已无实质 意义，目前计算机几乎都配置了浮点运算硬件单元，浮点数成为科学计算领域的 主流。因此，作为混沌系统抗退化能力的检验标准以及寻找安全混沌的依据，需 要在浮点格式下重新研究数字混沌系统的周期及其分布规律。 7 硕士学位论文 第一章绪论 1 3 论文研究内容及论文结构 第一章概述混沌的基本概念，包括混沌的发展历史、定义和特性，介绍混沌 数字化后的退化问题，并研究国内外已提出的各种混沌抗退化措施及其存在的不 足，阐述研究基于浮点格式的数字混沌系统周期的意义，最后是本文具体的研究 内容及论文组织结构。 第二章介绍i e e e7 5 4 标准浮点数，包括存储格式、浮点表示误差和浮点运 算误差，接着参照标准浮点数格式构造出非标准浮点数，并实验验证此构造方法 的合理性。 第三章描述数字混沌系统周期的快速搜索算法及程序流程图，并讨论周期测 算程序的快速性、准确性与可靠性。 第四章详尽论述1 1 种一维混沌系统及4 种二维混沌系统的周期分布，研究 影响周期分布的主要原因，并总结出浮点运算下数字混沌系统周期分布的普遍规 律以及定点、浮点格式下数字混沌系统的性能差异。 第五章从周期的角度探讨t d e r c s 混沌系统存在抗退化机制的可能性。 第六章总结本文研究工作及表述结论，提出数字混沌系统周期测算工作需优 化与改进之处，并展望整个课题的研究前景。 8 硕士学位论文第二章非标准浮点数的构造与实现 第二章非标准浮点数的构造与实现 本章首先介绍i e e e7 5 4 标准浮点数，接着参照标准浮点数格式，构造出7 种精度相异的非标准浮点数，并编程实现其中4 种低于6 4 位精度的非标准浮点 数，最后分析非标准浮点数的特性以及实验论证其构造方法的合理性。 2 1 标准浮点数 2 1 1i e e e7 5 4 标准浮点数格式 i e e e7 5 4 标准是国际电气及电子工程师协会制订的关于浮点数的行业标 准，最新版本为i e e es t d7 5 4 t m 2 0 0 8 1 6 3 1 。其内容包括：浮点数格式定义、运算 操作、舍入方法和异常情况处理等。 在i e e e7 5 4 标准中，浮点数分为符号域、指数域和尾数域三个部分( 图 2 1 ) ，域中保存的值分别用于表示二进制浮点数中的符号s 、指数e 和尾数m 。 根据各个域位数的不同，新版标准定义了四种不同的浮点数，其格式如表2 1 所 示。 图2 - 1i e e es t d7 5 4 t m 浮点数结构 表2 - 1i e e es t d7 5 4 r u 2 0 0 8 标准浮点数格式 三个域的取值含义如下： ( 1 ) 符号s 0 表示浮点数为正数，l 表示为负数。 ( 2 ) 指数e 9 硕士学位论文 第二章非标准浮点数的构造与实现 指数域的存储值e 减去一个固定的偏差( b i a s ) ，即为指数的实际值。单 精度浮点数( f l o a t 型) 的偏差值为2 7 1 = 1 2 7 ，双精度浮点数( d o u b l e 型) 的 偏差值为2 1 0 1 = 1 0 2 3 。以单精度浮点数为例，保存在指数域中的2 7 表示的 实际指数值为一1 0 0 ，而实际指数值o 在指数域中保存为1 2 7 。当实际指数值 e b i a s 为正值时，表示小数点向右移e b i a s 位；当e b i a s 为负值时，表 示小数点向左移e b i a s 位。由于偏差的引入，单精度浮点数可表达的指数值 范围为【- 1 2 7 ，1 2 8 。因特殊值的处理需要，指数值1 2 7 ( 保存为全o ) 和+ 1 2 8 ( 保存为全1 ) 被保留，于是单精度浮点数实际可表达的有效指数范围为 【- 1 2 6 ，1 2 7 。相应地，双精度浮点数的有效指数范围为【一1 0 2 2 ，1 0 2 3 。 ( 3 ) 尾数m 小数点后的数即为尾数。除特殊值( 非规范化数、n a n 、无穷、有符号的零) 外，i e e e7 5 4 标准要求浮点数必须是规范化的，即小数点左侧只能为1 ，且这 个l 是不用存储的。因此，对于规范化浮点数，m 位的尾数域实际表示的位 数为m + 1 。例如，二进制数1 0 1 0 0 1 ( 十进制值为5 1 2 5 ) 可表示为1 0 1 0 0 1 2 2 ，采用单精度浮点数表示时，忽略小数点左侧的1 ，右补0 以填满尾数域，即 得到尾数域的值0 1 0 0 1 0 00 0 0 0 0 0 00 0 0 0 0 0 0 。 通过不同取值的符号、指数和尾数，二进制浮点数可以表示多个实数值，如 表2 2 所示。根据指数和尾数的取值，浮点数可分为规范化数( 小数点左边第一 位隐含“1 ”) 、非规范化数( 小数点左边不隐含数) 、n a n ( 非数) 、无穷和 零共五种类型。规范化浮点数与实数r 之间的换算式为： r = ( 一1 ) s 2 r - 脑1 m ( 2 1 ) 表2 - 2i e e es t d7 5 4 t m 浮点数表示范围 l o 硕士学位论文第二章非标准浮点数的构造与实现 2 1 2 浮点表示误差 十进制实数按二进制浮点数格式表示时，先将十进制转换成二进制，再按相 应的浮点数格式存储。以实数5 1 2 5 为例，要表示为单精度浮点数，先将整数 部分5 转换为二进制形式1 0 1 ；接着将小数部分0 1 2 5 乘以基数2 ，乘积结 果的整数部分存于高位，继续不断重复将乘积结果的小数部分乘以2 的过程： 0 1 2 5 2 = 0 2 5 0 0 2 5 2 = 0 50 o 5x2 = 1 o 1 o 直至乘积结果的小数部分为0 ，此过程结束，得到的右侧一列数字为二进制数的 小数部分，即0 0 0 1 。这样，十进制数5 1 2 5 对应的完整二进制形式为1 0 1 0 0 1 ， 用规范化浮点数表示为1 0 1 0 0 1x2 2 。因为实数为负，符号域为l 。而指数为2 ， 指数域应为2 + 1 2 7 = 1 2 9 ，二进制形式为1 0 0 0 0 0 0 1 。尾数域需省略小数点左侧 的l ，为0 1 0 0 1 ，右侧用0 补齐。于是可得浮点数5 1 2 5 的存储值： l10 0 0 0 0 0 10 10 0 1o 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 在上述例子中，不断将小数部分乘以2 的过程结束标志是小数部分为0 。 实际上，只有5 与2 的乘积最后一位为0 ，因而存在大量的小数不能经过有限次 运算使得乘积过程结束。对于位数有限的浮点数尾数域，i e e e7 5 4 标准规定， 持续该过程直至得到的尾数填满整个尾数域，然后在小数点右侧最后一位进行舍 入操作。浮点数的表示误差正是源于此舍入操作。 i e e e7 5 4 标准默认的舍入模式为“最近舍入 ( r o u n dt on e a r e s t ) ，即舍 入到数值最接近该实数的浮点数。其原理近似于“四舍五入 ，两者不同之处在 于对o 5 的操作，“最近舍入 是采用取偶数的方式，因而“最近舍入亦称 为“舍入到偶数 ( r o u n dt oe v e n ) 。举例比较如下： “四舍五入”模式：r o u n d ( 0 3 ) = o ；r o u n d ( 3 5 ) = 4 ；r o u n d ( 4 5 ) = 5 “最近舍入 模式：r o u n d ( 0 3 ) = o ；r o u n d ( 3 5 ) = 4 ；r o u n d ( 4 5 ) = 4 另外，当一个单精度浮点数“最近舍入 成8 位的十进制数时，再将此十进 制数转换成浮点数，结果此二进制表示值可能与原值不相同。于是，d g o l d b e r g 明 提出定理：使用9 位的十进制数可以唯一地表示单精度二进制浮点数，而双精度 则需要1 7 位的十进制数。 舍入除舍入模式外，还存在舍入一致性的问题【6 8 】。在c p u 浮点部件或仿真 库等实际计算系统中，存储计算的中间结果时，通常使用如浮点数据寄存器格式 等中间格式。当完成计算后，再将中间格式转换成程序的运算格式，即内存格式。 一般地，内存格式精度不高于中间格式。在转换过程“真值一中间格式一内存格 硕士学位论文第二章非标准浮点数的构造与实现 式”中，如果内存格式低于中间格式，那么“中间格式一内存格式”便存在误差。 以表达式：a b + c d 为例，计算过程存在三种舍入方式： ( 1 ) 一次舍入 调入a 、b 和“d 到寄存器中( 中间格式) ，然后分别进行乘、加运算， 最后将结果返回给程序( 内存格式) 。计算过程只存在一次的舍入操作，发生在 计算的最后一步，表示为： e = a b + c d ( 2 ) 两次舍入 调入a 、b 到寄存器中( 中间格式) ，进行动运算并返回结果c ( 内存 格式) ，接着进行耐运算( 中间格式) ，再向程序返回与c 的相加结果( 内 存格式) 。计算过程存在两次的舍入操作，表示为： c = a b e = c + c d ( 3 ) 三次舍入 先进行动运算，返回结果c ( 内存格式) ；接着进行耐运算，返回 结果d ( 内存格式) ；最后返回c 和d 的相加结果( 内存格式) 。计算过 程存在三次的舍入操作，表示为： c = a b d = c d e = c + d 在实际计算系统中，使用中间格式存储，需占用系统中只少量存在的关键资 源。因此，方式( 1 ) 虽精度高，但只能在程序的个别运算中实现，无法全局实 现。方式( 3 ) 虽精度低，过程复杂，需进行多次的数据调入、格式转换以及寄 存器清空等操作，但其优点是保证了每次计算的精度一致，只存在内存格式一种 精度。方式( 2 ) 是一种混合方式，缺点在于每次计算的精度不一致。在上述的 例子中，c = a b 为内存格式精度，需要进行舍入操作一次，而耐为中间格式 精度，不需舍入操作，同一计算式子中采用两种不一致的精度可能会致使计算结 果与理论值截然相反。例如要计算两个复数a + b j 和c + a j 的积： ( 口+ t , j ) ( c + a j ) = ( a c - b d ) + ( a d + b c ) j 理论上当a + 够与c + 谚共轭，即a = c 、b = 一d 时，计算结果为实数。如果 采用舍入方式( 2 ) ，计算结果却完全相反。因为，耐+ 沈的运算过程为： c = a d e = c + b c 当a = c 、b = - d 时，有： 1 2 硕士学位论文 第二章非标准浮点数的构造与实现 c = - a b e = c + b a 运算c = 一口6 存在一次的舍入操作，而运算施不存在舍入操作，c 和6 口 因精度不同而数值相异，结果e 不为0 ，两个共轭复数的积不为实数。 出现上述情况，是由于舍入方式( 2 ) 在计算过程中精度没有保持一致，为 避免计算误差，舍入时需采用方式( 1 ) 或方式( 3 ) 。方式( 1 ) 受硬件限制较 大，而方式( 3 ) 虽然效率低，但能保持计算的一致性，且占用硬件资源少，故 成为最佳方案。在下文提到的用非标准浮点数进行浮点运算时，亦效仿方式( 3 ) 的原理，对表达式的每一步均进行格式转换例如表达式：幻+ 耐，操作步骤 如下： 分别将a 、b 、c 、d 转换成非标准浮点数格式； 将a 与b 相乘后的结果c = a b 转换成非标准浮点数格式： 将c 与d 相乘后的结果d = c a r 转换成非标准浮点数格式； 将c 与d 相加后的最终结果e = c + d 转换成非标准浮点数格式。 当使用i e e e7 5 4 标准浮点数格式表示“0 时，因1 位的符号域有两个取 值，故“0 ”存在两个值：+ o 和0 。在涉及无穷等特殊的计算中，有符号的“0 可避免计算结果出错。例如等式i o x ) = x ，如果“0 无符号，那么当x = 硼 时等式不成立。虽然如果“o o 亦无符号可使等式恒成立，但是当发生数值上溢 时无符号的“o o 却没法表达数值溢出的方向。然而，“0 如果有符号，则判 断语句i f 伍= = o ) 会由于x 可能是- 1 - 0 而使得结果不确定。为防止使用误 会，在i e e e7 5 4 标准中，规定正负零是相等的，因此本文中的程序是采用无序 的零的表示方法，则+ o = 0 = 0 。 2 1 3 浮点运算误差 十进制实数表示成二进制浮点数存在固有的表示误差，且误差随着浮点运算 次数的增多而逐渐累积，最后造成十进制运算在计算机上的结果只能为精确值。 例如计算( o 7 0 1 ) 的值时，使用c 语言编程运算的结果是0 5 9 9 9 9 8 5 。结果出 现误差的原因在于浮点数无法准确表示0 7 和o 1 ，而只能精确表示其经过舍入 后的值，两个近似值之间的运算结果自然异于理论准确值。 文献【6 9 】指出，多数实数运算和代数规则在浮点运算时不再适用。例如， 下列表达式在实数运算时是恒成立的，但在浮点运算时则不适用： 表达式说明 口1 0 = a乘法恒等式 1 3 硕士学位论文 第二章非标准浮点数的构造与实现 ( 口+ 6 ) + c = a + ( 6 + c )加法结合律 ( 口6 ) c = a ( 6 c ) 乘法结合律 ( 口+ 6 ) 一6 ) = a a b b 因式分解 a ( 6 + c ) = a b + a c分配律 a b = a ( 1 b ) 使用乘法逆元素计算除法 同时，文献 7 0 】表明，浮点运算均存在统一形式的误差界，并由此造成运 算结果异于理论值。例如实数7 0 0 1 和8 0 0 1 ，采用f l o a t 型浮点数表示时，分别 为： ( 7 0 0 1 ) 1 0 = ( 1 1 1 0 0 0 0 0 0 0 00 1 0 0 0 0 0 1 1 0 0 0 1 0 0 ) 2 = ( 1 1 1 0 0 0 0 0 00 0 0 1 0 0 0 0 0 1 1 0 0 0 1 ) 2 2 0 1 0 ( 8 0 0 1 ) 1 0 = ( 1 0 0 0 0 0 0 0 0 0 0 00 1 0 0 0 0 0 1 1 0 0 0 1 0 0 ) 2 = ( 1 0 0 0 0 0 0 0 00 0 0 0 1 0 0 00 0 1 1 0 0 0 ) 2 2 0 1 1 两者的尾数互不相同，8 0 0 1 因小数点左侧较7 0 0 1 多一位，因而小数点右侧需 丢失最后一位“1 ，且指数值变为0 1 1 。丢失的这个重要信息“1 刀使得运算 8 0 0 1 7 0 0 1 1 ，显然此结果不符合理论运算8 0 0 1 7 0 0 1 = l 。 因此，浮点运算需注意1 7 l 】： l 、结果的准确性受计算顺序的影响； 2 、正数与负数相加、正数与正数相减或者负数与负数相减，所得结果的精 度可能小于所采用的浮点数的精度； 3 、进行乘法或除法运算时，乘法和除法因子的数量级应尽量一致； 4 、进行一系列加、减、乘、除运算时，应先做乘法和除法，再做加法和减 法： 2 1 4v c 6 对浮点格式的支持 m i c r o s o f tv i s u a lc + + 6 0 ( 如下简称v c 6 ) 是微软公司推出的基于c c + + 编 程语言的w i n d o w s 应用程序开发平台，其内置了众多广受好评的技术如在代码 层次对w i n d o w sa p i 进行封装的m f c 类库、c o m 、a t l 等，满足技术人员的编 程需求，具有稳定、高效、方便等特点。 c c + + 标准支持f l o a t 、d o u b l e 和l o n gd o u b l e 三种类型浮点格式，而i e e e7 5 4 浮点标准要求强制实现f l o a t 型格式，建议实现d o u b l e 型格式，但对扩展双精度 l o n gd o u b l e 型格式的实现不做要求。基于i e e e7 5 4 浮点标准，v c 6 对于浮点 格式的支持可分为三个方面嘲j ：接口参数、库函数内部使用和用户层存储。支 持浮点格式作为接口参数是指用户可使用该格式与库函数进行数据交换，即函数 1 4 硕士学位论文第二章非标准浮点数的构造与实现 参数的调入和返回；支持浮点格式的库函数内部使用是指库函数内部使用该格式 计算或作为中间结果的存储格式；支持浮点格式的用户层存储是指编译器使用该 格式作为用户数据的存储格式。表2 - 3 列出了v c 6 对f l o a t 、d o u b l e 和l o n gd o u b l e 三种浮点格式的支持情况。 表2 - 3v c 6 对浮点格式的支持情况 f l o a t 型浮点数使用单精度格式，三者之中其精度最低，v c 6 支持其用于用 户层存储，但用于接口参数时，需将f l o a t 型强制转换成d o u b l e 型。因此，当v c 6 调用浮点函数时，在参数调入处使用f l o a t 型浮点数的效率低于d o u b l e 型，并且 因数值表示范围差异，参数赋值后函数的运行结果可能出现变化 d o u b l e 型是v c 6 唯一全面支持的浮点格式。v c 6 在接口层将f l o a t 型浮点数 强制转换成d o u b l e 型，因而使用其它浮点类型，实际上是间接使用d o u b l e 型。 c c + + 标准虽支持l o n gd o u b l e 型，但只约定l o n gd o u b l e 型的精度和数值表 示范围不低于d o u b l e