A Mathematical Theory of Communication

Reproducing at one point, exactly or approximately, a message selected at another point.

Semantic aspects are irrelevant to the engineering problem. What matters is that the actual message is one selected from a set of possible messages, and the system must work for every possible selection, not just the one actually sent.

It is practically more useful (time, bandwidth or number of relays vary linearly with the log of the number of possibilities); it matches intuition (two punched cards should store twice as much as one); it is mathematically more convenient for limiting operations.

The unit of information when logarithms are taken to base 2 (“binary digit”), a word suggested by J. W. Tukey. A device with two stable states stores one bit; \(N\) such devices store \(\log_2 2^N = N\) bits.

Base 2 gives bits, base 10 decimal digits (about 3⅓ bits each), base \(e\) natural units. Changing from base \(a\) to base \(b\) multiplies by \(\log_b a\).

Information source → transmitter → channel (where a noise source acts) → receiver → destination.

Discrete (message and signal are sequences of discrete symbols, e.g. telegraphy), continuous (both are continuous functions, e.g. radio, television) and mixed (e.g. PCM speech). The discrete case comes first and founds the others.

\(C = \lim_{T \to \infty} \frac{\log N(T)}{T}\), where \(N(T)\) is the number of allowed signals of duration \(T\): the growth rate of the log of the number of possible signals.

Each symbol carries \(\log_2 32 = 5\) bits, so \(C = 5n\) bits per second: the maximum rate, reached only if the source feeding the channel makes full use of it.

As a set of states with a graph: each state permits certain symbols, and sending one moves to a new state (e.g. after a space only a dot or dash may follow). Theorem 1 gives \(C = \log W\), with \(W\) the largest real root of a determinant equation built from the symbol durations.

Messages aren’t random: in English E is more frequent than Q, TH more than XP. Proper encoding exploits this, as Morse code already does by giving the most common letter, E, the shortest symbol (a dot).

As a stochastic process choosing successive symbols with probabilities that may depend on preceding choices; conversely any stochastic process producing discrete symbols from a finite set is a discrete source (natural languages, quantized speech, abstract processes).

\(p(i, j) = p(i)\,p_i(j)\) and \(p(i) = \sum_j p(i, j) = \sum_j p(j)\,p_j(i)\), with \(\sum_j p_i(j) = 1\). The general \(n\)-gram case needs \(n\)-gram probabilities or transition probabilities \(p_{i_1 \ldots i_{n-1}}(i_n)\).

Text generated by increasingly complex stochastic processes over 26 letters and space:

order	model
zero	letters independent and equiprobable
first	letters independent, with English frequencies
second	digram structure
third	trigram structure
word, first order	words independent, with their frequencies
word, second order	word transition probabilities

The output looks noticeably more like English at each step: an early demonstration of n-gram language models.

Samples have reasonably good structure out to about twice the range the model takes into account: digram text gives plausible four-letter sequences, and word-digram text gives runs of four or more words that fit into sentences.

By sampling from a book: pick a random letter, open another page and read until that letter appears, record the letter after it, and repeat. This samples from the true digram (or trigram, word) statistics.

There are finitely many states and transition probabilities \(p_i(j)\); a letter is produced at each transition. The states encode the “residue of influence” from preceding letters, so a trigram source needs up to \(n^2\) states (pairs of preceding letters).

One where every sequence has the same statistical properties (except for a set of probability zero): letter and \(n\)-gram frequencies in a long sequence converge to the same limits. It lets averages along one sequence stand for averages over the ensemble.

The graph doesn’t fall into two parts that can’t reach each other, and the greatest common divisor of the lengths of all its circuits is 1 (otherwise sequences have a periodic structure).

A weighted mixture \(L = p_1 L_1 + p_2 L_2 + \ldots\) of ergodic components: one component is chosen at the start with probability \(p_i\), and the sequence then continues according to it indefinitely.

(1) Continuous in the \(p_i\). (2) For equally likely events, a monotonically increasing function of \(n\). (3) If a choice is broken into successive choices, \(H\) is the weighted sum of the individual values of \(H\).

Choosing directly among three outcomes is equivalent to first choosing between two halves, then (half the time) between ⅔ and ⅓, so \(H(\tfrac12, \tfrac13, \tfrac16) = H(\tfrac12, \tfrac12) + \tfrac12 H(\tfrac23, \tfrac13)\).

The only \(H\) satisfying continuity, monotonicity and decomposition is \(H = -K \sum_{i=1}^{n} p_i \log p_i\), with \(K\) a positive constant (which just fixes the unit). Shannon called it entropy, after the \(H\) of Boltzmann’s H theorem.

No: he said the theorem isn’t necessary for the theory and only lends plausibility; the real justification of the definitions lies in their implications (the coding theorems).

\(H = -(p \log p + q \log q)\), \(q = 1 - p\): zero when \(p = 0\) or \(1\), maximal at 1 bit when \(p = \tfrac12\), symmetric around it.

\(H = 0\) only when one outcome is certain. For \(n\) outcomes \(H\) is maximal, \(\log n\), when all are equally likely; any change toward equalizing the probabilities (an averaging of them) increases \(H\).

\(H(x, y) \le H(x) + H(y)\), with equality only if \(x\) and \(y\) are independent: the uncertainty of a joint event is at most the sum of the individual uncertainties.

\(H_x(y) = -\sum_{i,j} p(i, j) \log p_i(j)\), the average uncertainty about \(y\) when \(x\) is known. Then \(H(x, y) = H(x) + H_x(y)\).

No: \(H(y) \ge H_x(y)\), with equality only if \(x\) and \(y\) are independent.

The average of the entropies \(H_i\) of the next-symbol distribution in each state, weighted by the state probabilities: \(H = \sum_i P_i H_i = -\sum_{i,j} P_i\,p_i(j) \log p_i(j)\) bits per symbol. Per second, \(H' = mH\) for \(m\) symbols per second.

For long sequences, almost all probability goes to sequences whose probability \(p\) satisfies \(\frac{\log p^{-1}}{N} \approx H\). So we may treat long sequences as if there were just \(2^{HN}\) of them, each with probability \(2^{-HN}\).

\(G_N = -\frac1N \sum p(B) \log p(B)\) over blocks \(B\) of \(N\) symbols (entropy per symbol of blocks); \(F_N\) is the conditional entropy of the next symbol given the \(N - 1\) before it, the entropy of the \(N\)th-order approximation. Both decrease monotonically to \(H\), and \(F_N \le G_N\) is the better estimate.

Relative entropy: the ratio of a source’s entropy to the maximum it could have with the same symbols, which is the maximum compression into the same alphabet. Redundancy = 1 − relative entropy.

Roughly 50%, counting statistical structure over about eight letters: half of what we write is determined by the structure of the language and half is chosen freely.

By several independent methods that agreed: computing the entropy of the approximations to English, deleting a fraction of letters and having people restore them, and known results in cryptography.

With zero redundancy any letter array would be a crossword; with too much, constraints make large crosswords impossible. Under random-like constraints large two-dimensional crosswords are just possible at 50% redundancy, and three-dimensional ones at about 33%.

As finite-state transducers: output \(y_n = f(x_n, \alpha_n)\) and next state \(\alpha_{n+1} = g(x_n, \alpha_n)\). A transducer is non-singular if an inverse transducer can recover its input.

The output is again a finite-state source with entropy per unit time no greater than the input’s; equal if the transducer is non-singular. Encoding cannot create information.

For a source with entropy \(H\) bits per symbol and a channel of capacity \(C\) bits per second, one can encode to transmit at an average rate of \(\frac{C}{H} - \epsilon\) symbols per second for arbitrarily small \(\epsilon\), but never faster than \(\frac{C}{H}\).

Sort the length-\(N\) messages by decreasing probability \(p_s\); encode message \(s\) by the binary expansion of the cumulative probability \(P_s\) of all more probable messages, to \(m_s\) places with \(\log_2 \frac{1}{p_s} \le m_s < 1 + \log_2 \frac{1}{p_s}\). Probable messages get short codes, and all codes differ.

The average length per symbol \(H'\) satisfies \(G_N \le H' < G_N + \frac1N\), so it approaches \(H\) as the block length \(N\) grows: longer delay buys better efficiency.

Sort messages by probability and split them repeatedly into two groups of nearly equal probability, assigning 0 or 1 at each split; apart from minor differences it equals Shannon’s method (Shannon–Fano coding).

For maximum power transfer a transformer matches a generator to its load; likewise the encoder should match the source to the channel statistically, so the channel sees the input statistics that maximize its entropy.

\(H = \tfrac12 \cdot 1 + \tfrac14 \cdot 2 + 2 \cdot \tfrac18 \cdot 3 = \tfrac74\) bits per symbol, achieved exactly by

A	0
B	10
C	110
D	111

The coded 0s and 1s are equally likely, one bit each, and the average length is \(\tfrac74\) digits per letter.

A source that can produce only one message (like a machine computing the digits of π) has zero entropy and needs no channel. If we choose to use only some statistics (e.g. letter frequencies of English), the needed capacity is the entropy of the maximum-entropy source satisfying those statistics.

Subtracting errors ignores that the receiver doesn’t know where they are. In the extreme of a channel whose output is independent of its input, half the symbols would still be “right” by chance, yet nothing is transmitted.

The equivocation \(H_y(x)\) is the conditional entropy of the message given the received signal: the average ambiguity left. The rate is \(R = H(x) - H_y(x)\). For 1% errors at 1000 symbols/s it is about 81 bits/s, so \(R \approx 919\) bits/s.

\(R = H(x) - H_y(x)\) (information sent minus uncertainty about what was sent) \(= H(y) - H_x(y)\) (information received minus the part due to noise) \(= H(x) + H(y) - H(x, y)\) (the bits common to both). Today this is the mutual information.

An observer seeing both sent and received messages can send correction data so all but an arbitrarily small fraction of errors are fixed if and only if the correction channel has capacity at least \(H_y(x)\): equivocation is exactly the extra information needed to correct the message.

\(C = \max \big(H(x) - H_y(x)\big)\), maximized over all possible input sources. For a noiseless channel \(H_y(x) = 0\) and this agrees with the earlier definition.

One might expect that driving the error rate to zero requires redundancy growing without bound, so the rate goes to zero. Instead there is a definite capacity \(C\): information can be sent at any rate below \(C\) with arbitrarily small error.

If the source entropy per second \(H \le C\), there is a code transmitting with arbitrarily small error frequency (or equivocation). If \(H > C\), equivocation can be brought down to \(H - C + \epsilon\) but no lower: “Nature takes payment by requiring just that much uncertainty.”

By random coding: assign the \(2^{TR}\) messages to randomly chosen typical channel inputs and average the error probability over all such codes. For \(R < C\) the chance that another message lands among the \(2^{TH_y(x)}\) plausible causes of a received signal vanishes as \(T\) grows, so some code (indeed almost every code) is nearly ideal.

Its proof is close to an existence proof: following it to build codes is impractical, and apart from trivial cases Shannon knew no explicit sequence of codes approaching the ideal, which he linked to the difficulty of explicitly constructing good approximations to random sequences.

Redundancy left in the source helps combat noise if the receiver uses it: telegraphy doesn’t compress away English’s ~50% redundancy, so a sizable fraction of letters can be garbled and still be reconstructed from context.

Besides matching probabilities to signal lengths, it lets a large sample of noise affect the signal before the receiver judges what was sent; larger samples sharpen the statistical decision.

Blocks of 7 binary symbols where noise flips at most one: \(X_3, X_5, X_6, X_7\) carry the message; \(X_4, X_2, X_1\) are parity bits making \(X_4{+}X_5{+}X_6{+}X_7\), \(X_2{+}X_3{+}X_6{+}X_7\) and \(X_1{+}X_3{+}X_5{+}X_7\) even. At the receiver, the three parity checks \(\alpha\beta\gamma\), read as a binary number, give the position of the wrong bit (0 = no error).

check	positions
\(\alpha\)	4 5 6 7
\(\beta\)	2 3 6 7
\(\gamma\)	1 3 5 7

It transmits at exactly the channel capacity, \(\tfrac47\) bits per symbol, with all errors corrected.

A function with no frequencies above \(W\) is completely determined by its values at points \(\frac{1}{2W}\) seconds apart: \(f(t) = \sum_n X_n \frac{\sin \pi(2Wt - n)}{\pi(2Wt - n)}\) with \(X_n = f\!\left(\frac{n}{2W}\right)\).

By the sampling theorem a signal of band \(W\) and duration \(T\) is fixed by \(2TW\) samples, which serve as coordinates; an ensemble of such signals is then a probability distribution in that space.

\(H = -\int p(x) \log p(x)\,dx\). Unlike discrete entropy it is relative to the coordinate system (it changes by the expected log Jacobian under a change of variables) and can be negative; rates and capacities, being differences of entropies, are unaffected.

The Gaussian, with \(H = \log \sqrt{2\pi e}\,\sigma\). (On a half line with fixed mean \(a\), the exponential, with \(H = \log ea\).)

\(C = W \log \frac{P + N}{N}\) for bandwidth \(W\), average signal power \(P\) and white noise power \(N\). To approach it, the transmitted signals must themselves resemble white noise.

Take \(M = 2^s\) samples of white noise of duration \(T\) as codewords; send the one numbered by each group of \(s\) message bits; the receiver picks the codeword with the least RMS distance to what it received (the most probable signal). As \(T\) grows, the rate approaches \(W \log \frac{P+N}{N}\).

Exact specification of a continuous quantity needs infinitely many bits, so exact transmission needs infinite capacity. The useful question is transmission within a tolerance, measured by a fidelity criterion.

With a fidelity criterion \(v = \iint \rho(x, y) P(x, y)\,dx\,dy\) (an average distortion), the rate \(R_1\) is the minimum of \(\iint P(x, y) \log \frac{P(x, y)}{P(x)P(y)}\,dx\,dy\) over systems achieving fidelity \(v_1\). Theorem 21: transmission at that fidelity is possible over a channel iff \(R_1 \le C\). This is the origin of rate–distortion theory.