基于卡诺图初等元胞自动机的演化规则.pdfVIP

维普资讯 第 25卷 第 1期 广西师范大学学报：自然科学版 Vo1．25 No．1 2007年 3月 JournalofGuangxiNormalUniversity：NaturalScienceEdition M ar．2007 基于卡诺图初等元胞 自动机的演化规则 朱留华 ，陈时东 ，孔令江 ，刘慕仁 (1．广西师范大学 物理与 电子工程学院，广西 桂林 541004；2．玉林师范学院物理与信息科学系，广西 玉林 537000) 摘 要：依据初等元胞 自动机演化规则的特点，借助卡诺图化简，导出初等元胞 自动机演化规则的函数形式。 进一步利用推导出的演化规则的函数形式，给出演化规则90和演化规则 184的演化定理及相关定理的证明。 关键词 ：初等元胞 自动机；卡诺图；演化定理 中图分类号 ：055O 文献标识码：A 文章编号 ：1001—6600(2007)01—0005—04 元胞 自动机 (CellularAutomaton，简称CA)起源于2O世纪40年代 。“现代计算机之父”VonNeumann 设计可 自我复制的自动机时，参照了生物现象中的自繁殖原理，提出了元胞 自动机 的概念和模型。它是一 时间和空间都离散的动力系统，散布在规则网格 中的每一元胞取有限的离散状态，遵循 同样的作用规则， 依据确定的局部规则作同步更新，大量元胞通过简单的相互作用而构成动态系统的演化 。 1 初等元胞 自动机概况 初等元胞 自动机是指每个元胞的状态 只取 2种 ，且邻域半径为 1，局部映射规则为 ： (￡+1)一F(H (￡)； (￡)；… (￡))。即每个元胞下一时刻的状态完全由该元胞及相邻的两个元胞(共 3个元胞)的当前状 态所决定。由于每个元胞只取 0、1两个状态值，因而 3个元胞的状态可为：(1l1)、(110)、(101)、(1OO)、 (011)、(010)、(001)、(ooo)共 8种排列。这样的排列到 {0，1}的每一组映射就确定了一个局部规则F，从而 也确定了一个初等元胞 自动机规则，所以初等元胞 自动机演化规则共有 2。一256种。为了讨论方便，一般 将规则中的上述 8种排列的映射值分别排在一个二进制数的O～7位，将此二进制数所对应的十进制数作 为初等元胞 自动机的规则代码 ，如表 1。 表 1 规则 76的映象表 表 2 32种合法规则的映象表 2 规则的函数形式及相关性质 在初等元胞 自动机 256种演化规则中有一类规则 比较类似于物理要求，它们具有如下特点：描述演化 规则的八位二进制数的最后一位要求是 0；演化规则中对称映射部分的元胞演化要一致。这类规则共有32 种 (见表 2)，Wolfram称它们为合法规则Eli。 为了获取演化规则的特点及性质，最好是能明确给出这些演化规则的函数形式。综观研究初等元胞 自 动机的相关文献nq]，我们发现在给出这些演化规则的函数形式时，作者往往是通过归纳与总结，不能兼 顾通用性与简洁性 。本文通过引入数字电路中常见的卡诺图_4]，对初等元胞 自动机的演化规则进行研究， 收稿 日期 ：2006—09—27 基金项 目：国家 自然科学基金资助项 目10562001 作者简介 ：朱留华(1974一)，男，江苏盐城人 ，广西师范大学硕士研究生 。 通讯作者 ：刘慕仁(1963一)，男，广西桂林人 ，广西师范大学教授 。 维普资讯 广西师范大学学报：自然科学版 第 25卷 从而避免了上述缺陷，使两者同时得以兼顾 。 2．1 演化规则 90的函数形式 首先，列出规则 90的真值表，见表 3。其次，根据真值表画出卡诺图，如图1。最后，化简结果如式(1)：