Von-Neumann Debiasing

Von-Neumann debiasing can be used to remove entropy bias from a sequence of random or pseudo-random binary digits using a simple algorithm.

Given the set of binary digits:

$\begin{eqnarray*} B &=& \{ k | k \in \{ 0, 1 \} \} \\ \end{eqnarray*}$

and $S$ a sequence of arbitrary binary digits:

$\begin{eqnarray*} S &=& {\huge\bullet_{i=1}^{n}} k_{i},k_{i} \in B,n \ge 2 \end{eqnarray*}$

Let $r_{i}$ be a debiased random binary number such that:

$\begin{equation} r_{i} = \begin{cases} 0 & k_{i-1} = 0,k_{i} = 1 \\ 1 & k_{i-1} = 1,k_{i} = 0 \end{cases} \end{equation}$

The following table shows the possible outcomes for the random binary digit $r_{i}$ :

Index