A Parallel Method for Generating Pseudorandom Binary Markovian Sequences

This paper describes a deterministic two-layer cellular array in which many virtual particles move pseudorandomly. The motion of the particles is defined by a two-state Markov chain. A parameter of the cellular array determines the eigenvalue of the transition matrix which defines the Markov chain. Thus, the cellular array can generate pseudorandom binary sequences with exponentially vanishing autocorrelation in parallel. Since such binary sequences can be used for spreading codes with excellent co-channel interference reduction in asynchronous DS/CDMA communications, the cellular array is expected to be applied to the communication systems. Numerical experiments show that the sequences generated by the cellular array have almost the same probability distribution and correlation properties as the sequences generated by truly probabilistic two-state Markovian systems have