Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!purdue!gatech!hubcap!mips!mips.com!mark
From: mips!mips.com!mark@decwrl.dec.com (Mark G. Johnson)
Newsgroups: comp.parallel
Subject: Random Numbers from Cellular Automata
Message-ID: <6137@hubcap.clemson.edu>
Date: 2 Aug 89 14:42:43 GMT
Sender: fpst@hubcap.clemson.edu
Lines: 17
Approved: parallel@hubcap.clemson.edu

There's an article in a recent journal that might be of interest:

   "Cellular Automata-Based Pseudorandom Number Generators for
    Built-In Self-Test", IEEE Transactions on Computer-Aided Design,
    Vol. 8 No. 8, August 1989, pp. 842-859.

The technique produces a parallel *word* of random bits once per clock
tick, unlike the Linear-Feedback Shift Register which produces a serial
bitstream, one bit per clock tick.  A major drawback of the LFSR is the
rather high auto- and cross-correlation in the stream of pseudorandoms;
the Cellular Automaton approach seems to improve this dramatically.

Knuth's tests for randomness are applied and the results are favorable.
-- 
 -- Mark Johnson	
 	MIPS Computer Systems, 930 E. Arques, Sunnyvale, CA 94086
	...!decwrl!mips!mark	(408) 991-0208