--- title: Channel Capacity and Coding url: https://doc.liz6.com/en/theory/01-information-theory/04-channel-capacity-and-coding locale: en area: theory tags: - theory - information-theory date: 2026-07-18 modified: 2026-07-29 description: 'Shannon’s channel coding theorem is the most counterintuitive conclusion in all of information theory: as long as the chosen transmission rate is below the channel capacity C = max I(X;Y), longer and smarter coding can reduce the error rate to arbitrarily close to zero, without needing to drive the rate all the way down to zero to further reduce errors. This theorem defines the asymptotic limit of communication.' --- # Channel Capacity and Coding > Shannon’s channel coding theorem is the most counterintuitive conclusion in all of information theory: as long as the chosen transmission rate is below the channel capacity $C=\max I(X;Y)$, longer and smarter coding can reduce the error rate to arbitrarily close to zero, without needing to drive the rate all the way down to zero to further reduce errors. This theorem defines the asymptotic limit of communication. ## Prelude: A Line Doomed to Error The previous chapters discussed "how to compress information." This chapter turns it 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 adding redundancy—retransmitting each bit three times, with the receiver using majority rule. But this drops the rate directly to $1/3$, and it still fails when noise is high. The answer Shannon gave in 1948 shocked the entire academic community at the time: as long as you first select a positive rate below the threshold, you can reduce the error rate to arbitrarily close to zero by increasing the codeword length and improving the coding, **without needing to continue driving the rate toward zero as the target error rate decreases**. This threshold is the channel capacity. This chapter clarifies it. ## Channel Model: How to Model Noise First, you need a noise model that can be calculated. A **channel** is a noisy mapping that turns input $X$ into output $Y$, characterized by the conditional distribution $p(y \mid x)$. Two fundamental models support all intuition: - **Binary Symmetric Channel (BSC)**: Input $0$ / $1$, flips with probability $p$ ($0$ becomes $1$ or $1$ becomes $0$), and passes correctly with probability $1-p$. Here, $p$ is the bit error rate. This is the simplest abstraction of digital communication—each bit has a certain probability of being flipped by noise independently. - **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: a layer of random noise is superimposed on the signal 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$. And exactly how much "partial" is measured by 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](/theory/01-information-theory/01-entropy-and-information-measures.md): $$I(X;Y) = H(X) - H(X \mid Y)$$ Reading it 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 passed through the channel**. Three extremes give you a good feel: - **Noiseless channel**: $H(X \mid Y)=0$, $I(X;Y)=H(X)$, what you send is what you receive. - **Pure noise channel** ($Y$ is independent of $X$): $I(X;Y)=0$, the received content is of no help in inferring the input. - **BSC with uniform input**: When $0$ / $1$ are input with equal probability, $I(X;Y)=1-H(p)$, where $H(p)$ is the [binary entropy function](/theory/01-information-theory/01-entropy-and-information-measures.md). Uniform input exactly achieves the capacity of the BSC; if the input is biased, mutual information is usually smaller. When $p=0.5$, $H(p)=1$, $I=0$—a flip probability of half is equivalent to 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 is the maximum number of bits that can be reliably carried per use of this channel, measured in bit / channel use. **Shannon’s Channel Coding Theorem (1948)** gives that counterintuitive conclusion: > For any transmission rate $R < C$, there exists a coding scheme such that the decoding error rate can be arbitrarily close to $0$; conversely, if $R > C$, the error rate cannot be reduced to $0$—reliable transmission is impossible. Where is it counterintuitive? People used to think that "to further reduce the error rate, you must continue to reduce the rate" (e.g., by increasing the number of repetitions). Shannon said: once you select $R Rate R and Achievability: C is a Sharp Threshold R C (Channel Capacity) R < C Coding exists such that error rate → 0 Can arbitrarily approach zero error R > C Error rate has a lower bound, cannot reach zero Reliable transmission is impossible The threshold is at C, not 0—below it, reliability is free; above it, reliability cannot be bought. The theorem has two halves: one guarantees the lower bound is achievable, and the other seals the upper bound: **Achievability** says that when $RC$, no code can escape a non-zero error rate. The two squeeze out $C$ as a sharp threshold from above and below. ### 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](/theory/01-information-theory/01-entropy-and-information-measures.md). - $p=0$ (noiseless): $H(0)=0$, $C=1$ bit. Each use transmits a full $1$ bit. - $p=0.11$ (approx. $11\%$ error rate): $H(0.11)\approx 0.5$, $C\approx 0.5$ bit. To transmit reliably, you need to send about $2$ channel bits for every $1$ bit of information on average, with half the bandwidth used to fight noise. - $p=0.5$ (pure noise): $H(0.5)=1$, $C=0$ bit. Output and input are independent; 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 exposes a common misconception: **what truly kills the channel is the "maximum uncertainty" of $p=0.5$, not the flipping itself**. The optimal input distribution to achieve capacity here is uniform ($0$ / $1$ with equal probability)—this also explains why the definition of $C$ requires $\max$ over all input distributions: how much the channel can transmit depends on how you feed it. ### AWGN Capacity: Why Power Must Be Constrained First The AWGN channel is written as $Y=X+N$, where noise $N\sim\mathcal N(0,\sigma^2)$. If the input signal power is allowed to be infinite, the transmitter can simply keep amplifying the signal amplitude to overcome the noise, and the capacity would have no finite upper bound. Therefore, when discussing AWGN capacity, an average power constraint $\mathbb E[X^2]\leq P$ must be given simultaneously. For a single-use real-valued AWGN channel, the capacity is: $$C=\frac{1}{2}\log_2\left(1+\frac{P}{\sigma^2}\right) =\frac{1}{2}\log_2(1+\mathrm{SNR})\quad\text{bit / channel use}$$ The $\frac12$ here comes from the口径 (perspective/unit) of "one real-valued channel use." The common form for continuous time with bandwidth $B$ is $C=B\log_2(1+\mathrm{SNR})$ bit/s. What's truly worth remembering is not the coefficient, but two points: **capacity depends on input constraints; the returns on increasing SNR are only logarithmic**. Doubling the power does not double the capacity. ### A Few Counterintuitive but Critical Points - **Once the rate is fixed below capacity, reliability is primarily traded for codeword length.** $RC$, it's not just "higher error rate," but **principally impossible** to reduce it to zero—adding more redundancy or using smarter codes is useless. This line is proven dead by the converse theorem. - **Shannon only proved "existence," not "how to construct."** The theorem proves the existence of good codes using random coding, but says nothing about how to efficiently encode and decode. This gap between existence and constructiveness fed the entire coding theory for over half a century. ## Engineering Significance of the Shannon Limit Emphasize again: Shannon's theorem is **existential**. It proves that good codes exist, but doesn't tell you how to build them, nor how fast decoding must be. For the next half-century, coding theory has been chasing this "**Shannon Limit**"—creating practical codes that both approach $C$ and allow 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 90s)** used iterative/belief propagation decoding to achieve within less than $1$ dB of the Shannon limit on AWGN. This was a victory for communication engineering; today, LDPC is used in 5G, Wi-Fi 6, and deep space communication. - The details of specific error-correcting code construction and iterative decoding are touched upon here. The skeleton to remember is: **the theoretical limit is set by Shannon, and engineering spends decades running right next to it**. ## Source-Channel Separation: How Compression and Error Correction Connect [Source coding](/theory/01-information-theory/03-source-coding-and-compression.md) is responsible for removing the source's own redundancy, compressing the rate to near the entropy rate; channel coding then controllably adds redundancy to resist transmission noise. Shannon's **Source-Channel Separation Theorem** states that for classic point-to-point, long-block, stationary sources, and memoryless channels, as long as the source entropy rate (after unit conversion) is lower than the channel capacity, you can "compress first, then correct errors" without losing asymptotic optimality. This provides the most concise criterion for the entire communication link: $$\text{Compressed Information Rate} < \text{Channel Capacity} \quad\Rightarrow\quad\quad\text{Reliable transmission is possible in principle}$$ It also explains why compression and error correction, seemingly in opposite directions, can work in series. However, "separate design is always optimal" has clear boundaries: under short latency, complex networks, multi-user, or strong real-time constraints, joint source-channel coding may be more appropriate. Therefore, channel coding (carefully adding redundancy to fight noise) and source coding (squeezing out predictable redundancy to approach the entropy rate) are a pair of mirrors, and the separation theorem connects these two ends into a closed loop. ## 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 derivation) - **Paper**: "Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codes" (Berrou et al., 1993 — practical codes that first approached the Shannon limit) *Keywords: channel capacity, binary symmetric channel BSC, additive white Gaussian noise AWGN, SNR, mutual information, channel coding theorem, source-channel separation, Shannon limit, LDPC, turbo codes, achievability and converse*