异步细胞自动机通用并行计算能力研究

发布时间：2017-04-29 12:14

  本文关键词：异步细胞自动机通用并行计算能力研究，由笔耕文化传播整理发布。

【摘要】：细胞自动机是一种离散的模型,能够完成复杂计算和模拟自然界的现象变化。作为细胞自动机的一种,异步细胞自动机在细胞演化时是不需要统一时钟控制的,对其研究要比同步细胞自动机复杂得多。作为对异步细胞自动机计算能力研究的一个重要方式,模拟同步细胞自动机演化是一种很好的方式。细胞自动机的本质通用性使得一个细胞自动机能够模拟另一个细胞自动机。生命游戏是最著名的同步细胞自动机,因其简单的控制规则和展现复杂的特性使得对其研究不断增多,如自我复制,超并行计算能力,以及在仿生学中的重要作用。特别的已经存在Moore相邻条件下的8状态下异步细胞自动机对生命游戏的模拟,但是利用了上百条状态转换规则。如果要模拟一个细胞自动机,那么其状态转换规则的计算是必不可少的,本文利用延时不敏感电路是异步电路的一种,在计算正确性和电路设计上的特性,同时能很好地嵌入到异步细胞自动机中的特性,设计了具备计算生命游戏状态转换规则的延时不敏感电路,可以有规则的在细胞自动机空间中摆放电路模块。然后利用几十条状态转换规则分别在von Neumann相邻条件下的4状态和5状态异步细胞自动机上模拟生命游戏演化。虽然不同状态下模拟的生命游戏细胞配置大小不同,但是其最终模拟结果是一样的。von Neumann相邻条件下4状态异步细胞自动机的计算能力虽然已经被证明出,但是其计算能力是有限的,本文通过在其上模拟生命游戏,为证明其通用计算能力和超并行计算能力提供了一种便捷的方法。通过在4状态和5状态异步细胞自动机中模拟生命游戏演化,为异步细胞自动机通用并行计算能力提供一种通用方法。
【关键词】：异步细胞自动机 延时不敏感电路 生命游戏 通用计算能力 本质通用性
【学位授予单位】：重庆大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP338.6
【目录】：

• 摘要3-4
• Abstract4-7
• 1 绪论7-10
• 1.1 研究背景7
• 1.2 研究现状7-8
• 1.3 研究内容意义8-9
• 1.4 论文结构9-10
• 2 细胞自动机10-17
• 2.1 细胞自动机定义10-12
• 2.2 细胞自动机计算能力12-14
• 2.2.1 细胞自动机的通用计算能力12
• 2.2.2 细胞自动机的本质通用性12-14
• 2.3 生命游戏14-16
• 2.3.1 生命游戏演化模式14-15
• 2.3.2 生命游戏通用计算能力15-16
• 2.4 本章小结16-17
• 3 延时不敏感电路17-26
• 3.1 延时不敏感电路及定义17-23
• 3.2 延时不敏感电路通用计算能力23-25
• 3.3 本章小结25-26
• 4 生命游戏嵌入到5状态异步细胞自动机26-45
• 4.1 延时不敏感电路在5状态ACA下配置26-28
• 4.2 计数器设计及5状态ACA下配置28-34
• 4.3 解析器设计及5状态ACA下配置34-36
• 4.4 DI电路模块构成生命游戏细胞及在4状态ACA下配置36-39
• 4.5 同步器设计及5状态ACA下配置39-41
• 4.6 在5状态ACA中模拟生命游戏简单演化41-43
• 4.7 本章小结43-45
• 5 生命游戏嵌入到4状态异步细胞自动机45-55
• 5.1 延时不敏感电路在4状态ACA下的配置45-47
• 5.2 计数器及其在4状态ACA下配置47-49
• 5.3 解析器及其在4状态ACA下配置49-50
• 5.4 DI电路构成的生命游戏细胞及其在4状态ACA下配置50-52
• 5.5 同步器及其在4状态异步细胞自动机中配置52-53
• 5.6 生命游戏嵌入到4状态ACA中53
• 5.7 本章小结53-55
• 6 总结55-56
• 致谢56-57
• 参考文献57-60
• 附录60
• A.作者在攻读硕士学位期间成果目录60

【相似文献】

中国期刊全文数据库 前10条

1 赵学锋;张全;;一种一维细胞自动机的分类[J];西北师范大学学报(自然科学版);2006年05期

2 王丽琴;陈桂强;;一种基于二维细胞自动机的秘密图像共享方案[J];现代电子技术;2008年03期

3 张永安;细胞自动机及其在经济与管理中的应用[J];科技导报;1998年02期

4 杜宁睿,邓冰;细胞自动机及其在模拟城市时空演化过程中的应用[J];武汉大学学报(工学版);2001年06期

5 赵冬;细胞自动机的可分类性[J];许昌师专学报;2002年02期

6 张传武;彭启琮;朱甫臣;;细胞自动机置换群加密技术研究[J];计算机科学;2003年03期

7 张传武,沈野樵,彭启琮;细胞自动机反向迭代加密技术研究[J];计算机学报;2004年01期

8 张传武;细胞自动机及其理论研究进展[J];贵州大学学报(自然科学版);2004年03期

9 曹兴芹;王能超;;新型细胞自动机规则空间的参数化[J];计算机科学;2007年03期

10 夏学文;李元香;张大斌;;对称耦合式触发细胞自动机在加密中的应用[J];小型微型计算机系统;2009年07期

中国重要会议论文全文数据库 前8条

1 应时彦;裴太乙;肖林荣;;基于三值量子细胞自动机的基本逻辑电路仿真[A];中国自动化学会控制理论专业委员会B卷[C];2011年

2 阮晓钢;董新久;;基于细胞自动机的肿瘤生长仿真模型[A];2001年中国智能自动化会议论文集（下册）[C];2001年

3 沈成武;杨吉新;唐小兵;;细胞自动机方法在复合材料层板弯曲中的应用[A];复合材料的现状与发展——第十一届全国复合材料学术会议论文集[C];2000年

4 刘长海;陈军;凌学书;;三维大型地震细胞自动机的初步工作结果[A];1995年中国地球物理学会第十一届学术年会论文集[C];1995年

5 钱柳羲;林水生;;基于可编程细胞自动机的高斯白噪声发生器的研究与实现[A];2008通信理论与技术新进展——第十三届全国青年通信学术会议论文集（上）[C];2008年

6 阮晓钢;胡日查;;用细胞自动机实现Logistic模型[A];中国生物医学工程学会第六次会员代表大会暨学术会议论文摘要汇编[C];2004年

7 刘娟;蔡自兴;;基于CoDi模型的神经细胞自动机及其在模式分类中的应用[A];第二十届中国控制会议论文集（下）[C];2001年

8 刘妙龙;陈鹏;;基于细胞自动机与多主体系统理论的城市模拟模型框架[A];中国地理信息系统协会第三次代表大会暨第七届年会论文集[C];2003年

中国博士学位论文全文数据库 前4条

1 张传武;细胞自动机在密码学中的应用研究[D];电子科技大学;2003年

2 刁元波;复杂网络理论和细胞自动机在生物信息学中的应用研究[D];四川大学;2007年

3 孙燕楠;扎龙湿地时空格局演变的细胞自动机模型研究[D];大连理工大学;2007年

4 黄小华;温度—水—应力下开挖扰动区裂隙花岗岩体流变过程研究及细胞自动机模拟[D];中国科学院研究生院（武汉岩土力学研究所）;2007年

中国硕士学位论文全文数据库 前10条

1 刘心元;基于支持向量机与细胞自动机的迁移学习研究[D];西安电子科技大学;2014年

2 梁志锋;基于反向建模的细胞自动机水泥水化仿真方法研究[D];济南大学;2015年

3 杜子骏;免疫系统的计算机模型研究[D];扬州大学;2015年

4 周文虎;异步细胞自动机通用并行计算能力研究[D];重庆大学;2015年

5 杨晓利;一种混沌细胞自动机的特性研究[D];东北师范大学;2009年

6 陈琳;若干一维细胞自动机动力学行为的复杂性研究[D];浙江师范大学;2009年

7 曾志峰;基于细胞自动机的协同演化优化方法[D];湖南大学;2010年

8 崔异;细胞自动机研究及应用[D];西南交通大学;2006年

9 朱湘艳;细胞自动机理论在流密码体制中的应用[D];南京理工大学;2008年

10 牛文科;基于细胞自动机的分类算法的研究及应用[D];西安电子科技大学;2009年

  本文关键词：异步细胞自动机通用并行计算能力研究，由笔耕文化传播整理发布。

，

本文编号：334817