细胞自动机伪随机序列的线性复杂度分析

细胞自动机是一种时间、空间和状态均离散的动力学系统,是反馈移位寄存器这一有限状态机的推广.本文使用Berlekamp-Massey算法对细胞自动机产生的伪随机序列进行线性复杂度分析,在此基础上利用计算机模拟出了细胞自动机的线性复杂度分类图.最后,对细胞自动机产生的m序列的局部伪随机统计特性进行了分析和仿真,实验说明了基于细胞自动机的伪随机序列具有与移位寄存器相似的伪随机统计特性,且其电路具有更高的速度优势.

Linear Complexity Analysis of the Pseudo-random Sequence Based on Cellular Automata

The Cellular automata is a kind of dynamic system which is discrete in time, space, and status. It is the generalization of the finite state machine-feedback shift register. This paper presents a method by using Berlekamp-Massey algorithms to classify the cellular automata based on linear complexity of their pseudo-random sequence, and the figures of categories of linear complexity are demonstrated on the basis of the computer's simulation. At last, the local pseudo-random statistical properties of pseudo-random sequence generated by cellular automata are analyzed and simulated, which indicate similar to the LFSR, while it has advantages in speed due to the locality of its interactions.