Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

VLSI implementation of Tausworthe random number generator for parallel processing environment

VLSI implementation of Tausworthe random number generator for parallel processing environment

For access to this article, please select a purchase option:

Buy article PDF
£12.50
(plus tax if applicable)
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IEE Proceedings E (Computers and Digital Techniques) — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

A fast Tausworthe-type random number generator has been implemented as a VLSI circuit on silicon for Monte-Carlo simulation purposes in a parallel multiprocessor system environment. The generator, which has uniform distribution, has been contructed for use as a peripheral device to be connected with each processor unit. General considerations for parallel random number generation are discussed and desirable properties are reviewed as a starting point for a VLSI implementation. The hardware design is based on the maximal length shift register sequences. It involves concurrent architecture in which a single shift operation is equivalent to 16 shifts in the original shift register unit. A new 16-bit random number is generated during each shifting operation. The chip is fully microprocessor bus compatible with a 16-bit bidirectional data bus and three I/O control lines. The methods of shift register sequence segmentation are also reviewed. Practical aspects for parallel processing system purposes are given. The generator has been submitted to a comprehensive set of statistical tests.

References

    1. 1)
      • C.P. Downing . Proposal for a digital pseudorandom number generator. Electron. Lett. , 11 , 435 - 436
    2. 2)
      • Saarinen, J., Kaski, K.: Electronics Laboratory Report 7–86, 1986.
    3. 3)
      • B.J. Collings , G.B. Hembree . Initializing generalized feedback shift register pseudo-random number generators. J. Assoc. Comput. Mach. , 4 , 706 - 711
    4. 4)
      • J.P.R. Tootill , W.D. Robinson , A.G. Adams . The runs up- and down-performance of Tausworthe pseudo-random number generator. J. Assoc. Comput. Mach. , 3 , 381 - 399
    5. 5)
      • K. Binder . (1983) , Applications of the Monte Carlo methods in statistical physics.
    6. 6)
      • N. Zierler , J. Brillhart . On primitive trinomials (mod 2). Inf. Control , 541 - 554
    7. 7)
      • D. Logan , C. Maples , A. Wouk . (1986) Scientific applications and numerical algorithms on the Midas multiprocessor system, New computing environments: parallel, vector and systolic.
    8. 8)
      • S.H. Tsao . Generation of delayed replicas of maximal-length linear binary sequences. Proc. IEE , 11 , 1803 - 1806
    9. 9)
      • P.D. Wasserman . (1989) , Neural computing, theory and practice.
    10. 10)
      • K.P. Yiu . A simple method for the determination of feedback shift register connections for delayed maximal-length sequences. Proc. IEEE , 4 , 537 - 538
    11. 11)
      • K. Binder . (1986) , Monte Carlo methods in statistical physics.
    12. 12)
      • J. Saarinen , K. Kaski , J. Viitanen . A Parallel multi-processor system for Monte Carlo simulations in statistical physics. Rev. Sci. Instrum. , 9 , 2981 - 2991
    13. 13)
      • O. Percus , M. Kalos . Random number generators for MIMD parallel processors. J. Parallel Distrib. Comput. , 477 - 497
    14. 14)
      • J.E. Marshall , B. Ireland , K.J. Latawiec . New method of generation of shifted linear pseudorandom sequences. Proc. IEE , 2
    15. 15)
      • R.C. Tausworthe . Random numbers generated by linear recurrency modulo two. Mat. Comput. , 201 - 209
    16. 16)
      • G. Fox , M. Johnson , G. Lyzenga , S. Otto , J. Salmon , D. Walker . (1988) , Solving problems on concurrent processors; general techniques and regular problems.
    17. 17)
      • A.B. Gardiner . Logic PRBS delay calculator and delayed-version generator with automatic delay-changing facility. Electron. Lett. , 5 , 123 - 125
    18. 18)
      • J.J. Narraway . Probability machines and shift-register sequence segmentation. IEE Proc. G , 5 , 209 - 215
    19. 19)
      • C.M. Rader , L.R. Rabiner , R.W. Schafer . A fast method of generating digital random numbers. Bell Syst. Tech. J. , 2303 - 2310
    20. 20)
      • J. Tomberg , J. Saarinen , K. Kaski . A fast random number generator chip for microprocessor system. Norchip News , 3 - 4
    21. 21)
      • K.S. Sastri . Generation of delayed replicas of linear p-level m-sequences. Int. J. Syst. Sci. , 5 , 409 - 416
    22. 22)
      • K.J. Latawiec . New method of generation of shifted linear pseudorandom binary sequences. Proc. IEE , 8 , 905 - 906
    23. 23)
      • A. Hoogland , J. Spaa , B. Selman , A. Compagner . A special-purpose processor for the Monte Carlo simulation of Ising Spin Systems. J. Computational Physics , 250 - 260
    24. 24)
      • B. Ireland , J.E. Marshall . Matrix method to determine shift-register connections for delayed binary sequences. Electron. Lett. , 21 , 467 - 468
    25. 25)
      • D.H. Green . Nonlinear product-feedback shift registers. Proc. IEE , 4 , 681 - 686
    26. 26)
      • N. Zierler , J. Brillhart . On primitive trinomials (mod 2). Inf. Control , 566 - 569
    27. 27)
      • R.B. Pearson , J.L. Richardson , D. Toussaint . A fast processor for Monte Carlo simulation. J. Comput. Phys. , 241 - 249
    28. 28)
      • M.T.G. Hughes . Transition-matrix construction for pseudorandom binary-sequence generators. Electron. Lett. , 19 , 417 - 419
    29. 29)
      • A.N. van Luyn . Shift-register connections for delayed versions of m-sequences. Electron. Lett. , 22 , 713 - 715
    30. 30)
      • T.G. Lewis , W.H. Payne . Generalized feedback shift register pseudorandom number algorithm. J. Assoc. Comput. Mach. , 3 , 456 - 468
    31. 31)
      • J.E. Marshall , B. Ireland , B.G. Bajoga , K.J. Latawiec . Correspondence to new method of generation of shifted linear pseudorandom binary sequences. Proc. IEE , 4
    32. 32)
      • R.W. Schafer , R.M. Mersereau , T.P. Barnwell . (1983) , TMS32010 user's guide.
    33. 33)
      • P. Fredrickson , R. Hiromoto , T.L. Jordon , B. Smith , T. Warnock . Pseudorandom trees in Monte Carlo. Parallel Comput.
    34. 34)
      • D.E. Knuth . (1981) , The art of computer programming, Vol. 2: Semi-numerical algorithms.
    35. 35)
      • N. Zierler . Primitive trinomials whose degree is a Mersenne exponent. Inf. Control , 67 - 69
    36. 36)
      • N.D. Deans , D.P. Mann . (1982) An Improved generation technique for random number sequences, Mathematics and computers in simulation XXIV.
    37. 37)
      • B.W. Kernighan , D.M. Ritchie . (1978) , The C Programming language.
    38. 38)
      • W.J. Hurd . Efficient generation of statistically good pseudonoise by linearly interconnected shift registers. IEEE Trans. , 2 , 146 - 152
    39. 39)
      • D.G. Maritsas , A.C. Arvillas , A.C. Bounas . Phase shift analysis of linear feedback shift register structures generating pseudorandom sequences. IEEE Trans. , 7 , 660 - 669
    40. 40)
      • R.P. Lippmann . An introduction to computing with neural nets. IEEE ASSP Mag. , 4 - 22
    41. 41)
      • P.D. Roberts , A.C. Davies , S.H. Tsao . Discussion on generation of delayed replicas of maximal-length binary sequences. Proc. IEE , 4 , 702 - 704
    42. 42)
      • Barel, M.: `Fast hardware random number generator for the Tausworthe sequence', Proc. 16th Annual Simulation Symp., 16–18 March 1983, Tampa, Florida, p. 121–135.
    43. 43)
      • S.M. Sze . (1988) , VLSI technology.
    44. 44)
      • A.C. Davies . Further notes on delayed versions of linear binary sequences. Electron. Lett. , 7 , 190 - 191
    45. 45)
      • M.G. Hartley . Development design and test procedure for random generators using chain-codes. Proc. IEE , 1 , 22 - 34
    46. 46)
      • J.R.B. Whittlesey . A comparison of the correlational behavior of random number generators for the IBM 360. Commun. ACM , 641 - 644
    47. 47)
      • University of Washington, Dept. of Computer Science, Seattle, Ousterhout, J.: `Editing VLSI circuits with CAESAR', 1985, VLSI Design Tools Reference Manual, Release 3.0.
    48. 48)
      • D.G. Maritsas , A. Bounas . Direct determination of feedback shift register connections for delayed m-sequences generation. Electron. Lett. , 10 , 308 - 310
    49. 49)
      • J.L. Perry , R.W. Schafer , L.R. Rabiner . A digital hardware realization of a random number generator. IEEE Trans. , 4 , 236 - 240
    50. 50)
      • J.P.R. Tootill , W.D. Robinson , D.J. Eagle . An asymptotically random Tausworthe sequence. J. Assoc. Comput. Mach. , 3 , 469 - 481
    51. 51)
      • J.L. Douce . Delayed versions of m-sequences. Electron. Lett. , 12
    52. 52)
      • A.J. Miller , A.W. Brown , P. Mars . A simple technique for the determination of delayed maximal length linear binary sequences. IEEE Trans. , 8 , 808 - 811
    53. 53)
      • R.W. Hockney , J.W. Eastwood . (1981) , Computer simulations using particles.
    54. 54)
      • S.W. Golomb . (1982) , Shift register sequences.
    55. 55)
      • A.C. Davies . Delayed versions of maximal-length linear binary sequences. Electron. Lett. , 3 , 61 - 62
    56. 56)
      • B. Ireland , J.E. Marshall . Matrix method to determine shift-register connections for delayed binary sequences. Electron. Lett. , 15 , 309 - 310
    57. 57)
      • J.R. Jordan , B. Kiani-Shabestari . Deriving delayed sequences from pseudo-random-noise generators using exclusive NOR feedback. IEE Proc. G , 3 , 89 - 93
http://iet.metastore.ingenta.com/content/journals/10.1049/ip-e.1991.0019
Loading

Related content

content/journals/10.1049/ip-e.1991.0019
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
This is a required field
Please enter a valid email address