A Mathematical Theory of Communication

How to read the original

1. Start with the communication-system model and distinguish source, encoder, channel, decoder, and destination.
2. Read Discrete Noiseless Systems before the noisy-channel arguments, keeping the assumed source distribution explicit.
3. Treat the coding calculations below as original examples, not as an assertion that the paper introduced the later Huffman algorithm.

Uncertainty is an engineering quantity

Shannon develops a mathematical treatment of communication using probabilistic sources and channels. Entropy measures uncertainty, rather than importance or truth. Channel capacity concerns reliable information transmission under a specified channel model. The source and channel are different objects: compressing predictable messages and adding redundancy against noise solve different problems, even though a practical system may perform both.

Consider an original four-symbol source producing A, B, C, and D independently with probabilities 1/2, 1/4, 1/8, and 1/8. Its entropy in bits is the sum of p*log2(1/p): 1/2+1/2+3/8+3/8=1.75 bits per symbol. A fixed-length representation needs two bits per symbol because there are four possibilities. The difference comes from unequal frequencies, not from one symbol carrying less human meaning.

Build a code and check the decoding contract

Assign codewords A=0, B=10, C=110, and D=111. No codeword is a prefix of another, so a decoder can consume bits from left to right and emit a symbol whenever it reaches a complete codeword. For example, 010111 decodes as A, B, D. The average length is 0.51+0.252+0.1253+0.1253=1.75 bits, matching this particular source’s entropy.

This equality is convenient because the probabilities are powers of one half. It is not a promise that every finite alphabet has an integer-length symbol code achieving entropy exactly. Block coding can approach the appropriate asymptotic limit under stated assumptions, while headers, finite messages, unknown probabilities, and computational constraints add practical costs.

If the actual source emits D much more often than expected, the same code may become inefficient. A coding theorem does not eliminate the need to model the source honestly. Correlation also matters: a sequence of individually balanced bits may be highly compressible if adjacent values repeat predictably. Entropy per isolated symbol and entropy rate of a process need not coincide.

Separate reliability from compression

Now suppose each transmitted bit flips independently with probability p=0.1. An uncoded bit has error probability 0.1. Repeating a bit three times and taking a majority vote fails when two or three copies flip. The probability is 3p^2(1-p)+p^3=0.028. Reliability improves, but the scheme sends only one information bit per three channel uses.

For a binary symmetric channel, capacity is 1-H2(p), where H2 is binary entropy. At p=0.1 it is about 0.531 bits per channel use. The repetition code’s rate is about 0.333, below capacity, but its finite block error is still nonzero. Being below capacity does not make every code reliable or provide a specific decoder. The theorem concerns the existence of suitable coding families with vanishing error in the relevant asymptotic regime.

Read the limits with their assumptions

Independent flips are an assumption. Bursty errors can defeat a repetition scheme differently, and adversarial changes are not modeled by an ordinary random-noise channel. Checksums can detect some corruption without authenticating a sender. Compression can preserve every symbol while preserving no guarantee that the message is factually correct.

The practical lesson is to name the random variables, the distribution, the rate unit, and the error criterion before comparing systems. A percentage called accuracy, a file-size reduction, and a channel-capacity bound answer different questions. Shannon’s framework makes those distinctions precise; it does not supply semantic judgment or erase implementation cost.

Reconstruction exercise

For a binary source with P(1)=1/4 and P(0)=3/4, calculate its entropy and compare it with a one-bit fixed code. Then compute the error probability of threefold repetition with majority decoding when independent flips occur with probability 0.2. Explain why the repeated code can improve bit reliability while increasing transmitted length. Finally give a concrete correlated-error model in which all three copies flip together, and calculate the majority decoder’s error rate under a 0.2 probability of that joint event.

Worked solution

The source entropy is -(1/4)log2(1/4)-(3/4)log2(3/4), about 0.8113 bits per symbol. A direct binary symbol code uses one bit, while suitable longer-block coding can exploit the bias under the specified source model. For independent p=0.2 flips, majority decoding fails with probability 3*(0.2)^2*0.8+(0.2)^3=0.104, less than the uncoded 0.2 error rate. The cost is three channel uses for each original bit. If a single event flips all three copies with probability 0.2 and otherwise leaves all unchanged, majority voting fails with probability 0.2. The independence-based improvement disappears because the copies contain no independent protection against that shared disturbance. This comparison isolates the role of the channel model and prevents a coding result from being generalized to an incompatible failure process.

Test the limits and transfer the idea

1. Entropy derivation · allow 45 minutes

Compress balanced bits by modeling dependence

Let X1 be a fair bit. For each later position, independently choose to flip the preceding bit with probability 0.1; otherwise repeat it. This is an original stationary binary Markov source. Show that every individual Xi is fair, then calculate the entropy of a four-bit block and the entropy rate. Compare both with the claim that a fair-bit stream always requires one bit per symbol.

For nonoverlapping two-bit blocks, use the prefix code 00→0, 11→10, 01→110, 10→111. Compute its expected bits per source bit. Explain why this code fails to reach the entropy rate and why a low entropy rate does not imply every finite sequence compresses.

Get a starting hint

Use the chain rule: the initial bit is uncertain, while each following bit adds only the uncertainty of the independent flip decision.

Compare your reasoning with the worked solution

If Xi is fair, P(Xi+1=1)=0.5×0.9+0.5×0.1=0.5. Induction makes all one-bit marginals fair. Nevertheless, adjacent bits are dependent. Given the preceding bit, uncertainty is H2(0.1)=-0.1log2(0.1)-0.9log2(0.9), about 0.468996 bits. The four-bit block entropy is 1+3H2(0.1), about 2.406987 bits, rather than four. For length n the entropy is 1+(n-1)H2(0.1), so the entropy per bit approaches 0.468996.

The pair probabilities are P(00)=P(11)=0.45 and P(01)=P(10)=0.05. The code's mean length is 0.45×1+0.45×2+0.05×3+0.05×3=1.65 bits per pair, or 0.825 per source bit. Prefix decoding is valid, but the code loses efficiency through integer-length constraints and by not using dependence across pair boundaries. Pair entropy itself is 1+H2(0.1), about 1.468996 bits, already above twice the entropy rate because the first bit of each isolated pair is treated as fresh uncertainty.

The entropy rate concerns average information in the source model, not the appearance of each symbol alone. A particular rare sequence may need a long representation, and any lossless code over all fixed-length strings must make some strings no shorter, or longer, when others become shorter. Headers, model identification, and finite-block effects add costs. These source assumptions must be stated before invoking an asymptotic coding claim.

Check your reasoning

• Derives fair marginals and the block chain-rule entropy.
• Calculates pair probabilities and 0.825 bits per source bit.
• Explains cross-block dependence, integer lengths, and finite-message limits.

2. Derivation and feasibility · allow 45 minutes

Match source information to an erasure channel

Consider an original memoryless binary erasure channel: each input bit is delivered correctly with probability 0.75 and replaced by a visible erasure symbol with probability 0.25, independently of its value. There are no undetected flips. Derive I(X;Y) for arbitrary input bias and find capacity in bits per channel use.

A separate independent source emits 1 with probability 1/4. Determine whether transmitting 1.05 source symbols per channel use could achieve vanishing error in the ideal asymptotic model. Find the boundary ratio of source symbols to channel uses. Then explain why resending only erased bits cannot be assumed in a model without a feedback channel, and why operating below the boundary does not validate every finite code.

Get a starting hint

When Y is a nonerased bit, X is known; when Y is erased, its uncertainty remains H(X). Keep source symbols and channel uses as distinct units.

Compare your reasoning with the worked solution

Since the erasure event is independent of X, H(X|Y)=0.25H(X). Thus I(X;Y)=H(X)-H(X|Y)=0.75H(X). Binary entropy is at most one, achieved by a fair channel input, so capacity is 0.75 information bits per channel use. This is an erasure channel, not the binary symmetric flip channel; applying 1-H2(0.25) would answer a different question.

The biased source has entropy H2(1/4), about 0.811278 bits per source symbol. A rate of 1.05 source symbols per channel use requires approximately 1.05×0.811278=0.851842 information bits per channel use, exceeding 0.75. Under the stated memoryless, asymptotic lossless/reliable framework, that requirement cannot be met with vanishing error. The boundary ratio is 0.75/0.811278, about 0.924467 source symbols per channel use. Suitable rates strictly below the boundary can be approached by appropriate source and channel coding; the calculation alone does not construct those codes or settle equality-case behavior.

The receiver knows which positions were erased, but that knowledge is not automatically available to the sender. Selective retransmission needs an explicit reverse path and a protocol, whose time and capacity costs must be modeled. Without feedback, redundancy can still permit recovery, but it must be encoded in advance. Finite block length, decoder design, and the chosen error criterion determine the actual reliability of a particular code.

Check your reasoning

• Derives capacity using conditional entropy and maximizes over input bias.
• Uses consistent units to reject 1.05 and compute the boundary ratio.
• Separates channel feedback, coding existence, and finite-code reliability.

Check your understanding

For probabilities 1/2,1/4,1/8,1/8, what is the average length of codewords 0,10,110,111?

• 2 bits.
• 1 bit.
• 1.75 bits.

Explanation

Weight each codeword length by its source probability.

A code operates below a channel’s capacity. Which conclusion follows immediately?

• Every finite message decodes without error.
• Nothing about this particular code’s error rate without analyzing its construction and block length.
• The source has no semantic ambiguity.

Explanation

Capacity is an asymptotic achievable-rate boundary under a channel model, not a guarantee for every code.

Original paper and sources

Claude E. Shannon. A Mathematical Theory of Communication. Bell System Technical Journal 27, July and October 1948, pp. 379-423 and 623-656. Linked edition is a corrected reprint.

Read the original paper →

Read the primary paper: Harvard University

• A Mathematical Theory of Communication: Harvard University