ciphergoth.org > Software > Unbiasing

Random data unbiasing

This algorithm converts integers representing the duration of successive clicks from a Geiger counter into unbiased, uncorrelated random bits. Detailed description.

geiger-unbiaser-python
A simple implementation of the algorithm in Python.
geiger-unbiaser.c
a C implementation of the same algorithm, rather more complex but much faster.
jjsh-unbiaser
A Python implementation of an alternative strategy for the same job, due to Juels, Jakobsson, Shriver, and Hillyer.
jjsh.c
An optimised C implementation of that strategy, based on GNU MP.

A simpler problem is that of converting a stream of independent coin flips with a fixed but unknown bias to a stream of independent unbiased random bits. An asymptotically optimal strategy for this is the Advanced Multi-Level Strategy (AMLS), first proposed by Yuval Peres. AMLS is used as a component of the algorithm above. Here are some implementations of that strategy:

simple-amls
in Python, but try reading it even if you don't speak Python. It's a very straightforward implementation of the strategy, with a simple test rig.
amls.c
a C implementation of the same strategy. This uses a rather cunning technique due to corners@sbcglobal.net which overwrites the input bits array rather than using auxiliary storage to generate the output bits recursively; Peres informs me he presented this same technique in the very first lecture describing the AMLS. Version 0.5.
AMLS.cpp
corners' original version of the above code, in C++ (really C). "You can do anything you want with it. It comes with a "garbage man's guarantee". Satisfaction guaranteed, or double your garbage back. (smile)"
amls-unbiasing
in Python. A more complex version that produces bits asynchronously; you push input bits into it and it pushes output bits upstream. Extremely space inefficient.
amls-extract.c
a similar C implementation; call "amls_accept_bit(1, bit, &output);" every time you get a biased random bit, and it will write as many output bits as it can to the output. It also uses fixed storage, so it doesn't reach the asymptotically perfect efficiency, but in practice that doesn't really matter. Version 0.1.
amls-2n2n1.txt
amls-fib.txt
Two implementations by Benjamin Goldberg, goldbb2@earthlink.net.

Papers

How to Turn Loaded Dice into Fair Coins
Ari Juels, Markus Jakobsson, Elizabeth Shriver, Bruce K. Hillyer, IEEETIT: IEEE Transactions on Information Theory, 1998.
Iterating von Neumann's Procedure for Extracting Random Bits [PDF]
Yuval Peres, The Annals of Statistics, 1992, pp 590-597. The paper which first presented the AMLS. From Yuval Peres' research archive.
Tossing a Biased Coin [PDF]
Teaching notes by Michael Mitzenmacher describing the Advanced Multi-Level Strategy - a very good introduction. Six pages. From this course.

Links

ciphergoth.org > Software > Unbiasing