4.2. Using Transition Mappings to De-Skew

Another technique, originally due to von Neumann [VON_NEUMANN], is to examine a bit stream as a sequence of non-overlapping pairs. One could then discard any 00 or 11 pairs found, interpret 01 as a 0 and 10 as a 1. Assume that the probability of a 1 is 0.5+E and that the probability of a 0 is 0.5-E, where E is the eccentricity of the source as described in the previous section. Then the probability of each pair is shown in the following table:

pair	probability
00	(0.5 - E)^2 = 0.25 - E + E^2
01	(0.5 - E)*(0.5 + E) = 0.25 - E^2
10	(0.5 + E)*(0.5 - E) = 0.25 - E^2
11	(0.5 + E)^2 = 0.25 + E + E^2

This technique will completely eliminate any bias but requires an indeterminate number of input bits for any particular desired number of output bits. The probability of any particular pair being discarded is 0.5 + 2E^2, so the expected number of input bits to produce X output bits is X/(0.25 - E^2).

This technique assumes that the bits are from a stream where each bit has the same probability of being a 0 or 1 as any other bit in the stream and that bits are uncorrelated, i.e., that the bits come from identical independent distributions. If alternate bits are from two correlated sources, for example, the above analysis breaks down.

The above technique also provides another illustration of how a simple statistical analysis can mislead if one is not always on the lookout for patterns that could be exploited by an adversary. If the algorithm were misread slightly so that overlapping successive bits pairs were used instead of non-overlapping pairs, the statistical analysis given would be the same. However, instead of providing an unbiased, uncorrelated series of random 1s and 0s, it would produce a totally predictable sequence of exactly alternating 1s and 0s.