Maximum-length sequences, cellular automata, and random numbers
type: Item
instance of: scholarly article
title: Maximum-length sequences, cellular automata, and random numbers
zbMATH Open document ID: 0616.65001
DOI: 10.1016/0021-9991(87)90037-4
author: A. Compagner
author: A. Hoogland
published in: Journal of Computational Physics
publication date: 1987-01-01T00:00:00Z
review text: The statistical properties of maximum-length sequences generated by linear-feedback shift registers are investigated. Two-dimensional bit patterns constructed from these sequences are found to exhibit characteristic triangular structures, in the simplest case consisting of triangles of zeros supported by a backbone of ones. The size distribution of these triangles is given, and the relation with cellular automata is pointed out. Randomness is defined in terms of the correlation functions of any order. Not only the pair correlation function, but also all higher order correlation functions are two-valued. The number of correlation functions of any order that deviate from randomness is determined exactly. All maximum-length sequences of the same length are found to be equally random in a strict sense, although their suitability as a source of random numbers may differ widely in different applications; longer sequences are more random. It is concluded that extremely long maximum- length sequences, with periods of up to \(2^{9689}-1\), can in fact be used a reliable random-number generators for many purposes. Fast software or hardware programs for the production of these sequences are readily constructed.
Mathematics Subject Classification ID: 65C10
Mathematics Subject Classification ID: 65C99
zbMATH DE Number: 3999098
zbMATH Keywords: maximum-length sequences
zbMATH Keywords: linear-feedback shift registers
zbMATH Keywords: cellular automata
zbMATH Keywords: correlation functions
zbMATH Keywords: random-number generators
zbMATH Keywords: software
MaRDI profile type: Publication
full work available at URL: 0021-9991(87)90037-4
OpenAlex ID: W2051931634
cites work: A special-purpose processor for the Monte Carlo simulation of Ising spin systems
cites work: A fast processor for Monte-Carlo simulation
cites work: Q5684568
cites work: Q4146667
cites work: Random Numbers Generated by Linear Recurrence Modulo Two
cites work: The Runs Up-and-Down Performance of Tausworthe Pseudo-Random Number Generators
cites work: An Asymptotically Random Tausworthe Sequence
cites work: Pseudo-randomness properties of binary shift register sequences (Corresp.)
cites work: Theory and design of a digital stochastic computer random number generator
cites work: Partitioning the Period of a Class of m -Sequences and Application to Pseudorandom Number Generation
cites work: A very fast shift-register sequence random number generator
cites work: Time-Dependent Statistics of the Ising Model
cites work: On rotational tessellations and copses
cites work: Statistical mechanics of cellular automata
cites work: On primitive trinomials (mod 2), II
cites work: On xn + x + 1 over GF(2)
cites work: Primitive Binary Polynomials
cites work: Parallel concepts in graph theory
cites work: Q5832397
cites work: Q3935355
description: scientific article; zbMATH DE number 3999098