Re: Does this have a flaw in de-biasing an entropy stream?

David Eather wrote:

I've been scratching my head over this. I can't find a fault, but since
it seems to be twice as efficient as Shannon's method to de-bias a data
stream, I should be skeptical and cautious.

Shanon's method is to look at the bits in pairs 01 = 1, 10 = 0, and
discard 00, 11. This removes bias but if present increases correlations.

However, if I run a biased stream of 1's and 0's through an edge
triggered "T" flip-flop (toggles state from 1 to 0 or 0 to 1 on the
transition of the input) bias is removed completely (seems to be?)
although also with an increase in correlations. Am I missing anything ?

I ask because the T type flip-flop stuff can be done easily at 10's of
MHz which would be nice for a USB noise source.

Von Neumann's method takes a stream of bits that
- arrive at some rate R,
- are uncorrelated with each other,
- are biased with a 1:0 ratio of B,
and produces an output stream of bits that
- depart at an average rate of R*B/(1+B)^2,
- are uncorrelated with each other,
- are unbiased.

Now, what does your method do?
You seem to be claiming that your method does the
same thing but with a higher output rate; but your
method appears not to produce uncorrelated output
bits, so it's not the same thing. I say "appears"
because it's unclear how your output clock is generated,
i.e., when the next output bit is considered to be
available. Correct output clocking is essential to
Von Neumann's method, and is responsible for the
factor of B/(1+B)^2 in the output rate.

--
Peter Pearson
To get my email address, substitute:
nowhere -> spamcop, invalid -> net

.

Relevant Pages
Quantcast