线性细胞自动机的可逆性分析.pdfVIP

摘要 摘要 细胞自动机(Celiu]arAutomata)是离散的和确定性的动态系统，它们尤其 适合用于建模与仿真，可以被描述为简单的对象彼此局部相互作用的庞大集合 的自然系统。近几年来，细胞自动机已经广泛应用在科学的各个分支，如物理 学(生长过程模型)、生物学(自我繁殖模型、生物结构等)、信息科学(图像 处理、纠错码、密码学等)。 在一维细胞自动机方面，目前在零边界、反射边界和周期边界条件下，一 维线性细胞自动机的可逆性已经取得了一些成果，但是许多已有研究工作都是 针对特定的某些线性规则，难以做到判定任意线性规则的可逆性。本文创新性 地引入De Bruijn图这一强大工具，可以在零边界条件下快速确定任意一维线性 细胞自动机的可逆性，并且可以推广到有限状态域t上。 在二维细胞自动机方面，Karl等人证明了二维或高维细胞自动机在全局的 可逆性是不可判定问题。本文探究了零边界条件下二维线性细胞自动机的可逆 性，通过实验给出了整体可逆的二维线性CA和整体不可逆的二维线性CA所 需要满足的条件。同时对于非上述两种情况的二维线性CA的可逆性给出了一 些结论。 细胞自动机的可逆性因对图像加密等问题具有重要意义，而成为近年来研 究的热点问题。本文在二维细胞自动机的可逆性方面给出的结论可以应用在图 像加密领域上，并且我们发现该加密方法能够得到较好的加密效果。 关键词：细胞自动机；可逆性；状态转移矩阵；线性规则；De Bruijn图 万方数据 Abstract ———————————————————————————————————————————————一 Abstract CellularAutomata arediscreteand deterministic are dynamical systems．Thev suitablefor especially natural thatcanbe modelingsystems describedasmassive collectionsof with simpleobjects eachother．In interactinglocally recentvears．a wide of ofCA variety hasbeen applications forwardinseveral put branchesof sciencesuchas of Physics(modeling growth for self-reprodu