Claude Shannon

How to use this course

Claude Shannon wrote two founding documents of the digital age eleven years apart. His 1937 master’s thesis showed that relay circuits obey Boole’s algebra of logic, which made circuit design a branch of algebra. His 1948 paper “A Mathematical Theory of Communication” defined information as a measurable quantity, proved that every channel has a capacity, and showed that reliable communication at any rate below capacity is possible. Around these he did fundamental work on cryptography, sampling, computer chess and machine learning. He also built juggling machines and rode a unicycle through the corridors of Bell Labs.

Each technical lesson opens with a paragraph for the general reader, then gives precise statements, proof sketches and exercises with folded solutions. Logarithms are to base 2 unless stated otherwise, so information is measured in bits. Lessons 05 to 07 follow the 1948 paper and its 1949 companion on noise; Lesson 08 covers the secrecy paper; Lessons 09 and 10 cover his later work.

Timeline

Gaylord and Ann Arbor, 1916–1936

Claude Elwood Shannon was born on 30 April 1916 in a hospital in Petoskey, Michigan, and grew up in the nearby small town of Gaylord. His father, also named Claude Elwood Shannon, was a businessman who served for a time as a probate judge. His mother, Mabel Wolf Shannon, taught languages and became principal of Gaylord High School.

As a boy he built things: model aeroplanes, a radio-controlled boat, and a telegraph line to a friend’s house half a mile away that used the wire of a barbed-wire fence. He delivered telegrams for Western Union. His hero was Thomas Edison, who turned out to be a distant relative. The habit of building gadgets stayed with him all his life and fed directly into his science.

Michigan

He graduated from Gaylord High School in 1932 and entered the University of Michigan in Ann Arbor. There he first met Boole’s algebra of logic. In 1936 he graduated with two bachelor’s degrees, one in electrical engineering and one in mathematics. The double training mattered: almost everything he did afterwards came from seeing an engineering problem with a mathematician’s eyes.

MIT: relays and genetics, 1936–1940

In 1936 Shannon answered a notice for a research assistant to run Vannevar Bush’s differential analyzer at MIT. The analyzer was a room-sized mechanical computer that solved differential equations with shafts, gears and wheel-and-disc integrators. It was set up for each problem by a complex control circuit of relays. Shannon noticed that the relay circuits behaved like propositions in Boole’s logic. He spent the summer of 1937 at Bell Telephone Laboratories, where switching networks of exactly this kind ran the telephone system.

His master’s thesis, A Symbolic Analysis of Relay and Switching Circuits, submitted in August 1937 and published in 1938, worked this out in full (Lesson 04). The paper won the Alfred Noble Prize of the American engineering societies. Later writers have called it the most important master’s thesis of the century. It turned the design of switching circuits from an art into a calculation, and every digital computer’s logic is designed in its language.

A thesis in genetics

Bush then suggested that Shannon try algebra on another subject, and arranged for him to work at the Cold Spring Harbor laboratory on Long Island. The result was his doctoral thesis in mathematics, An Algebra for Theoretical Genetics (MIT, 1940), supervised by Frank Lauren Hitchcock. It gave an algebraic calculus for the distribution of genotypes in a population under random mating over several generations. Shannon never published it, and population geneticists did not see it until it was printed in his collected papers in 1993.

In January 1940 he married Norma Levor; they divorced the following year.

Princeton, Bell Labs and the war, 1940–1945

In 1940–41 Shannon held a National Research Fellowship at the Institute for Advanced Study in Princeton, working under Hermann Weyl. He spent much of his time thinking about the transmission of information, the problem that would occupy him for the next eight years. In 1941 he joined Bell Labs in New Jersey as a research mathematician.

The war set his agenda. Under contracts with the National Defense Research Committee he worked on anti-aircraft fire control: predicting where an aircraft will be from noisy radar tracks. With Ralph Blackman and Hendrik Bode he wrote a report on data smoothing and prediction in fire-control systems, which treated the problem as separating a signal from noise, in parallel with Norbert Wiener’s classified work on prediction. He also worked on secure telephony, including the X System that protected transatlantic telephone conversations between Allied leaders.

Early in 1943 Alan Turing came to Bell Labs to study speech encipherment. Neither could tell the other about his secret work, but they met at tea in the cafeteria and talked about thinking machines; Turing showed Shannon his 1936 paper on computable numbers. In September 1945 Shannon finished a classified memorandum, “A Mathematical Theory of Cryptography”. Much of the theory of information appears there first, worked out for codebreaking. The declassified version became the 1949 secrecy paper (Lesson 08). The general theory came out in 1948.

Switching algebra

For the general reader. A relay is a switch worked by an electromagnet. Two switches in a row let current through only if both are closed; two side by side let it through if either is. These are exactly “and” and “or” in logic. Shannon saw that a whole network of relays is therefore a formula in Boole’s algebra, and that simplifying the formula simplifies the circuit.

The calculus of contacts

Give each contact a variable that is 1 when the contact conducts and 0 when it does not. A series connection conducts when both parts do, so it corresponds to the product \(xy\). A parallel connection conducts when either does, so it corresponds to \(x+y\) with \(1+1=1\). A contact that is closed when relay \(X\) is unenergized corresponds to the complement \(x'\). Shannon’s 1938 paper used the dual convention: his variable was the hindrance, 0 for a closed contact, so that series became sum and parallel became product. The two conventions are interchanged by De Morgan’s laws, and engineers soon adopted the one used here.

Proof. Both sides are Boolean functions; check them at \(x_i=1\) and at \(x_i=0\). At \(x_i=1\) the right side is \(f|_{x_i=1}+0\); at \(x_i=0\) it is \(f|_{x_i=0}\). ∎ The expansion is Boole’s, from his books of 1847 and 1854; Shannon made it the basic tool of circuit synthesis. In circuit terms it is a transfer contact on relay \(X_i\) that routes the current to one of two smaller networks.

How big must a circuit be?

In “The synthesis of two-terminal switching circuits” (1949) Shannon asked how many contacts are needed to realize a function of \(n\) variables. There are \(2^{2^n}\) functions, a huge number, while the number of small networks is comparatively modest. A counting argument then shows that most functions need large networks.

The lower bound is proved by showing that the number of networks with \(k\) contacts is at most about \((Ckn)^k\) for a constant \(C\), and comparing with \(2^{2^n}\) (Exercise 4.3 does the same for gate circuits). Oleg Lupanov showed in 1958 that \((1+\varepsilon)2^n/n\) contacts always suffice, so the constant is sharp. The paradox Shannon left behind is that although almost every function is hard, no one can name a specific function proved to need large circuits. That gap is still at the centre of complexity theory.

Entropy and source coding

For the general reader. How much information is in a message? Shannon’s answer ignores meaning and looks only at uncertainty. A fair coin toss carries one bit. A message from a predictable source, like English text where “q” is almost always followed by “u”, carries less per symbol than its length suggests, and can be compressed. Shannon’s entropy measures exactly how far: no lossless code can do better on average, and good codes come arbitrarily close.

Entropy

Shannon built on Harry Nyquist’s 1924 and Ralph Hartley’s 1928 papers at Bell Labs; Hartley had measured information by the logarithm of the number of possible messages. Shannon added probability. For a random variable \(X\) taking values with probabilities \(p_1,\dots,p_n\),

Shannon took the name from statistical mechanics, where the same expression, with Boltzmann’s constant in place of the base-2 logarithm, is the Gibbs entropy. He credited John Tukey with the word “bit”.

Proof sketch. Grouping \(s^m\) equally likely outcomes into \(s^{m-1}\) groups of \(s\) gives \(A(s^m)=mA(s)\). Comparing \(s^m\le t^n<s^{m+1}\) and using monotonicity shows \(A(t)/A(s)=\log t/\log s\), so \(A(n)=K\log n\). For rational probabilities \(p_i=n_i/N\), view a choice among \(N\) equal outcomes as a choice of \(i\) followed by a choice among \(n_i\); then \(K\log N=H(p)+\sum p_iK\log n_i\), which gives the formula. Continuity extends it to all \(p\). ∎

The source coding theorem

Let \(X_1,X_2,\dots\) be independent copies of \(X\). By the weak law of large numbers applied to \(-\log p(X_i)\),

This is the asymptotic equipartition property. It says that for large \(n\) almost all probability sits on a typical set of about \(2^{nH}\) sequences, each of probability about \(2^{-nH}\).

For lossless variable-length codes the corresponding statement is sharp at every block length. A prefix code is one in which no codeword begins another, so that a stream can be cut into codewords without separators.

Proof of the bound. With \(q_i=2^{-\ell_i}/\sum_j2^{-\ell_j}\), \(\bar L-H=\sum p_i\log(p_i/q_i)-\log\sum_j2^{-\ell_j}\ge0\), since the first term is a Kullback–Leibler divergence and the second is non-negative by Kraft. The lengths \(\lceil-\log p_i\rceil\) satisfy Kraft and are less than \(-\log p_i+1\). ∎ Coding blocks of \(k\) symbols brings the cost per symbol within \(1/k\) of \(H\). Shannon’s construction, and a similar one by Robert Fano, are not always optimal; David Huffman, a student in Fano’s class, found the optimal algorithm in 1952.

Channel capacity

For the general reader. Before 1948 engineers assumed that to make errors rarer on a noisy line you had to send more slowly, and that error-free transmission needed an infinitely slow rate. Shannon proved the opposite. Every channel has a capacity. Below it, clever coding makes errors as rare as you like at a fixed rate; above it, no coding can. The result was a complete surprise, and it set the goal that coding theorists spent the next fifty years trying to reach.

Mutual information

A discrete memoryless channel is a family of conditional distributions \(p(y\mid x)\) from an input alphabet to an output alphabet, used independently at each time step. For an input distribution \(p(x)\), define the conditional entropy \(H(X\mid Y)=-\sum_{x,y}p(x,y)\log p(x\mid y)\) and the mutual information

Shannon called \(H(X\mid Y)\) the equivocation: the uncertainty about what was sent that remains after receiving. The capacity is \(C=\max_{p(x)}I(X;Y)\).

Proof sketch

Achievability by random coding. Fix the capacity-achieving \(p(x)\) and choose every symbol of every codeword independently from it. Decode \(y^n\) to the unique codeword that is jointly typical with it. The true codeword is jointly typical with high probability by the AEP. A fixed wrong codeword, independent of \(y^n\), is jointly typical with probability about \(2^{-nI(X;Y)}\). With \(2^{nR}\) wrong codewords, the union bound gives a total error of about \(2^{-n(I-R)}\to0\). The average over random codes is small, so some code is good; discarding the worse half of its codewords makes the maximal error small too. Shannon’s argument was a sketch; Amiel Feinstein (1954) and Jacob Wolfowitz (1957) made it rigorous.

Converse. Let the message \(W\) be uniform on \(2^{nR}\) values and \(P_e\) the error probability. Fano’s inequality gives \(H(W\mid Y^n)\le1+P_e\,nR\). The channel is memoryless, so \(I(W;Y^n)\le I(X^n;Y^n)\le nC\). Then \(nR=H(W)\le1+P_enR+nC\), so \(P_e\ge1-C/R-1/(nR)\), bounded away from 0 when \(R>C\). ∎

The proof shows that good codes exist, since random ones work, but it gives no practical way to decode them. Constructing codes that approach capacity with efficient decoding took decades: Robert Gallager’s low-density parity-check codes (1960), turbo codes (1993) and polar codes (Erdal Arıkan, 2009).

Sampling and the Gaussian channel

For the general reader. Telephone lines and radio links carry continuous waveforms, not bits. Shannon showed how to bring them into the same framework. A signal that contains no frequencies above \(W\) is completely determined by \(2W\) samples per second. With noise added, each sample can carry only a limited number of bits, and the resulting formula for capacity, \(W\log(1+S/N)\), is the most famous equation in communication engineering.

Sampling

The sampling theorem was published by Shannon in “Communication in the presence of noise” (Proceedings of the IRE, January 1949). He noted that it was common knowledge in the communication art. Edmund Whittaker (1915), Vladimir Kotelnikov (1933) and Nyquist had given versions; Shannon’s paper made it standard.

Proof. Write \(f(t)=\int_{-W}^{W}F(\nu)e^{2\pi i\nu t}d\nu\). Expand \(F\) on \([-W,W]\) in the Fourier series \(F(\nu)=\sum_nc_ne^{-2\pi i n\nu/2W}\), where \(c_n=\frac1{2W}\int F(\nu)e^{2\pi in\nu/2W}d\nu=\frac1{2W}f(\tfrac n{2W})\). Substitute and integrate term by term: \(\int_{-W}^{W}e^{2\pi i\nu(t-n/2W)}d\nu=2W\operatorname{sinc}(2Wt-n)\). ∎

So a band-limited signal of duration \(T\) has about \(2WT\) degrees of freedom: it is a point in a space of dimension \(2WT\).

The Gaussian channel

Suppose each sample \(x_i\) is received as \(y_i=x_i+z_i\), with \(z_i\) independent Gaussian noise of variance \(N\), and the transmitter has average power \(P\), so that \(\frac1n\sum x_i^2\le P\).

Sphere-packing picture. A codeword is a point in \(\mathbb R^n\) of norm at most \(\sqrt{nP}\). Noise moves it to a nearby point; by the law of large numbers the received point lies, with high probability, near the surface of a sphere of radius \(\sqrt{nN}\) about the codeword. All received vectors lie in a sphere of radius \(\sqrt{n(P+N)}\). Decoding works if the noise spheres barely overlap, so the number of codewords is at most about the ratio of volumes,

that is, \(\tfrac12\log(1+P/N)\) bits per sample. Shannon showed by random coding on the sphere that this rate can actually be achieved. The analytic proof uses differential entropy \(h(Z)=-\int p\log p\), and the fact that among densities with variance \(\sigma^2\) the Gaussian maximizes it, with \(h=\tfrac12\log(2\pi e\sigma^2)\). Then \(I(X;Y)=h(Y)-h(Z)\le\tfrac12\log2\pi e(P+N)-\tfrac12\log2\pi eN\).

Secrecy systems

For the general reader. Before Shannon, cryptography was a craft of clever tricks. His 1949 paper treated a cipher as a noisy channel deliberately built to confuse the enemy, and asked what security can be proved. He showed that unbreakable secrecy is possible but expensive: the secret key must be as long as the message. He also showed that natural language is so redundant that, with an ordinary cipher, a few dozen letters of intercepted text usually determine the key.

A secrecy system has a message \(M\), a key \(K\) chosen independently of \(M\), and a cryptogram \(E=e_K(M)\), from which \(M\) can be recovered when \(K\) is known. The enemy knows the system and the probability distributions, but not the key.

Proof. \(M\) is determined by \(E\) and \(K\), so \(H(M\mid E,K)=0\). Then \(H(M)=H(M\mid E)\le H(M,K\mid E)=H(K\mid E)+H(M\mid E,K)=H(K\mid E)\le H(K)\), where the first equality is perfect secrecy. For the pad: for any \(m\) and \(c\), \(P(E=c\mid M=m)=P(K=c\oplus m)=2^{-n}\), independent of \(m\). ∎ The pad itself goes back to Gilbert Vernam’s teleprinter cipher of 1917; Shannon proved it secure and proved that nothing cheaper can be.

Equivocation and unicity distance

For a practical cipher with a short key, the enemy’s uncertainty about the key, the key equivocation \(H(K\mid E_1\dots E_n)\), decreases as more cryptogram letters \(E_1,\dots,E_n\) are intercepted. If the language has entropy \(H_L\) bits per letter in an alphabet of size \(A\), its redundancy per letter is \(D=\log A-H_L\). Each intercepted letter then removes about \(D\) bits of uncertainty about the key, until none remains.

Shannon’s companion paper “Prediction and entropy of printed English” (1951) estimated \(H_L\) by asking people to guess the next letter of a text. He found roughly 0.6 to 1.3 bits per letter once long-range context is used, against \(\log27\approx4.75\) for 26 letters and a space. English is therefore more than half redundant. The 1949 secrecy paper also introduced the ideas of confusion and diffusion that still guide the design of block ciphers.

Games, mazes and reliable machines

For the general reader. After 1948 Shannon turned his playful inventiveness on the new computers. He wrote the first serious analysis of how a computer could play chess, built a mechanical mouse that learned its way through a maze, showed how to build reliable machines from unreliable parts, and found the smallest number of internal states a universal computer needs. Much of early artificial intelligence and fault-tolerant computing starts from these papers.

Chess

“Programming a computer for playing chess” (Philosophical Magazine, 1950) begins from the fact that chess is a finite game of perfect information.

So chess is in principle trivial, and in practice impossible to solve. Shannon estimated about \(10^3\) possibilities for a pair of moves (one by each side) and about 40 move pairs in a typical game, so about \(10^{120}\) games, now called the Shannon number. He proposed instead to search a few moves ahead and apply an evaluation function to the positions reached, scoring material, pawn structure and mobility, and to back the values up by minimax. He distinguished “type A” programs, which search every line to a fixed depth, from “type B” programs, which search selectively, as human players do. Computer chess followed this plan until Deep Blue defeated Garry Kasparov in 1997.

In 1950 he built, with Betty Shannon’s help, Theseus, a mouse on magnets moved beneath a maze of 25 squares by a relay circuit. It explored by trial and error, remembered in relays which exit had worked from each square, and then ran the maze directly. If the maze was changed it relearned. He demonstrated it at the Macy conference on cybernetics in 1951.

Reliable circuits from unreliable relays

In 1956 Edward F. Moore and Shannon answered a question raised by John von Neumann: can arbitrarily reliable computation be done with unreliable parts? Suppose each contact is closed with probability \(p\), independently. A network built from such contacts is closed with a probability \(h(p)\), a polynomial in \(p\).

The idea is amplification: a network with \(h(p)>p\) above the crossing point and \(h(p)<p\) below it pushes probabilities apart, and composing networks (substituting a copy for each contact) iterates \(h\). Choosing networks whose crossing point lies between \(c\) and \(a\) and iterating drives \(a\) towards 1 and \(c\) towards 0.

A two-state universal machine

In Automata Studies (1956), which he edited with John McCarthy, Shannon showed that a universal Turing machine can be built with only two internal states, at the price of a large tape alphabet, and that one state is not enough. He also showed that two tape symbols suffice, at the price of many states. The product of states and symbols became the standard measure of the size of a universal machine.

After 1948: zero error and distortion

For the general reader. Shannon kept extending his theory in a handful of papers, each opening a field. One asked what rate is possible if errors are forbidden outright, not merely made rare; the answer turned into a deep problem in graph theory. Another asked how much information is needed to reproduce a source only approximately, which is the mathematics behind every compressed photo and song.

Zero-error capacity (1956)

Call two inputs of a channel confusable if some output can arise from both, and let \(G\) be the graph on the inputs with confusable pairs joined. A zero-error code of length 1 is an independent set in \(G\). For length \(n\), two input words are confusable if they are confusable or equal in every coordinate; this is the strong product \(G^{\boxtimes n}\).

Shannon computed \(\Theta\) for every graph with at most five vertices except the pentagon \(C_5\), for which he showed \(\sqrt5\le\Theta(C_5)\le5/2\). László Lovász proved \(\Theta(C_5)=\sqrt5\) in 1979 with his theta function. \(\Theta(C_7)\) is still unknown. The same 1956 paper proved that feedback from receiver to sender does not increase the ordinary capacity of a memoryless channel.

Rate–distortion (1959)

Let a source emit independent symbols \(X\), let \(d(x,\hat x)\ge0\) measure the cost of reproducing \(x\) as \(\hat x\), and allow average distortion \(D\).

For a fair binary source with Hamming distortion, \(R(D)=1-H(D)\) for \(0\le D\le\tfrac12\). For a Gaussian source of variance \(\sigma^2\) with squared error, \(R(D)=\tfrac12\log(\sigma^2/D)\) for \(D\le\sigma^2\): each extra bit cuts the mean-square error by a factor of 4. Shannon also observed the duality between this problem and channel coding, and in 1961 opened multi-user information theory with a paper on two-way channels.

Bell Labs and MIT, 1948–1978

“A Mathematical Theory of Communication” appeared in the Bell System Technical Journal in July and October 1948. In 1949 it was reprinted as a book, The Mathematical Theory of Communication, with an expository essay by Warren Weaver of the Rockefeller Foundation; the change from “A” to “The” in the title marked how quickly it had been accepted. On 27 March 1949 Shannon married Mary Elizabeth (Betty) Moore, a numerical analyst at Bell Labs, who worked with him on several of his machines.

Fame came fast, and Shannon was uneasy with it. Information theory was applied to psychology, biology, linguistics and economics, often loosely. In 1956 he wrote a one-page editorial, “The Bandwagon”, warning that the theory was not a universal solvent and asking for careful work. The same year he helped organize, with John McCarthy, Marvin Minsky and Nathaniel Rochester, the Dartmouth summer workshop that gave artificial intelligence its name. In 1951 he had joined a classified advisory group on cryptology for the government.

MIT

In 1956 Shannon went to MIT as a visiting professor, and in 1958 he became Donner Professor of Science, a post he held until 1978, when he became professor emeritus. He kept a consulting connection with Bell Labs. He published less and less, preferring to work on problems that amused him. His doctoral students at MIT included Ivan Sutherland, whose 1963 thesis Sketchpad founded interactive computer graphics, Heinrich Ernst, who built an early computer-controlled robot hand. Danny Hillis, later designer of the Connection Machine, is also listed among his students.

His interests included the stock market and gambling. He pointed his colleague Edward Thorp to John Kelly’s 1956 paper on betting with inside information, which gives the optimal fraction of capital to wager in terms of information rates. With Thorp he built a small wearable computer, about 1961, to predict roulette. At home he built juggling machines, a calculator working in Roman numerals (THROBAC), and a machine that solved Rubik’s Cube. He juggled and rode a unicycle, and he formulated a juggling theorem relating the times balls spend in the air and in the hand. In 1965, on a visit to the Soviet Union, he played a game of chess with the world champion Mikhail Botvinnik.

Last years and legacy

In 1973 Shannon was the first recipient of the Shannon Award of the IEEE information theory group, and he gave the first Shannon Lecture, in Ashkelon, Israel. He received the National Medal of Science in 1966, the IEEE Medal of Honor in the same year, the Harvey Prize in 1972 and the Kyoto Prize in 1985. He had been elected to the National Academy of Sciences in 1956. In 1985 he made a surprise appearance at the International Symposium on Information Theory in Brighton, England, where participants lined up for his autograph.

From the mid-1990s he suffered from Alzheimer’s disease, and he spent his last years in a nursing home. He died on 24 February 2001 in Medford, Massachusetts, aged 84.

Legacy

• Digital logic: switching algebra, from the 1937 thesis, is the language of every logic design tool.
• Communication: capacity is the target of all modern coding. LDPC, turbo and polar codes now operate within a fraction of a decibel of Shannon’s limit in mobile telephony, Wi-Fi, satellite links and deep-space probes.
• Compression: lossless compression rests on the source coding theorem, and audio, image and video coding on rate–distortion theory.
• Cryptography: the 1949 paper turned cryptography into a mathematical science; perfect secrecy, unicity distance, confusion and diffusion remain standard concepts.
• Mathematics: information theory became a branch of probability, with links to statistics, ergodic theory (Kolmogorov–Sinai entropy), combinatorics (the Shannon capacity of graphs) and quantum physics (quantum information).
• Computing and AI: computer chess, learning machines, fault tolerance and the minimal universal machine all start from his papers.

Sources and further reading

Biography

1. J. J. O’Connor and E. F. Robertson, Claude Elwood Shannon, MacTutor History of Mathematics.
2. Claude Shannon, Wikipedia.
3. S. W. Golomb et al., Claude Elwood Shannon (1916–2001), Notices of the AMS 49 (2002) 8–16.
4. Mathematics Genealogy Project, Claude Elwood Shannon.
5. Engineering and Technology History Wiki, Oral history: Claude E. Shannon (interview by R. Price, 1982).
6. J. Soni and R. Goodman, A Mind at Play: How Claude Shannon Invented the Information Age, Simon & Schuster, 2017.
7. J. Gleick, The Information: A History, a Theory, a Flood, Pantheon, 2011.

Mathematics

1. C. E. Shannon, A symbolic analysis of relay and switching circuits, Trans. AIEE 57 (1938) 713–723.
2. C. E. Shannon, A mathematical theory of communication, Bell System Tech. J. 27 (1948) 379–423, 623–656. PDF.
3. C. E. Shannon, Communication in the presence of noise, Proc. IRE 37 (1949) 10–21.
4. C. E. Shannon, Communication theory of secrecy systems, Bell System Tech. J. 28 (1949) 656–715.
5. C. E. Shannon, The synthesis of two-terminal switching circuits, Bell System Tech. J. 28 (1949) 59–98.
6. C. E. Shannon, Programming a computer for playing chess, Philosophical Magazine (7) 41 (1950) 256–275.
7. C. E. Shannon, Prediction and entropy of printed English, Bell System Tech. J. 30 (1951) 50–64.
8. C. E. Shannon, The zero error capacity of a noisy channel, IRE Trans. Inform. Theory 2 (1956) 8–19.
9. E. F. Moore and C. E. Shannon, Reliable circuits using less reliable relays, J. Franklin Inst. 262 (1956) 191–208, 281–297.
10. C. E. Shannon, A universal Turing machine with two internal states, in C. E. Shannon and J. McCarthy (eds.), Automata Studies, Princeton, 1956.
11. C. E. Shannon, Coding theorems for a discrete source with a fidelity criterion, IRE Nat. Conv. Rec. part 4 (1959) 142–163.
12. N. J. A. Sloane and A. D. Wyner (eds.), Claude Elwood Shannon: Collected Papers, IEEE Press, 1993.
13. T. M. Cover and J. A. Thomas, Elements of Information Theory, 2nd ed., Wiley, 2006.
14. L. Lovász, On the Shannon capacity of a graph, IEEE Trans. Inform. Theory 25 (1979) 1–7.