The Question

A source emits a long message one letter at a time. Each letter is drawn from a finite alphabet $\mathcal{A}$ with the same distribution $p$ , independently of the others. The message is cut into blocks of $n$ letters, and each block is to be written as a string of bits from which it can be read back. Spending $nR$ bits on a block of $n$ letters is a rate of $R$ bits per letter. How small can the rate be made while the probability of reading a block back correctly still tends to one as the blocks grow long?

The Source and Its Entropy

The source is a probability distribution $p$ on the finite alphabet $\mathcal{A}$ : a nonnegative number $p(a)$ for each letter $a$ , with $\sum_{a} p(a) = 1$ .

The Shannon entropy $H(X)$ of a letter $X$ of the source, distributed according to $p$ , is the real number $H(X) = -\sum_{a \in \mathcal{A}} p(a) \log p(a),$ (1)^✦ with the natural logarithm, so that $H(X)$ is measured in nats.

Compression Schemes

A block of $n$ letters is an element $x = (x_1, \dots, x_n)$ of $\mathcal{A}^n$ , and a bit string of length $m$ an element of $\{0,1\}^m$ . A compression scheme $(C_n, D_n)$ for blocks of $n$ letters with $m$ bits is a pair of maps, a compression map $C_n$ and a decompression map $D_n$ , $C_n : \mathcal{A}^n \to \{0,1\}^m, \qquad D_n : \{0,1\}^m \to \mathcal{A}^n .$ (2)^✦ The scheme has rate $R$ when $m = \lfloor nR \rfloor$ , the largest integer not above $nR$ .

The success probability $P_{\mathrm{succ}}(C_n, D_n)$ of a scheme $(C_n, D_n)$ for the source $p$ is the probability that a block of the source comes back unchanged after compression and decompression, $P_{\mathrm{succ}}(C_n, D_n) = \sum_{x \in \mathcal{A}^n :\; D_n(C_n(x)) = x} p(x_1)\, p(x_2) \cdots p(x_n) .$ (3)^✦

The Claim

Theorem 1 (Shannon’s noiseless channel coding theorem). Let $p$ be a probability distribution on a finite alphabet $\mathcal{A}$ , with entropy $H(X)$ , and let $R$ be a real number. If $H(X) < R \log 2$ , there are compression schemes $(C_n, D_n)$ of rate $R$ , one for each block length $n$ , with $\lim_{n \to \infty} P_{\mathrm{succ}}(C_n, D_n) = 1 .$ (4)^✦ If $R \ge 0$ and $R \log 2 < H(X)$ , then for any compression schemes $(C_n, D_n)$ of rate $R$ , one for each block length $n$ , $P_{\mathrm{succ}}(C_n, D_n) \not\longrightarrow 1 \quad \text{as } n \to \infty .$ (5)^✦

In bits the entropy is $H(X)/\log 2$ .

What Is Checked

The theorem is stated over the Shannon entropy (1) of the letter distribution, over compression schemes (2) with $\lfloor nR \rfloor$ bits for blocks of $n$ letters, and over their success probability (3). What the library proves about these constructions is the theorem itself, both halves, (4) and (5).