The Thinking Machine Chronicles #0012: A Mathematical Theory of Communication: Shannon Invents Information Theory

Era 1 · The Foundations (1936–1955) A 32-year-old engineer at Bell Labs answers a question that communication engineers had been asking wrong for a century: not "how do I build a faster circuit" but "how much information can any channel carry, ever, regardless of how it is built?"

The World in 1948

In 1948 the old world was still pulling itself apart and a new one was forming around the wreckage. The Marshall Plan was signed into law by President Truman on 3 April, committing $13 billion, roughly$140 billion in 2024 dollars,to the reconstruction of Western Europe, with the explicit strategic aim of preventing the economic desperation that had fed fascism from providing an opening for communism instead. In June, the Soviets sealed West Berlin's land corridors, expecting the Western Allies to negotiate; instead, the Berlin Airlift began, eventually setting a record of 12,940 tonnes delivered in a single day. The World Health Organisation was established in April. The long-playing vinyl record was introduced by Columbia Records in June. In Hollywood, the House Un-American Activities Committee had been interrogating film industry workers for nearly a year.

The scientific year was extraordinary. In December 1947, Bardeen and Brattain had demonstrated the point-contact transistor at Bell Labs, the device we examined in TMC #0010,and by mid-1948 the implications were only beginning to be understood within the Labs. In June, the Manchester Small-Scale Experimental Machine ran the first stored program. Wiener's Cybernetics was in press. And in the same building at Murray Hill where the transistor had been built, a 32-year-old mathematician named Claude Shannon was preparing to submit the two-part paper that would give the concept of information its first precise mathematical definition.

The Problem Shannon Was Solving

Communication engineers in the late 1940s had a practical problem with no theoretical framework. Telephone and telegraph networks transmitted signals over noisy channels, and every engineer knew from experience that noise degraded messages, that bandwidth was limited, that redundancy helped recover from errors, and that encoding affected efficiency. But there was no mathematics that connected these observations. How much information could a channel carry? How efficiently could a message be compressed? Could you, in principle, transmit perfectly over a noisy channel? Nobody had precise answers, or even precise questions.

Shannon had been at Bell Labs since 1941. During the war he worked on classified fire-control systems and cryptography, and in 1945 produced a secret internal report, "A Mathematical Theory of Cryptography," that contained many of the ideas he would publish in 1948. The insight that bridged cryptography and communication theory was this: uncertainty is information. A message you already know conveys nothing. A message that surprises you conveys a great deal. The measure of information in a message should be the measure of the uncertainty it resolves.

Shannon Entropy

Shannon defined the information content of an event with probability $p$ as $-\log_2 p$ bits. The logarithm is chosen so that two independent events with probabilities $p_1$ and $p_2$ carry additive information: $-\log_2(p_1 p_2) = -\log_2 p_1 - \log_2 p_2$. The base-2 logarithm calibrates the unit so that a fair coin flip, the simplest possible binary choice,carries exactly 1 bit.

For a discrete random variable $X$ taking values $x_1, x_2, \ldots, x_n$ with probabilities $p_1, p_2, \ldots, p_n$, the Shannon entropy is the expected information content:

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

By convention, $0 \log_2 0 = 0$. Entropy is maximised when all outcomes are equally likely:

$H_{\max} = \log_2 n \text{ bits}$

and minimised (at zero) when one outcome has probability 1. For two variables $X$ and $Y$:

$H(X,Y) = -\sum_{i,j} p(x_i, y_j) \log_2 p(x_i, y_j)$

$H(Y \mid X) = H(X,Y) - H(X)$

$I(X;Y) = H(X) + H(Y) - H(X,Y)$

The mutual information $I(X;Y)$ measures how much knowing $X$ reduces uncertainty about $Y$. It is zero when the variables are independent and equal to $H(X) = H(Y)$ when they are perfectly correlated.

English Has 4.11 Bits Per Letter: But Needs Only 1

One of Shannon's most striking demonstrations was the entropy of English text. If the 26 letters were equally probable, each would carry $\log_2 26 \approx 4.70$ bits. But letters in English are not equally probable: E appears with probability ~12.7%, Z with ~0.07%. Computing Shannon entropy over the empirical letter frequencies yields $H \approx 4.11$ bits per letter.

But first-order letter entropy ignores statistical dependencies between adjacent letters: Q is almost always followed by U, TH is a common pair, and common words like "the" occur far more often than their letter-product probabilities would predict. Shannon measured human subjects' ability to predict the next letter in a text, and from those experiments estimated that the true entropy of English (accounting for all long-range correlations) is somewhere between 0.6 and 1.3 bits per letter. English, in other words, is between 70% and 87% redundant, a consequence of the fact that language evolved in a noisy acoustic channel and built in its own error correction.

The Source Coding Theorem

Shannon's first theorem (the source coding theorem) connects entropy to compression. For a discrete memoryless source with entropy $H(X)$ bits per symbol, the average number of bits required per source symbol satisfies:

$\bar{L} \geq H(X)$

and there exists an encoding that achieves $\bar{L} < H(X) + 1$. In other words, $H(X)$ is the minimum average description length, the most compressed a message can ever be, regardless of the encoding scheme. You cannot compress English below 0.6–1.3 bits per letter without losing information (for lossless compression), no matter how clever the encoder.

The Huffman code (1952) achieves optimal prefix-free compression within one bit of the entropy: assign shorter codewords to more probable symbols and longer codewords to rare ones. For English letters using empirical frequencies:

Symbol	Probability	Huffman code	Length
E	0.127	000	3 bits
T	0.091	001	3 bits
...	...	...	...
Z	0.001	11111110	8 bits

The average code length $\bar{L} \approx 4.16$ bits per symbol, versus the entropy $H \approx 4.11$, an efficiency of 98.8%.

Channel Capacity: The Shannon-Hartley Theorem

Shannon's second theorem (the noisy channel coding theorem) is the result that stunned communication engineers. Consider a channel with bandwidth $B$ Hz and additive white Gaussian noise, where the signal power is $S$ and the noise power is $N$. Shannon proved that the channel capacity, the maximum rate at which information can be reliably transmitted,is:

$C = B \log_2\!\left(1 + \frac{S}{N}\right) \text{ bits/second}$

For a telephone channel with $B = 3.4\text{ kHz}$ and $S/N = 1000$ (30 dB), the capacity is approximately 34 kbps, a number that would not be approached in practice until the development of V.34 modems in the early 1990s, more than four decades after Shannon derived it.

The theorem has two parts, and the second is the extraordinary one. The achievability direction says: for any target bit-rate $R < C$, there exists a code that allows transmission at rate $R$ with error probability approaching zero as the block length grows. This was radical, engineers in 1948 believed that you could reduce error by adding redundancy but that error could never be made arbitrarily small. Shannon proved it could.

The converse says: no code can achieve reliable communication at rate $R > C$. The capacity $C$ is a hard physical limit, not an engineering challenge.

For the Binary Symmetric Channel (BSC), which flips each transmitted bit with probability $p$,the capacity is:

$C_{\text{BSC}} = 1 - H_b(p) = 1 + p \log_2 p + (1-p) \log_2 (1-p)$

At $p=0$ (no noise) the capacity is 1 bit per use; at $p=0.5$ (pure noise) the capacity is 0.

The Code: An Information Theory Toolkit

The companion project implements Shannon's core results in pure Python. It computes entropy, mutual information, channel capacity, and a Huffman codebook, demonstrating both the source coding bound and the Shannon-Hartley limit:

def entropy(probs: list[float]) -> float:
    """Shannon entropy in bits. Treats 0 log 0 = 0 by convention."""
    return -sum(p * math.log2(p) for p in probs if p > 0)

def shannon_hartley_capacity(bandwidth_hz: float, snr_linear: float) -> float:
    """C = B log₂(1 + S/N) in bits/second."""
    return bandwidth_hz * math.log2(1 + snr_linear)

def bsc_capacity(p: float) -> float:
    """Binary Symmetric Channel capacity: C = 1 - H_b(p)."""
    if p == 0 or p == 1:
        return 1.0
    return 1.0 - entropy([p, 1 - p])

The full project computes the entropy of the English letter distribution and compares it to the uniform bound, builds a Huffman codebook and measures how close the average code length is to the entropy bound, and sweeps channel capacity over a range of SNR values to show how close the theoretical limit was to practical modem speeds in different decades.

Why It Mattered

Information theory mattered because it quantified two things engineers had treated as vague intuitions: the amount of information in a message, and the capacity of a physical channel. Those two numbers are related by a hard limit. Everything else, data compression, error-correcting codes, spread-spectrum modulation, cryptographic key strength, neural network training,is, in some sense, an engineering attempt to approach that limit from one direction or another.

For AI specifically, Shannon's entropy became the universal measure of uncertainty. Decision trees split on the attribute that maximises information gain. Mutual information quantifies how much one variable predicts another. The cross-entropy loss that trains every modern deep learning model is Shannon's $H(p, q) = -\sum p \log q$ applied to predicted vs. true distributions. The KL divergence that appears in variational autoencoders, generative models, and reinforcement learning is the relative entropy $D_{KL}(p \| q) = \sum p \log (p/q)$. Shannon's 1948 paper did not mention neural networks. It established the measure by which all probabilistic reasoning is now evaluated.

The societal impact was equally profound. Shannon demonstrated that information can be quantified, compressed to its irreducible minimum, and transmitted over any noisy channel at a definite maximum rate. This showed that communication was a physical process governed by the same kind of precise limits as thermodynamics, not an engineering art form subject to incremental improvement, but a mathematical science with optimal solutions. The digital age is, in a precise sense, the age of approaching Shannon's limits.

What Came Next

Shannon's paper defined what a bit was and proved how many bits a channel could carry. The next question was what to do with the bits once they arrived, how to store them, execute programs on them, and turn a general-purpose stored-program computer from a theoretical construct into a physical machine a programmer could actually use. In June 1948, while Shannon was finalising his paper, the Manchester Small-Scale Experimental Machine,the "Baby", ran the world's first stored program on real electronic hardware, 17 instructions written by Freddie Williams and Tom Kilburn on the machine they had built in a converted stable. That is the next story: The Thinking Machine Chronicles #0013: The Baby That Changed Everything: The First Stored-Program Computer Runs.

---

References

1. Shannon, C.E. (1948). A Mathematical Theory of Communication. Bell System Technical Journal, 27(3), 379–423; 27(4), 623–656. The original paper; freely available at the Bell Labs/Nokia Bell Labs website.
2. Shannon, C.E. & Weaver, W. (1949). The Mathematical Theory of Communication. University of Illinois Press. The book version with Weaver's introductory essay for a general audience.
3. Cover, T.M. & Thomas, J.A. (2006). Elements of Information Theory (2nd ed.). Wiley. The modern graduate standard; covers entropy, channel capacity, rate-distortion, and Kolmogorov complexity.
4. Shannon, C.E. (1949). Communication Theory of Secrecy Systems. Bell System Technical Journal, 28(4), 656–715. The declassified version of the 1945 wartime report; shows how close information theory and cryptography are in Shannon's thinking.
5. Huffman, D.A. (1952). A Method for the Construction of Minimum-Redundancy Codes. Proceedings of the IRE, 40(9), 1098–1101. Huffman's original paper, derived as a student assignment under Shannon's MIT colleague Robert Fano.
6. Pierce, J.R. (1980). An Introduction to Information Theory: Symbols, Signals and Noise (2nd ed.). Dover. The most readable popular introduction; Pierce worked with Shannon at Bell Labs.