Skip to main content

Noisy channels and capacity: from error probability to Shannon's second theorem

The binary symmetric channel, channel capacity, and Shannon's second theorem: the foundation of reliable communication over real channels.

What do you think about this article?

Noisy channels and capacity: from error probability to Shannon's second theorem
Information Theoryfedericocalo.dev

At a Glance

The binary symmetric channel, channel capacity, and Shannon's second theorem: the foundation of reliable communication over real channels.

A real communication channel is not perfect: noise distorts the signal, and the receiver obtains a corrupted version of the transmitted message. How can we transmit information reliably over a noisy channel? The answer is the channel capacity, defined by Claude Shannon (1948): the maximum rate (bits/second) at which information can be transmitted with arbitrarily small error probability. For the binary symmetric channel (BSC) - the simplest and most fundamental model - the capacity is C = 1 - H(p), where p is the bit error probability and H(p) is binary entropy. This article shows how to compute channel capacity from scratch, what happens when you transmit at the critical rate, and why there is a sharp boundary between the possible (reliable) and the impossible (with guaranteed error). The central theme is Shannon's second theorem (channel coding theorem): there exists a coding strategy (add redundancy intelligently) that allows you to approach capacity, but no strategy can exceed it - it is an absolute limit of nature.

Historical context and formalization

Shannon (1948), in the foundational paper "A Mathematical Theory of Communication", identifies a paradox: intuitively, if the channel introduces errors, error probability increases with message length. Yet Shannon proves that there exists a critical rate below which you can keep error arbitrarily small by adding redundancy - and above that rate, error is guaranteed. This is the pillar of the theory: the critical rate is the capacity. Formally, Shannon defines capacity as the maximization of mutual information I(X;Y) over input distributions. For the BSC, maximization is achieved with uniform input (X = Bernoulli(0.5)), yielding C = 1 - H(p). The proof of the channel coding theorem required probability theory, counting arguments, and the typical set lemma - reasons it remained obscure until the 1960s, when constructive proofs by Fano and others clarified it.

Article outline

  1. The binary symmetric channel: definition and error probability
  2. Binary entropy and mutual information: ingredients of capacity
  3. Channel capacity of the BSC: definition and explicit computation
  4. Numerical example: capacity of a degraded Wi-Fi channel
  5. Shannon's second theorem: critical rate and reliable zone
  6. At the boundary: decoding error probability

The binary symmetric channel: definition and error probability

A binary symmetric channel (BSC) is a probabilistic model: you transmit a bit x ∈ {0, 1}, and receive y which is

  • the correct bit x with probability 1 - p
  • the flipped bit 1 - x with probability p

The error probability p is symmetric: it does not distinguish between 0→1 and 1→0 errors.

Formally, Pr[y = 1 | x = 0] = p and Pr[y = 0 | x = 1] = p. This is the transition probability of the channel.

If you transmit n independent bits, the total number of errors is binomial Bin(n, p): the expected number is np, and the standard deviation is sqrt(n p (1 - p)). This is the foundation for understanding the second theorem: if you transmit fast (large n) at the critical rate, errors are concentrated, but if you transmit above the critical rate, errors explode.

Binary entropy and mutual information: ingredients of capacity

Recall from the first article in the series: binary entropy is H(p) = -p log2(p) - (1-p) log2(1-p). Mutual information between input and output is I(X;Y) = H(Y) - H(Y | X).

For the BSC, if input is Bernoulli(0.5), the output is also Bernoulli(0.5) - so H(Y) = 1 bit. Conditional on input X = x, the received Y is x with probability 1 - p and 1 - x with probability p - so H(Y | X = x) = H(p) regardless of x. Therefore H(Y | X) = H(p), and I(X;Y) = 1 - H(p).

The channel capacity is the maximum mutual information over all possible input distributions:

C = max_{p(x)} I(X;Y) = 1 - H(p)

where H(p) is the entropy of error. Note: when p = 0 (no error), C = 1 bit (perfect transmission); when p = 0.5 (completely random), C = 0 (no information transmitted); when p = 1 (guaranteed but deterministic error), C = 1 again (because you know the flip).

Channel capacity of the BSC: definition and explicit computation

The capacity of the BSC is:

C(p) = 1 - H(p) bits/symbol

Where H(p) is binary entropy. If the channel has bandwidth W (Hz) and you transmit 2W symbols per second (Nyquist), the overall capacity is C_bit = 2W * (1 - H(p)) bits/second.

Interpretation: 1 - H(p) quantifies how much information "survives" the noise. If p is small (good channel), H(p) ≈ p and C ≈ 1 - p (nearly 1 bit, with small degradation). If p is near 0.5 (poor channel), C ≈ 0 (practically no information transmitted reliably).

Numerical example: capacity of a degraded Wi-Fi channel

Suppose a Wi-Fi channel with p = 0.01 (1% bit error probability). What is the capacity?

H(0.01) = -0.01 * log2(0.01) - 0.99 * log2(0.99)
        ≈ -0.01 * (-6.644) - 0.99 * (-0.0145)
        ≈ 0.0664 + 0.0144
        ≈ 0.0808 bits

C(0.01) = 1 - 0.0808 ≈ 0.919 bits

Interpretation: even though the channel has 1% error, you can transmit 91.9 hundredths of a bit per symbol - nearly the maximum. The channel is good. If you add intelligent redundancy (error-correcting code), you reach this capacity with arbitrarily small error.

Now, p = 0.1 (10% error - moderate channel):

H(0.1) = -0.1 * log2(0.1) - 0.9 * log2(0.9)
       ≈ -0.1 * (-3.322) - 0.9 * (-0.152)
       ≈ 0.3322 + 0.1365
       ≈ 0.4686 bits

C(0.1) = 1 - 0.4686 ≈ 0.531 bits

The channel is degraded: less than half of transmitted bits carry genuine information. Finally, p = 0.2 (20% error):

H(0.2) ≈ 0.722 bits → C(0.2) ≈ 0.278 bits

Only 27.8% of capacity is usable. The lesson: even small increases in p drastically reduce capacity.

Shannon's second theorem: critical rate and reliable zone

The channel coding theorem (Shannon's second theorem) states:

  1. Existence of reliable codes: For every rate R < C, there exists a sequence of codes (block length n → ∞) with rate R such that the decoding error probability P_e → 0.
  2. Impossibility above capacity: For every code with rate R > C, the error probability P_e > δ for some δ > 0, regardless of how long the block is.

In simple terms: C is the "critical rate". If you transmit below the critical rate (R < C), a code exists that allows you to do so reliably - there is no limit on redundancy, but redundancy is required. If you transmit above the critical rate, no code in the world saves you: you are forced to accept a constant error.

The proof uses the typical set method (introduced by Shannon): the probability that the received sequence is not "typical" of the input decays exponentially with block length. This exponential decay is fast enough to allow you to distinguish between different messages, even with noise.

The intuitive proof: typicality and counting

The proof of the channel coding theorem (Shannon's second theorem) is non-constructive: Shannon proves the code exists, but does not tell you how to build it. The central idea is typicality. Here is the intuition:

Let R < C be the desired coding rate. We transmit a message chosen uniformly from 2^(nR) possible messages (block length n). Each message is encoded into a sequence of n bits.

The receiver sees a sequence y corrupted by noise. The question is: how many plausible messages could have generated y? The answer depends on mutual information I(X; Y):

If I transmit at rate R and I(X; Y) = C (capacity achieved), the number of "typical" messages compatible with y is approximately 2^(n(H(X) - I(X; Y))) = 2^(n(H(X) - C)). Since H(X) = R (the transmission rate, with uniform input), the number of compatible messages is 2^(n(R - C)). If R < C, this number is 2^(n × negative number) → exponentially small. So with high probability, y is compatible with only one original message: maximum-likelihood decoding is reliable.

Conversely, if R > C, then R - C > 0, and the number of messages compatible with y grows exponentially. Confusion among messages is inevitable: you cannot distinguish between 2^(n(R-C)) plausible messages. This is why error remains constant.

The rigorous proof uses the typical set method (Shannon, Fano): it defines sets of "typical" sequences with expected statistical properties, shows that with high probability the received signal falls in the intersection of the typical set of the true message and the source, and that other messages have exponentially small probability of falling in the same set. The result is that the error probability P_e decays exponentially with n if R < C.

The converse: why above capacity you cannot

The converse of the channel coding theorem states: if R > C, then for any code of length n and rate R, the error probability P_e is bounded below by a constant δ > 0, regardless of n.

Intuition: if you transmit above capacity, you communicate more information than the channel can "faithfully" pass. By Fano's inequality, error probability is bounded by:

P_e ≥ (R - C) / (log2(alphabet_size))   (approximation for R > C)

This is the "absolute limit of nature": no code, however sophisticated, can surpass capacity. It is like trying to send 10 bits over a channel that can reliably transmit only 5 - the rest will be lost.

Combining the direct theorem (R < C → reliability) and converse (R > C → impossibility), the theorem establishes C as the sharp boundary between possible and impossible.

At the boundary: decoding error probability

What happens exactly when you transmit at the critical rate R = C - ε (slightly below capacity)? The decoding error probability decreases exponentially with block length n:

P_e ≤ 2^(-n E_r(R))

where E_r(R) is the reliability exponent, which depends on R and capacity C. When R = C - ε, the exponent is positive and grows as ε decreases. When R > C, no positive exponent exists - error remains constant.

This is the heart of the second theorem: the difference C - R determines how fast error decays. More margin below capacity means faster decay - but the boundary itself is absolute.

Trade-off reasoning

I chose to present the binary symmetric channel as the primary model, not the continuous Gaussian channel (AWGN), because: (i) BSC is discrete and pedagogically transparent; (ii) capacity 1 - H(p) is a closed-form formula, not an integral; (iii) all phenomena (critical rate, insurmountable boundary, trade-off between redundancy and reliability) emerge here already. The Gaussian channel is a refinement over continuous input, not a conceptual change. If your application is digital (error-correcting code, network), BSC is the relevant model; for analog communications (radio, telephony), AWGN becomes important.

Advanced connections

Binary erasure channel (BEC): The BEC is "kinder" than the BSC: you transmit 0 or 1, and the receiver gets 0, 1, or an erasure symbol (?) meaning "I don't know". Formally: Pr[y = 0 | x = 0] = 1 - p, Pr[y = ? | x = 0] = p, and symmetrically for x = 1. Capacity is C_BEC = 1 - p - higher than BSC at the same error probability p, because the receiver knows where errors are (the erasures) and can request retransmission. Decoding for BEC is simpler: no need to correct errors, just fill in erasures. This is the channel used in practice for ARQ (Automatic Repeat reQuest) systems where retransmission is possible.

Turbo codes and LDPC codes: In the 1990s, turbo codes (Berrou 1993) and low-density parity-check codes (LDPC, rediscovered Gallager 1960s → modern 2000s) achieved performance within 0.7 dB of theoretical capacity on AWGN channels - the closest ever achieved in practice. The secret is iterative decoding: the syndrome (from the error-correcting codes article) provides soft information (probabilities, likelihood ratios) that two decoders exchange iteratively. After 10-50 iterations, error converges near capacity. Not constructive in Shannon's sense (no proven guarantee), but empirically powerful.

Gaussian channel (AWGN): For a continuous-time channel with white Gaussian noise, capacity is the Shannon-Hartley formula: C = W log2(1 + P/N0W), where W is bandwidth, P is power, N0 is spectral noise density. The form resembles BSC: capacity grows logarithmically with signal-to-noise ratio.

Rate-distortion: Shannon's third theorem (article 1721) addresses the inverse problem: what is maximum compression at a given distortion? Capacity is the limiting case of rate-distortion when distortion = 0.

Quantum channels: In quantum channels (quantum communication), the second theorem generalizes: the classical capacity of a quantum channel is still maximized mutual information, but over quantum states. The bounds are more complex.

Pitfalls and common errors

  • Confusing error probability with capacity. A channel with p = 0.01 (1% error) does not have capacity 0.99; it has capacity 0.919. The difference is the entropy of error. Many students think C = 1 - p directly, without the logarithm.
  • Thinking "below capacity" means "zero error". False. It means "arbitrarily small error with long enough block". There is always some error; the decay rate is exponential.
  • Adding rates of parallel channels. If you have k independent BSC channels, total capacity is k * C_single, not (complex combination). Independence is key.
  • Forgetting the maximization over p(x). Capacity also depends on how you distribute inputs. For BSC, uniform distribution is optimal, but for other channels it may not be.

Advanced exercises

  1. Capacity computation: A BSC channel with p = 0.05. Compute C(0.05) using the H(p) formula. Verify numerically with Python (scipy.special.entropy).
  2. Channel comparison: Given a Wi-Fi channel (p ≈ 0.01) and a 4G channel (p ≈ 0.001), which has twice the capacity? How does C(p) scale relative to p?
  3. Decoding error probability: Generate a sequence of n = 1000 bits to transmit, introduce errors with probability p = 0.1, apply a simple repetition code (repeat each bit 3 times), decode by majority, measure P_e. Repeat for n = 10000 and observe the decay.
  4. Critical rate: For the channel with p = 0.1, we computed C ≈ 0.531 bits. What is the maximum rate R in bits/symbol if you want a 10% margin below C? (R = 0.9 * C = 0.478 bits/symbol)
  5. Entropy vs capacity: Show that as p → 0, H(p) → 0 (using approximation p log p ≈ 0 for small p) and thus C → 1. As p → 0.5, H(p) → 1 and C → 0.
  6. BEC channel: A BEC has p_erasure = 0.2 (20% of bits are erased). Compute capacity C_BEC = 1 - 0.2 = 0.8 bits/symbol. Compare with a BSC with p_error = 0.1 (10% bits flipped): compute C_BSC = 1 - H(0.1) ≈ 0.53 bits/symbol. Why is BEC "easier" even though p_erasure > p_error?

Essential bibliography

  • T. M. Cover, J. A. Thomas, Elements of Information Theory, 2nd ed., Wiley, 2006. (Chapters 7-8: Channel Capacity)
  • C. E. Shannon, "A Mathematical Theory of Communication", Bell System Technical Journal, 1948. (Foundational paper, Sections 12-13: The Noisy Channel)
  • D. J. MacKay, Information Theory, Inference, and Learning Algorithms, Cambridge, 2003. (Chapters 8-9: Correlated Data Compression, Channel Capacity)
  • R. Hamming, Coding and Information Theory, 2nd ed., Prentice Hall, 1986. (Practical application of codes)
  • S. Lin, D. J. Costello, Error Control Coding, 2nd ed., Pearson, 2004. (Construction of practical codes)
  • MIT OpenCourseWare 6.441 - Information Theory (2007): Lecture Notes on Channel Capacity

Technical prerequisites

  • Shannon entropy (previous article in the series)
  • Mutual information and Fisher information
  • Conditional probabilities and Bernoulli distributions
  • Logarithms base 2
  • Python: NumPy, SciPy (for entropy computations)

Related resources and internal links

Published 2026-09-29, graduate level, references Cover & Thomas 2006 and Shannon 1948.

Commenti

Caricamento commenti...

Sign in to comment

Discuss this article in the community

Join the Telegram group to discuss with other developers, ask questions and share your experiences.

Did you like this article?

Explore other content on the blog or discover my projects