bits.

FREE HISTORICAL FIGURES OF COMPUTING PROFILE

Claude Shannon

1916–2001 · Mathematician and electrical engineer

Claude Shannon

Mathematician and electrical engineer · 1916–2001 · United States

Claude Shannon connected mathematical descriptions with engineering limits. His work on relay circuits showed how symbolic logic could support circuit analysis. His communication theory made it possible to ask precise questions about compression and reliable transmission. These are related achievements, but Boolean circuit equivalence, statistical uncertainty, and the meaning of a message are different subjects.

Two projects, with careful dates

Shannon came to MIT after studying mathematics and electrical engineering at Michigan. His relay-circuit work dates from his graduate research in 1937 and appeared as an article in 1938. MIT's thesis catalog records the M.S. thesis under 1940, the year of his master's and doctoral degrees. It lists Frank Hitchcock as adviser; describing Vannevar Bush's influence does not make Bush the cataloged thesis adviser. MIT thesis record, MIT obituary, 1938 article

At Bell Labs, Shannon published A Mathematical Theory of Communication in two parts in 1948. Its introduction explicitly builds on Nyquist and Hartley and credits John Tukey for the word “bit.” This was a major synthesis and extension, not a claim that no quantitative work on communication existed before it. 1948 paper

Worked mechanism: equivalent switching functions

Use this modern teaching convention: a variable is 1 when its ideal switch conducts, series paths implement AND, and parallel paths implement OR. Consider two parallel branches, one containing A then B, the other A then NOT B. Their conduction condition is:

(A AND B) OR (A AND NOT B)

Factoring gives A AND (B OR NOT B) = A. If A is off, neither branch conducts. If A is on, exactly one of B and its complement allows a path. One ideal A-controlled switch has the same truth table.

This is an original illustrative circuit, not a replica of Shannon's hardware or notation. Logical equivalence is only one engineering criterion. Physical contacts have delays, bounce, wear, and current limits. Separate signals intended to represent B and NOT B may briefly disagree during a transition. A symbolic simplification does not automatically prove identical timing, fault tolerance, power consumption, or implementation cost.

Worked mechanism: expected length, not the size of every file

Suppose an independent source emits symbols A, B, and C with probabilities 0.5, 0.3, and 0.2. Its entropy is the average surprise:

H = −0.5 log2(0.5) − 0.3 log2(0.3) − 0.2 log2(0.2) ≈ 1.4855 bits/symbol.

A prefix code assigns A=0, B=10, C=11. No codeword starts with an entire other codeword, so a concatenated stream can be parsed without separators. Its expected length is 0.5×1 + 0.3×2 + 0.2×2 = 1.5 bits per symbol. For example, ABCA becomes 010110, six bits rather than the eight required by a fixed two-bit code. That particular message is an illustration, not the definition of the expectation.

For a discrete distribution, entropy lower-bounds the expected length of a uniquely decodable binary symbol code. Suitable prefix codes attain an expected length less than H+1. Coding longer independent blocks makes the per-symbol overhead of this bound smaller. Model description, framing, and finite-sample costs still matter. A source entropy does not impose the same minimum length on each individual file, nor does it say every compressor reaches the bound. MIT information and entropy notes, chapter 6

Reliability has a rate and a model

For a memoryless binary symmetric channel, each transmitted bit flips independently with probability p. Its capacity is 1 − h2(p) bits per channel use, where h2 is binary entropy. At p=0.1, capacity is about 0.5310 bits per use. This is not the fraction of raw bits that arrive unchanged, which is 0.9. Coding must make entire messages distinguishable despite many possible noise patterns. Author-hosted information-theory text, example 1.18

The channel-coding result concerns the existence of codes with arbitrarily small error probability at rates below capacity as block lengths increase under the stated model. It does not give zero errors at every finite length, and it does not say an arbitrary code or decoder succeeds. Delay, computational cost, and mismatch between real noise and the model remain engineering problems. 1948 paper, noisy-channel theorem

Compression and error correction therefore perform different tasks. Compression avoids spending bits on predictable source structure. Channel coding adds deliberately structured redundancy to distinguish messages after corruption. Removing all redundancy and then expecting immunity to noise would ignore the second problem.

Secrecy is another distinct requirement

Shannon's 1949 secrecy paper defines perfect secrecy through probabilities: observing the ciphertext must not change the adversary's distribution over messages. For an n-bit message M and an independent uniformly random n-bit key K, C=M XOR K has this property. For any fixed message and ciphertext there is exactly one compatible key, with probability 2^(−n). The same construction fails if that key is reused across messages, because C1 XOR C2=M1 XOR M2. 1949 paper

This one-time-pad example is not a claim that it is the only perfectly secret scheme. Nor does secrecy imply authenticity: flipping a ciphertext bit flips the corresponding recovered message bit. The definitions tell us which property was established and prevent a proof of confidentiality from becoming an unsupported claim about an entire secure system.

Exercises

  1. Coding under a changed model. Keep the code A=0, B=10, C=11, but make the three symbols equally likely. Calculate entropy and expected length. Decode 011100, and explain why the original 1.4855-bit estimate no longer applies.
  2. Capacity versus observed accuracy. For the binary symmetric channel with p=0.1, compare sending 1000 information bits using 1500 channel uses with using 2500. Calculate both rates. Which is below capacity? What conclusion can and cannot be drawn without specifying a finite code and decoder?
  3. Perfect secrecy and reuse. Let M1=01, M2=10, and K=11. Compute both ciphertexts and their XOR. Prove that one ciphertext alone has the same probability for each fixed plaintext under a fresh uniform two-bit key. Explain how known M1 recovers M2 when K is reused.
Compare your reasoning with the worked solutions
  1. Entropy becomes log2(3) ≈ 1.5850 bits per symbol. Expected length is (1+2+2)/3 = 5/3 ≈ 1.6667. Parse the stream as 0 | 11 | 10 | 0, giving ACBA. The source probabilities changed, so the average surprise and expected length changed even though the codebook did not. Neither entropy value describes a message's semantic importance; both refer to a specified probability model.
  2. Rates are 1000/1500 = 2/3 ≈ 0.6667 and 1000/2500 = 0.4 information bits per channel use. Only 0.4 is below approximately 0.5310. The theorem permits families of codes approaching arbitrarily low error at the lower rate as lengths grow. It does not guarantee that the particular 2500-use scheme is reliable. At the higher fixed rate, asymptotically vanishing error is unavailable under this channel model, even though individual raw bits are correct 90% of the time.
  3. C1=10 and C2=01; their XOR is 11, equal to 01 XOR 10. For any fixed two-bit plaintext m and observed ciphertext c, exactly one of the four equally likely keys, m XOR c, produces c, so P(C=c|M=m)=1/4, independent of m. With reuse and known M1, compute K=C1 XOR M1=11, then M2=C2 XOR K=10. A proof requiring a fresh independent key cannot be carried over to a reused-key protocol.

Sources and further study