# A Mathematical Theory of Communication

> By Claude E. Shannon (1948). Originally published in *The Bell System Technical Journal*, Vol. 27, pp. 379–423, 623–656, July, October, 1948.
> Digital Edition: https://spinchange.github.io/the-mathematical-theory-of-communication/
> Full Unabridged Text: https://spinchange.github.io/the-mathematical-theory-of-communication/llms-full.txt

The foundational paper of Information Theory and digital communications. Shannon established the mathematical definition of information, introduced the universal term and concept of the **bit** (suggested by John W. Tukey), quantified source entropy ($H = -\sum p_i \log_2 p_i$), defined channel capacity ($C$), formulated the Source Coding Theorem, proved the Noisy Channel Coding Theorem, derived the Shannon-Hartley theorem ($C = W \log_2(1 + P/N)$), and inaugurated Rate-Distortion Theory.

---

## 🧭 Structure & Section Directory

### Introduction
- [Introduction](https://spinchange.github.io/the-mathematical-theory-of-communication/#sec-intro): Defines the general communication system model (Information Source, Transmitter, Channel, Noise Source, Receiver, Destination). Establishes the logarithmic measure of information and introduces the **bit** (binary digit).

### Part I: Discrete Noiseless Systems
- [1. The Discrete Noiseless Channel](https://spinchange.github.io/the-mathematical-theory-of-communication/#sec-1): Capacity $C = \lim_{T\to\infty} \frac{\log N(T)}{T}$; determinant equation for allowed sequence graph states (Theorem 1).
- [2. The Discrete Source of Information](https://spinchange.github.io/the-mathematical-theory-of-communication/#sec-2): Statistical sources modeled as discrete Markov processes; transitions, state probabilities, and artificial stochastic languages.
- [3. The Series of Approximations to English](https://spinchange.github.io/the-mathematical-theory-of-communication/#sec-3): Landmark introduction of $n$-gram language models: Zero-order, 1st-order, 2nd-order (digram), 3rd-order (trigram), 1st-order word, and 2nd-order word approximations to English.
- [4. Graphical Representation of a Markoff Process](https://spinchange.github.io/the-mathematical-theory-of-communication/#sec-4): Linear graphs of Markov processes, closed loops, and circuit analysis.
- [5. Ergodic and Mixed Sources](https://spinchange.github.io/the-mathematical-theory-of-communication/#sec-5): Ergodicity in information sources; decomposing mixed sources into ergodic components.
- [6. Choice, Uncertainty and Entropy](https://spinchange.github.io/the-mathematical-theory-of-communication/#sec-6): Axiomatic derivation of information entropy $H(p_1, \dots, p_n) = -K \sum p_i \log p_i$ (Theorem 2).
- [7. The Entropy of an Information Source](https://spinchange.github.io/the-mathematical-theory-of-communication/#sec-7): Entropy rate of ergodic sources; conditional entropy and asymptotic equipartition (Theorems 3–6).
- [8. Representation of the Encoding and Decoding Operations](https://spinchange.github.io/the-mathematical-theory-of-communication/#sec-8): Transducers, unicity, and preservation of ergodicity (Theorems 7–8).
- [9. The Fundamental Theorem for a Noiseless Channel](https://spinchange.github.io/the-mathematical-theory-of-communication/#sec-9): Shannon's Noiseless Coding Theorem: average transmission rate can approach $C/H$ with arbitrarily small coding delay (Theorem 9).
- [10. Discussion and Examples](https://spinchange.github.io/the-mathematical-theory-of-communication/#sec-10): Shannon-Fano prefix coding algorithm and efficiency proofs.

### Part II: The Discrete Channel with Noise
- [11. Representation of a Noisy Discrete Channel](https://spinchange.github.io/the-mathematical-theory-of-communication/#sec-11): Transition probability matrix $p_i(j)$; joint entropy and conditional entropy.
- [12. Equivocation and Channel Capacity](https://spinchange.github.io/the-mathematical-theory-of-communication/#sec-12): Equivocation $H_y(x)$ (conditional entropy of transmitted message given received signal); mutual information $R = H(x) - H_y(x)$; Channel Capacity $C = \max [H(x) - H_y(x)]$ (Theorem 10).
- [13. The Fundamental Theorem for a Discrete Channel with Noise](https://spinchange.github.io/the-mathematical-theory-of-communication/#sec-13): **Shannon's Landmark Noisy-Channel Coding Theorem**: For any transmission rate $R < C$, there exists a code that achieves arbitrarily small probability of error $\epsilon$; impossible for $R > C$ (Theorem 11).
- [14. Discussion](https://spinchange.github.io/the-mathematical-theory-of-communication/#sec-14): Random coding technique; high-dimensional geometry of transmitted and received signal spheres (Theorem 12).
- [15. Example of a Discrete Channel and its Capacity](https://spinchange.github.io/the-mathematical-theory-of-communication/#sec-15): The Binary Symmetric Channel ($C = 1 + p \log_2 p + q \log_2 q$).
- [16. The Channel Capacity in Certain Special Cases](https://spinchange.github.io/the-mathematical-theory-of-communication/#sec-16): Symmetric transition matrices and channel decomposition.
- [17. An Example of Efficient Coding](https://spinchange.github.io/the-mathematical-theory-of-communication/#sec-17): Parity-check matrix codes, geometric hypercube error correction (anticipating Hamming codes).

### Appendices 1–4
- [Appendix 1](https://spinchange.github.io/the-mathematical-theory-of-communication/#app-1): Growth of Blocks of Symbols with Finite State Condition.
- [Appendix 2](https://spinchange.github.io/the-mathematical-theory-of-communication/#app-2): Mathematical proof and derivation of $H = -\sum p_i \log p_i$.
- [Appendix 3](https://spinchange.github.io/the-mathematical-theory-of-communication/#app-3): Rigorous theorems on ergodic sources.
- [Appendix 4](https://spinchange.github.io/the-mathematical-theory-of-communication/#app-4): Maximizing rate for systems with constraints.

### Part III: Mathematical Preliminaries
- [18. Sets and Ensembles of Functions](https://spinchange.github.io/the-mathematical-theory-of-communication/#sec-18): Stochastic processes in function spaces, stationary and ergodic function ensembles.
- [19. Band Limited Ensembles of Functions](https://spinchange.github.io/the-mathematical-theory-of-communication/#sec-19): **Nyquist-Shannon Sampling Theorem**: $f(t) = \sum_{-\infty}^\infty X_n \frac{\sin \pi (2Wt - n)}{\pi (2Wt - n)}$; $2W$ coordinates per second completely determine a signal of bandwidth $W$ (Theorem 13).
- [20. Entropy of a Continuous Distribution](https://spinchange.github.io/the-mathematical-theory-of-communication/#sec-20): Differential entropy $H = -\int p(x) \log p(x) dx$; transformation under coordinate changes.
- [21. Entropy of an Ensemble of Functions](https://spinchange.github.io/the-mathematical-theory-of-communication/#sec-21): Entropy power $N_1 = \frac{1}{2\pi e} \exp(2H')$ and Gaussian maximum entropy.
- [22. Entropy Loss in Linear Filters](https://spinchange.github.io/the-mathematical-theory-of-communication/#sec-22): Entropy power gain in dB through linear filters; Table 1 filter characteristics (Theorem 14).
- [23. Entropy of a Sum of Two Ensembles](https://spinchange.github.io/the-mathematical-theory-of-communication/#sec-23): Entropy power inequality: $\overline{N}_1 + \overline{N}_2 \le \overline{N}_3$ (Theorems 15–16).

### Part IV: The Continuous Channel
- [24. The Capacity of a Continuous Channel](https://spinchange.github.io/the-mathematical-theory-of-communication/#sec-24): Definition of continuous channel capacity $C = \lim_{T\to\infty} \max [H(y) - H_x(y)]$.
- [25. Channel Capacity with an Average Power Limitation](https://spinchange.github.io/the-mathematical-theory-of-communication/#sec-25): **The Shannon-Hartley Theorem**: $C = W \log_2\Bigl(1 + \frac{P}{N}\Bigr)$ for bandwidth $W$, signal power $P$, and white Gaussian noise $N$ (Theorems 17–19).
- [26. The Channel Capacity with a Peak Power Limitation](https://spinchange.github.io/the-mathematical-theory-of-communication/#sec-26): Upper and lower capacity bounds under peak power constraints (Theorem 20).

### Part V: The Rate for a Continuous Source
- [27. Fidelity Evaluation Functions](https://spinchange.github.io/the-mathematical-theory-of-communication/#sec-27): Foundation of **Rate-Distortion Theory**; distortion measure $v(x, y)$ and RMS discrepancy.
- [28. The Rate for a Source Relative to a Fidelity Evaluation](https://spinchange.github.io/the-mathematical-theory-of-communication/#sec-28): Rate-distortion function $R(v_1)$ and source transmission bounds (Theorem 21).
- [29. The Calculation of Rates](https://spinchange.github.io/the-mathematical-theory-of-communication/#sec-29): Explicit rate formula for Gaussian sources under RMS distortion: $R = W_1 \log \frac{Q_1}{N}$ (Theorems 22–23).

### Appendices 5–7
- [Appendix 5](https://spinchange.github.io/the-mathematical-theory-of-communication/#app-5): Preservation of ergodicity under measure-preserving invariant time shifts.
- [Appendix 6](https://spinchange.github.io/the-mathematical-theory-of-communication/#app-6): Derivation of lower and upper bounds on entropy power of convolutions.
- [Appendix 7](https://spinchange.github.io/the-mathematical-theory-of-communication/#app-7): Abstract formulation of mutual information $R = \frac{1}{T}\iint P(x,y)\log\frac{P(x,y)}{P(x)P(y)}dx dy$, data-processing inequality ($R(x,v) \le R(x,y)$), and topological dimension rate $\lambda$.

---

## 📐 Canonical Equations

1. **Shannon Entropy (Discrete)**:
   $$H = -\sum_{i=1}^n p_i \log_2 p_i$$

2. **Equivocation & Mutual Information**:
   $$R = H(x) - H_y(x) = H(y) - H_x(y) = H(x) + H(y) - H(x, y)$$

3. **Noiseless Channel Capacity**:
   $$C = \lim_{T\to\infty} \frac{\log_2 N(T)}{T}$$

4. **Noisy Channel Capacity**:
   $$C = \max_{P(x)} [H(x) - H_y(x)]$$

5. **Shannon-Hartley Theorem (AWGN Continuous Channel)**:
   $$C = W \log_2\Bigl(1 + \frac{P}{N}\Bigr)$$

6. **Sampling Theorem**:
   $$f(t) = \sum_{n=-\infty}^\infty X_n \frac{\sin \pi (2Wt - n)}{\pi (2Wt - n)}$$

7. **Rate-Distortion (Continuous White Noise Source)**:
   $$R = W_1 \log_2 \frac{Q_1}{N}$$

---

## 💡 Key Quotations

> "The fundamental problem of communication is that of reproducing at one point either exactly or approximately a message selected at another point. Frequently the messages have meaning; that is they refer to or are correlated according to some system with certain physical or conceptual entities. These semantic aspects of communication are irrelevant to the engineering problem. The significant aspect is that the actual message is one selected from a set of possible messages." (Introduction)

> "The choice of a logarithmic base corresponds to the choice of a unit for measuring information. 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." (Introduction)

> "Can we define a quantity which will measure, in some sense, how much information is 'produced' by such a process, or better, at what rate information is produced? ... The form of $H$ will be recognized as that of entropy as defined in certain formulations of statistical mechanics." (§6)

---

## 🎓 Citation & Colophon

```bibtex
@article{shannon1948communication,
  title={A Mathematical Theory of Communication},
  author={Shannon, Claude E.},
  journal={The Bell System Technical Journal},
  volume={27},
  number={3},
  pages={379--423, 623--656},
  year={1948},
  publisher={Nokia Bell Labs}
}
```