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.)