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

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

作　　者：张传武[1,2] 彭启琮[3] 李玉柏[3] 

机构地区：[1]西南民族大学电气信息工程学院 [2]电子科技大学通信与信息工程学院,成都610054 [3]电子科技大学通信与信息工程学院

出　　处：《电子测量与仪器学报》2005年第1期69-73,共5页Journal of Electronic Measurement and Instrumentation

基　　金：国防科技保密通信重点实验室基金项目 (基金编号 2 0 0 0JS0 6 1 2ZS0 6 0 1);西南民族大学项目共同支持

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

关 键 词：伪随机序列 线性复杂度 细胞自动机 统计特性 移位寄存器 M序列 BERLEKAMP-MASSEY算法 类图 有限状态机 动力学系统 

分 类 号：TH133.3[机械工程—机械制造及自动化] TN918[电子电信—通信与信息系统]