Parallel random number generation for VLSI systems using cellular automata
Abstract
A novel random number generation (RNG) architecture of particular importance in VLSI for fine-grained parallel processing is proposed. It is demonstrated that efficient parallel pseudorandom sequence generation can be accomplished using certain elementary one-dimensional cellular automata (two binary states per site and only nearest-neighbor connections). The pseudorandom numbers appear in parallel from various cells in the cellular automaton on each clock cycle and pass standard empirical random number tests. Applications have been demonstrated in the design and analysis of special-purpose accelerators for Monte Carlo simulation of large intractable systems. In addition, significant advantages in pseudorandom built-in self-test of VLSI circuits using cellular automata based RNGs have been demonstrated.>
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Parallel random bit generation methods could dramatically improve the generation rate and scalability by producing many random bits simultaneously.
“Parallel random bit generation methods could dramatically improve the generation rate and scalability by producing many random bits simultaneously.”
From Scalable parallel physical random number generator based on a superluminescent LED (2011) · cites this paper as [12]
Cites
Statistical mechanics of cellular automata
Wolfram, S. (1983) · Reviews of Modern Physics · doi:10.1103/revmodphys.55.601 · Cited by 3,059 · see citing works
Universality and complexity in cellular automata
Wolfram, S. (1984) · Physica D Nonlinear Phenomena · doi:10.1016/0167-2789(84)90245-8 · Cited by 1,938 · see citing works
Applications of Number Theory to Numerical Analysis
(1972) · Elsevier eBooks · doi:10.1016/c2013-0-11736-9 · Cited by 506 · see citing works
Random sequence generation by cellular automata
Wolfram, S. (1986) · Advances in Applied Mathematics · doi:10.1016/0196-8858(86)90028-x · Cited by 494 · see citing works
Random numbers generated by linear recurrence modulo two
Tausworthe, R. C. (1965) · Mathematics of Computation · doi:10.1090/s0025-5718-1965-0184406-1 · Cited by 432 · see citing works
Design for testability—A survey
Williams, T. W., & Parker, K. P. (1983) · Proceedings of the IEEE · doi:10.1109/proc.1983.12531 · Cited by 394 · see citing works
Cellular automata-based pseudorandom number generators for built-in self-test
Hortensius, P. D., McLeod, R. D., Pries, W., et al. (1989) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/43.31545 · Cited by 350 · see citing works
Self-citationFourier Analysis of Uniform Random Number Generators
Coveyou, R. R., & MacPherson, R. (1967) · JACM · doi:10.1145/321371.321379 · Cited by 301 · see citing works
A very fast shift-register sequence random number generator
Kirkpatrick, S., & Stoll, E. (1981) · Journal of Computational Physics · doi:10.1016/0021-9991(81)90227-8 · Cited by 254 · see citing works
Group Properties of Cellular Automata and VLSI Applications
Pries, Thanailakis, & Card (1986) · IEEE Transactions on Computers · doi:10.1109/tc.1986.1676709 · Cited by 161 · see citing works
Origins of randomness in physical systems
Wolfram, S. (1985) · Physical Review Letters · doi:10.1103/physrevlett.55.449 · Cited by 120 · see citing works
A Statistical Evaluation of Multiplicative Congruential Random Number Generators with Modulus 231— 1
Fishman, G. S., & Moore, L. R. (1982) · Journal of the American Statistical Association · doi:10.1080/01621459.1982.10477775 · Cited by 113 · see citing works
Fishman, G. S., & Moore, L. R. (1982) · Journal of the American Statistical Association · doi:10.2307/2287778 · Cited by 64 · see citing works
Parallel computation of non-deterministic algorithms in vlsi
Hortensius, P. D. (1987) · Mspace (University of Manitoba) · Cited by 18 · see citing works
Self-citationImportance sampling for Ising computers using one-dimensional cellular automata
Hortensius, P. D., CARD, H. C., McLeod, R. D., et al. (1989) · IEEE Transactions on Computers · doi:10.1109/12.24285 · Cited by 14 · see citing works
Self-citation
Flagged first, then by citations
Cited by
Sorted by citations
Scalable parallel physical random number generator based on a superluminescent LED
Li, X., Cohen, A. B., Murphy, T. E., & Roy, R. (2011) · Optics Letters · doi:10.1364/ol.36.001020 · Cited by 146 · see citing works
- Authors
- Hortensius, P. D., McLeod, R. D., & Card, H. C.
- Affiliations
- IBM Research - Thomas J. Watson Research Center (US)
- University of Manitoba (CA)
- ORCID
- McLeod, R.D.
- Venue
- IEEE Transactions on Computers
- Published
- 1989
- Volume
- 38
- Issue
- 10
- Pages
- 1466-1473
- ISSN
- 0018-9340 (ISSN-L)
- OpenAlex
- W2138274182
- Cited by
- 225
- References
- 15
- Citations by year
- 2026: 1 · 2025: 7 · 2023: 7 · 2022: 4 · 2021: 3 · 2020: 6 · 2019: 6 · 2018: 9 · 2017: 2 · 2016: 3 · 2015: 2 · 2014: 9 · 2013: 4 · 2012: 9
- FWCI
- 3.53
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- IEEE Transactions on Computers (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Cellular Automata and Applications
- Physical Sciences › Computer Science › Hardware and Architecture › VLSI and Analog Circuit Testing
- Physical Sciences › Engineering › Electrical and Electronic Engineering › VLSI and FPGA Design Techniques
- Keywords
- random number generation, cellular automata, pseudorandom sequence generation, VLSI architecture, built-in self-test
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
