There is an interesting trick to improve the randomness of an input that has
a bias towards 0 or 1.

For example, if you build a zener diode based noise generator to create a
truly random data stream it will have a tendency to generate more ones than
zeros, or vice versa. This is just a consequence of the way it is biased.
Rather than trying to get the bias just right and holding it there across
temperature, voltage, etc. variations; you can do the following:

Obtain _two_ INDEPENDENT samples from the RNG, lets call them A and B in
order to get _one_ bit of the final result.

If the two samples are the same then you have a zero.

If the two samples are different then you have a one.

To understand how this works:

Given x = P(A=1) = P(B=1)

This means x is the probability that A is a one, which is the same as the
probability that B is a one. Thus x should be somewhere near, but not
exactly equal to 0.5.

Then (1-x) = P(A=0) = P(B=0)

This follows from the fact that if A isn't a one then it has to be a zero
(and the same for B).

So, to compute P(OUT=1):

P(A=1 and B=1) = x * x = x^2
P(A=0 and B=0) = (1-x) * (1-x) = 1 - 2x + x^2

Thus, P(OUT=1) = P(A=1 and B=1) + P(A=0 and B=) = 1 - 2x + x^2

And, to compute P(OUT=0):

P(A=0 and B=1) = x * (1-x) = x - x^2
P(A=1 and B=0) = (1-x) * x = x - x^2

Thus, P(OUT=0) = P(A=0 and B=1) + P(A=1 and B=0) = x - 2x^2

Now lets look at some particular values for 'x':

First, as expected, when P(A=1) = 0.5, then P(OUT=1) = P(OUT=0) = 0.5

Here is a table of some more values:

      P(A=1) P(OUT=1) P(OUT=0)
      0.5 0.5 0.5
      0.1 0.82 0.18
      0.2 0.68 0.32
      0.3 0.58 0.42
      0.4 0.52 0.48
      0.5 0.5 0.5
      0.6 0.52 0.48
      0.7 0.58 0.42
      0.8 0.68 0.32
      0.9 0.82 0.18


Notice how that whether P(A=1) is less than or greater than 0.5, P(OUT=1) is
closer to 0.5 than P(A=1).

Now for the really neat trick!!

You can apply this algorithm recursively to get as close as you want to an
unbiased output stream, even with a very biased input source. For example,
start with 8 raw inputs, say with P(A=1) = 0.3. Using these you can generate
four output bits with  P(OUT=1) = 0.58

Now take those four bits and feed then through the algorithm a second time,
to create two bits. In this case we have P(A=1) = 0.58, giving us P(OUT=1) =
0.5128.

Finally, take those two bits throught the algorithm one more time, to create
a single final output bit. For this pass we have P(A=1) = 0.5128, giving us
P(OUT=1) = 0.500328

Notice how in just 3 passes we took a strongly biased input and got a rather
unbiased output.

One more table. Here is a table showing what happens as we perform nine
passes of the algorithm, starting with P(A=1) = 0.01 (now that is VERY
biased!)

      P(A=1) P(OUT=1) P(OUT=0) PASS
      0.01 0.9802 0.0198 1
      0.9802 0.961184 0.038816 2
      0.961184 0.925382 0.074618 3
      0.925382 0.861899 0.138101 4
      0.861899 0.761942 0.238058 5
      0.761942 0.637227 0.362773 6
      0.637227 0.537662 0.462338 7
      0.537662 0.502837 0.497163 8
      0.502837 0.500016 0.499984 9


Note that, since we have nine passes of the algorithm we will need 2^9 = 512
raw input bits to compute each output bit.

Bob Ammerman
RAm Systems

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics