（物理学专业论文）细胞自动机矩阵分析与应用.pdf

四川大学博士后研究工作报告 摘要 细胞自动机以其特有的组成单元的简单规则性、单元之间的局部 互连性和表现出的复杂全局状态而使得其在完成电子信息系统的 v l s i 实现即片上系统s o c 实现时不仅可以简化系统的设计，而且具 有速度方面的性能优势。 本项目主要是利用矩阵方法，采用细胞自动机的矩阵方程与特征 多项式来分析其状态转移方程，从而分析细胞自动机的群非群特性 和细胞自动机状态转移的同构性等特性，研究证明了“具有不可约特 征多项式的9 0 1 5 0 加性细胞自动机的状态转移具有同构性”。同时根 据细胞自动机所具有的特性、结合电子信息科学领域的特征来研究细 胞自动机的应用，其中主要包括利用细胞自动机状态转移来产生伪随 机数，将细胞自动机的二叉树型状态转作为h a s h 函数的轮函数，利 用等圈长细胞自动机和反向迭代规则进行信息加密等。最后，从v l s i 实现的角度分析细胞自动机的实现特点，并利用其与移位寄存器的 c p l d 实现来分析细胞自动机的物理实现优势。 关键词：细胞自动机、状态转移矩阵、特征多项式、伪随机数伪随 机序列、h a s h 函数、信息加密。 摘要 a b s t r a c t c e l l u l a ra u t o m a t a ( c a ) h a st h ec h a r a c t e r so fs i m p l i c i t yo fb a s i c c o m p o n e n t s ，l o c a l i t y o fc e l l u l a ra u t o m a t ai n t e r a c t i o n s ，m a s s i v e p a r a l l e l i s mo f i n f o r m a t i o np r o c e s s i n g ，a n de x h i b i t sc o m p l e xg l o b a l p r o p e r t i e s t h ec a c a ns i m p l i f yt h ec o m p l e x i t yo fd e s i g na n dh a sh i g h e r s p e e dp e r f o r m a n c ei nt h ev l s ii m p l e m e n t a t i o no rs y s t e mo nc h i p ( s o c ) i m p l e m e n t a t i o n t h i sp r o j e c t u s i n g t h em a t r i xa n dc h a r a c t e r i s t i cp o l y n o m i a lo f c e l l u l a ra u t o m a t at oa n a l y s i si t ss t a t e st r a n s i t i o n ，t h u sc a na n a l y s i st h e g r o u pp r o p e r t ya n dt h ei s o m o r p h i s mp r o p e r t y f o rt h e9 0 15 0a d d i t i v e c e l l u l a ra u t o m a t aw i t hi r r e d u c i b l ep o l y n o m i a l ，t h e yh a v et h es a m e s t r u c t u r eo fs t a t e st r a n s i t i o n w es t u d i e dm a n yc a s e sa b o u tc e l l u l a r a u t o m a t aa p p l i e di nt h ee l e c t r o n i ci n f o r m a t i o ns c i e n c e ，s u c ha su s i n gt h e s t a t e st r a n s i t i o no ft h ec e l l u l a ra u t o m a t at og e n e r a t et h ep s e u d o - r a n d o m ， u s i n gt h ec e l l u l a ra u t o m a t aw i t ht w op r e d e c e s s o r so fr e a c h a b l es t a t ea s t h er i n gf u n c t i o ni nt h eh a s hf u n c t i o n ，u s i n gt h ec e l l u l a ra u t o m a t aw i t h e q u a lc i r c l e ss t a t e st r a n s i t i o na n d 也ec e l l u l a ra u t o m a t aw i t hi n v e r s e i t e r a t i o nr u l e st oe n c r y p t i o ni n f o r m a t i o n i nt h ee n d ，f r o mt h ev i e w p o i n t s o ft h ev l s ii m p l e m e n t a t i o n ，w ed e m o n s t r a t e dt h ep e r f o r m a n c e s ( s p e e d s a n dc o m p l e x i t y ) a d v a n t a g e so fc e l l u l a ra u t o m a t ab yt h ec o n t r a s to f s h i f t - r e g i s t e ri nt h ec p l di m p l e m e n t a t i o n k e y w o r d s ：c e l l u l a ra u t o m a t a m a 缸i xo f s t a t e s t r a n s i t i o n , c h a r a c t e r i s i t ep o l y n o m i a l ，p s e u d o r a n d o ms e q u e n c e ，h a s hf u n c t i o n , a n d i n f o r m a t i o ne n c r y p t i o n 四川大学博士后研究工作报告 1 1 研究背景 1 1 1 电子信息系统设计要求 随着社会的进步和电子信息科学技术的发展，对电子信息系统的要求越来越 高：在要求其功能越来越复杂的同时要求其性能越来越好，这便对电子信息系统 的设计实现提出了越来越高的要求。为了简化电子信息系统的系统设计实现和提 高电子信息系统的性能，方面需要提高系统的集成度，以便将实现某功能的 元件数降为最少，甚至使用一个器件实现一个子系统或系统，这便是片上系统 ( s y s t e m o n c h i p ：s o c ) 的思想，这样就只需集中精力于某一功能的片上系统s o c 的设计实现，从而简化整个系统设计实现【1 1 。另一方面，为了简化和规范片上系 统s o c 的设计实现，在片上系统s o c 设计实现时便需要采用更为规范的体系结 构，从而达到系统设计实现更加简洁和规范的目的【”。这样，简洁、规范的设计 实现体系便有利于电子信息系统的设计简化和整个电子信息系统性能的提高。 1 1 2 细胞自动机特点 细胞自动机具有组成单元的简单规则性、单元之间作用的局部互连性和模块 之间的可级连性、并表现出复杂的全局特性等特点，一方面使得其特别适合于超 大规模集成电路( v e r yl a r g es c a l ei n t e g r i t y ：v l s i ) 实现，规范片上系统s o c 的 设计实现，从而成为片上系统s o c 的最佳实现技术；另一方面可以完成更复杂 的系统功能。 细胞自动机单元之间的局部互连性不但可以带来信息处理的并行性，而且可 弱化在v l s i 的小尺度环境中由于导线的电阻和寄生电容带来的时延效应【l 】1 2 1 ， 从而极大提高了其实现系统的性能。这使得细胞自动机与线性反馈移位寄存器 ( l i n e a rf e e ds h i t tr e g i s t e r ：l f s r ) 相比，在几乎不增加系统复杂度的条件下， 可以获得更高的处理速度和更好的性能。p h t s a l i d e s 等人比较了两个使用线性反 馈移位寄存器和细胞自动机实现的6 阶内置逻辑块观察器( b u i l t - i nl o g i cb l o c k o b s e r v e r ：b b 0 ) 系统，其最高速率分别为3 3 m 和5 5 m ( 工艺为2 微米n c m o s ) 3 1 。对于更大的系统，细胞自动机具有更大的优势，这是因为在v l s i 的小尺度 下导线的延时与其长度的平方成正比【4 】。在文献 5 】中利用复杂可编程逻辑器件 ( c o m p l e xp r o g r a m m a b l el o g i cd e v i c e ：c p l d ) 实现比较了完成相同伪随机序列 产生的细胞自动机与l f s r ( 包括i 型和i i 型) ，研究表明：在几乎不增加系统 资源的情况下，细胞自动机比l f s r 有一倍以上的速度优势。所以，对于系统的 第一章绪论 v l s i 实现，细胞自动机是一种理想的方法1 6 1 1 7 】【8 】。 细胞自动机表现出的复杂全局特性可以完成更复杂的系统功能和应用到更 广泛的领域。目前，细胞自动机已广泛应用于计算模型、系统模拟、信息处理和 测试等领域。 1 1 3 研究目的 根据对电子信息系统的设计要求和细胞自动机的特性分析可知：将细胞自动 机应用于电子信息系统中不仅可以简化和规范系统的设计实现、而且可以提高系 统的性能。所以，为了推广和加深细胞自动机的应用，研究细胞自动机原理、特 性，并将其结合应用于特定领域的研究便具有重要的学术价值和现实意义。 1 2 细胞自动机研究现状 早期细胞自动机的发展应归功于，v o nn e u m a a n ，但其思想起源于s t a n i s l a w u l a mi s 。1 9 4 8 年，j v o nn c u m a n n 在研究“什么逻辑组织结构的自动机具有通 用图灵机那样的自我复制特性f 1 0 1 ”的问题时，在s t a n i s l a w u l a m 的建议下，j v o n n e u m a n n 采用二维细胞空间即细胞自动机结构，使用具有2 9 个状态的二维细胞 自动机建立了一个具有自我复制特性和通用计算能力的细胞自动机模型。后来 c o d d 对其进行了简化，使用具有8 个状态的二维细胞自动机建立了一个具有自 我复制特性和通用计算能力的细胞自动杌模型。但是，这些模型需要数量庞大 的细胞单元实现，以至于其物理实现难以完成【”j 。j c o l an e u m a n n 逝世后，经过 许多人的改进，最后由a wb u r k s 完成和扩展了j 、，o nn e u m a m t 的研究，物理 实现了具有自我复制特性和通用计算能力的细胞自动机模型。早期的细胞自动机 研究主要集中于理论方面【2 】，并在并行计算模型的算法建立、语言和模式识别、 复杂性理论等方面和作为诸如物理、化学、生物、经济等自然过程模型这两个方 面得到了较快的发展【1 3 1 。但是，由于早期细胞自动机本身的复杂性而限制了其在 其它方面的应用研究。2 0 世纪8 0 年代初，s w o l f r a m 提出对细胞自动机进行简 化，他建议简化细胞自动机的状态空间和邻域半径，以获得具有组成单元结构的 简单规则性、单元之间作用的局部互连性和信息处理的高度并行性等优点的细胞 自动机，并提出了具有两个状态、邻域半径为一的基本细胞自动机【1 4 1 。简化后的 细胞自动机不仅具有适合v l s i 层次的简单规则结构、信息并行处理的局部互连 结构，而且具有复杂的动力学特性。s w o l f r a m 对细胞自动机的简化极大的推动 了细胞自动机理论和应用研究的发展。 1 2 1 细胞自动机理论研究 2 四川大学博士后研究工作报告 细胞自动机的理论研究主要有两个方面的问趔”】：前向问题即细胞自动机的 分析和反向问题即细胞自动机的综合，前向问题是指确定具有一定规则的细胞自 动机的特性；而反向问题则是根据对细胞自动机特性的描述，寻找具有相应规则 的细胞自动机。这两个问题是紧密相关的，为了设计具有给定特性规则的细胞自 动机，就必须在设计中找到一种确定规则特性的方法：相反，前向问题一般只研 究已经发现的具有某些特性的规则。细胞自动机前向问题的目标是对于任意给定 的细胞自动机，可以使用相应的方法对其进行功能特性的分析；而反向问题的长 期目标是发展出可以定量产生具有一定特性的物理系统的细胞自动机规则的方 法。 1 2 1 1 细胞自动机分析 早期对细胞自动机的分析主要集中于细胞自动机的可逆性分析，1 9 6 2 年， e em o o r e 首先提出了g a r d e no f f _ m e n 定理【1 6 】：“如果细胞自动机的状态中存在 多对一映射时，那么便存在没有前向状态的伊甸园( g a r d e no f f d e n ) ，此时细胞 自动机为不可逆”。1 9 6 3 年，j m y h i l l 则证明了旧：“对于有限细胞自动机，如 果其全局状态为单射，那么它必然是满射”。1 9 7 2 年，d r i c h a r d s o n 证明了：“如 果一个细胞自动机的全部状态映射为单射，那么细胞自动机可逆，并证明了可逆 细胞自动机的逆仍然是细胞自动机”u s o1 9 7 4 年，s a m o r o s o 等人证明了存在 一种算法可以通过一维细胞自动机的邻域函数规则确定其可逆性 1 9 1 ，随后j k a r i 证明了二维细胞自动机的可逆性不能由邻域函数确定1 2 1 l 。后来人们逐渐转向 对某一类细胞自动机可逆性的研究，1 9 8 8 年，p a l a s hs a r k a r 等人提出了一种构造 9 0 1 5 0 可逆细胞自动机的算法；并相继出现了构造其他可逆细胞自动机如 6 0 1 0 2 2 0 4 等的方法 2 2 1 。 在二十世纪八十年代初期s w o l f r a m 提出对细胞自动机进行简化后，对细胞 自动机的分析发展为对其状态转移结构的分析。在这个阶段，主要出现了使用多 项式方法和矩阵方法对线性t 加性细胞自动机的状态转移结构进行分析的方法， 这是因为只有加性细胞自动机才具有可分析的代数结构【2 3 1 。细胞自动机的状态空 间一般为z 2 【1 4 l 【2 3 1 1 2 4 1 1 2 5 l 【矧，并可扩展到具有素数口个元素的空间z q 2 7 j 和合数小 个元素的空间z m l 2 ”，但只有当状态空间的元素个数为素数时其代数运算才具有 完备性1 24 1 。细胞自动机中研究和应用最为广泛的是z 2 空间的细胞自动机，这不 仅是因为其具有最适合v l s i 实现的结构，而且z 2 空间的细胞自动机具有最大的 并行度【”l 。 1 9 8 3 年，s w o l f r a m 首先提出使用多项式方法来分析一维、线性、单一基本 细胞自动机【1 4 l 。1 9 8 4 年，o l i v i e rm a r t i n 等人使用有限域上的多项式方法对循环 边界的单一基本细胞自动机的可逆性、状态可达性和状态结构等统计特性进行了 第一章绪论 研究1 2 4 i 。1 9 8 6 年，w e r n e rp r i e s 等人使用有限域上的多项式方法对线性、单一、 基本细胞自动机的状态转移群特性进行了分析【2 3 1 。1 9 8 6 年，p g u a n 等使用循环 矩阵来分析循环边界条件的线性、单一细胞自动机，并得到其可逆的条件f 3 0 1 。但 是o l i v i e r m a r t i n 、w e m e r p r i e s 和p g u a n 等人的方法都不能计算出细胞自动机任 意t 次迭代后的全局状态。1 9 9 3 年，b k k a r 等人根据有限域上的多项式方法， 使用线性细胞自动机的生成函数写出了其任意t 次迭代的状态转移的闭合式，从 而可以赢接计算出现行细胞自动机t 次迭代后的全局状态p u 。 虽然有限域上的多项式方法能够有效分析一维、线性、单一细胞自动机，但 是对于更为广泛的混合细胞自动机却无法使用有限域上的多项式方法进行分析。 为了能够对一维混合细胞自动机进行分析，1 9 9 0 年a l o k ek d a s 等人引入将状 态转移矩阵引入到一维线性混合细胞自动机中，从而可以通过分析细胞自动机状 态转移矩阵的最小多项式来分析维混合细胞自动机的状态转移特性，这便是细 胞自动机的矩阵分析方法【2 5 】。 1 9 8 9 年，n p i t s i a n i s 等人使用细胞自动机状态转移矩阵的方法分析了规则 1 5 0 的零边界、单一细胞鲁动机的群特性【3 2 1 。1 9 9 2 年，a l o k ek ，d a s 等人从特征 矩阵方法中引申出向量空间理论方法对线性、单一基本细胞自动机的群特性和可 达性等统计特性进行了分析1 3 3 1 。1 9 9 2 年，a l o k ek d a s 等人提出了使用特征矩阵 和最小多项式来分析循环边界的线性细胞自动机的状态转移特性【3 ”。1 9 9 3 年， j o h n gs t e v e n s 等人使用细胞自动机状态转移矩阵的最小多项式方法对零边界的 线性细胞自动机的瞬时和周期状态转移特性进行了研究1 3 ”。1 9 9 3 年，s h i n - i c h i t a d a k i 等根据状态转移矩阵的特征多项式分析了规则9 0 循环边界细胞自动机的 状态转移特性【3 6 i 。1 9 9 3 年，d r o yc h o w d h u r y 等将一维、线性细胞自动机的状 态转移矩阵分析方法扩展到二维线性细胞自动机，并对垂直邻域受限的二维线性 细胞自动机的群特性进行了分析【3 7 】。1 9 9 8 年，p o h y o n gk o h 等使用细胞自动机 状态转移矩阵的特征多项式的方法研究了任意边界条件的9 0 1 5 0 混合细胞自动， 并求出了固定边界条件与零边界条件下细胞自动机的特性多项式之间的关系 3 s l 。 随后，文献1 3 9 1 使用矩阵方法分析了9 0 1 5 0 加性细胞自动机，并指出对于具有不 可约特征多项式的9 0 1 5 0 线性细胞自动机，其对应的加性细胞自动机具有与其 同构的状态转移特性。文献【2 2 】分析了6 0 1 0 2 2 0 4 加性细胞自动机的群特性，并 从矩阵方程的解特性出发给出和证明了6 0 1 0 2 2 0 4 加性细胞自动机获得等圈长 状态转移的条件为其可逆且其规则2 0 4 的单元取补规则。 1 2 1 2 细胞自动机综合 细胞自动机的综合是指给定具有某些特性的序列，并根据这些特性综合出相 应细胞自动机的方法。但是，目前只能实现在给定一个不可约多项式的情况下， 4 四川大学博士后研究工作报告 将其作为细胞自动机的特征多项式来综合出相应的9 0 1 5 0 线性细胞自动机。1 9 9 0 年，p h b a r d e l l 提出了细胞自动机的综合问题 4 0 1 ；1 9 9 0 年，m i c a e l as c r r a 等人 提出了一种o f ( 2 ) 中的i , a n c z o s 矩阵三角化的算法来完成从l f s r 到9 0 1 5 0 混合 细胞自动机的转化，从而第一次实现了9 0 1 5 0 细胞自动机的综合算法f 4 2 l ；但 是l a n c z o s 矩阵三角化的算法的有效性差，1 9 9 6 年，k e v i nc a t t e l l 等人提出了一 种在o f ( 2 ) q a 基于欧几里德除法的高效细胞自动机综合方法【蚓，从而基本解决了 根据不可约多项式来综合9 0 1 5 0 细胞自动机的问题；1 9 9 6 年，k e v i nc a t t e l l 等 人又将其推广到o f ( q ) q ，从而得到更为普遍的细胞自动机综合算法【州。 】2 2 细胞自动机应用研究 细胞自动机的应用研究包括多个方面，其中主要包括细胞自动机并行计算模 型 4 s l 4 s l h 7 1 、细胞自动机物理、化学的自然模拟模型 4 9 l i 4 9 1 娜1 、细胞自动机在内建 自测试中的应用【5 2 j 【5 3 】，以及细胞自动机在电子信息科学中的应用吲【5 6 1 等。 其中，细胞自动机在电子信息科学中的应用包括细胞自动机伪随机数伪随机序 列发生方法、细胞自动机分组密码方法、细胞自动机h a s h 函数方法和细胞自动 机非对称密码方法等。文献i s 7 1 对细胞自动机在密码学中的应用研究进行了较为 广泛的论述。 由于细胞自动机具有动力学系统所特有的复杂的动力学特性，所以可以将这 一特性用于伪随机数发生方法中。1 9 8 5 年美洲密码学年会上，s w o l f r a m 首次 提出了将细胞自动机的初始状态作为密钥，使用规则3 0 细胞自动机前向迭代产 生的伪随机序列作为序列密码p ”，从而开创了细胞自动机在密码学中的应用研 究，但是s w o l f r a m 的方法不能保证产生伪随机序列的周期特性。1 9 8 9 年，p e t e r d h o r t e n s i u s 提出使用具有历序列特性的细胞自动机产生伪随机序列p 9 1 ；1 9 9 4 年，s n a n d i 提出使用o f ( 2 ) 上的可编程细胞自动机和存储单元来产生伪随机序 列1 6 0 】；1 9 9 7 年，d o l o r e sd el ag u i a - m a r t i n e z 等提出了一种使用线性移位寄存器 来控制每个时刻细胞自动机迭代次数的伪随机序列发生方法，以提高产生伪随机 序列的线性复杂度和周期【6 1 】；1 9 9 8 年，m d a s c a l u 等在w o l f r a m 方法基础上加 入存储单元来减少细胞自动机过早的进入状态循环【6 2 1 ，但是它们同样不可避免的 不能保证产生伪随机序列的周期特性。1 9 9 8 年，m i o d r a g m i h a l j e v i e 等提出在o f ( q ) 上使用线性细胞自动机的前向迭代产生伪随机序列的方法【6 3 l ，并于1 9 9 9 年提出 了在g f ( q ) 上使用线性可编程细胞自动机的前向迭代产生伪随机序列的方法研l ， 但是与m i o d r a gm i h a l j e r i c 指出的相反，对于一般实用的伪随机序列方法均是在 o f ( 2 ) 而非c v ( q ) 上实现的，这不仅是因为在g f ( 2 ) 上产生伪随机序列最容易，丽 且使用硬件实现时g f ( 2 ) 具有最大的并行性。文献【6 5 】根据具有不可约特征多项 式的单元9 0 1 5 0 线性细胞自动机与其个加性细胞自动机的状态转移同构这 第一章绪论 一性质提出了基于具有所序列特性的9 0 1 5 0 加性细胞自动机伪随机序列发生方 法，它扩展了p e t e rd h o r t e n s i u s 等的方法p 9 l ，具有更大的灵活性和更广泛的伪随 机数发生方法；文献【6 6 】将9 0 1 5 0 细胞自动机的这种状态转移的同构特性应用到 二维细胞自动机，从而提出了基于垂直邻居受限的二维细胞自动机伪随机序列发 生方法；应用到可编程细胞自动机而得到基于可编程细胞自动机的伪随机序列发 生方法”4 】；文献【6 7 】和 5 4 】在具有输入变量的非自治细胞自动机中根据9 0 1 5 0 细 胞自动机的同构特性提出了基于非自治、确定性细胞自动机的准随机序列发生方 法和基于非自治、可编程细胞自动机的准随机序列发生方法，可以方便灵活的获 取具有随机特性好和不可恢复特性的准随机序列；为了有效提高产生伪随机序列 的线性复杂度和周期，可以进一步采用基于状态转移同构细胞自动机比特与、或 和异或组合运算的组合伪随机序列发生方法，不仅具有有效增加序列周期和线性 复杂度的作用，而且具有提高序列伪随机统计特性的作用，同时还可以增加伪随 机数发生方法的灵活性。 细胞自动机在伪随机数，伪随机序列发生方法方面获得应用的同时，在细胞 自动机信息加密如对称密码方面也有相应的发展。1 9 9 4 年，s n m x d i 等人根据 细胞自动机循环群特性提出了基于置换群基本变换的分组加密技术【6 。1 9 9 5 年， b s d s u c h i n w o n g 等人提出将非线性细胞自动机用于f e i s t e l 型密码中的非线性函 数，并将另一个线性细胞自动机作为每一分组数据的加密密钥的方法 6 8 1 。1 9 9 6 年，l a t e ，o ，首次提出基于细胞自动机变换的概念，并提出了一种基于细胞自动 机变换的加密方法1 6 9 1 1 7 0 l 。2 0 0 2 年，c h a n gn z h a n g 等提出了s n a n d i 等人在文 献【6 0 】中提出的基于置换群基本变换的分组加密技术的一种实现方法1 7 1 1 文献【7 2 】 从具有不可约特征多项式的9 0 1 5 0 线性细胞自动机与其对应的9 0 1 5 0 加性细胞 自动机具有状态转移的同构性这一结论出发，并根据可逆细胞自动机的周期特性 和细胞自动机的边界条件不影其群特性等性质，提出了种基于具有本原多项式 的9 0 1 5 0 加性细胞自动机的输入边界可逆细胞自动机对称密码模型。此方法大 大扩展和增加了以前基于可逆细胞自动机的密码系统的密钥空间和灵活性。文献 f 5 5 根据系统输出序列熵最大化原则和基于细胞自动机反转规则的反向迭代原 理提出了一种基于细胞自动机反转规则表的反向迭代对称密码方法。同时，文献 【7 3 】为了克服sn a n d i 等方法【6 0 l 中密钥数量受限的缺点，提出了种具有输入的 细胞自动机置换群加密技术，扩展了以前s n a n d i 等的方法，具有更大的密钥 空间和更灵活的加解密方式。 在h a s h 函数设计中，一般将单向函数作为其迭代的轮函数的设计。2 0 0 0 年， p r a b i rd a s g u p t a 等人在文献 7 4 】中提出了一种使用具有一个吸引子的二前向状态 的细胞自动机作为h a s h 函数的方法。文献 7 5 1 提出了一类具有二叉树型状态转 6 四川大学博士后研究工作报告 移特性的规则9 0 加性细胞自动机，从而可以将细胞自动机应用与h a s h 函数的轮 函数设计中。 1 9 8 7 年，p g u a n 根据复杂系统的多项式方程求逆的困难性，提出了一种基 于混合细胞自动机的公钥加密技术1 7 6 1 ，但是系统难以用有效的方法构建。1 9 9 4 年，z h a n g ，c n 等在文献【7 7 忡提出了一种基于扩展可编程细胞自动机的密钥交 换的实现算法。2 0 0 0 年，d k b h a t t a c h a r r y y a 等在文献【7 8 】中提出了一种基于细 胞自动机的密钥交换认证的方法。细胞自动机在密钥交换等方面的研究逐渐展 开。 虽然基于细胞自动机的密码算法的安全性还有待于检验，同时其作为一个完 整的密码算法实现还处于探索阶段，但是细胞自动机作为密码系统中的一个构件 模块是具有很好的前途畔1 。 1 3 本项目的主要工作 根据有关细胞自动机的研究背景、方法和目的，针对细胞自动机、尤其是线 性细胞自动机的分析方法，本项目提出了对线性细胞自动机相对应的加性细胞自 动机同构性进行研究的思路，同时针对细胞自动机可能广泛应用领域的特点来研 究细胞自动机伪随机数发生方法、细胞自动机加密方法和细胞自动机内建式自测 试方法等；最后针对细胞自动机的实现问题提出利用细胞自动机与l f s r 的v l s i 实现对比来比较其实现特点和优势，从而为细胞自动机在电子信息科学中的应用 推广奠定基础。 1 3 1 细胞自动机同构性分析 采用线性细胞自动机相类似的矩阵方程来表示加性细胞自动机的状态转移 结构，这样便可以通过状态转移矩阵方程及其特征多项式来分析加性细胞自动机 的状态转移特性，从而求出其状态转移图。零边界9 0 1 5 0 线性细胞自动机状态 转移矩阵的最小多项式等于其特征多项式，状态转移矩阵方程及其特征多项式分 析证明了；特征多项式为不可约多项式时的零边界9 0 1 5 0 线性细胞自动机对应 的加性细胞自动机具有相同结构的状态转移图，即它们同构。这一结论可以广泛 应用于诸如伪随机数产生、密码学和内建式自测试等领域。 1 3 2 细胞自动机应用研究 细胞自动机的应用研究领域广泛，主要包括并行计算模型、物理化学的自然 模拟模型、伪随机数产生、信息加密和内建式自测试等。 细胞自动机研究初期主要应用于并行计算模型、自然界物理化学模型和社会 7 第一章绪论 发展模型等模拟，随着细胞自动机理论的发展而逐步应用于其他领域，尤其是 2 0 世纪8 0 年代初经s w o l f r a m 简化后细胞自动机所具有的简单规则的组成单 元、单元之间的局部互连特性和表现出的复杂全局状态转移特性，从而可以应用 于伪随机数产生、信息加密和内建式自测试等领域。同时，细胞自动机同构性分 析所获得的细胞自动机状态转移的同构特性的结论进一步增强了细胞自动机在 这些领域的应用。 1 3 3 细胞自动机实现研究 由于细胞自动机所具有的组成单元的简单规则性、单元之间作用的局部互连 性私信息处理的高度并行性等，使得其特别适合于v l s i 的实现。同时，由于 9 0 1 5 0 细胞自动机与l f s r 的同构性而使得其可以广泛应用于伪随机数产生、信 息加密和内建式自测试等电子信息科学领域。所以研究细胞自动机与l f s r 的 v l s i 实现比较具有重要的理论价值和现实意义。文献【7 9 】通过v l s i 的实现特点， 结台细胞自动机和l f s r 的实现特征比较了产生同样伪随机序列的细胞自动机 和l f s r ，结果表明细胞自动机在几乎不增加复杂度的情况下具有l f s k 无法比 拟的速度优势。如果进一步采取诸如时钟特别处理等措施时，细胞自动机将具有 更大的优势。 1 4 小结 基于上述的细胞自动机研究特点，本项目首先利用矩阵分析方法对细胞自动 机进行分析，主要研究了加性细胞自动机的同构特性问题，获得了“特征多项式 为不可约多项式时的零边界9 0 1 5 0 线性细胞自动机对应的加性细胞自动机具有 相同结构的状态转移图即同构”的结论；然后，根据这一结论，结合电子信息科 学领域的特点来分析细胞自动机，从而将其应用于伪随机数产生、h a s h 函数和 对称加密等领域；最后，从v l s i 设计角度和c p l d 实现角度出发，分析了产生 相同伪随机序列的细胞自动机和l f s r 的实现特点，得出了在完成相同功能的伪 随机数产生时，细胞自动机在几乎不增加资源的情况下，具有比l f s r 不可比拟 的速度优势，从而说明了能够完成l f s r 相同功能的细胞自动机在v l s i 实现时 具有l f s r 无法比拟的性能优势。这样，从细胞自动机的原理分析、应用研究到 实现仿真的研究为细胞自动机的进一步研究、应用推广和实现奠定了基础，具有 较为重要的学术意义和应用价值。 g 四川大学博士后研究工作报告 2 细胞自动机代数分析法 2 1 细胞自动机 细胞自动机是一种特殊的有限状态机，是与连续c a n t o r 映射动力学系统相对 应的离散动力学系统，具有时间、空间和状态的离散性【鲫，在电子科学领域称 为迭代阵列( i t e r a t i v ea r r a y ) 【8 ，同时又称为细胞结构( c e l l u l a rs t r u c t u r e s ) 、同 类结构( h o m o g e n e o u ss t r u c t u r e s ) 和网格自动机( t e s s e l l a t i o n a u t o m a t a ) 等【1 4 1 。 早期细胞自动机的发展应归功于j v o nn e u m a n n ，但其思想起源于s t a n i s l a w u l 锄p j 。1 9 4 8 年，j v o n n e u m a n n 在研究“什么逻辑组织结构的自动机具有通用 图灵机一样的自我复制特性f l o 】”的问题时，在s t a n i s l a wu l a m 的建议下，j y o n n e u m a n n 采用具有2 9 个状态的二维细胞空间即细胞自动机建立了一个具有自我 复制特性和通用计算能力的细胞自动机。j y o nn e u m a n n 逝世后，awb u r k s 完成和扩展了j v o n n c u m a n n 的研究，但是早期的细胞自动机研究主要集中于理 论方面1 2 l ，并且由于早期细胞自动机结构的复杂性而限制了其应用。2 0 世纪8 0 年代初，s w o l f r a m 提出对细胞自动机进行简化，他建议简化细胞自动机的状态 空间和邻域半径，以获得具有组成单元结构的简单规则性、单元之间作用的局部 互连性和信息处理的高度并行性等优点的细胞自动机，并提出了具有两个状态、 邻域半径为一的基本细胞自动机唧e m e n t a r y c e l l u l a r a u t o m a t a ：e c a ) t 1 4 1 。简化后 的细胞自动机不仅具有适合v l s i 层次的简单规则结构和信息并行处理的局部互 连结构，而且具有复杂的动力学特性。s w o l f r a m 对细胞自动机的简化极大推动 了细胞自动机理论及其应用研究。 2 1 1 细胞自动机定义 细胞自动机是d 维空间中一组细胞单元组成的阵列，每个细胞单元处于状 态空间中的某种状态，各细胞单元下一时刻的转移状态根据相应的邻域函数规则 ( 确定邻域范围及其到转移状态的映射) 和各时间阶的邻域状态配置( 确定邻域 中细胞单元的状态) 进行状态更新即1 i 札1 。绝大部分细胞自动机的定义将其细胞 单元定义为无限1 4 6 1 1 救1 ，且未对其边界条件进行限定，但由于其物理实现的限制 而不具有工程应用价值。为此，作者将细胞自动机定义为由有限个细胞单元组成 的阵列，并对其边界条件作相应的限定。 定义2 1 h 细胞自动机是一个c a = ( 如，z 。，。：、，动的四元组，其中： ( 1 ) 空 间结构a d ： 9 第二章细胞自动机代数分析法 4 。：nz ： = ( f 。，一。) i f 。z “，z l ，f 。一。z 。) 是由d d d 维细胞单元构成的空间结构，其中丌z m = z ox z n , 一。为集 i - - o 合z “，z l ，z 。的笛卡尔积( c a r t e s i a n p r o d u c t ) ， z m = ( 0 , 1 ，f 一1 ) 为模婀的整数集，f = ( f o ，f 1 - ，屯一，) 为细胞单元的 d 维空间地址索引值； ( 2 ) 状态空间乙：细胞自动机中细胞单元；的状态取值范围。一般为具有 g 个元素的有限交换环z 。= o i ，q 一1 ，状态赋值函数s ；确定了t 时刻细胞自动机中第i 个细胞单元与状态空间乙之间的映射关系 s ；：( 尊z m - 乙，；县d - i z m ，。状态空间一般取z 2 ，因为 其最易v l s i 实现且具有最大的并行度1 2 9 1 。 ( 3 ) 邻域函数规则t ( 。，；) ：称由细胞自动机的邻域半径，= ( ，o ，l ，d 一) 确 定的第；个细胞单元的0 阶邻域状态配置 ，7 ；t ( 。， ) = 。p z 。，1 ，。一f 0 降，o ，i j 。一引，i 厶一。一f l ，d 一j 与其 转移 状态 j ，1 之间的映射 s r l = f ；( 。) b ；。l 。z 。，i ，。一f 0 i i = 0 其中第f 个单元的状态值是全局状态多项式中x i 的系数。 同时，使用如下多项式来表示线性、单一细胞自动机的邻域函数规则： t ( x ) = 吼，x _ ，+ + 口。+ + 口，x 7 = 口l x ( 2 2 2 ) ，= 一， 并称之为线性、单一细胞自动机的邻域函数多项式，当r = l 时为线性、单一、 基本细胞自动机的邻域函数多项式。这样，与转移状态相对应的转移状态多项式 便可以表达为全局状态多项式与邻域函数多项式的乘积： s “1 ( 砖= t ( x ) s ：( x ) l r 警辫x 一l ，n u u b o u n d a r y ( 2 2 3 ) 【s t + l ( x ) = t ( 功s ( x ) m o d 一1 ，p e r i o d i cb o u n d a r y 第二章细胞自动机代数分析法 式( 2 2 3 ) 中，截取运算肌脚( ) 一般在每一步进行，但取模运算m o d ( ) 却可 以在任意多步后进行。所以，有限域上的多项式分析方法般只适用于分析循环 边界的线性、单一细胞自动机，其f 步状态转移多项式方程为： s ( x ) = t ( x ) s o ( x ) m o dx ”一1 ( 22 4 ) 式( 22 4 ) 表明，可以通过有限域上多项式的特性来分析细胞自动机的状态 转移特性。根据线性细胞自动机的线性可加性可知：一个任意初始状态 s o = ( 霹，j 。0 。) 经过p个时刻后的转移状态等于 ( j ：，o ，o ) ，( o ，o ，o ) ，( o ，o ，0 一。) 分别为初始状态的f 步转移状态的模二 加。此时，对细胞自动机任意初始状态s o = ( s o ，s , o ，0 一) 的状态转移方程的分 析等同于对初始状态为( 1 0 ，o ) 的转移状态方程的分析，即有： s ( x ) = t ( 功r o o dx ”一1 ( 2 2 5 ) 式( 2 2 ，5 ) 表示：对细胞自动机的转移状态特性的分析等同于对细胞自动机 邻域函数多项式t o ) = 口l 一的分析。 t 2 一r 有限域上的多项式方法只适用于一维、线性、单一细胞自动机。 2 2 2 细胞自动机矩阵分析法 由于有限域上的多项式方法只适用于一维、线性、单一细胞自动机，为了能 够对一维、加性、混合细胞自动机进行分析，d a s 等人引入了状态转移矩阵分析 方法【 1 ，通过分析细胞自动机状态转移矩阵的最小多项式来分析一维、加性、 混合细胞自动机的状态转移特性1 3 j f 2 6 1 1 3 2 肼】【4 1 1 。 2 2 | 2 1 一维线性细胞自动机矩阵分析 在r = l 的一维、线性、混合细胞自动机中，由于每个细胞单元的邻域函数规 则不完全相同，所以分别将第0 1 , i v - 1 个细胞单元的转移状态表示为其邻域状 态的映射，即： j 1 = c i o 。o s ；+ 口o l + c 口仉一i 一t s ：”2q 一1 t + a i 。+ q 。l s ； ( 22 6 ) n t + 一1 1 = c a n 吐l s ：+ 吐一i 十1 + - l o q 1 6 四川大学博士后研究工作报告 其中c = 0 为零边界条件，c = l 为循环边界条件。将式( 2 26 ) 改写成矩阵形 式为： 巨 即有 s “= t s 其中称t = 口n 1 00 c a o 一 q 。oa 1 1 0 00 a 一1 ，一1a 一1 ( 2 2 8 ) a o 1 00 c a m l q 。oq 1 0 0 0 口一1 1 口一1 o ( 2 2 7 ) 为细胞自动机的状态转移 矩阵， s = ( ，t 一。) 为细孢自动机在t 时刻的全局状态配置。 方程式( 2 2 7 ) 和( 2 2 8 ) 便是一维线性细胞自动机的状态转移方程，其以 s o = ( 霹，s ? ，0 一。) 为初始状态的t 次迭代方程为： s = t s o ( 2 2 9 ) 式( 2 2 9 ) 表示的状态转移方程为满足线性可加性的线性运算，即一个任意 初始状态s o = ( 吒0 ，s ? ，0 。) 经过t 个时刻后的转移状态等于( 吒0 ，o ，o ) 7 、 ( o 砰，o ，o ) 、j ( o ，o ，嚣。圹等为初始状态的t 步转移状态的模二加，此时 对细胞自动机任零初始状态( ，砖一。) 7 的状态转移方程的分析等同于对初 始状态为( o ，o ，霹= l ，o ，o ) 7 的转移状态方程的分析，即： s 1 = t f s 。= ( ( t 。) 吖，( t 。) ，( t f ) 。了 ( 2 2 1 0 ) 式( 2 2 1 0 ) 表示：可以通过分析细胞自动机状态转移矩阵t 的特性来分析 其状态转移特性。 2 2 2 2 一维加性细胞自动机矩阵分析 在一维加性细胞自动机中，细胞单元的邻域