博客网 >

元胞自动机基础
作者:分类:默认分类标签:
    元胞自动机(cellular automaton, CA)是最近一个比较热门的研究课题,其是物理、数学、计算机和生物等学科的交叉产物。在计算机领域中,CA在人工智能、计算复杂性分析以及加密等多个领域中有着较大的用途。特别是在大约十年前,密码学家H. Gutowitz根据CA的基本原理,提出了分块加密算法CA-1.1,使得CA在密码学中真正的迈出了第一步,也使得越来越多的密码学家开始了对CA的研究。最近,我也开始对这个方面产生了浓厚的兴趣,并开始了一些学习,就先来简单的说说什么是CA吧!
    简单的说,元胞自动机是一个空间、时间和状态上都离散的动态系统。构成CA的基本单位成为元胞(cellular),规则的分布在元胞空间(spatial lattice)的格点上,且各自的状态随着时间按照一定的局部规则变化。也就是说,元胞的状态只能从一个有限的状态集中取值,每个时刻元胞的状态仅与其自身和邻居在上一时刻的状态有关,并且,所有的元胞在每个时刻均是同时更新的。
    以上即是对CA的一个定性的描述,下面给出一个基于集合论的定量描述(L. Hurd等):
    设d为CA空间的维数,k代表元胞的状态,集合S表示CA的整体状态,r表示元胞的邻居半径。为了简单起见,我们在d=1,即一维空间上对CA进行讨论。CA的动态性可以由一个全局函数F: St→St+1决定,并且,每个元胞的状态可以由一个局部函数f:kt→kt+1决定。
    由于多维空间的CA具有很强的复杂性,故目前对CA的研究主要集中在一维和二维空间。就一维空间而言,CA的结构显然只有可能是线性结构。在二维空间,CA的结构可能有三角、四边或多边等构成方式。显然,结构上的差异会对其在计算机表示及其他部分特性上带来一定的差异。而CA的邻居结构也通常包括Von. Neumann、Moore、扩展Moore和Margolus等多种形态,不同的邻居结构带来的特性和复杂度也不尽相同。
    通过分析CA的构成及其基本规则,不难得出标准CA的一些特征:
    1、同质性:CA内的每个元胞的变化都服从相同规则,且分布方式是相同的。
    2、离散性:CA在空间、时间、状态上都是离散分布的,并且其状态分布是有限的。
    3、并行性:CA每个元胞的更新都是同步进行的。
    再来看看基于一维CA加密的一个简单讨论。分析CA的基本机理,不难得出,基于一维CA的加密是一个典型分块密码。不妨假设该一维CA的空间长度为N,则每轮更新均可得到一组长度为N的子密钥,用于对明文“分块”进行加密。如果更新算法设置得当,每次生成的子密钥序列可以做到是尽可能随机的,从而保障了加密的强度。
    目前,已经有了一些基于一维CA的加密算法的实现,最前沿的研究是基于二维CA的。
<< 基本入侵技术 / Vigenere密码的改进 >>

专题推荐

不平凡的水果世界

不平凡的水果世界

平凡的水果世界,平凡中的不平凡。 今朝看水果是水果 ,看水果还是水果 ,看水果已不是水果。这境界,谁人可比?在不平凡的水果世界里,仁者见仁,智者见智。

中国春节的那些习俗

中国春节的那些习俗

正月是农历新年的开始,人们往往将它看作是新的一年年运好坏的兆示期。所以,过年的时候“禁忌”特别多。当然,各个地方的风俗习惯不一样,过年的禁忌也是不一样的。

评论
0/200
表情 验证码:

Romeo

  • 文章总数0
  • 画报总数0
  • 画报点击数0
  • 文章点击数0
个人排行
        博文分类
        日期归档