A Mathematical Theory of Communication — Information Gets a Unit

Page 379 of the Bell System Technical Journal, Volume XXVII, Number 3, July 1948, opens a forty-five-page paper by Claude Shannon of Bell Telephone Laboratories. The title is "A Mathematical Theory of Communication". Page 423 ends with three words in parentheses: "(To be continued)". The continuation ran in Number 4 of the same volume, October 1948, pages 623 to 656.

One paper, two instalments. The July issue carried the introduction, Part I (Discrete Noiseless Systems) and Part II (The Discrete Channel with Noise). The October issue carried Part III (Mathematical Preliminaries), Part IV (The Continuous Channel) and Part V (The Rate for a Continuous Source). The discrete theory went out first; the continuous theory followed three months later.

It begins by throwing meaning away

The sentence that fixes the character of the whole paper appears on the first page: "The fundamental problem of communication is that of reproducing at one point either exactly or approximately a message selected at another point."

Shannon then does something that reads as an act of engineering discipline rather than of philosophy. Messages frequently have meaning, he grants; they refer to or are correlated with physical or conceptual entities. "These semantic aspects of communication are irrelevant to the engineering problem." What matters is only that the actual message is one selected from a set of possible messages — and that at design time nobody knows which. The system must therefore be built to work for every possible selection.

Refusing to handle meaning is not a limitation confessed; it is the precondition for measurement. Strip out meaning and what is left is choice, and choices can be counted.

The bit

That measurement should be logarithmic was already Hartley's point, and Shannon says so. What he adds is that the choice of base is the choice of unit — and then this: "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."

He does not claim the word. He attributes it, in print, to the statistician John Tukey. The examples that follow are as concrete as the sentence: a device with two stable positions, such as a relay or a flip-flop circuit, stores one bit; N such devices store N bits, since the number of possible states is 2^N. Use base 10 and the unit is the decimal digit, worth about 3.32 bits.

Memory capacity, bandwidth, compression ratio, key length — everything since has been quoted in this unit.

Entropy, source coding, channel capacity

The apparatus the paper introduces sits in modern textbooks in very nearly the form it was first given.

Entropy. For a source emitting symbols with probabilities p, the quantity H = −Σ p log p measures how much information it produces. A source with statistical structure — English text, say — carries far less than a naive count of its symbol alphabet suggests. Redundancy became a measurable quantity rather than an impression.

Source coding. A biased source can be compressed to an average length approaching H, and no further. That is the floor under every lossless compressor ever written.

Capacity and noise. Theorem 11, in Part II, is the centre of the paper. Given a discrete channel of capacity C and a source of entropy H per second: if H ≤ C, there exists a coding system such that the source can be transmitted over the channel with an arbitrarily small frequency of errors. If H > C, the equivocation can be brought within an arbitrarily small margin of H − C — and no method of encoding gives an equivocation less than H − C.

This ran against the intuition of the day. Noise was understood to impose errors, and the way to reduce errors was to slow down. Shannon showed that so long as you stay under capacity, error rate can be driven arbitrarily low without giving up rate. And the proof does not exhibit a code. It shows that a code with the required property must exist somewhere within a certain family. What is achievable was established without any construction being offered, and the following half-century of coding theory was largely the work of building real codes up to the performance that existence proof had promised.

Part IV carries the argument into continuous signals and arrives at Theorem 17: a channel of bandwidth W perturbed by white thermal noise of power N, with average transmitter power limited to P, has capacity C = W log((P+N)/N). Communications engineers still use that expression.

Where it stood

Shannon did not conjure the field out of nothing, and says so in his opening paragraph: a basis for such a theory, he writes, is contained in the important papers of Nyquist and Hartley. What the present paper adds, he continues, is a number of new factors — in particular the effect of noise in the channel, the savings available from the statistical structure of the message, and the savings available from the nature of the final destination.

Shannon's wider career belongs on his own page. Confined to this paper, the effect is easy to state. In 1948 a unit for measuring information and a set of theorems bounding what could be done with it arrived together. From those two instalments onward it became possible, for transmission, storage, compression and secrecy alike, to say where the limit is and prove it.