随机数发生器研究与实现

1、摘 要随机数是专门的随机试验的结果。在统计学的不同技术中需要使用随机数，比如在从统计总体中抽取有代表性的样本的时候，或者在将实验动物分配到不同的试验组的过程中，或者在进行蒙特卡罗模拟法计算的时候等等。产生随机数有多种不同的方法。这些方法被称为随机数发生器。随机数最重要的特性是：它所产生的后面的那个数与前面的那个数毫无关系。随着Internet和无线网络通信的发展，随机数不仅应用与信息安全领域，而且在通信系统中也有广泛的应用。特别是随着社会资源越来越依赖网络通信，对网络传输的稳定性、高效性要求也越来越高。因而研究应用于网络通信的随机数发生器在当今社会中极有意义。本文主要研究各种随机数的性质，利用

2、NS2仿真系统实现随机数发生器，并将随机数发生器应用于网络中，分析其网络性能优劣。关键词：随机数，均匀分布，正态分布，指数分布，随机数发生器注：本设计（论文）题目来源于教师的省级科研项目，项目编号为： 。AbstractRandom number is a random the test results. the statistics of various technologies need to use the random number, in drawn from the statistics on the representative samples, or experiments o

3、n animals will be assigned to various tests, or when use Monte carlo simulation method , etc.A random number of several different ways.This method is called a random number generators. Random number of the most important feature is: it by the back of the number and the number does not matter. As the

4、 internet and radio network of communication and development of random number is not only to information security, and in a communication system also is widely used. In particular with the social resources and communications depend on the network to network transmission stability, efficient and high

5、er demands. they study internet communication in the random number generators in our society is very meaningful.This major study of random number of simulation system of ns2 for the random number generators and random number generators applied to the internet, analyzing the network performance from

6、the chaff.Key words: Random Number,Uniform Distribution,Normal Distribution,Exponential Distribution,Random Number Generator目 录1绪论11.1随机数概述11.2随机数发生器研究现状及意义11.2.1 随机数算法研究现状21.2.2 随机数发生器研究现状31.2.3论文主要研究内容及结构安排42典型均匀分布随机数62.1均匀分布随机数的简述62.2均匀分布随机数的各种算法62.2.1线性同余法72.2.2线性同余组合法82.2.3混沌影射法92.3均匀分布的随机数的测试检

7、验标准102.3.1参数检验112.3.2均匀性检验122.3.3独立性检验（相关性检验）132.3.4频谱检验133正态分布随机数153.1正态分布随机数的简述153.2正态分布随机数的生成算法153.2.1数学模型153.2.2正态分布和标准正态分布的特征153.2.3实现原理184指数分布随机数234.1指数分布随机数的简述234.2指数分布随机数的生成算法234.2.1数学模型234.2.2生成方法234.2.3实现原理244.3网络传输中的泊松流和指数分布264.3.1泊松流与指数分布275 NS2仿真系统305.1 NS2仿真系统简介305.2随机数发生器的仿真测试305.2.1随

8、机数发生器的种子305.2.2均匀分布随机数发生器的仿真315.2.3正态分布随机数发生器的仿真335.2.4指数分布随机数发生器的仿真355.3随机数发生器在网络应用中的仿真实验375.3.1仿真网络结构图375.3.2效果评比指标：吞吐量（Throughput）385.3.3实验程序TCL代码编写385.3.4仿真实验结果40结 论44参考文献45附录A NS2随机数发生器仿真程序代码47分析网络吞吐量程序代码：47致 谢49481绪论1.1 随机数概述随机变量（或随机向量）的样本简称为随机数。它广泛用于系统仿真、测试、信息安全等诸多领域。随机数产生方法已经有很长的研究历史，至今仍有统计学

9、者继续研究其产生理论与方法。产生随机数的方法一般有四种：手工方法、随机数表方法、物理方法和数学方法。目前比较常用的是物理方法和数学方法。物理方法大多利用物理噪声作为随机源，这种方法产生的随机数是真随机数，它的适用范围是安全性和速度都要求特别高的场合。在大多数网络安全中很少采用真随机数源，主要原因有二：一方面真随机数序列不可重现，另一方面数的精度不够。此外，这些真随机数源的设备很难连接到网络系统种，并且需要经常检查和维修，以保持物理随机数发生器的稳定性，这导致该方法的适用价值大大降低。数学方法是目前应用最广泛、发展很快的一类方法，它是利用数学递推公式来产生随机数，具有占用内存少、速度快且便于计算

10、等特点。与利用物理方法产生真随机数的真随机数发生器相对应，利用数学方法产生伪随机数称为伪随机数发生器（pseudo random number generator,PRNG）。一个好的伪随机数发生器应当具备以下几点条件：1、 产生的随机数序列要具有均匀的总体随机样本的统计性质，如分布的均匀性， 抽样的随机性数列间的独立性等等（经验检验）。2、 产生的伪随机序列要具有较好的理论支持（或具有好的格结构），如分布的谱检验（spectral test）和高维分布检验（k-distribution test）（理论检验）。3、 产生的伪随机数序列要有足够长的周期，以满足模拟计算的需要。4、 产生的伪随机

11、数序列速度快，占用计算内存少，具有完全可重复性1。随着计算机运算速度的不断提高，存储容量和字长的不断扩大，3和4两点一般都能满足；条件2属于理论研究问题，由于涉及到很多数论等基础数学内容，本问不作过多的研究。因此，条件1是构造伪随机数发生器的关键，需要大量的统计检验工作。1.2 随机数发生器研究现状及意义1.2.1 随机数算法研究现状对于不同的应用和社会需求，人们研究发明了不同的随机数生成算法。常见的实现方法如下所示：Von Neuman在1940年提出了平方取中法，其原理示将一格给定的2n比特的数平方，然后高位补0得到4n比特的数，再截取中间的2n位进行下一次迭代，并得到一个随机数序列。这种

12、方法无论是在硬件实现上，还是在仿真测试上都比较容易实现，但是它的周期受初始值的影响很大，如果初始值选得补好，会严重影响随机数序列的质量和周期，而且其最大周期不会超过22n。Fibonacci方法是产生随机数的一种常用方法，它只要两个初值和一个模数即可，其递推公式如下所示： (1.1)从公式1-1可以看出，用此方法产生得随机数序列周期位3M/2，而且没有乘法运算，因此其生成速度非常快，物理实现也十分简单，但是它有两个致命得缺陷：1、 产生得随机数序列有着令人不能容忍得不居中现象，即用前两个随机数得到的第三个随机数不是同时大于就是同时小于前两个而永不居中。2、 产生的序列有明显的相关性。1951年

13、，Lehmer提出的线形同余法示用得比较多得随机数产生方法，真迭代公式如下所示： (1.2)当模数M足够大时，用线性同余法产生得随机数在区间(0,1很密集，而且接近均匀分布，其随机数序列具有较好统计特性2。虽然序列的参数，如乘子、增量和模数对随机数的质量和和周期影响很大，但是它们都有自己的选取准则，可以使产生的随机数序列性能最优。在实际应用种，人们常用线性反馈移位寄存器来产生伪随机数发生器，其实现方式最简单，其迭代公式如式1-3所示： (1.3)式中为0或1，表示序列，表示异或操作，表示寄存器的阶数，表示第个随机数。用线性反馈移位寄存器产生的随机数最大周期可达，阶数越大，序列就越长，但这样所需

14、的寄存器就越多，会增加硬件的面积，如果用静态存储器（SRAM）来代替寄存器，那么会使随机数序列的周期更长，但这样会使得硬件得面积和功耗进一步增加。Marsaglia-Aaman在1991年提出了一类新随机数发生器，包括进位加（add-with-carry，简称AWC）和借位减（subtract-with-borrow，简称SWB），它们的生成速率比线性同余法还快，而且具有超长的周期。1998年LEcuyer提出了线性同余组合随机数发生器，该方法产生的随机数序列具有线性同余序列的所有特性，而且其在高维空间的均匀性要比线性同余发生器要好。当然，除了上面这些算法之外，还有很多其他方法来产生随机数，如

15、混沌映射法、逆同余法、无理数变换法等，这里不作一一介绍。1.2.2 随机数发生器研究现状由于随机序列发生器在信息安全、军事、商业等应用领域中发挥的作用越来越重要。统计独立性更好的真随机数成为应用领域最受关注的一个研究方向，国内外对真随机数发生器(TRNG)的研究也越来越重视。很多这方面的文献资料显示在国外，这些项目多有政府、金融机构、军方的资助，发展速度很快。早在1985年Intel公司在研究访问受控EEPROM芯片时就曾采用过一个简单的片上随机数发生器，后来它的一个科研小组利用电阻上热噪声设计了一种随机数发生器，是采用的双振荡器结构。1997年Georgia Institute of Tec

16、hnology采用1.2微米Bi-CMOS工艺开发了基于运算放大器噪声的随机数发生器芯片。2002年前后瑞士日内瓦大学根据量子效应开展随机数发生器的研究。相应地中国科学院研究院的冯凯锋、望等人也开展量子随机数发生器的研究工作。北京工业大学的冯艳、杨镇海等人也提出了利用无理数无限不循环的特性建立随机序列产生的模型。在2003年，中科院研究生院的苏桂平等人根据小波分析理论为数字物理噪声源的随机性建立数学模型，利用电路内部噪声信号研制随机序列发生器。同年成都电子科技大学的张传武、彭启宗等人在S.Wofram提出的利用细胞自动机产生随机数方法的基础上，进行了深化研究，提出了基于具有本原多项式的90/1

17、50加性细胞自动机的随机数发生器模型。通过查阅最近的研究文献后发现，目前对真随机数发生器的研究开始越来越多地关注于优化物理随机源的设计。这其中便于采用纯数字电路实现的振荡环采样法成为当前的研究热点。由于各种物理环境变化的影响，基于硬件实现的随机序列源通常具有一定的相关性。在2000年时C.S.Pstrie和J.A.Connelly通过将放大后的噪声源、采样振荡环噪声、离散时间混沌映射这三个熵源进行结合，很好地解决了这个相关性的问题。在2003年M.Bucci等人通过放大热噪声构建慢时钟驱动DFF对一个稳定的快速时钟采样，设计了一种数模混合的熵源。解决了基于振荡环采样的随机源因为抖动密度不够而造

18、成的输出速率低、随机性能差等问题。后经0.18umCMOS工艺实现后，验证了该设计输出速率高且性能良好。2004年H.Bock与M.Bucci等人合作，提出了一种带有补偿环(Compensation loop)的振荡采样源，当慢时钟的抖动密度不够时，可以自动降低慢时钟的采样速率，从而提高输出的统计性能，且该设计可以全部用数字电路进行实现。2006年Jovan Dj.Golic等提出了2种新的结构：斐波那契(Fibonacci)和伽罗华(Galois)结构。这两种新结构在通常的振荡环上引入了数学上的LFSR概念，从而将具有真随机性的时钟抖动与具有伪随机性的LFSR结合起来。同年Bucci，L.G

19、iancane等人采用了延迟模块和MOS开关，构造了一种新颖的耦合振荡器，这种振荡器实现了约为13Mbit/s的高数据输出率3。现如今，真随机序列生成算法和硬件随机序列发生器不断涌现，呈现出百家争鸣的态势。虽然真随机数发生器在密码、密钥的应用中起着重要作用，但是目前大多数真随机数发生器还是基于一种理想状况来分析其输出的随机序列的性能。实际中以上这些方法中仍存在一些弱点，如产生的随机数的分布特性较差、稳定性不佳等缺点，所以在实际使用中，通常还需要对其发生器的输出序列进行后期的算法处理，才能使其输出的序列能够通过各种随机性的测试。1.2.3论文主要研究内容及结构安排本论文在总结前人研究成果的基础上

20、，分析随机数的实现算法，并用网络仿真系统方式加以实现，使其产生适用于计算机网络范畴的网络传输领域的不同分布的随机数。本论文着重研究的内容如下：一、了解三种不同分布随机数均匀分布、正态分布、指数分布，熟悉其数学模型、分布特征、实现算法等。二、比较同分布随机数用不同算法实现时的优缺点。并用NS2仿真系统对三种随机数进行仿真分析，比较不同分布随机数发生器在网络传输吞吐量的优缺点。本论文主要内容分为6章，第1章是绪论部分，简单的介绍了随机数算法以及随机数发生器国内外研究现状和意义；第2、3、4章是分别介绍均匀分布随机数、正态分布随机数以及指数分布随机数的理论和生成算法；第5章是本论文的核心部分，将利用

21、NS2仿真系统设计一个不同分布的随机数发生器对网络传输吞吐量影响研究的实现，分别对2、3、4章所介绍三种分布随机数进行仿真，记录其结果并加以分析研究；第6章是总结，对本文的研究结果进行了总结和展望。2典型均匀分布随机数的生成 2.1 均匀分布随机数的简述均匀分布的随机数是指随机数序列中每个随机数都具有相同的出现概率，均匀地出现在分布区问上。均匀分布的随机数是产生其他分布的随机数的基础，它的性能好坏直接影响到所产生的其他分布的随机数的性能，因此，本论文着重讨论均匀分布的随机数的算法、测试检验以及硬件实现。与其他大多数应用相比，对应用于网络通信中的随机数有更严格的要求，必须满足以下几个方而的要求：

22、1、 不可预测性，即无法根据当前状态或先前状态猜测随机数的下个状态，也就是说，随机数序列中各个随机数是互不相关的，而且它任意长的子序列也是互小相关的。对于真随机数，当然满足不相关性；但对于伪随机数，我们应尽量研究、改进其算祛，使其满足这一要求。2、 不可重复性，即随机数序列的周期必须为无穷大，但伪随机数序列通常是由具有周期性的数学公式产生，因此其本身也必然表现出周期性，即序列中一段子序列与另一段了序列相同。由于伪随机数周期性重复出现，使得随机数序列必然表现出相关性和不均匀性。如果要把伪随机数当作真随机数来应用，那么它的周期必须是无限长的，这样必然会占用大量的空间、内存以及计算时间。3、 能通过

23、随机性统计检验，为了检查一个均匀分布得随机数能否通过随机性统计检验，必须对随机数做各种测试检验，尤其是FIPS140测试3。如果一个随机数序列满足上述三方面条件， 那么这个随机数在一定范围内可以当作真随机数来使用。相对于真随机数，伪随机数具有物理实现简单，产生速率快，占用的内存较少等优点，囚此伪随机数广泛的应用于网络通信、科学研究、校拟计算等领域。2.2均匀分布随机数的各种算法本节简单地介绍产生均匀分布的随机数的各种算法，对各种方法产生的随机数分析其性能，并且选择最优的算法来生成高质量的均匀分布的随机数，作为生成其他分布的随机数的基础。目前，产生均匀分布的随机数的最流行方法主要有线性同余法、线

24、性反馈移位寄存法、线性同余组合法和混沌映射法等4。2.2.1线性同余法线性同余法是利用数论中的同余运算来产生随机数，它的递推公式为： (2.1)上式中，序列在区间上服从均匀分布，是随机序列的第个数，是第个数，变量都是常量，其中是乘子，是增量，是模，是密钥，也是种子的初始值。如果，此线性同余法称为混合同余法，否则称为乘同余法。从上式可知，如果知道的值，那么这个随机数序列就可以计算出来。线性同余法产生的随机数序列具有周期性，其最大周期为。在线性同余法中，变量和初值的选择对随机数序列有很大的影响。为使统计特性最优以及随机数序列有最大周期，的选取应该符合以下准则：1、 初值对序列的周期没有影响，对其统

25、计特性的影响也不大，一般取不小于的奇数。2、 为了保证序列有很大的周期，使其产生的随机数尽可能的接近于真随机数，M应取尽可能大的素数，但不能大于，是计算机尾部字长。如果不取素数，那么序列的右半部分的随机性非常不好。3、 乘子对随机数的性能影响很大，特别不能随意，一般应在区间之内。4、 增量对随机数序列的影响较小，一般取为奇数，。为了使线性同余法有最大周期的充要条件是：(1) 如果对的所有素数因子，均成，即。(2) 当为的倍数时，还应成立。(3) 同互素（即和的最大公因数为1）。当满足以上几个条件后，线性同余法产生的随机数具有最大周期，而且产生的随机数具有均匀性好、独立性好等特点。2.2.2线性

26、同余组合法所谓组合发生器是指用几个线性同余发生器组合成一个新的发生器。例如有个乘同余发生器(2.2)式中，表示各乘同余发生器的模，是互异的素数。设为中最大值，按构建最大周期的线性同余发生器原理：乘子为模的原根5。令是个任意的非零整数，并定义组合发生器的数学表达式如下：(2.3)(2.4)则组合发生器在区间0,1上的序列如下：(2.5)序列、都可看作是服从分布的随机数。当然组合对象并不只限于线性同余发生器，也可以用前面提到几种发生器，如线性反馈移位寄存器、混沌映射法等。但是不同组合的理论分析是十分困难的，现在只有对线性同余法的组合有较深的理论研究，本论文中也采用线性同余法来构成组合同余发生器6。

27、经研究表：如果随机变量是在区间上的相互独立，是整数，又设, 若且是整数，则。（注：可以不是，且也可以不是整数）假如被组合的序列是最大周期的线性同余序列，其分别周期为当与互素时，这个组合发生器的周期是这个线性同余序列的周期的最小公倍数（LCM）。如果构成线性同余发生器的模是互素的，那么组合发生器将具有最大的周期，其周期可视无穷大。组合发生器优于组成它的任何一个线性同余发生器，但是组合发生器木质上仍近似等价于其中某一个线性同余发生器。因此对十线性同余组合发生器的统计性质的研究可以近似简化为对某个关联的线性同余发生器的研究7。因为线性同余法具有高维网格稀疏结构的特征，那么组合同余法也必然具有此特征。

28、但是由上组合同余发生器的模数巨大，与线性同余法相比，其高维网格就没那么稀疏和规则，而且网格现象也不容易被察觉。2.2.3混沌影射法所谓混沌，就是动力学系统产生的一种极其复杂的类似噪声的运动行为，它具有如下特性：1、时域上为随机过程；2、频域上为宽带非对称的连续谱；3、对初始值的灵敏依赖性；4、具有分形结构。混沌所具有的类似噪声的行为无疑给构成随机数提供了新的思路。An（1996）曾经研究了混沌映射（chaotic mapping）产生随机数的方法8，该文使用的递推公式如下： (2.6)并指出此递推式可产生周期为无穷的序列，其经验分布的极限为 (2.7)根据产生随机数中的熟知理论，若随机变量的分

29、布函数的，则有从分布。于是有随机数产生公式： (2.8)结合公式(2.7)和公式(2.8)可得如下结论：1、混沌映射法产生的序列的最大游程的长度只能是2 ,也就是说混纯序列只有两种游程，即游程为1和游程为2；2、混沌序列不可能产生“0011”或“1100”序列。证明如下：结论1证明，要使随机数序列输出“0”序列，那么,即，设这个值为。假设要使序列输出“000”序列，那么必须都小于，由公式(2.1)2的第一个公式可知：由于、都小于0.5，则，因为，所以必定大于0.5， 结论与假设相矛盾。所以混沌算法不可能产生三个或大于三个的连续“0”序列。同理，也可以证明其不可能产生三个或大于三个的连续“1”序

30、列。因此混沌算法产生的随机数的最大游程为2。结论2证明，假设序列存在子序列“0011”或“1100”。当序列“0011”存在时，设，。由代入公式及，得，再把代入公式(2.1)2中的第一个公式，得代入公式(2.1)2中的第一个公式，得。因为，所以把代入公式(2.1)2中的第二个公式，得，通过计算得到，所以由上面的证明得到：不可能大于，与上面的假设相矛，所以用混沌算法产生的随机数不可能出现序列“0011”。同理，也可以证明混沌算法产生的随机数不可能出现序列“1100”。从上面两个结论可以得出：用混沌算法产生的随机数序列中，序列“1”和序列“0” 的出现概率几乎是相等的，出现序列“00”和“11”的

31、概率比序列“01”、“10”低的多，而且从结论2可以看到，因为不可能出现序列“0011”和“1100”，所以出现序列“01”和“10”的概率应该是相等的。2.3均匀分布的随机数的测试检验标准用数学公式产生的随机数都属于伪随机数，在应用之前，必须通过一系列测试检验。测试检验指标包括FIPS140测试和一些统计检验。FIPS140测试包括频数检验、跟随特性检验、游程检验、长游积检验和Poker检验。统计检验包括理论检验和经验检验，理论检验只要给定参数就司进行检验小必实际产生具体的序列，谱检验属于理论检验;而参数检验、均匀性检验、独立性检验、都属于经验列，谱检验属于理论检验:而参数检验、均匀性检验、

32、独立性检验、都属于经验检验9。对应用于加密模块的随机数，美国标准与技术国家研究所(National Institute of Standards and Technology)提出了联邦信息处理标准FIPS140测试标准10。如果随机数通过FIPS140测试， 那么该随机数算法或随机数产生器可以应用于密码学范畴的安全领域。FIPS140测试标准主要由以下五个方而组成：1、频数检验，该检验的日的是测试比特串中“1”序列和“0”序列的个数是否人致相等。一般而言，在一个20,000位的连续比特流中，如果“1”序列的个数在（9654，10346）之间，那么该随机数序列通过频数检验。2、跟随特性检验，跟

33、随特性是检验序列中相邻元素的出现情况，该检验的日的是为了检验序列中序列“00” 、“01” 、“10” 、“11”的出现概率是否大致相等。假如序列“1000101111” ，那么出现序列“00”的个数为2，序列“11”的个数为3，序列“10”的个数为2，序列“10”的个数为2。3、游程检验，游程是指待测序列中连续符号形成的自序列，游程长度是指连续符号的个数。游程检验的目的是统计长度为1的游程（即单个“0”序列和单个“1”序列）约占总游程的1/2，长度为2的游程（即“00”序列和“11”序列)约占1/4，长度为的 游程约占等。4、长游程检验，在20,000个连续的比特流中，假如连续“0”序列和连

34、续“1”序列的游程长度都小于34，那么通过此项检验。5、Poker（扑克）检验，将20,000位随机数按4位组分成5,000组，每组共有16种可能。计算 5,000组中每种可能性的数量，计算公式如下： (2.9)式中，是数出现的个数。当时，通过Poker检验。FIPS140所提出的随机数测试标准是一个在信息安全领域厂为接受的标准，在本质上与其他统计检验方法是一样的，只是各自的角度不一样，因而各自的计算方法也不一样下面简单地叙述下的四种统计检验即参数检验、均匀性检验、相关性检验和频谱检验。2.3.1参数检验参数检验是检验随机序列的均值（或称数学期望）和方差与理论值是否一致。假如随机数在区间上服从

35、均匀分布，那么在理论上，此随机数的均值为，方差为。序列均值和方差的计算公式如下： (2.10) (2.11)均值和方差的统计量的计算公式如下： (2.12) (2.13)对参数进行区间估计，所谓区问估计是指在总体的分布中含有未知参数和是构成样本的两个统计量，对于给定的正数，都有这样的概率： (2.14)当公式(2.14)成立时，称区间为参数的置信区间，公式(2.12)和公式(2.13)可用如下公式表示： (2.15) (2.16)其中为置信度，为显著性水平，知是根据查概率论与数理统计正态分布表所得。当随机数的均值和方差满足公式(2.15)和公式(2.16)时，随机数通过参数检验，否则就没通过参

36、数检验。2.3.2均匀性检验假如序列在区间上服从均匀分布，均匀性检验是指产生的随机数序列是否均匀地出现在区间上，也就是检验经验频率与理论频率是否一致。在理论上，如果随机序列在区间上服从均匀分布，把区间均匀地分成等份，任取个随机数，那么在任何子区间中随机数的个数应等于。它的检验方法有检验，检验以及序列检验等11。本论文中采用了检验，检验过程如下：1、 把区间均匀地分成等份，然后统计落在区间上的随机数个数。2、 根据每个区间的随机数个数，计算统计量，计算公式如下： (2.17)式中，渐进服从分布。3、 给定显著性水平，查表得到的值为，如果，那么认为随机数在区间上服从均匀分布，通过均匀性检验，否则随

37、机数通不过检验。2.3.3独立性检验（相关性检验）独立性检验是检验序列各个随机数之问的相关性和序列任何两个子序列之问的相关性。一般采用顺序相关法来判断序列的相关程度，所谓顺序相关法是通过计算随机数序列的相关系数来判定随机数序列的相关性。相关系数是检验两个变量之间线性相关程度的一个重要数字特征，它的 取值在-1和1之间。如果越接近1，那么表明相关程度越高；如果越接近0， 表明相关程度越弱：如果，则表明这两个变量不相关。在算法论证中，通常用相关系数来检验随机数的相关性，其检验过程如下：假设随机数序列为，、分别表示随机数的均值和方差，则序列的相关系数的计算公式如下： (2.18)2.3.4频谱检验频

38、潜检验方法在综合检验和评价随机数序列的质量方而有其独特的优点，其网格稀疏程度可直接反映序列的均匀性好坏。所谓频谱检验主要是计算基于相邻平行超平面间的最大距离，这个距离越大，表明序列的性能越差。假如一个随机序列，相继个随机数看作维空间上的一个点的坐标时，随机序列由此组成的点分布在维空间的平面上，这些平面的间距的计算公式如所示： (2.19)式中，表示线性同余法的模，称该发生器的维精度上，称为超平而间的最大趾离。在本论文中，采用二维空间频谱图，假如随机数序列在区间服从均匀分布，建立一个二维坐标，分别用和表示轴和轴。随机数序列的个随机数构成个坐标，即，然后在二维空间上找出这个坐标，并观察个点的分布情

39、况，以此来判断随机数网格的稀疏程度。对于均匀分布的随机数序列，主要做FIPS140测试、参数检验、均匀性检验、相关性检验和频谱检验，其中FIPS140中的频数检验是最基本的检验，如果一个随机数序列通小过频数检验，那么就没必要做其他检验，因为频数检验通不过，其他检验肯定不会通过。对于其他分布的随机数，只做参数检验、分布特性检验、相关性检验和频谱检验。3正态分布随机数的生成 3.1正态分布随机数的简述均匀分布的随机数是产生其他分布的随机数的“基准”，而目均匀分布的随机数的性能好坏直接影响到所产生的其他分布的随机数。对十其他分布的随机数，如正态分布、指数分布、伽马分布等，都可以通过反函数法、变换法等

40、方法来实现12。下面具体介绍一下正态分布的随机数的数学模型以及实现算法等。3.2正态分布随机数的生成算法3.2.1数学模型设连续型随机变量的高斯分布的概率密度为 (3.1)其中为常数，则称服从参数为的正态分布或高斯（Gauss）分布，记为。均值和方差的计算见公式3.2和公式3.3所示，可得到正态分布随机变量的均值和方差。 (3.2) (3.3)3.2.2正态分布和标准正态分布的特征一，正态分布正态分布的主要特性有：1、 完全由均值和标准差衡量，表示为2、 偏度=0 ，意味着正态分布关于均值对称，即，并且均值=中位数=众数3、 峰度3 ，峰度衡量分布的扁平程度，如峰度3 ，则意味着高峰分布4、

41、正态分布随机变量的线性组合也是正态分布5、 高于和低于均值的结果的概率变得越来越小，但永远不为0（瘦尾但无限扩展）。6、 置信区间(Confidence Interval)可以通过假设离均值的某几个标准差的距来设定正态分布置信区间，正态分布置信区间如图3.1所示。图3.1 正态分布置信区间正态分布置信区间内：(1) 大约50%观测值落在区间 内。(2) 大约68%观测值落在区间内。(3) 大约90%观测值落在区间内。(4) 大约95%观测值落在区间内。(5) 大约99 %观测值落在区间内。二，标准正态分布标准正态分布是指一种被标准化了的正态分布，其均值为0，标准差为1。即。z 值表示给定观察值

42、远离总体均值的标准差数。标准化指的是将随机变量的观察值转化为z 值的过程。下面的公式用于标准化一个随机变量：(3.4)标准正态分布的计算： (3.5)推导过程为：从正态分布中抽样：定义中心极限定理(The Central Limit Theorem)简单随机抽样(Sample Random Sampling)，是指使得总体中的每一个个体被选择出的概率是相同的抽样方法。样本误差(Sampling Error)：样本的统计量（样本的均值、方差或者标准差）与相应的总体的统计量之间的差异。Sample error of the mean = sample meanpopulation mean13 需

43、要注意的是：样本的统计量本身就是一个随机变量，因此具有一个概率分布。样本统计量的抽样分布通过一系列从总体当中抽取出来的等规模样本计算出来的。中心极限定理：对均值为及有限方差的总体，所有可能的大小为n（n足够大时）的样本的样本均值的抽样分布近似服从均值为方差为的正态分布。中心极限定理（central limit theorem , CLT）的存在，使得正态分布非常重要。该定理声明n 个独立同分布变量的均值当观测数n 增加时收敛为一个正态分布14。这是非常强的结论，对于任意分布均成立，但是对独立假设的依赖性非常强。定义为均值，其中每一个变量都有相同的均值及有限方差，我们有中心极限定理的重要性：正态

44、分布相对容易应用到假设检验及置信区间的构建中。无论总体的分布如何，只要样本规模充分大，样本均值可以用来推断总体均值。中心极限定理的特征：1、如果样本的规模足够大，那么样本均值的抽样分布将近似于正态分布。2、总体的均值和所有可能的样本均值的所构成的分布的均值是相等的。3、样本均值分布的方差等于总体方差除以样本规模。样本均值的标准误差是样本均值的分布所构成的分布的标准差当总体的标准差己知，那么样本均值的标准误差等于：实际上，总体的标准差是很难知道的，通常样本均值的的标准误差通过样本均值的标准差除以来近似求出：这里，：样本均值的标准误差 ：样本标准差 n：样本规模 3.2.3实现原理实现正态分布的随

45、机数有多种方法，但每种方法都需要多个相互独立的均匀分布的随机数。现在，介绍一下实现正态分布的随机数的两种最常用的方法，即中心极限定理法和Box-Muller变换法15。 1、 中心极限定理实现正态分布的随机数设随机变量相互独立，服从同一分布，且一具有相同的均值和方差：，则随机变量的分布函数对于任意都满足（3.6）即当趋向于无穷大时，随机变量近似的服从标准正态分布16。在实际应用中，当大于等于30时，可以把当作服从均值为，方差为的正态分布，那么变量近似服从标准正态分布。其实现框图如图3.2所示，图中表示相互独立的均匀分布的随机数序列。图3.2中心极限定理实现正态分布的随机数发生器的结构框图2、

46、改进型中心极限定理实现正态分布的随机数改进型中心极限定理的实现原理跟传统的中心极限定理一样，只不过它对输入的个相互独立的均匀分布的随机数序列做了一下预处理，以减少输入的随机数序列和加法器的目，同时产生的高质量的正态分布的随机数序列17。设计中引入了概率密度转换器( PDC,Probability Density Converter )，在随机数序列累加之前，对随机数序列做概率密度转换，然后再对转换后的序列进行累加，最终得到正态分布的随机数序列，其实现框图如图3.3所示，图中表示相互独立的均匀分布的随机数序列，表示相互独立的随机位。图3.3 改进型中心极限定理实现正态分布的随机数发生器的结构框图

47、 图3.3的概率转换器主要是用来减少加法器的数目， 其实现原理如图3.4所示。图3.4 概率转换器的结构框图图3.4中，表示随机位，用来控制随机数序列是保持不变，还是右移一位。表示一个均匀分布的随机数序列的随机位（0或1），表示转换后的随机数序列。实际上，概率转换器是一个受控的移位寄存器，当信号=0时，移位寄存器向右一位：当信号=1时，移位寄存器保持小变。3、 Box-Muller变换实现正态分布的随机数变换法是通过一个变换将一个分布的随机数变换成一个不同分布的随机数。高斯分布的密度函数见公式3.1所示，通过Box-Muller变换，它可以产生精确的正态分布的随机变量。其变换式如下： (3.7

48、) (3.8)式中是在在区问0，1上服从均匀分布，且相互独立的随机变量，所以得到的随机变量也应该是相互独立的，且服从的标准正态分布。Box-Muller变换的推导过程如下：由公式3.6和公式3.7可得： (3.9)因为在区间上是一一对应的，令，对求雅可比式，得：(3.10)由等式, 且己知变量u，v在区 间0，1上服从均匀分布且 互相独立，可得变量u，v的概率分布如公式3.10所示：(3.11)由公式3.9和公式3.10，以及变量相互独立，可得：(3.12)(3.13)从公式3.11和公式3.12可知，变量在区间服从标准正态分布，即。从上面三种方法可以看出，虽然用中心极限定理法来生成正态分布的

49、随机数序列需要多个相互独立的均匀分布的随机数序列，但其硬件实现原理比较简单，只需几个加法器即可，而且其性能并不比Box-Muller变换法差，仿真分析结果见第五章所示。而Box-Muller变换法虽然用软件方法很容易实现，但要用硬件方式来实现就比较困难，因为在Verilog语言中没有对和 , 的操作。如果硬要用Box-Muller变换法来实现的话，就要引入SRAM（静态存储器），事先把和，的值存入SRAM，在访问的时候，电路将值x转换成二进制，访问SRAM，读出的值。这样的话，硬件实现就相当麻烦，而且而积、功耗、延时都会有所增大。4指数分布随机数的生成 4.1指数分布随机数的简述指数分布具有如

50、下形式的概率密度函数（pdf）：(4.1)以及累积分布函数（cdf）：(4.2)参数可以理解为单位时间内发生的平均数。例如，如果到达间隔时间服从速度为的指数分布，则可以理解成单位时间内的平均到达数，或到达速度。注意，对于任意有(4.3)因此，是平均到达间隔时间18。这里，目的是开发一个程序用来生成具有指数分布的的值。4.2指数分布随机数的生成算法4.2.1数学模型 设连续型随机变量X的指数分布的概率密度为(4.4)当x<0时，。式中，为衰减指数。由公式3.2和公式3.3可知，服从指数分布的连续变量X的均值和方差。4.2.2生成方法 1、反变换法设是一个具有连续分布函数的随机变量，则在0，

51、1上有均匀分布。设概率分布函数是严格单调增的，的反函数记作。先产生，再取即为所求，称为反变换法。指数分布能够方便地用反变换法产生。由的分布函数，可得 (4.5)2、卷积法如果随机变量是个独立、同分布的另一随机变量之和，而又容易产生时，先产生个独立的，再令即可。因为的分布函数是分布函数的卷积，故称为卷积法。二项分布可以用卷积法产生。因为是个独立的之和，而很容易由按以下方法得到：若，令；否则令。3、取舍法若随机变量在有限区间内变化，但概率密度具有任意形式（甚至没有解析表达式），无法用前面的方法产生时，可用取舍法。一种比较简单的取舍法的步骤是：(1) 产生和；(2) 记，若，则取；否则，舍去，返回(

52、1)。4.2.3实现原理 对于指数分布的随机数，通常用反函数法来实现，反函数法是产生任意分布的随机数的最常用的方法之一19。其原理是：已知在区间0,1上均匀分布的随机数，将所需概率分布的随机数的分布函数进行反变换，得其反函数，就是概率分布函数为的伪随机数。由公式4.2可知，是单调下降函数，而且其区间在0和1之间，因此其反函数也必定是单调函数，求其反函数如下：(4.6)当是在区间0,1)上均匀分布的随机数时，那么产生的随机数序列为服从 指数分布的随机数，其均值为，方差为。对于公式4.6，用软件方法很容易实现指数分布的随机数发生器，但是如果要用硬件来实现，那就有一定的难度，因为Verilog语言中

53、没有直接对对数函数的操作运算。可以通过SRAM（静态存储器）查表法或展开对数函数来产生指数分布的随机数发生器。对于SRAM查表法，要事先把对数函数的值存入SRAM中，在访问的时候，电路将值x转换成二进制，访问SRAM，读出的值。对于用麦克劳林展开对数函数法，它把对数函数转换成一系列乘、除、加运算，这样Verilog就比较容易实现。本论文采用展开对数函数来实现指数分布的随机数发生器。对数函数的麦克劳林展开式如下式所示：(4.7)所以公式4.6的展开式为： (4.8)这样对数函数只有乘、加以及除操作，可以用Verilog语言来实现其硬件结构，其框图如图4.1和图4.2所示。框图中一次方电路表示对宽

54、为n的随机数的作一次方运算，两次方电路表示对宽为n的随机数的二次方运算，以此类推。一次除电路表示除法电路的输入值除以线性同余发生器的模，即把一次除电路的输入值右移n位；两次除电路表示除法电路的输入值除以线性同余发生器模的二次方，即把二次除电路的输入值右移2n位，以此类推。除2电路、除3电路、除m电路表示除以公式4.7中的系数2，3，m。除电路包括除衰减指数2（当衰减指数不是2中，可以放入除m电路中），表示产生一个宽为5的随机数序列。其设计原理如下：1，用线性同余法产生一个宽为n的随机数，设为：2，对这个随机数作m+l次方，然后把结果向右移m* n位，同时再除以m，得到；3，把和相加的值再右移n-4位，得到一个宽为5的随机数。整个电路受时钟边沿控制，每个时钟周期输出个宽为5的随机数。图4.1 指数分布的随机数发生器的结构框图图4.2 改进型指数分布的随机数发生器的结构框图4.3网络传输中的泊松流和指数分布网络传输中的事件流包括数据包到达流和响应时间流。由于数据包到达的间隔时间和响应时间不