细胞自动机的特点及应用领域研究

２０１４年第ｌＯ期　（总第１４２期）　信息通信　ＩＮＦＯＲⅣ【ＡＴＩＯＮ＆Ｃ０ＭＭ［Ｉ　ＮＩＣＡＴＩＯＮＳ　２０１４　（Ｓｕｍ．Ｎｏ　１４２）　细胞自动机的特点及应用领域研究　曾志峰　（湖南人文科技学院，湖南娄底４１７０００）　摘要：细胞自动机是定义在一个具有离散、有限状态的细胞组成的细胞空间上，并按照一定演化规则，在离散的时间上演　化的动力学系统，具有自己明显的特点，它在数字图像压缩、数据加密领域、计算数学、空间复杂性以及交通系统等领域　应用前景广阔。　关键词：细胞自动机；特点；应用领域　中图分类号：ＴＰ３０９　文献标识码：Ａ　文章编号：１６７３．１１３１（２０１４）１０．０１５９—０１　细胞自动机（ＣｅｌｌｕｌａｒＡｕｔｏｍａｔａ），简称ＣＡ。细胞自动机是　一种特殊的有限状态机，是与连续Ｃａｎｔｏｒ映射动力学系统相　对应的离散动力学系统，具有时间、空间和状态的离散性Ⅲ。它　是由细胞、细胞空间、邻居及演化规则组成的。早期细胞自动　机的发展应归功于Ｖ．Ｎｅｕｍａｎｎ，但其思想起源于ｓ．Ｕｌａｍ【２】。随　着细胞自动理论研究的发展的同时，也促进了其应用的发展。　ｌ细胞自动机的特点　细胞自动机具有三个比较明显的特点，即基本单元的简　单性、大规模并行性以及细胞单元交互作用的局部性，这三个　特点相辅相成，由于有简单性和局部性的存在，大规模并行性　才会有可能，这三种特点任何一个得意改变，都会使得细胞计　算的含义发生改变。　１．１基本单元的简单性（ｓｉｍｐｌｉｃｉｔｙ　ｏｆｂａｓｉｅ　ｃｏｍｐｏｎｅｎｔｓ）　组成细胞自动机的基本处理单元细胞的结构十分简单。　目前传统的处理器，如ＣＰＵ、ＤＳＰ等都具有强大的处理功能，　能较好的处理各种繁杂的任务。相比之下，细胞自动机每个　细胞所具备的功能就相对来说要简单很多，规则的简单却丝　毫不影响它的计算能力。当使小自动机的单个细胞的规则等　同于图灵机的时候，细胞自动机相当于并行计算。　１．２大规模并行性（ｍａｓｓｉｖｅ　ｐａｒａｌｌｅｌｉｓｍ）　目前，较多的并行机往往包括几十个甚至上百个的处理　器，ＭＰＰ（Ｍａｓｓｉｖｅｌｙ　Ｐａｒａｌｌｅｌｉｓｍ　Ｐｒｏｃｅｓｓ）则包含几千个处理单　元，处理器的个数达到上万的数量。相对于细胞计算（Ｃｅｌｌｕｌｒａ　Ｃｏｍｐｕｔｉｎｇ）来说，这样的规模可以说是较小的，因为细胞处理　器的单元数量是能够达到百万个以上的。细胞自动机的巨大　的处理单元数量是可以较大幅度地提升系统的整体性能的。　１．３细胞单元交互作用的局部性（１ｏｃａｌｉｔｙｏｆｃｅｌｌｕｌａｒｉｎｔｅｒａｃｔｉｏｎｓ）　细胞自动机的各个细胞之间是局部互联的，全部细胞会　根据其局部所处的环境进行操作，每个细胞处理单元并不是　和其它所有的细胞处理单元进行通信，它们进行通信的是与　其相互关联的几个细胞处理单元，局部性特征明显。尽管细　胞自动机当中没有一个细胞具有全局视点，但是在整体上，细　胞计算却产生了“突现”（ｅｍｅｒｇｅｎｃｅ），能进行很好的全局计算。　２细胞自动机的应用　随着细胞自动机研究理论的不断发展，细胞自动机模型在　各个领域得到应用与发展，目前，其在数字图像压缩、数据加密领　域、计算数学、空间复杂性以及交通系统等领域应用前景广阔。　２．１数字图像压缩领域　图像处理过程当中的数据量是非常之大的，因此，处理系　统中的算法的运算速度问题一直被关注，如果算法运算速度过　慢，则无法达到图像处理的要求，目前，使用的串行图像处理算　法速度己经无法满足图像处理的更高要求，因此，寻找运算速　度更快的算法成为了图像处理者们的重点研究方向，研究者把　目光转移到了细胞自动机的应用上。由于细胞自动机能产生　数以亿个基函数，其中总是可以找到一个细胞自动变换基，这　个基下细胞自动机变换能尽量地减少非零系数，用细胞自动机　来处理图像后，数据具有很高的保真度，并且还能对图像进行　对称与不对称的压缩。在数字图像压缩领域的研究应用成果　表明，细胞自动机在图像处理当中前景广阔。　２．２数据加密领域　细胞自动机的变换基对数据进行编码的过程中是毫无错　误的，这种特性使得它能应用于数据加密领域，并被认为是密　码技术自主化方面最有希望的核心技术之一。数据加密的密　匙可以由产生细胞自动机的变换基的所有关键值组成。通过　细胞自动机所进行的数据的传输和存储后，如果需要解密，则　需要当时使用加密时所用的全部关键值才能得以破译。　２－３计算数学领域　细胞自动机的交换基具有正交性和强大的数据变换能力，　具有鲁棒性和可逆性的性质，目前，在积分方程当中将被广泛　地应用。　２．４空间复杂性领域　一直以来，地理学理论研究和应用都较为缓慢，其中主要　的原因之一就是缺乏数学工具和有效的试验手段。近年来，　细胞自动机被西方地理学界应用于地理学科来解决空间复杂　性的研究，通过细胞自动机这一工具进行地理系统形成、演化　的模拟，从而获得全新的思维方式。　２．５交通系统领域　现在人们利用细胞自动机空间、时间以及状态的离散的　特性能使得它在计算机中模拟各中复杂现象，而且模型规则　简单且计算熟读快，于是便产生应用于交通系统领域的研究。　尽管细胞自动机引入交通系统在目前还是理论阶段的研究，　在研究的过程当中根据实际情况不断改进规则、标定参数，其　实际应用也是指日可待的。　３结语　由于细胞自动具有结构简单且强大的并行计算能力，在　复杂系统的研究当中扮演着越来越重要的作用，在目前的实　际应用当中尽管还存在许多的局限性，但它展现出的美好前　景是值得期待的。　参考文献：　［１］Ｓ．Ｗｏｌｆｒａｍ．Ｕｎｉｖｅｒｓｉｔｙ　ａｎｄ　Ｃｏｍｐｌｅｘｉｙｔ　ｉｎ　Ｃｅｌ￣ｌｒａ　Ａｕｔｏｍａ－　ｅｒ［Ｊ］．Ｐｈｙｓｉｃａ　Ｄ，１９８４，１０（１）：１－３５　【２】Ａ．Ｗ．Ｂｕｒｋｓ（ｅｄｉｔｏｒ）．Ｅｓｓａｙ　ｏｎ　Ｃｅｌｌｕｌａｒ　Ａｕｔｏｍａｔａ［Ｍ］．Ｕｒｂａｎａ，　ＩＬ：Ｕｎｉｖｅｒｓｉｙｔ　ｏｆ　Ｉｌｌｉｎｏｉｓ，１　９７０　基金项目：湖南人文科技学院校级青年基金项目（２０１１ＱＮ１５）　作者简介：曾志峰（１９７６．），男，湖南双峰人，硕士，讲师。　１５９