This shows you the differences between two versions of the page.
Previous revisionNext revision | |||
— | fuss:computer_science [2021/10/07 05:02] – office | ||
---|---|---|---|
Line 1: | Line 1: | ||
+ | ====== Von-Neumann Debiasing ====== | ||
+ | |||
+ | 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}$: | ||
+ | ^ $k_{i-1}$ ^ $k_{i}$ ^ $r_{i}$ ^ | ||
+ | | 0 | 0 | discard | | ||
+ | | 0 | 1 | 0 | | ||
+ | | 1 | 0 | 1 | | ||
+ | | 1 | 1 | discard | | ||
+ | |||
+ | ====== Index ====== | ||
+ | |||
+ | {{indexmenu> |