1.8 — Information Theory

Part 1 began with a promise made in 1.1: the forbidden voltage zone, the noise margin, the idea that a signal can be sent perfectly through an imperfect world — all of it, we said, would get its mathematics eventually. This is eventually. In 1948, a single paper by Claude Shannon — the same man whose 1937 thesis married Boolean algebra to circuits (1.1) — created an entire science from nothing and answered questions no one had even known how to ask: What is information, exactly? How small can data be squeezed? How fast can we communicate over a noisy channel without errors? His answers are exact numbers, they are provably optimal, and they run every hard drive, phone call, streaming video, and deep-space probe alive today. This chapter closes Part 1 by giving you the concepts that quantify the very stuff this whole book is made of.

1. What is information? Surprise, measured

Before Shannon, "information" was a vague, qualitative notion. His radical move was to strip away meaning entirely and define information as the resolution of uncertainty. The information content of a message is how much it reduces your surprise — how many of your questions it answers.

Consider: if I tell you "the sun rose this morning," I've given you almost no information — you already knew it, probability ~1, zero surprise. If I tell you "it snowed in the Sahara today," that's enormous information — deeply improbable, hugely surprising. The rarer the event, the more information its occurrence carries.

The two pieces of math notation this chapter uses — explained from scratch

Everything below needs exactly two symbols. Neither is hard, and you need no prior maths.

The logarithm, \log_2 x. A logarithm answers the question: "how many times must I multiply this base by itself to reach x?" Base 2 (which is all we use) asks: how many times must I double 1 to reach x? So \log_2 8 = 3, because 2 \times 2 \times 2 = 8 — three doublings. \log_2 16 = 4; \log_2 2 = 1; \log_2 1 = 0 (no doublings needed). It's the inverse of raising 2 to a power: if 2^3 = 8, then \log_2 8 = 3. The intuition that matters here: \log_2 x counts how many yes/no questions you need to pin down one option out of x equally-likely options. With 8 options, three well-chosen yes/no questions suffice (each halves the field: 8 → 4 → 2 → 1) — hence \log_2 8 = 3. That is precisely why information measured this way comes out in bits (1.3): a bit is one yes/no. Note also that logarithms turn division into subtraction, so \log_2(1/p) = -\log_2 p — the two forms in the next formula are the same thing written two ways.

The summation sign, \sum. The Greek capital sigma just means "add up all of these." \sum_i x_i reads "sum the values x_i over every i" — so if the values are 2, 5, and 9, then \sum_i x_i = 2 + 5 + 9 = 16. It's shorthand for a loop that accumulates a total; nothing more.

Shannon made the idea precise: the information in an event of probability p is

I = \log_2\left(\frac{1}{p}\right) = -\log_2 p \quad \text{bits.}

A coin flip (heads, p = \tfrac12) carries \log_2 2 = 1 bit — exactly one yes/no's worth, which is why the bit (1.3) is the natural unit of information. One of eight equally-likely outcomes carries \log_2 8 = 3 bits. The base-2 log is why information is measured in bits: it counts how many binary questions you'd need to pin the answer down. This is the same word Shannon helped popularize in 1.3, now given a precise, quantitative meaning: a bit is not just a switch — it's one bit's worth of resolved uncertainty.

2. Entropy — the true size of a message

Extend that from one event to a whole source that keeps emitting symbols (letters, pixels, samples), each with some probability. The average information per symbol is the source's entropy, Shannon's central quantity:

H = -\sum_i p_i \log_2 p_i \quad \text{bits per symbol.}

Entropy measures the average unpredictability of a source. A source that always emits the same symbol has H = 0 (no surprise, no information). A source with all symbols equally likely has maximum entropy (maximum unpredictability). English text has fairly low entropy — letters are far from random: q is almost always followed by u, e is common, z is rare, and after "th" you can guess "e" — so each letter carries fewer than the naive \log_2 26 \approx 4.7 bits; the real figure is closer to ~1–1.5 bits per letter once you account for all that predictability.

And here is the payoff that makes entropy one of the most practical ideas in this book: entropy is the hard theoretical floor on compression. Shannon's source coding theorem proves you cannot losslessly compress data below its entropy — that's the true, irreducible size of the information — and you can get arbitrarily close to it. This is why 1.4's lossless compression works and why it has a limit: a compressor finds the predictability (the low entropy) and encodes it away; once you've removed all redundancy, entropy is the wall. It's also why you can't compress already-compressed data (a ZIP of a ZIP): the first pass already pushed it near its entropy floor, leaving nothing predictable to exploit. Random data is incompressible precisely because it has maximal entropy — no patterns to remove. The intuition "compression = removing predictability" is now a theorem with a number attached.

Entropy connects to physics — and it's not a coincidence

The formula H = -\sum p_i \log p_i is, up to a constant, identical to the entropy of thermodynamics (Volume IV) — the measure of disorder that governs heat, engines, and the arrow of time. Shannon's colleague von Neumann reportedly told him to call his quantity "entropy" partly because the physics formula matched and "no one knows what entropy really is, so you'll win every argument." The deep link between information and physical disorder is one of the profound threads of modern science — pulled further in Volume IV.

3. Coding — spending short codes on common symbols

Entropy says how small data can get; coding is how you get there. The core idea is beautifully intuitive and you already know it from Morse code: give the most common symbols the shortest codes. Morse gives e (the commonest English letter) a single dot, and q a long dash-dash-dot-dash — spending brevity where it's used most.

The classic algorithm, Huffman coding (1952, devised by a student, David Huffman, to dodge a hard exam — and it beat his professor's own method), does this optimally: it builds a tree that assigns each symbol a variable-length bit code, shortest for the most probable, guaranteeing no code is a prefix of another (so the stream decodes unambiguously with no separators). Feed it English text and common letters get 2–3 bits while rare ones get 8–10, and the average lands remarkably close to the entropy floor. Huffman coding lives inside ZIP, JPEG, MP3, and PNG — every one of them, after finding structure to remove, uses a Huffman-style final pass to spend bits efficiently. (Modern variants like arithmetic and range coding squeeze even closer to entropy, but Huffman is the idea to hold.) This is 1.4's compression, now with its engine exposed: model the probabilities, then code the common things short.

4. The noisy channel — Shannon's miracle

Now the deepest result, and the one that redeems 1.1's promise directly. Real communication channels — a wire, a radio link, a scratched DVD, a signal from Voyager 15 billion miles away — corrupt bits with noise. The pre-Shannon assumption was grim: noise means errors, and to get fewer errors you must slow down and shout (send each bit many times), approaching zero errors only by approaching zero speed. Everyone believed reliable communication over a noisy channel meant near-zero throughput.

Shannon proved them spectacularly wrong. His noisy channel coding theorem states that every channel has a fixed maximum rate — its capacity C — below which you can communicate with an error rate as close to zero as you like, and above which you cannot. For the common case of a channel with bandwidth B and signal-to-noise ratio SNR, the capacity is the celebrated Shannon–Hartley formula:

C = B \cdot \log_2(1 + \text{SNR}) \quad \text{bits per second.}

Two revelations live in this one line. First: reliable, essentially error-free communication over a noisy channel is possible at a positive rate — you do not have to slow to a crawl. The trick is error-correcting codes: add cleverly-structured redundancy so the receiver can detect and repair corruption, achieving near-perfect delivery at rates approaching C. This is the mathematics behind the "regeneration" of 1.1's digital signal, behind why your phone call is clear at the edge of coverage, why a scratched Blu-ray still plays, why RAID rebuilds a dead drive, and why Voyager's whisper is still decoded across interstellar distances. Second: there is a hard speed limit. No amount of engineering cleverness can push error-free data faster than C. When your ISP sells "up to X Mbps," X is bounded by this formula — capacity rises only by widening bandwidth B or improving SNR (more signal power or less noise). It is the ultimate speed limit of every communication link in the universe, and it ties straight back to Volume III's communication systems (III 7.5).

Figure 1 — The noisy channel. Structured redundancy at the encoder lets the decoder repair noise-induced errors. Shannon proved a rate exists — the capacity — below which delivery can be made essentially perfect.

5. Error correction, concretely — the Hamming idea

How does adding redundancy actually repair errors, not just detect them? The simplest detector is a parity bit: append one bit making the total number of 1s even. Flip any single bit in transit and the parity is now odd — error detected. But parity can't tell you which bit flipped, so it can't fix it, and two flips cancel undetected.

Richard Hamming — a Bell Labs colleague of Shannon, exasperated in 1950 that weekend computer jobs died on a single error with no operator to restart them — invented codes that locate and correct. A Hamming code uses several parity bits, each guarding an overlapping subset of the data bits, arranged so that the pattern of which parity checks fail spells out, in binary, the position of the flipped bit — flip it back and you've corrected the error with no retransmission. Add more redundancy and you correct more errors (the general theory: a code's minimum distance between valid codewords determines how many errors it can detect and fix). This is the concrete machinery behind Shannon's existence proof — ECC memory in servers that silently corrects cosmic-ray bit-flips, QR codes that scan when partly damaged, CDs that survive scratches, and the deep-space codes that keep Voyager talking all descend from Hamming's insight: structure the redundancy so errors reveal their own location.

6. The expert lens

Shannon drew the boundaries of the possible — twice. 1.7 gave limits on what can be computed; this chapter gives limits on information itself — the smallest data can be squeezed (entropy) and the fastest it can flow reliably (capacity). Both are provably optimal walls, not engineering targets. Half a century of coding research has been the pursuit of reaching Shannon's limits, which he proved existed before anyone knew how (modern LDPC and turbo codes finally kiss the capacity bound). Knowing a limit is provably there changes the game from "can we do better?" to "how close can we get?" — a profoundly different, and more honest, engineering posture.

Entropy is a lens you'll reuse constantly. It measures predictability, so it quantifies far more than compression: password strength is literally measured in bits of entropy (how unpredictable, hence how hard to guess — Part 8); a good hash function maximizes entropy in its output; the "randomness" a cryptographic key needs is high entropy; even decision trees in machine learning (Part 12) split on the feature that reduces entropy most. Once you see information as resolved uncertainty, the same measure illuminates security, ML, data, and communication alike.

The whole book, quantified. Part 1 built a machine that stores and transforms bits; this chapter tells you what a bit is, how few of them a message truly needs, and how reliably they can travel. Every later Part spends bits — a database stores them (Part 7), a network moves them under Shannon's limit (Part 5), a compressor shrinks them toward entropy (everywhere), cryptography makes them unpredictable (Part 8), an LLM predicts the next one (Part 12). You now hold the unit of account for all of it.

Part 1 complete. You've traveled from a single electron crossing a noise margin to the mathematical limits of information itself — the physics, the logic, the machine, the number systems, the CPU, the memory, the theory, and now the information. Everything above this floor — operating systems, languages, algorithms, networks, the web, databases, security, AI — is built on what you now understand from the ground up. Part 2 begins the ascent: the operating system that turns this raw machine into something a program can live on.

Recall

• Information = resolved uncertainty: a rarer event carries more; the information of a probability-p event is -\log_2 p bits. A fair coin = 1 bit.
• Entropy H = -\sum p_i \log_2 p_i is the average information (unpredictability) per symbol — and the hard floor on lossless compression (Shannon's source coding theorem). You can't compress below entropy; that's why compressed data won't re-compress.
• Coding reaches the floor by giving common symbols short codes; Huffman coding does this optimally and lives inside ZIP/JPEG/MP3/PNG.
• Channel capacity C = B\log_2(1+\text{SNR}): below it, error-correcting codes make communication essentially error-free over a noisy channel; above it, impossible. The ultimate speed limit of every link.
• Hamming codes structure redundancy so a failed-parity pattern pinpoints and corrects the flipped bit — the concrete machinery (ECC RAM, QR codes, CDs, deep-space comms) behind Shannon's proof. This is the math behind 1.1's noise margins and signal regeneration.

Self-test: Why does a rare event carry more information than a common one? What does entropy set a hard limit on, and why can't you compress a ZIP? What are the two things Shannon–Hartley tells you about a noisy channel? How does a Hamming code correct (not just detect) an error?

Quiz Bank

FoundationalHow does information theory define 'information', and why is the bit its unit?

Information is the resolution of uncertainty — how much an event reduces your surprise. An event of probability p carries -\log_2 p bits, so rarer (less probable) events carry more information. The unit is the bit because base-2 log counts how many yes/no questions are needed to pin the answer down: a fair coin flip resolves exactly 1 bit, one of eight equally-likely outcomes resolves 3 bits.

FoundationalWhat is entropy, and what practical limit does it set?

Entropy H = -\sum p_i \log_2 p_i is the average information per symbol from a source — its average unpredictability (0 for a constant source, maximal when all symbols are equally likely). Its key practical role: by Shannon's source coding theorem it is the hard lower bound on lossless compression — no lossless scheme can go below a source's entropy, and good ones approach it. Low-entropy (predictable) data compresses well; maximal-entropy (random) data can't be compressed at all.

AppliedWhy can't you meaningfully compress an already-compressed (e.g. ZIP) file?

A good compressor removes redundancy, pushing the data close to its entropy floor — the point where it looks essentially random (no exploitable patterns left). A second pass finds no remaining predictability to exploit, so it can't shrink it further (and may even grow it slightly from overhead). This is a direct consequence of entropy being the irreducible size of the information: once you're near the floor, there's nothing left to remove.

AppliedExplain Huffman coding and where it's used.

Huffman coding builds an optimal prefix-free code: it assigns each symbol a variable-length bit string, giving the shortest codes to the most probable symbols (like Morse's dot for 'e'), with no code a prefix of another so the stream decodes unambiguously. The average code length approaches the source's entropy. It's the final entropy-coding stage inside ZIP, JPEG, MP3, and PNG — after those formats model/remove structure, Huffman (or a close variant) spends the remaining bits efficiently.

InterviewState the noisy channel coding theorem and the Shannon–Hartley formula, and why they matter.

Shannon's noisy channel coding theorem says every channel has a capacity C: below C you can transmit with arbitrarily small error using error-correcting codes; above C, reliable communication is impossible. For a bandwidth-B channel with signal-to-noise ratio SNR, Shannon–Hartley gives C = B\log_2(1+\text{SNR}) bits/second. It matters because (1) it proves near-perfect communication over a noisy channel at positive rate is possible — the basis of all digital comms, Wi-Fi, storage, deep-space links — and (2) it sets a hard maximum speed you can only raise by increasing bandwidth or SNR.

InterviewHow does a Hamming code correct an error, not merely detect one?

A single parity bit only detects an odd number of flips — it can't say which bit. A Hamming code uses multiple parity bits, each checking an overlapping subset of data bits, arranged so that the set of parity checks that fail encodes, in binary, the position of the flipped bit. The decoder reads that position and flips the bit back — correction with no retransmission. More redundancy (greater minimum distance between codewords) corrects more errors. This is the concrete mechanism behind ECC memory, QR codes, CD/DVD resilience, and deep-space communication.

StaffA teammate proposes measuring and enforcing password strength. Frame this using information theory and note the subtlety.

Password strength is naturally expressed as entropy in bits — a measure of how unpredictable the password is, i.e. how many guesses an attacker needs on average. A truly random 12-character password from a 94-symbol set carries \approx 12\log_2 94 \approx 79 bits; each added bit doubles the guessing effort. The subtlety: entropy is only meaningful relative to the attacker's model of the distribution. Human-chosen passwords are not uniformly random — they cluster on words, dates, and patterns (low real entropy), so naive per-character estimates massively overstate strength; attackers exploit the true (low-entropy) distribution with dictionaries and rules. So enforce entropy by maximizing real unpredictability — favor length and true randomness (passphrases, generated passwords), block known-common passwords, and don't credit predictable complexity ("P@ssw0rd!" is low-entropy despite the symbols). Ties directly to Part 8's hashing and key-strength requirements.

Flashcards

FlashInformation of a probability-p event

-\log_2 p bits — rarer events carry more information. Fair coin = 1 bit.

FlashEntropy formula and meaning

H = -\sum p_i \log_2 p_i — average bits per symbol; the hard floor on lossless compression.

FlashWhy compressed files don't re-compress

They're already near their entropy floor — no predictable redundancy left to remove.

FlashHuffman coding idea

Optimal prefix-free code: shortest codes for the most frequent symbols; used in ZIP/JPEG/MP3/PNG.

FlashShannon–Hartley capacity

C = B\log_2(1+\text{SNR}) bits/s — the max error-free rate of a channel; raise it via bandwidth or SNR.

FlashParity bit vs Hamming code

Parity detects a single-bit error; a Hamming code locates and corrects it (failed-check pattern = error position).

Scenario Drill

DrillA satellite link to a remote sensor is dropping too many corrupted packets, and you can't increase transmit power much. Using this chapter, lay out your options and their theoretical limits.

Frame it with channel capacity, C = B\log_2(1+\text{SNR}). The corruption means the effective rate is too close to (or above) what the current SNR supports. Options, each tied to the theory: (1) Add stronger error-correcting codes — more structured redundancy lets the decoder repair more flips, pushing the reliable rate toward capacity; this is the first lever and often enough, at the cost of lower payload throughput (you spend bits on redundancy). (2)

Lower the data rate — operating further below C makes near-zero error achievable per Shannon; slower but reliable. (3) Increase SNR — more transmit power or a higher-gain/larger antenna raises SNR and thus C (you said power is limited, but antenna gain and pointing may help). (4)

Widen bandwidth B if spectrum allows — raises C linearly. The hard truth to communicate: you cannot get error-free throughput above C no matter the coding cleverness — so if the target rate exceeds capacity at the available SNR and bandwidth, something must give (rate, power, antenna, or spectrum). The professional answer names the capacity wall explicitly and picks the cheapest lever (usually better ECC + a modest rate reduction) rather than chasing an impossible target. Ties to Volume III's communication systems for the modulation/coding specifics.