Shannon's noiseless coding theorem places an upper and a lower bound on the minimal possible expected length of codewords as a function of the entropy of the input word (which is viewed as a random variable) and of the size of the target alphabet.

Shannon's statement

Let X be a random variable taking values in some finite alphabet Σ₁ and let f be a decipherable code from Σ₁ to Σ₂ where ∣Σ₂^*∣ = a. Let S denote the resulting wordlength of f(X).

If f is optimal in the sense that it has the minimal expected wordlength for X, then

$$\frac{H(X)}{\log_2 a} \leq \mathbb{E}S < \frac{H(X)}{\log_2 a} +1$$

Proof

Let s_i denote the wordlength of each possible x_i (i = 1, …, n). Define q_i = a^− s_i/C, where C is chosen so that ∑q_i = 1.

Then

$$\begin{matrix} H(X) &=& - \sum_{i=1}^n p_i \log_2 p_i \\ && \\ &\leq& - \sum_{i=1}^n p_i \log_2 q_i \\ && \\ &=& - \sum_{i=1}^n p_i \log_2 a^{-s_i} + \sum_{i=1}^n \log_2 C \\ && \\ &\leq& - \sum_{i=1}^n - s_i p_i \log_2 a \\ && \\ &\leq& - \mathbb{E}S \log_2 a \\ \end{matrix}$$

where the second line follows from Gibbs' inequality and the third line follows from Kraft's inequality: C = ∑_i = 1ⁿa^− s_i ≤ 1 so logC ≤ 0.

For the second inequality we may set

s_i = ⌈ − log_ap_i⌉

so that

$$- \log_a p_i \leq s_i < -\log_a p_i + 1$$

and so

a^− s_i ≤ p_i

and

∑a^− s_i ≤ ∑p_i = 1

and so by Kraft's inequality there exists a prefix-free code having those wordlengths. Thus the minimal S satisfies

$$\begin{matrix} \mathbb{E}S & = & \sum p_i s_i \\ && \\ & < & \sum p_i \left( -\log_a p_i +1 \right) \\ && \\ & = & \sum - p_i \frac{\log_2 p_i}{\log_2 a} +1 \\ && \\ & = & \frac{H(X)}{\log_2 a} +1 \\ \end{matrix}$$

Category: Quantum Information Theory