Information Theory

Source: “The Story of Information Theory: from Morse to Shannon to ENTROPY”, Visual Electric.

Stub

Autogenerated draft, unreviewed.

Information theory is the mathematical field, founded by Claude Shannon’s 1948 paper “A Mathematical Theory of Communication,” that defines the information content of a message as the uncertainty it resolves rather than simply the number of symbols it could have been, and derives hard limits on how far a message can be compressed and how reliably it can cross a noisy channel. Shannon’s synthesis rested on a century and a half of prior work in long-distance signaling — from 18th-century optical semaphore through the electric telegraph to the measurement work of his own Bell Labs colleagues in the late 1920s.

Precursors: semaphore and the electric telegraph

Chappe’s optical semaphore

In 1794, amid the French Revolutionary Wars, engineer Claude Chappe’s optical semaphore system came into military use. Each tower carried a movable regulator arm with two shorter indicator arms at its ends, positionable into around 92 distinct configurations (“symbols”), read by telescope from the next tower in the chain and relayed onward. Chappe’s codebook (the Vocabulaire) went a step further: it paired two consecutive symbols, the first giving a page number and the second a line number, yielding roughly 92 × 92 ≈ 8,464 encodable words and phrases — far more than the primary symbol set alone could hold.

Reconstructed Chappe semaphore tower ("Milan" type, 1809) at the Cité des Télécoms telecommunications museum, Pleumeur-Bodou, France. Zubro, 2006. CC BY-SA 3.0, via Wikimedia Commons.

The same summer, a French army balloon, L’Entreprenant, flew tethered reconnaissance over the Battle of Fleurus (26 June 1794) — history’s first recorded military use of aircraft. Read together, the two innovations mark a turning point: for the first time, both eyes and messages could outrun a horse.

Electromagnetism and the electric telegraph

In 1820, Hans Christian Ørsted, working in Copenhagen, found that current through a wire deflected a nearby compass needle — the first demonstrated link between electricity and magnetism. Where Chappe’s towers needed line-of-sight and stopped working in fog or at night, electricity promised signals sent invisibly through a wire, at speeds no human courier could match.

Portrait of Hans Christian Ørsted, from J.P. Trap: berømte danske mænd og kvinder (1868). Public domain, via Wikimedia Commons.

Samuel Morse, an American portrait painter, learned of the effect from physician Charles Thomas Jackson during an 1832 Atlantic crossing and began building a telegraph on his return. With machinist and business partner Alfred Vail, he demonstrated a working system at the Speedwell Ironworks in Morristown, New Jersey, on January 11, 1838, and — most famously — sent a message between the U.S. Supreme Court chamber in Washington and Baltimore on May 24, 1844.

Morse’s system needed only a single wire, encoding letters as sequences of short and long pulses (“dots” and “dashes”). It competed with Cooke and Wheatstone’s British system, which used five magnetic needles and six wires to spell out letters in parallel — more hardware, but readable without training. Vail made a discrete, uncredentialed contribution to what would later become information theory: he counted how many copies of each letter a Morristown print shop kept in its type case, reasoned that more copies meant more frequent use, and assigned the shortest code sequences to the most common letters — the same principle, worked out by hand a century before Huffman coding formalized it mathematically.

Morse telegraph apparatus, 1837 pattern, at the Cité des Télécoms telecommunications museum, Pleumeur-Bodou, France. Zubro, 2006. CC BY-SA 3.0, via Wikimedia Commons.

Automating the code: Baudot

Morse’s system still needed a trained human to read clicks and write letters. French engineer Émile Baudot automated the process: his code, patented in 1874, assigned every letter, digit, or control signal a fixed 5-bit pattern — 2⁵ = 32 possibilities — entered on a five-key keyboard and read out mechanically at the far end, first tested between Paris and Bordeaux in 1877. The unit of signaling rate, the baud, is named for him.

Portrait of Émile Baudot, engraving by A. Delzers. Public domain, via Wikimedia Commons.

Seen through the lens Shannon would later provide, Baudot’s code is a step backward in efficiency even as it’s a step forward in automation: every character costs the same five bits regardless of how often it occurs, ignoring the very redundancy Vail’s frequency-weighted dots and dashes had already exploited by hand.

Quantifying information: Hartley and Nyquist

By the late 1920s, cables and wires spanned the globe, but no theory yet said how much information a channel could actually carry. Two Bell Labs engineers supplied the missing pieces.

Hartley’s logarithmic measure (1927–28)

In September 1927, Ralph Hartley presented a paper at the International Congress of Telegraphy and Telephony on Lake Como, in Mussolini’s Italy, published the following year in the Bell System Technical Journal as “Transmission of Information.” Hartley’s insight: sending n consecutive symbols from an alphabet of size s selects one message out of sⁿ possibilities, and that total grows explosively — Chappe’s 92-symbol alphabet gives 92¹⁰ possible ten-symbol messages, already more than the number of stars in the observable universe. Hartley proposed measuring information as the logarithm of that count instead of the raw number, so that information grows linearly, one increment per symbol, rather than exponentially. This gives Chappe’s semaphore a rate of log₂92 ≈ 6.5 bits per symbol, and Baudot’s code exactly log₂32 = 5 bits per symbol.

Ralph V.L. Hartley, Bell Labs researcher. Courtesy R.W. Hartley. CC BY-SA 3.0 / GFDL, via Wikimedia Commons.

Nyquist and channel bandwidth

Hartley’s colleague Harry Nyquist connected the discrete world of symbols to the continuous world of physical signals. In “Certain Topics in Telegraph Transmission Theory” (1928), Nyquist decomposed telegraph pulses into sinusoidal components and showed that a channel’s bandwidth limits how many distinct signaling events it can carry per second — a channel that strips away high frequencies distorts pulses sent too close together. This result, later formalized as the Nyquist rate, ties a channel’s physical bandwidth directly to its maximum symbol rate.

Claude Shannon

Claude Shannon joined this lineage as a 21-year-old graduate student. His 1937 MIT master’s thesis, “A Symbolic Analysis of Relay and Switching Circuits,” showed that Boolean algebra — the logic of true/false, and/or — could describe and design electrical switching circuits, laying the theoretical groundwork for digital logic; Harvard’s Howard Gardner later called it “possibly the most important, and also the most famous, master’s thesis of the century” (Gardner, cited in Soni & Goodman 2017). At Vannevar Bush’s suggestion, Shannon’s 1940 MIT PhD dissertation, “An Algebra for Theoretical Genetics,” applied similar algebraic methods to Mendelian inheritance. He then joined Bell Labs, where his day work on wartime cryptography and secure-voice systems ran alongside a private, after-hours project on the nature of information itself.

Claude Shannon, undated portrait photograph. Tekniska museet. CC BY 2.0, via Wikimedia Commons.

A Mathematical Theory of Communication (1948)

Shannon’s landmark paper opens by crediting Hartley and Nyquist, then goes further. He modeled any communication system as five parts — an information source, a transmitter, a channel, a receiver, and a destination — and separated two questions Hartley had run together: how much capacity a channel has, versus how much information a source actually generates.

Hartley had treated every symbol sequence as equally likely. Shannon modeled real sources — English text, in particular — as statistical processes (formally, Markov processes) in which some sequences are vastly more probable than others. “Apples are red” is one specific message from an astronomically large space of possible three-word sequences, but the space of sequences a source will actually produce is much smaller than the space it could in principle produce.

To measure this, Shannon defined entropy: the average “surprise,” −log₂p, of each symbol, weighted by its own probability p. Entropy is maximized when all outcomes are equally likely and drops toward zero as outcomes become predictable — an outcome you already know carries no information when confirmed.

Symbol	Probability	Surprise (−log₂p)	Fixed-length code	Frequency-weighted code
Red	50%	1 bit	`00`	`0`
Blue	25%	2 bits	`01`	`10`
White	12.5%	3 bits	`10`	`110`
Black	12.5%	3 bits	`11`	`111`

A fixed-length code (Baudot’s approach) costs 2 bits per symbol regardless of which symbol is sent. Assigning shorter codes to more probable symbols (Vail’s approach, done rigorously) brings the average down to 0.5(1) + 0.25(2) + 0.125(3) + 0.125(3) = 1.75 bits per symbol — exactly equal to this source’s entropy, because every probability here happens to be a power of one-half. Shannon proved this is a general limit, not a coincidence of this example: no lossless code can beat a source’s entropy, and — via what’s now called the asymptotic equipartition property — long-enough sequences from any stationary source collapse onto a “typical set” whose size is governed by exactly that same entropy, no matter how complex the source’s internal statistics are.

Noisy channels and channel capacity

A channel that’s merely fast is not yet useful if it’s unreliable. Shannon quantified the effect of noise with conditional entropy (sometimes called equivocation): the uncertainty that remains about what was sent, given what was received. Consider a fair coin flip reported by a source that lies 10% of the time. The coin itself carries 1 bit of entropy per flip, but the lying introduces an equivocation of h(0.1) = −0.1log₂0.1 − 0.9log₂0.9 ≈ 0.469 bits. The information actually conveyed is the difference: 1 − 0.469 ≈ 0.531 bits per flip, not the naive 0.9 bits a reader might guess from “90% honest.”

Shannon’s most audacious result, the noisy-channel coding theorem, showed that as long as a source’s transmission rate stays below a channel’s capacity, it’s possible to design a code — using long enough blocks — that drives the error probability toward zero, even over an arbitrarily noisy channel. The argument is a striking non-constructive one: assign codewords to messages at random, and show that as block length grows, the chance of ambiguity between two plausible messages vanishes, because the space of possible channel outputs grows exponentially faster than the space of messages being packed into it.

Finally, extending entropy to continuous (rather than discrete) signals let Shannon state the capacity of a physical channel limited by bandwidth B and corrupted by noise, unifying Nyquist’s and Hartley’s earlier results into what’s now called the Shannon–Hartley theorem:

$C = B lo g_{2} (1 + \frac{S}{N})$

— the channel capacity C, in bits per second, as a function of bandwidth and signal-to-noise ratio: the ultimate speed limit for reliable communication over any real channel.

Legacy

Shannon’s entropy and channel-capacity results underpin lossless data compression (Huffman and arithmetic coding directly implement the “match code length to surprise” idea from the table above), modern error-correcting codes, and — via Shannon’s own later work on secrecy systems — information-theoretic cryptography. The same entropy formula, reused as cross-entropy and KL divergence, now shows up throughout machine learning loss functions, and analogous ideas have been applied in economics, neuroscience, and (via a genuine, if contested, formal analogy to thermodynamic entropy) statistical physics.

Terminology

bit: Shannon’s unit of information — the amount conveyed by resolving one binary (50/50) uncertainty; formally log₂2 = 1.
entropy: the average surprise of a source’s output, −Σpᵢlog₂pᵢ; a lower bound on lossless compression and a measure of a source’s inherent unpredictability.
channel capacity: the maximum rate, in bits per second, at which information can be sent over a channel with arbitrarily low error probability.
redundancy: the gap between a source’s raw symbol rate and its entropy — the part of a message that’s predictable, and therefore compressible.
Markov source: a statistical model in which the probability of the next symbol depends on some fixed amount of preceding context, rather than being independent of it.
typical set / asymptotic equipartition property (AEP): the result that long sequences from a stationary source overwhelmingly cluster into a comparatively small set of “typical” sequences, whose size is governed by the source’s entropy.
conditional entropy (equivocation): the residual uncertainty about a transmitted message after observing the (possibly noisy) received signal.
teleprinter: a device that automatically encodes typed characters into a transmission code (e.g. Baudot’s) and decodes them back into text at the receiving end.
semaphore: a signaling system using the position of visible mechanical elements (arms, flags, lights) to encode symbols, read at a distance.
baud: a unit of signaling rate (symbols per second), named for Émile Baudot.

Sources

Shannon, C. E. (1948). “A Mathematical Theory of Communication.” Bell System Technical Journal, 27(3), 379–423.
Hartley, R. V. L. (1928). “Transmission of Information.” Bell System Technical Journal, 7(3), 535–563.
Nyquist, H. (1928). “Certain Topics in Telegraph Transmission Theory.” Transactions of the AIEE, 47(2), 617–644.
Soni, J. & Goodman, R. (2017). A Mind at Play: How Claude Shannon Invented the Information Age. Simon & Schuster.
Nahin, P. J. (2013). The Logician and the Engineer: How George Boole and Claude Shannon Created the Information Age. Princeton University Press.
Standage, T. (1998). The Victorian Internet: The Remarkable Story of the Telegraph and the Nineteenth Century’s On-Line Pioneers. Walker & Company.
Howe, D. W. (2007). What Hath God Wrought: The Transformation of America, 1815–1848. Oxford University Press.
Holland, R. S. (1911). The Story of Samuel Morse and the Telegraph.

nebunebu

Explorer

Information Theory

Table of Contents