Shannon information theory and coding
A human genome is about 3.1 billion letters, each A, C, G or T: at two bits per letter, about 780 megabytes. Specialized compressors squeeze it to well under two bits per letter, because the sequence is not random: some letters and patterns are more common than others. How far can compression go? In 1948 Claude Shannon, at Bell Labs, answered that question for any source of data with a single number, its entropy, and in the same paper found the maximum rate at which information can cross a noisy channel. Quantum information theory is built on his foundations.
On the plate: the measured entropy of a sample of text, a sample of DNA, and random letters.
Entropy
A source emits symbol with probability . Shannon’s entropy is
It is the average surprise per symbol. A fair coin has 1 bit; a coin that lands heads 99% of the time, 0.08 bits; four equally likely DNA bases, 2 bits. Choose a sample: , , . The plate counts each symbol and computes the entropy of the single-letter frequencies. English letters carry about 4.1 bits each by frequency alone, well below the of uniform letters and space; using context, Shannon estimated about 1 bit. Established
The compression limit
Shannon’s source coding theorem: a long message of symbols can be compressed to about bits and no fewer without loss. The reason is typical sequences: of all possible messages, almost all the probability falls on about of them, each with probability near . Number those and you need only bits. A Huffman code, giving frequent symbols short codewords and rare ones long, comes within one bit per symbol of the limit. The same idea, quantized, is Schumacher compression (Chapter 105), where qubits replace bits.
Mutual information and capacity
How much does knowing tell you about ? The mutual information . A noisy channel turns inputs into uncertain outputs, and its capacity is the largest mutual information any input distribution can achieve. For the binary symmetric channel, which flips each bit with probability ,
Set the flip probability to 0.11. Shannon’s noisy channel coding theorem says that at any rate below , codes exist that make errors as rare as you like; above it, none do. Remarkably, a channel that flips 11% of bits can still carry half a bit per use, reliably. It took until the 1990s, with turbo and LDPC codes, to get close to his limit in practice; your phone does so now. Established
Why this matters for what comes
Quantum information inherits Shannon’s questions and changes the answers. A qubit can hold a continuum of states but yields at most one bit when read (Chapter 96). Quantum channels can carry classical information, quantum information, or private information, each with its own capacity, and entanglement can double some of them (Chapter 103). Quantum entropy (Chapter 105) reduces to Shannon’s for classical states. And in Part Four, the entropy of DNA sequences and of neural spike trains will reappear in biology.
What you now have
Shannon entropy, the compression limit and typical sequences, Huffman coding, mutual information, channel capacity and the binary symmetric channel, and the noisy channel coding theorem.
· · ·
Three questions to carry with you.
And one to work out. What is the capacity of a binary symmetric channel that flips 11% of bits, ?
Sources: C. E. Shannon, Bell Syst. Tech. J. 27, 379 and 623 (1948); Bell Syst. Tech. J. 30, 50 (1951) (entropy of English). D. A. Huffman, Proc. IRE 40, 1098 (1952). T. M. Cover and J. A. Thomas, Elements of Information Theory. D. J. C. MacKay, Information Theory, Inference, and Learning Algorithms. Checked by code: C(0.11) = 0.5001, C(0.01) = 0.919; entropies of the plate’s samples computed from their letter counts.