Path: cactus.org!milano!uudell!news.dell.com!swrinde!mips!pacbell.com!att!bu. + edu!news.bbn.com!news.bbn.com!aboulang From: aboulang@bbn.com (Albert Boulanger) Newsgroups: sci.crypt Subject: Re: IBM-PC random generator, source included Message-ID:Date: 28 Jun 92 01:32:35 GMT References: <2673@accucx.cc.ruu.nl> <1992Jun23.080147.15804@cactus.org> + <2797@accucx.cc.ruu.nl> <1992Jun24.184848.21881@cactus.org> + <1992Jun25.033711.26770@massey.ac.nz> <2809@accucx.cc.ruu.nl> Reply-To: aboulanger@bbn.com Organization: BBN, Cambridge MA Lines: 65 NNTP-Posting-Host: kariba.bbn.com In-reply-to: nevries@accucx.cc.ruu.nl's message of 25 Jun 92 09:45:07 GMT In article <2809@accucx.cc.ruu.nl> nevries@accucx.cc.ruu.nl (Nico E de Vries) wr ites: Great. Thats excactly what I expected. Does anyone know WHY the "phase noise" (new term :-)) is nondeterministic? Has this been investigated? Are there papers which claim this? Here is some references I sent to Tony Patti on the Devil's staircase which can occur with non-linearly coupled oscillators. I do *not* know if in fact the Devil's staircase does occur in such systems of crystal oscillators. I had played with a similar scheme by combining the bits by XOR from just the bit flipping of 7 or more tight loops (based on some tests of randomness) on the BBN Butterfly a MIMD machine. **************************************************************** I think that the essence to how these multi-oscillator RNGs work is that they getenerate/couple to a thermodynamic heatbath of algorithmic randomness with a surprisingly small N. The way this happens is that the timing relationships for the clock streams are open to external influences -- thus one couples to a larger heatbath environment. Each oscillator is giving you a pretty nonrandom stream but it is nondeterministic in the sense that its timing relationship with the other oscillators is determined by a very high quality heat bath. This means that the randomness with two streams is pretty much 101010101010... but along the stream there will be longer runs of 0s and 1s. As one add streams these runs converge to the expected distributions for a random source. One could do a good RNG with two oscillators if one knew PI and set one to be PI times faster. (Maybe??) Since we don't have access to PI we make use of a heatbath that is a good substitute to the algorithmic randomness in a number like PI. Coupled oscillators can exhibit an interesting mode capturing behavior that is called Arnold's Tongues which leads to a mode hopping curve that is called the Devil's Staircase. Finally, the Fermi, Pasta, Ulam problem was a problem of coupled nonlinear oscillators and is pretty famous. (I think the coupling in this problem is too strong. The Devil's Staircase occurs in systems more like your coupled oscillators. It would be interesting to look for the Devil's Staircase in your system. The Circuits and Systems article has some info on who to set up test circuits.) (If you can't get to these, I will send the papers to you.) The staircase is described in "The Devil's Staircase", Per Bak, Physics Today, December 1986, 38-45 and "The Devil's Staircase: The Electrical Engineer's Fractal", Michael Kennedy, et al, IEEE Trans on Circuits and Systems, Vol 36 No 8 (Aug 1989), 1133-1139 Also you might want to borrow the book: "From Clocks to Chaos: The Rhythms of Life" Leon Glass and Michael Mackey Princeton University Press, 1988 (If you get anywhere on the theory, I would appreciate your acknowledgement in anything you write.)