2
$\begingroup$

Suppose we have $n$ bits of random-looking data, and we want to encode it in such a way that instead of 1/2 the bits being 1's, we have (say) 3/4 the bits being 1's. The entropy of each bit in the new encoding is $-0.75\log_2(0.75)-0.25\log_2(0.25)\approx 0.81$, so we should be able to do it in about $1.23n$ bits.

(By 3/4 the bits being 1's, I mean that each bit should be indistinguishable from an event that happens with probability 3/4; as opposed to a long block of unbiased random bits followed by an equal length block of 1's.)

We could try, for each bit, put the next bit of the original data with probability 1/2, and put a 1 with probability 1/2. Then somehow include extra information about which bits encode the original data, and which are filler. But this reqiures at least $2n$ bits, well above the theoretical minimum. So how can the minimum actually be achieved?

$\endgroup$
1
$\begingroup$

Suppose you want exactly $3/4$ of the bits to be 1. If the encoded vector is of length $m$, it can be identified as a subset of $\{1,\ldots,m\}$ of size $(3/4)m$, of which there are $\binom{m}{(3/4)m}$. If $\binom{m}{(3/4)m} \geq 2^n$ then you can encode every $n$-bit string as such a subset using the technique of binomial encoding. Since $\binom{m}{(3/4)m} \approx 2^{mh(3/4)}$, this works as long as $m \gtrsim n/h(3/4) \approx 1.23n$.

Binomial encoding relies on Pascal's identity $$ \binom{a}{b} = \binom{a-1}{b-1} + \binom{a-1}{b}. $$ To encode a number $x$ in the range $[0,\binom{a}{b})$, we act as follows:

  1. If $x < \binom{a-1}{b-1}$ then we recursively encode $x$ as a subset $S$ of $\{1,\ldots,a-1\}$ of size $b-1$, and output $S \cup \{a\}$.
  2. If $x \geq \binom{a-1}{b-1}$ then we recursively encode $x - \binom{a-1}{b-1}$ as a subset $S$ of $\{1,\ldots,a-1\}$ of size $b$, and output $S$.

The procedure can easily be reversed (exercise).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.