Source Summary: Shannon 1948 — Information Theory
Full title: A Mathematical Theory of Communication
Authors: C. E. Shannon
Affiliation: Bell Telephone Laboratories
Venue: Bell System Technical Journal, Vol. 27, pp. 379–423, 623–656 (July, October 1948)
PDF: papers/shannon-1948-a-mathematical-theory-of-communication.pdf
Contributions
- Information entropy — H = −Σ pᵢ log pᵢ as the fundamental measure of uncertainty/information in a discrete source.
- Channel capacity — C = max_{p(x)} I(X;Y), the maximum rate at which information can be reliably transmitted through a noisy channel.
- Shannon’s noisy channel coding theorem — For any rate R < C, there exist codes that allow transmission with arbitrarily small error probability; for R > C, reliable communication is impossible.
- Source coding theorem — The minimum compression rate for a source is its entropy H; you cannot compress below H without information loss.
- Five-component communication system model — source → transmitter → channel (with noise) → receiver → destination.
Methodology
The Communication System (Part I: Discrete Noiseless)
The fundamental problem: reproduce at a destination a message selected at a source.
Discrete channel capacity:
C = lim_{T→∞} log N(T) / T
where N(T) = number of allowed signals of duration T.
Entropy of a discrete source:
H = −Σ pᵢ log pᵢ
(bits, when log is base 2; nats for base e)
For a source with states and transition probabilities Pᵢ(j):
H = −Σᵢ Pᵢ Σⱼ P(j|i) log P(j|i)
Noiseless coding theorem
Given source entropy H and channel capacity C:
- If H ≤ C: messages can be encoded and transmitted at rate approaching C/H symbols per second with zero error
- The most efficient encoding achieves average code length per symbol approaching H
Practical implication: Morse code assigns short symbols to frequent letters — optimal coding approaches the entropy bound.
Noisy Channel (Part II)
Mutual information: I(X;Y) = H(X) − H(X|Y) — reduction in uncertainty about X given knowledge of Y.
Channel capacity:
C = max_{p(x)} I(X;Y) bits per channel use
Noisy channel coding theorem (Shannon’s main theorem):
- For any desired error probability ε > 0 and any rate R < C, there exist codes of length N (N large enough) with error probability < ε
- For R > C, the probability of error is bounded away from zero for any code
This is the most counterintuitive result: adding redundancy to combat noise can reduce it to arbitrarily small levels, not just partially.
Continuous Channels (Part III)
Entropy of a continuous distribution:
h(X) = −∫ f(x) log f(x) dx
Capacity of a band-limited channel with Gaussian noise:
C = W log(1 + S/N) bits per second
(Shannon-Hartley theorem) where W = bandwidth, S = signal power, N = noise power.
Key Results
| Result | Significance |
|---|---|
| H = −Σ pᵢ log pᵢ | Unique measure satisfying natural axioms; matches intuition |
| H_max = log n (uniform) | Uniform distribution maximizes uncertainty |
| Noiseless coding theorem | Entropy = minimum description length |
| Noisy coding theorem | Reliable communication possible iff R < C |
| C = W log(1 + S/N) | Bandwidth and SNR are interchangeable resources |
Redundancy
English text has entropy ~1 bit/character (contextual entropy) but is written with ~4.7 bits/character (26 letters). Redundancy ≈ 75% — which is why you can read texts with many letters removed.
Key References
- Nyquist 1924, 1928 — Sampling theorem, telegraph transmission
- Hartley 1928 — Logarithmic measure of information (precursor)
- Boole 1854 → Shannon 1938 → Shannon 1948: logical calculus → circuit algebra → information algebra