Information Measures and Source Coding

Surprise and Self-Information

Information, in Shannon's sense, is tied to surprise. If a weather forecast says "sunny in the Sahara," you learn almost nothing, because you expected it. If it says "snow in the Sahara," you learn a great deal. The less probable an outcome, the more information its occurrence conveys.

For an event $x$ with probability $p(x)$, the self-information is defined as

$I(x) = \log_2 \frac{1}{p(x)} = -\log_2 p(x)$

The base-2 logarithm makes the unit the bit: one bit is the information in a fair coin toss. The logarithm is chosen so that information from independent events adds, since probabilities multiply. A certain event with $p = 1$ carries zero information, and an event with very small $p$ carries a large amount. The curve below shows how quickly self-information grows as probability shrinks.

Self-information describes a single outcome. A source produces a stream of outcomes, and what matters for compression is the typical amount of information per symbol. Averaging self-information over all outcomes leads directly to entropy, which is the subject of the next section.

Entropy as the Average Uncertainty of a Discrete Source

Consider a discrete memoryless source that emits symbols $x_1, x_2, \ldots, x_M$ with probabilities $p_1, p_2, \ldots, p_M$. The entropy of the source is the expected self-information of its output:

$H(X) = -\sum_{i=1}^{M} p_i \log_2 p_i \quad \text{bits per symbol}$

Entropy is the average number of bits needed to describe a symbol once the source statistics are known. It is zero when one symbol is certain, because then there is nothing to decide. It is largest when all $M$ symbols are equally likely, in which case $H(X) = \log_2 M$. This maximum is the reason uniform sources are the hardest to compress.

The binary case shows the shape of this behaviour clearly. For a source with two symbols, of probabilities $p$ and $1-p$, the entropy is the binary entropy function $H(p) = -p\log_2 p - (1-p)\log_2(1-p)$. It peaks at 1 bit when $p = 0.5$ and falls to zero at the extremes.

Entropy is a property of the source alone, not of any code. It sets the benchmark against which every code is measured. A code that uses fewer bits per symbol on average than $H(X)$ is impossible to construct for lossless compression, and this is the content of the source coding theorem below.

Joint, Conditional, and Average Mutual Information

Real systems involve two random variables at once, such as an input $X$ and an output $Y$ of a channel, or a pixel and its neighbour. The joint entropy $H(X,Y)$ measures the uncertainty of the pair. The conditional entropy $H(X \mid Y)$ measures the uncertainty left in $X$ after $Y$ is known. These are linked by the chain rule $H(X,Y) = H(X) + H(Y \mid X)$.

The central quantity is the average mutual information, which measures how much knowing $Y$ reduces the uncertainty about $X$:

$I(X;Y) = H(X) - H(X \mid Y)$

Mutual information is symmetric, so $I(X;Y) = I(Y;X)$. It is zero when $X$ and $Y$ are independent, because then knowing $Y$ tells you nothing about $X$. It never exceeds $H(X)$. The Venn-style picture below summarises how these quantities relate.

This is the bridge to channel coding. When $X$ is the transmitted symbol and $Y$ the received symbol, the mutual information measures how much of the message survives the channel. Maximising this quantity over input distributions leads to channel capacity, which is covered in the module on channel models and capacity.

Information Measures for Continuous Random Variables

Many sources, such as speech samples or sensor readings, take values in a continuum. The natural extension of entropy replaces the sum with an integral over a probability density $f(x)$. This quantity is called differential entropy:

$h(X) = -\int f(x)\log_2 f(x)\,dx$

Differential entropy behaves differently from discrete entropy in two important ways. It can be negative, since a density can exceed 1 over a narrow range. It also changes under scaling: $h(aX) = h(X) + \log_2|a|$, so it is not an absolute measure of uncertainty in the way $H(X)$ is. The mutual information $I(X;Y)$ between continuous variables, however, remains non-negative and invariant under such changes, which is why it, rather than differential entropy alone, is the quantity that carries operational meaning.

For a Gaussian random variable with variance $\sigma^2$, the differential entropy takes a particularly clean form, and among all densities with a given variance it is the largest. This is the reason the Gaussian appears as the worst-case noise in the capacity results that follow in the channel module. The detailed derivations, the scaling properties, and the relation to discrete entropy as a quantised limit belong to the dedicated article on this topic.

The Source Coding Theorem

A source code maps each source symbol to a binary string, called a codeword. The code is useful only if the original message can be recovered from the encoded bits. The class that is practical for real-time decoding is the prefix code, in which no codeword is the beginning of another. Prefix codes can be decoded instantly, reading bits until a complete codeword appears.

If a symbol $x_i$ receives a codeword of length $l_i$, the average codeword length is $\bar{L} = \sum_i p_i l_i$. Shannon's source coding theorem states that for a discrete memoryless source, the best achievable average length satisfies

$H(X) \le \bar{L} < H(X) + 1$

The lower bound is a hard limit: no lossless code can average fewer bits per symbol than the entropy. The upper bound says that a good code is never more than one bit per symbol above the limit. The gap of less than one bit can be reduced further by coding blocks of several symbols together, so that the average length per symbol approaches $H(X)$ as the block length grows. Whether a prefix code with given lengths exists at all is governed by the Kraft inequality, which is developed in the child article.

The theorem makes entropy an operational quantity. It is not merely a formula for average surprise but the exact compression limit for lossless coding. The next section shows a practical construction that comes very close to this limit.

Huffman Codes and Their Efficiency

Huffman coding builds an optimal prefix code for a known set of symbol probabilities. The idea is greedy and easy to state. Repeatedly take the two least probable symbols, merge them into a single node whose probability is their sum, and continue until one node remains. Reading the branch labels from the root to each leaf then gives the codewords. Frequent symbols end up near the root with short codewords, and rare symbols end up deep in the tree with long ones.

Take a source with symbols A, B, C, D having probabilities 0.4, 0.3, 0.2, 0.1. Merging C and D gives 0.3, then merging B with that node gives 0.6, and finally merging A with that gives 1. The resulting codewords are A = 0, B = 10, C = 110, D = 111. The average length is $\bar{L} = 0.4(1) + 0.3(2) + 0.2(3) + 0.1(3) = 1.9$ bits per symbol. The entropy is approximately 1.846 bits, so the bound $1.846 \le 1.9 < 2.846$ holds.

The efficiency of a code is $\eta = H(X)/\bar{L}$, which here is about 97 percent. The remaining gap is the redundancy $\bar{L} - H(X)$, about 0.054 bits per symbol. Huffman's method is optimal among symbol-by-symbol prefix codes, meaning no other such code achieves a smaller average length for the same distribution. Its limitation is that it needs the probability model in advance, and it cannot beat the one-bit gap without grouping symbols into blocks. Adaptive and arithmetic methods address these limitations, and the child article details the construction, the proof of optimality, and the choice of blocks.