基于同余和线性反馈移位寄存器的伪随机数生成方法是目前应用比较广泛的一种伪随机数生成方法，我们见到的大多数MP3播放器在进行随机播放时，大多数使用的都是这两种方法。但是这两种方法前者在硬件上难以实现，后者在在超大规模集成电路上又难以模块化，同时它们在运算速度上都存在着一定的问题。随着现在的电子科技日益发展，高速运算以及超大规模集成电路必然会越来越普及，这样的不足这毫无疑问会成为一种阻碍。

1．2  国内外发展现状

1．3  研究内容

本文就二维梯形可控元胞自动机的基础与性质进行研究，主要研究内容如下：

(1) 在二维空间中构造一个二维元胞自动机，通过添加梯形邻域和可控元胞等规则，使之成为一个二维梯形可控元胞自动机。

(2) 通过对该二维梯形可控元胞自动机性质的分析，编写一个基于其的伪随机数生成器。

(3) 使用该伪随机数生成器，通过NTIS随机数质量测试结果，评价该伪随机数生成器的性能。文献综述

(4) 使用该伪随机数生成器，通过改变不同参数，从而分析不同参数对伪随机生成器的随机性造成影响的差异。

1．4  本文结构

第一章，引言先介绍了伪随机数的发展背景，然后就国内外元胞自动机及其伪随机数生成器的发展状况做了简要分析，最后简要阐述了本文主要的研究内容。

第二章，就元胞自动机的基本理论做了一个详细的介绍，并详细说明了二维梯形可控元胞自动机的构造。

第三章，对基于二维梯形可控元胞自动机的伪随机数生成器进行了详细的描述，并以介绍了笔者编写的一种伪随机数生成器。

第四章，通过使用生成器进行仿真实验，对实验数据进行了对比分析总结。

2  元胞自动机基本理论

2．1  一维元胞自动机

元胞自动机有四个重要要素：元胞空间，邻域，有限状态集，状态转变函数。从数学的角度来看，元胞自动机是一组具有有限离散状态的N维元胞阵列，实际研究中一般取N=1，2，3。定义在每个离散的时间步长内，当前时刻t的元胞自动机的状态，是由各自独立的元胞状态构成的N元组：

 元胞自动机的每个元胞具有有限的状态，可表示为：

  ∈ P,(i=1,2，，N-1)

邻居半径r表示了一个元胞的邻居范围，通常研究时一般取r=1，r越大则邻居范围涉及得越广，邻居越多。而元胞自动机的每个元胞的下一状态，取决于它自身和周围邻居的元胞的当前状态及转变规则。一个r=1时的元胞自动机的下一状态可表示为：

 当 是一个线性函数时，f也是一个从N元组映射到N元组上的一个线性函数。一个r=1的一维元胞自动机，其第i个元胞的变化可以用第(i-1)、第i个、第(i+1)个元胞的当前状态构成的函数来表示：