4.1 Source Coding

Shannon's Source Coding Theorem

Source coding is the process of encoding purely random information from the symbols $x\in \mathcal{X}$ into a bit string representation that uses the most compressed sequence of bits for which it is possible to recover the symbols.

Source coding is governed by the Source Coding Theorem, which states that any source coding scheme must use, on average, at least as many bits per symbol as the entropy of the source, ensuring that the encoded message retains all the original information.

Mathematically, for a sequence of symbols $X_1,X_2,\dots ,X_n$ with a random binary length $l(X)$, and an arbitrarily small $ϵ>0$, there is a source coding scheme from which the sequence can be recovered with high probability (i.e. $p>1-ϵ$), such that
$H(X)\le {\lim }_{n\to \infty }\mathbb{E}\left[\frac{l(X_1,\dots ,X_n)}{n}\right]\le H(X)+ϵ,$
where $\frac{l(X_1,\dots ,X_n)}{n}$ represents the average bits per symbol of the sequence.

Intuition