NEW BOUNDARY CONDITIONS FOR 1-D CELLULAR AUTOMATA

Abstract

Cellular Automata (CA) have been suggested forPseudo Random Sequence (PRS) generation as a new butcharacteristically different alternative to the classicalFeedback Shift Registers (FSR). One-dimensional (1-D) aswell (2-D) two-dimensional CAs has been used withremarkable success in generating PRS that have goodstatistical features. This research presents a new butnotwithstanding remarkably simple design for PRSgeneration. The outputs of linear FSRs (LFSRs) act ascontinuous inputs or perturbations to the two extremeboundary cells of a 1-D CA. The results of sufficiently longevolutions time steps show superior randomness features ascompared to the periodic boundary conditions classicalapproach. The output strings of such CAs under certainchaotic local transition rules have passed the stringentDiehard statistical battery of tests. The design is a viablecandidate for parallel PRS generation, has strongcorrelation immunity, good order of asymptotic complexityand is inherently amenable for VLSI implementation.Index Terms — Boundary Conditions, Cellular Automata,Diehard Tests, Linear Feedback Shift Registers, RandomNumber Generators.