Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!mcvax!lambert
From: lambert@mcvax.uucp (Lambert Meertens)
Newsgroups: comp.arch
Subject: Re: random number generator in hardware
Message-ID: <7160@boring.mcvax.UUCP>
Date: Mon, 24-Nov-86 04:29:40 EST
Article-I.D.: boring.7160
Posted: Mon Nov 24 04:29:40 1986
Date-Received: Mon, 24-Nov-86 22:35:50 EST
References: <317@zuring.mcvax.UUCP> <267@bath63.UUCP> <7334@utzoo.UUCP>
Reply-To: lambert@boring.uucp (Lambert Meertens)
Organization: CWI, Amsterdam
Lines: 37
Apparently-To: rnews@mcvax


>>> My understanding is that the problem is avoiding bias in the resulting
>>> numbers...
>> 
>> 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.
>
> Only if the generators drift independently, which in general they won't:
> things like temperature and aging effects will be similar for all.

By xor'ing cumulatively a single random bit generator another random
bit generator is obtained with guaranteed probability 1/2.  There may
still be a serial correlation because of bias in the original one, but
unless it was far of the mark, that drops off fast over larger time
spans.  Now, xor'ing several of these "cumulative" generators makes the
serial-correlation effect drop exponentially with the # of generators
involved.  It does not matter if the original set drifts together.

A technique that has mentioned on the net before to turn a random bit
generator with bias but whose bits are independent into another one
with independent bits without bias is to group the output in twos,
discard 00's and 11's, and turn 10's and 01's into 0's and 1's,
respectively:

    111101100100001101010101111010101001110110000100000000010100
     = =\|\|\| = = =\|\|\|\| =\|\|\|\|\| =\|\| =\| = = = =\|\| =
         1 0 1       1 1 1 1   0 0 0 0 1   1 0   1         1 1  

This is good only if the consuming process can afford to wait for the
next output bit.  The random device can start to compute its next output
immediately after it has been polled, and with some engineering tricks
you can make sure that there is always an output bit ready with epsilon
probability that it was not theoretically fully random.

-- 

Lambert Meertens, CWI, Amsterdam; lambert@mcvax.UUCP