基于四方邻域路径映射的二维元胞自动机高质量伪随机数发生方法

A Four-Neighborhood Path-Mapping-Based Two-Dimensional Cellular Automaton Method for High-Quality Pseudorandom Number Generation

摘要: 针对硬件伪随机数发生器在蒙特卡洛仿真、统计抽样及片上系统测试等非对抗性应用场景中的应用需求，研究一种兼顾长周期、统计随机性、多路输出低相关性与实现复杂度的二维元胞自动机伪随机数发生方法。基于四方邻域（半径 1，含中心）的二维元胞自动机模型，提出一种路径映射构造框架，将 R×C阵列沿行映射、列映射及其蛇形映射线性化为长度 N=RC的一维序列，并在一维空间中利用 Cattell-Muzio方法合成与给定本原多项式对应的混合元胞自动机（规则 90/150），再回映射至二维拓扑，从而在二维结构上显式继承最大周期与线性复杂度等可分析性质。在 64×64阵列、周期边界及单流 10⁶ bit的统一仿真平台下，所提出的路径型二维元胞自动机在 NIST SP 800-22随机性测试套件的多项核心子测试中均通过；在 K=64路并行输出场景下，蛇形路径映射在零时延多流相关矩阵的非对角相关系数上显著低于多种典型二维更新核。结果表明，该方法在随机性质量、多流去相关能力与逻辑复杂度之间实现了较为均衡的折中，适用于通用硬件伪随机激励与片上系统测试等非对抗性应用场景。

Abstract: High-quality pseudorandom number generators are fundamental to Monte Carlo sim-ulation, statistical sampling, and non-adversarial on-chip testing applications. To ad-dress the limitations of one-dimensional structures in multi-stream and two-dimensional array scenarios, a path-mapping-based two-dimensional cellular automaton pseudoran-dom number generation method with a four-neighbor neighborhood is presented. The proposed approach linearizes an R×C array into a one-dimensional sequence of length N=RC through reversible row/column and snake-path mappings, synthesizes a hybrid cellular automaton based on rules 90/150 using the Cattell-Muzio method, and maps it back to the two-dimensional topology, thereby explicitly inheriting the maximal pe-riod and linear complexity associated with primitive polynomials. Simulation results obtained on a 64×64 array with periodic boundaries and single-stream outputs of 10⁶ bits demonstrate that the proposed method passes all selected core subtests of the NIST SP 800-22 test suite. In multi-stream evaluations with K=64 parallel outputs, snake-path mappings exhibit signi.cantly reduced inter-stream correlation compared with several representative two-dimensional cellular automaton kernels. These results indicate that the proposed method achieves a favorable trade-o. among theoretical analyzability, statistical randomness quality, multi-stream decorrelation capability, and logic complexity, making it suitable for general-purpose hardware pseudorandom excitation and non-adversarial multi-stream applications.