细胞自动机组合伪随机序列发生器

Combined Pseudorandom Sequence Generator Based on Cellular Automata

结合细胞自动机所特有的单元结构的简单性、单元之间作用的局部性和信息处理的高度并行性等特点,利用细胞自动机产生高速序列;分析了比特与、或、异或运算周期特性,其周期等于各自周期的最小公倍数;证明了比特异或运算的频率特性优于原有的频率特性。研究了比特组合运算的线性复杂独特性,比特与、或运算的线性复杂度等于各自线性复杂度的乘积,异或运算的线性复杂度等于各自线性复杂度之和。利用伪随机特性检测方法和线性复杂度的测试方法的计算机模拟表明细胞自动机组合伪随机序列发生器实现简单、速度高、能有效增加序列周期长,改善序列伪随机统计特性,并能有效增加伪随机序列的线性复杂度。

By analyzing the period of the bit computation of AND, OR, and XOR, it is proved that the frequency characters of the bit computation of XOR is better than the original frequency characters. The study of the linear complexity of the combined bits demonstrates that： the linear complexity of the bit computation of AND and OR is equal to the product of the linear complexity of the originals; and the linear complexity of the bit computation of XOR equal to the addition of the linear complexity of the originals. Computer simulation demonstrates that the combined pseudorandom sequence generator has simple architecture and high speed information processing characters, and can efficiently increase the period and linear complexity efficiently of pseudorandom sequence.