Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!rutgers!sri-unix!hplabs!tektronix!uw-beaver!ubc-vision!alberta!calgary!radford
From: radford@calgary.UUCP (Radford Neal)
Newsgroups: comp.arch
Subject: Re: random number generator in hardware (XOR scheme)
Message-ID: <533@vaxb.calgary.UUCP>
Date: Tue, 25-Nov-86 15:05:58 EST
Article-I.D.: vaxb.533
Posted: Tue Nov 25 15:05:58 1986
Date-Received: Sun, 30-Nov-86 19:38:31 EST
References: <317@zuring.mcvax.UUCP> <267@bath63.UUCP> <7334@utzoo.UUCP> <3915@columbia.UUCP>
Organization: U. of Calgary, Calgary, Ab.
Lines: 62
Summary: Theoretical results

In article <3915@columbia.UUCP>, dupuy@amsterdam.columbia.edu (Alexander Dupuy) writes:
> > ME:
> > > How about taking the exclusive-or of several such random bit generators?
> > > This converges exponentially toward probability 1/2 as the number of
> > > bits xor'ed increases.
> >
> >Henry Spencer:
> >Only if the generators drift independently, which in general they won't:
> >things like temperature and aging effects will be similar for all.
> 
> Actually, the xor scheme works best if the generators all drift in the same
> direction.  Taking four generators which have drifted to 75% ones and 25%
> zeros...
>
> [ 47% vs. 53% results]
>
>     3% drift is not bad considering the generators are each 25% off.
> This works well for odd as well as even numbers of generators.  This
> setup is vulnerable to drift if generator pairs drift in _opposite_
> directions, but with careful design, the factors you mention will tend
> to prevent this.

Your results are in agreement with the general formula, which I think is

  p(zero) = ( 1 + (2z-1)^N ) / 2

where z is the original, drifted, zero probability (assumed the same for all
generators), and N is the number of bits XOR'ed.


To prove this:

  1 = 1^N = (z + (1-z)) ^ N = sum over i [ C(N,i) (1-z)^i z^(N-i) ]

  (z - (1-z)) ^ N = sum over i [ C(N,i) (1-z)^i z^(N-i) (-1)^i ]

subtracting these two expansions:

  1 - (z - (1-z)) ^ N = 2 * sum over odd i [ C(N,i) (1-z)^i z^(N-i) ]

but the right side is simply the sum of those terms of the binomial
probability distribution which will result in the XOR being one (odd
number of one's). So the probability of the result being one is:

  p(one) = ( 1 - (2z-1)^N ) / 2

and the probability of zero is thus:

  p(zero) = ( 1 + (2z-1)^N ) / 2


If the generators don't all drift in the same way, things may be 
more complicated, but I don't think the results are neccessarily bad.
Consider the XOR of two generators, one of which has zero probability
0.4 and the other of which has zero probability 0.7:

  p(zero) = 0.4*0.7 + 0.7*0.4 = 0.56

which is closer to 0.5 than either of the inputs.

    Radford Neal
    The University of Calgary