Channel Capacity and Coding

Shannon's channel coding theorem is the most counterintuitive conclusion in all of information theory: as long as the transmission rate is below the channel capacity C = \max I(X;Y), the error rate can be reduced to arbitrarily close to zero—without sacrificing rate for reliability, the only cost being longer, smarter coding. This theorem defines the physical limits of communication, and modern LDPC/turbo codes already run right up against it.

Introduction: A Line Destined to Error

The previous chapters discussed "how to compress information." This chapter turns the problem around: how do you ensure information isn't destroyed by noise as it traverses a noisy line to the other side?

Lines flip bits and add noise. The dumbest countermeasure is to add redundancy—retransmit each bit three times, and have the receiver use majority voting. But this drops the rate directly to 1/3, and it still fails when noise is high.

The answer Shannon provided in 1948 shocked the entire academic community: you do not have to trade rate for reliability. As long as the transmission rate is below a certain threshold, the error rate can be reduced to arbitrarily close to zero, without giving up any rate. That threshold is the channel capacity. This chapter clarifies this concept.

Channel Model: How to Model Noise

First, you need a calculable noise model. A channel is a noisy mapping that transforms input X into output Y, characterized by the conditional distribution p(y \mid x). Two fundamental models underpin all intuition:

• Binary Symmetric Channel (BSC): Input is 0 / 1. With probability p, the bit flips (0 becomes 1 or 1 becomes 0); with probability 1-p, it passes through correctly. Here, p is the bit error rate. This is the simplest abstraction in digital communication—each bit has an independent probability of being flipped by noise.
• Additive White Gaussian Noise (AWGN) Channel: Output Y = X + N, where N is Gaussian noise with mean 0 and variance \sigma^2. This is the standard model for analog/wireless channels: the signal is overlaid with random noise during transmission. The higher the signal-to-noise ratio (\text{SNR}), the smaller the relative noise.

The essential constraint of a channel is that noise prevents the receiver from completely determining what was sent; Y carries only partial information about X. The measure of "how much" partial information is mutual information.

Mutual Information: How Much Information Did the Channel Actually Transmit?

Using a channel once, the amount of information output Y provides about input X is mutual information:

I(X;Y) = H(X) - H(X \mid Y)

Reading this out makes sense: the uncertainty about X before sending is H(X); the residual uncertainty after receiving Y is H(X \mid Y) (this is the ambiguity introduced by noise). The difference between the two is the information that successfully traversed the channel.

Three extreme cases provide good intuition:

• Noiseless channel: H(X \mid Y)=0, so I(X;Y)=H(X). What you send is exactly what you receive.
• Pure noise channel (Y is independent of X): I(X;Y)=0. What you receive provides no help in inferring the input.
• Per-bit mutual information of a BSC: I = 1 - H(p), where H(p) is the binary entropy function. When p=0.5, H(p)=1, so I=0—a flip probability of half equals pure noise, and the channel is completely useless.

Channel Capacity and Shannon's Channel Coding Theorem

Channel capacity is defined as the maximum value mutual information can take over all possible input distributions.

C = \max_{p(x)} I(X;Y)

It represents the maximum number of bits that can be reliably carried per use of this channel, measured in bits per channel use.

Shannon's Channel Coding Theorem (1948) provides that counterintuitive conclusion:

For any transmission rate R < C, there exists a coding scheme such that the decoding error rate approaches 0 arbitrarily closely; conversely, if R > C, the error rate cannot be reduced to 0—reliable transmission is impossible.

Where is the counterintuitive part? People used to believe that "to reduce the error rate, you must reduce the rate" (e.g., retransmitting each bit three times drops the rate to 1/3). Shannon said no. As long as you are below C, you can maintain your rate while reducing the error rate to arbitrarily low levels.

So where does the cost go? It goes to coding complexity and codeword length. The method involves packing many bits into long codewords and using the statistical patterns over long blocks to resist noise—the longer the codeword, the closer you get to this limit.

The theorem has two halves: one guarantees the lower bound is achievable, and the other seals the upper bound. Achievability states that when R<C, good codes can be constructed using random coding (this is an existence proof and does not provide specific codes); the converse states that when R>C, no code can escape a non-zero error rate. Together, they pinch off C as a sharp threshold.

Calculating the Capacity of a BSC

After the abstract discussion, let's plug in numbers. The capacity of a BSC has a closed-form solution: C = 1 - H(p), where p is the flip probability and H(p) is the binary entropy function.

• p=0 (noiseless): H(0)=0, so C=1 bit. Each use transmits 1 bit at full capacity.
• p=0.11 (approx. 11\% error rate): H(0.11)\approx 0.5, so C\approx 0.5 bit. To transmit reliably, you need to send about 2 channel bits for every 1 bit of information, using half the bandwidth to fight noise.
• p=0.5 (pure noise): H(0.5)=1, so C=0 bit. The output is independent of the input, so no information can be transmitted.
• p=1 (certain flip): C=1 bit. Interestingly—deterministic flipping is not noise; you can simply invert the received bit, and the information remains intact.

The last point highlights a common misconception: what truly kills a channel is the "maximum uncertainty" of p=0.5, not the flipping itself. The optimal input distribution to achieve capacity here is uniform (0 and 1 with equal probability)—this also explains why the definition of C requires \max over all input distributions: how much a channel can transmit depends on how you feed it.

Several Counterintuitive but Crucial Points

• Reliable transmission does not require sacrificing rate. Intuition suggests "to be more reliable, add more redundancy and lower the rate," but Shannon says that as long as R<C, zero error does not require trading rate; you trade codeword length instead. Repetition codes (sending 1 bit three times) are the dumbest way to fight noise, dropping the rate to 1/3 and still performing worse than a good code.
• Capacity is a hard wall, not a soft constraint. When R>C, it's not just that "the error rate is higher"; it is impossible in principle to reduce it to zero—adding more redundancy or using smarter codes is useless. This line is proven by the converse theorem.
• Shannon only proved "existence," not "construction." The theorem proves good codes exist using random coding, but says nothing about how to efficiently encode or decode. The gap between existence and constructiveness fueled the entire coding theory for over half a century.

Engineering Significance of the Shannon Limit

To emphasize: Shannon's theorem is existential. It proves good codes exist but doesn't tell you how to build them, nor how fast decoding should be. For the next half-century, coding theory has been chasing this "Shannon limit"—creating practical codes that approach C while allowing efficient encoding and decoding.

• Early Hamming and Reed-Solomon codes were far from the limit.
• Turbo codes (1993) and LDPC codes (Gallager 1962, rediscovered in the 1990s) achieved performance within less than 1 dB of the Shannon limit on AWGN channels using iterative/belief propagation decoding. This was a victory for communication engineering; today, 5G, Wi-Fi 6, and deep space communications all use LDPC.
• The details of specific error-correcting code construction and iterative decoding are briefly mentioned here. The skeleton to remember is: the theoretical limit is set by Shannon, and engineering has spent decades running right up against it.

Finally, mention a beautiful duality. Channel coding (carefully adding redundancy to data to fight noise) and source coding/compression (squeezing out redundancy to approach entropy) are a pair of mirrors: one adds redundancy, the other removes it, and both ends are capped by the limit theorems of information theory.

References

• Paper: "A Mathematical Theory of Communication" (Shannon, 1948 — the original source of channel capacity and coding theorems)
• Textbook: "Elements of Information Theory" (Cover & Thomas — Chapter 7 Channel Capacity, BSC/AWGN, and capacity derivations)
• Paper: "Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codes" (Berrou et al., 1993 — the first practical codes to approach the Shannon limit)

Keywords: channel capacity, binary symmetric channel BSC, additive white Gaussian noise AWGN, mutual information, channel coding theorem, Shannon limit, LDPC, turbo codes, achievability and converse