S5-1.4 Information Theory & Source Coding

What this is and why it exists

Before Shannon, nobody could say how much a message could be compressed. Nobody could say how fast a noisy link could carry data reliably either. This topic gives both answers as numbers.

The starting move is a definition. Information is surprise. An event certain to happen tells you nothing when it happens.

The vocabulary

• Self-information — the surprise in one outcome. It is the logarithm, base two, of one divided by that outcome's probability.
• Entropy — the average self-information of a source, measured in bits per symbol.
• Source coding — replacing symbols with codewords so that the average codeword is short.
• Prefix code — a code in which no codeword is the start of another, so a stream can be read without markers.
• Shannon-Fano coding — a code built by repeatedly splitting the symbol list into two nearly equal halves of probability.
• Huffman coding — a code built by repeatedly merging the two least likely symbols. It is optimal symbol by symbol.
• Discrete memoryless channel — a channel whose output depends only on the present input. It is described by a table of transition probabilities.
• Mutual information — how much the received symbol tells you about the transmitted one.
• Channel capacity — the largest mutual information the channel allows, over all input distributions.
• Error control coding — adding structured redundancy so errors can be detected or corrected.

The mental model

Entropy first. A source that always sends the same symbol has zero entropy, because nothing about it is ever a surprise. A source with equally likely symbols has the highest entropy for its alphabet size. Everything else falls between. Entropy is measured in bits per symbol, and that unit is the whole point. It is a length, so it can be compared against a real code.

The source coding theorem supplies the comparison. It says the average codeword length cannot be shorter than the entropy, and that you can get as close to it as you like. Without that theorem the codes below would be recipes with nothing to be judged against.

Shannon-Fano is the first practical code. Sort the symbols by probability. Split them into two groups of nearly equal probability. Give one group a leading zero and the other a leading one, then repeat inside each group. It is quick to do by hand, and it is not quite optimal.

Huffman closes that gap. Work from the bottom instead of the top. Repeatedly take the two least likely symbols and merge them into one node whose probability is their sum. Continue until one node remains, then read the tree back to get the codewords. It is optimal for symbol-by-symbol coding, and it is worth building trees by hand until the construction is automatic.

Now cross to the receiving end. A discrete memoryless channel is a table. For each symbol you send, it gives the probability of each symbol coming out. Real links are several stages, so cascaded channels matter as much as single ones.

Mutual information measures what survives that table. It is the uncertainty about the input, minus the uncertainty that remains once you have seen the output. A perfect channel leaves nothing uncertain, so mutual information equals the source entropy. A useless channel leaves everything uncertain, so mutual information is zero.

Capacity is the largest mutual information the channel permits, taken over every way of choosing the input probabilities. It is a property of the channel alone.

Keep the two great results apart, because they are routinely mixed up. Source coding says how far you can compress. Channel capacity says how fast you can send and still be reliable. Capacity promises that a reliable code exists below that rate. It does not build one. Error control coding is the work of getting near the bound in practice.

What you should now be able to explain or do

Compute the entropy of a discrete source. Build Shannon-Fano and Huffman codes by hand and compare their average lengths against the entropy. Explain why a prefix code needs no separators. Read a channel transition table and compute mutual information from it. State the two theorems separately, in your own words, without merging them.

Check yourself