03 · Information & Coding

This chapter is the bedrock floor beneath every message the tower moves — it fixes what a signal is, and how much of one a channel can carry.

How much surprise can a channel carry?

Before 1948, every engineer working on a noisy line believed the same thing, and it was wrong. Noise corrupts messages; to fight it you shout louder or you repeat yourself. Either way you buy accuracy with power or with time, and the exchange rate looked merciless: to drive the error rate near zero you had to slow the message near to a stop. Reliability and speed were a seesaw, and that was simply the nature of physical channels.

Then Claude Shannon, at Bell Labs, published a paper in two parts, in the July and October 1948 issues of the Bell System Technical Journal, and the seesaw broke (Shannon, 1948). Every channel, he proved, has a number attached to it — its capacity. Send at any rate below that number and you can push the probability of error as close to zero as you like, without slowing down at all. Send above it and nothing saves you: not more power, not more repetition, not any coding scheme anyone will ever invent. Not a seesaw. A speed limit, with a free lunch underneath it.

To get there, Shannon first had to say what a message is.

Information is surprise, not meaning. His second paragraph throws away the thing everyone else cared about: "These semantic aspects of communication are irrelevant to the engineering problem." What matters is only that a message is a selection from a set of possible messages, and the engineering job is to reproduce the selection at the far end. That reframing gives the unit: "If the base 2 is used the resulting units may be called binary digits, or more briefly bits, a word suggested by J. W. Tukey." One fair coin flip is one bit; one fair die is about 2.6. A message you could have predicted carries none, however long it is, and a message you could not carries a great deal, however short. Entropy — Shannon's H — is just the average surprise per symbol from a source. Harry Nyquist and Ralph Hartley had circled this in the same journal in 1924 and 1928; Shannon closed the circle by making it a measure.

Entropy is the floor of compression. Once surprise has a number, the number binds. Shannon's noiseless coding result (Theorem 9 in the paper) says a source of entropy H cannot be encoded in fewer than H bits per symbol on average, and can be encoded in arbitrarily close to H. English is nowhere near the 4.7 bits per character that a 26-letter alphabet would allow, because letters predict each other — q is followed by u, and you already knew how this sentence would end. That gap between the alphabet's capacity and the language's entropy is exactly what every compressed archive eats. Compression is therefore not a trick performed on data; it is the removal of predictability. Which explains two things everyone has noticed: a compressed file does not compress again, and truly random data does not compress at all.

Capacity is a speed limit, and redundancy is how you drive at it. Shannon's noisy-channel theorem (Theorem 11) is the free lunch stated formally, and Theorem 17 puts a number on it for the commonest case: "The capacity of a channel of band W perturbed by white thermal noise of power N when the average transmitter power is P" is C = W log(1 + P/N) bits per second (BSTJ 27, no. 4). Note what this licenses. Repeating a message three times is redundancy spent stupidly — it triples your cost for a modest gain. Shannon proved that redundancy spent cleverly buys near-perfect reliability at almost no cost in rate. He did not, however, say how. His proof shows that good codes exist by showing that a randomly chosen code is probably good — an existence proof that handed engineers a construction project lasting fifty years.

The construction project. Richard Hamming had a personal stake. Working weekends on Bell Labs' relay computer in 1947, with no operator present, he would submit a job on Friday and return Monday to find that the machine had detected a card-reading error, dumped his work, and moved on. Twice in a row. "Dammit," he recalled thinking, "if a machine can find out that there is an error, why can't it locate where it is and change the setting of the relay from one to zero or zero to one?" (IEEE Computer Society). The answer became the Hamming codes (BSTJ 29, no. 2, April 1950: 147–160) — parity bits arranged so that the pattern of failed checks spells out the position of the flipped bit in binary. Detection had become correction.

Then the codes got good. Reed and Solomon's 1960 construction over finite fields (Journal of the SIAM 8: 300–304) survives bursts of damage rather than isolated flips, which is what deep space demanded: JPL launched Voyager 2 toward Uranus knowing its Reed–Solomon decoders did not yet exist, "gambl[ing] that by the time Voyager II would reach Uranus in 1986, decoding algorithms and equipment would be both available and perfected. They were correct!" (NASA TM 102162). Robert Gallager had meanwhile invented low-density parity-check codes in his 1960 MIT thesis, published them in 1962 (IRE Transactions on Information Theory 8: 21–28), and watched them vanish — too expensive to decode on the hardware of the day. They were rediscovered by MacKay and Neal in 1995–96, alongside the turbo codes of Berrou, Glavieux and Thitimajshima (Proc. IEEE ICC, 1993), and the wall Shannon had drawn was finally reached: by 2001 an irregular LDPC code came within 0.0045 decibels of capacity (Chung, Forney, Richardson & Urbanke, IEEE Communications Letters 5, 2001). Your phone uses both descendants — LDPC for 5G data channels, and Erdal Arıkan's polar codes, published in 2009 and standardized within a decade, for the control channels.

And the floor's silence is its leak. Everything above is indifferent to what a message says. Shannon's disclaimer was a precondition for the theory's power, not an oversight — but it means this floor can price the transmission of a diagnosis and of a spam message identically, and has nothing to say about which was worth sending. Every floor above pays for that silence in its own currency: cryptography (11) must add who sent it, databases (08) must add what it means, and machine learning (12) spends its whole existence trying to recover meaning from statistics — while quietly using Shannon's entropy as its loss function.

Connections

Beside this floor: 02, whose Ω(n log n) sorting bound is this chapter's counting argument in disguise — log₂(n!) is the number of bits needed to name one ordering. Above: 09, where TCP builds reliability out of an unreliable channel — the same bargain, made at a higher floor; 08, where compression and checksums guard stored data; 11, where a cipher's strength is counted in bits; 12, where a model that predicts the next token well is, by the argument above, a compressor.

Open questions

Shannon deliberately excluded meaning — and no accepted theory of semantic information has replaced what he set aside, though the question is now live again because language models make it practical. Is compression the same thing as understanding, or merely correlated with it? And on the physical side: how close to capacity is close enough to stop, given that the last fraction of a decibel now costs more energy in decoding than it saves in transmission?

Go deeper

• Claude Shannon, "A Mathematical Theory of Communication," Bell System Technical Journal 27 (1948): 379–423, 623–656 — still the clearest exposition of its own ideas (PDF).
• David MacKay, Information Theory, Inference, and Learning Algorithms, Cambridge University Press, 2003 — free from the author's site, and the book that connects this floor to chapter 12 (inference.org.uk).
• Richard Hamming, "Error Detecting and Error Correcting Codes," Bell System Technical Journal 29, no. 2 (April 1950): 147–160 — the first working answer to Shannon's existence proof (scan).