hi, Using Transition Mappings to De-Skew
Randomness Recommendations for Security RFC 1750 An extract from it..... Another technique, originally due to von Neumann [VON NEUMANN], is to examine a bit stream as a sequence of non-overlapping pair | 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 at the expense of taking 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). Eastlake, Crocker & Schiller [Page 12] RFC 1750 Randomness Recommendations for Security December 1994 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 not correlated, i.e., that the bits are identical independent distributions. If alternate bits were 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 mis-read slightly so that overlapping successive bits pairs were used instead of non-overlapping pairs, the statistical analysis given is the same; however, instead of provided an unbiased uncorrelated series of random 1's and 0's, it instead produces a totally predictable sequence of exactly alternating 1's and 0's. A few doubts regarding the above. Another technique, originally due to von Neumann [VON NEUMANN], is to examine a bit stream as a sequence of non-overlapping pairs What do they mean by bit stream as a sequence of non-over lapping pairs? Also isn't idea-1 of my earlier post "Two idea's for random number generators" very similar to this? www.neo.ircsuper.net Wouldn't the problem in idea 1 be solved if I choose a bit stream as a sequence of non-over lapping pairs? If we choose bits that 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 not correlated, i.e., that the bits are identical independent distributions. Would n't idea 1 work? Regards Data. __________________________________________________ Do You Yahoo!? Yahoo! Games - play chess, backgammon, pool and more http://games.yahoo.com/