双层交叉细胞自动机的伪随机数发生方法.pdf

维普资讯 小 型 微 型 计 算 机 系 统 2008年 9月 第 9期 Vo1．29 No．9 2008 JournalofChineseComputerSystems 双层交叉细胞 自动机的伪随机数发生方法 夏学文 ，李元香。，戴志锋。 (武汉大学 计算机学院，湖北 武汉 430079) (武汉大学 软件工程国家重点实验室，湖北 武汉 430072) (湖北经济学院计算机科学与技术学院，湖北 武汉 430205) E—mail：laughkid@163．corn 摘 要 ：提 出一种基于两层交叉细胞 自动机 (twi—layercrosscellularautoma，TICCA)结构的伪随机发生器 (pseudorandom numbersgenerator，PRNG)．TICCA的复杂性介于一维细胞 自动机与二维细胞 自动机之间，而且输 出方式简单 ；细胞 间采用 了一种新的对称交叉式的邻居关系，该结构一方面保证 了对称性，另一方面减少 了相邻细胞 问的相关性．并利用多 目标遗传算 法对邻居关系结构进行 了优化 ，最终的实验结果表 明该结构的PRNG可以高效地生成高质量的伪随机数 ，而且易于用硬件实 现 ． 关键 词：两层交叉细胞 自动机；伪随机数发生器；遗传算法；多 目标优化 中图分类号：TP273．4 文献标识码 ：A 文 章 编 号 ：1000—1220(2008)09—1579—05 ApplicationofTwi-layerCrossCellularAutomatain Pseudorandom NumbersGenerator XIA Xue—wen ，LIYuan—xiang。。DAIZhi—feng。 (SchoolofComputer，WuhanUniversity，Wuhan430079，China) 0(StateKeyLaboratoryofSoftwareEngineering．WuhanUniversity，Wuhan430072，China) 。(Schoolo厂ComputerScienceandTechnology，HubeiUniversityofEconomics，Wuhan430205，China) Abstract：A pseudorandom numbersgenerator(PRNG)basingonanovelstructureisproposedwhichiscalledtwi—layercross cellularautomata (TLCCA)．TICCA iscomposedoftwolayers，andeachlayerisa1-CA．SothecomplexityofTLCCA is moresimplethan2-dimension，andthemethodofnumber’sexportisverysimplewhich improvestheefficiencyofPRNG．A new neighborhoodwhichiscalledsymmetriccrossneighborhoodhasbeenselectedinTLCCA．Theneighborhoodreducesthe correlationbetweenconterminouscellsaswellasguaranteesthesymmetry．Andtheneighborhoodisoptimizedbymulti—objec— tivegeneticalgorithm (MOGA)．TheresultsofexperimentsindicatethatthePRNG basedonTLCCA ，whichispronetobe implementedonhardware·cangeneratehighqualitypseudorandom numbers． Keywords：twi—layercrosscellularautomata；pseudorandom numbersgenerator；geneticalgorith