Channel Capacity

Table of Contents

• 0. Motivation: The Noisy Channel Problem
  • 0.1 Repetition Codes Are Wasteful
  • 0.2 Shannon’s Surprising Answer
  • 0.3 A First Look at Concrete Capacities
• 1. Channels and Codes
  • 1.1 The Discrete Memoryless Channel
  • 1.2 Codes, Rate, and Error Probability
  • 1.3 Achievability and Operational Capacity
• 2. Channel Capacity: Definition and Key Examples
  • 2.1 Information-Theoretic Definition
  • 2.2 Binary Symmetric Channel
  • 2.3 Binary Erasure Channel
  • 2.4 AWGN Channel
  • 2.5 Concavity of Mutual Information and the Capacity-Achieving Distribution
• 3. Fano’s Inequality
  • 3.1 Setup
  • 3.2 Proof
  • 3.3 Weaker Form and Operational Meaning
• 4. Shannon’s Noisy Channel Coding Theorem
  • 4.1 Statement
  • 4.2 Achievability: Random Coding and Jointly Typical Decoding
  • 4.3 Converse: Rates Above Capacity Are Impossible
  • 4.4 Proof Summary and Interpretation
• 5. Error Exponents: Gallager’s E0 Function
  • 5.1 The Question Beyond the Threshold
  • 5.2 Gallager’s E0 Function and the Reliability Function
  • 5.3 Sphere-Packing Bound
  • 5.4 Behavior of E(R) Across Rate Regimes
• 6. Channel Capacity Under Constraints
  • 6.1 Cost-Constrained Capacity
  • 6.2 Feedback Does Not Increase Capacity
  • 6.3 Additivity: n Uses of the Channel
• 7. Connections
  • 7.1 Source-Channel Separation
  • 7.2 Duality with Source Coding
  • 7.3 Forward Reference: Rate-Distortion
• References

0. Motivation: The Noisy Channel Problem

0.1 Repetition Codes Are Wasteful

Imagine transmitting a single bit \(m \in \{0, 1\}\) across a channel that flips each bit independently with probability \(p\). If we transmit \(m\) once, the receiver decodes incorrectly with probability \(p\). The naive fix: transmit \(m\) three times and have the receiver take a majority vote. This reduces error to roughly \(3p^2\), but the transmission rate drops from 1 bit per channel use to \(\frac{1}{3}\) bit per channel use.

Continuing this logic — send \(m\) five times for even lower error, then seven times, and so on — suggests that reliable communication requires paying an ever-steeper price in rate. Before 1948, this intuition was considered essentially correct: most engineers believed that pushing error probability to zero required pushing the rate to zero as well.

0.2 Shannon’s Surprising Answer

Shannon’s 1948 paper demonstrated that this intuition is fundamentally wrong. Surprisingly, there is a sharp threshold — the channel capacity \(C\) — with the following property:

• For any rate \(R < C\), there exist encoding and decoding schemes that transmit at rate \(R\) with error probability converging to zero as block length \(n \to \infty\).
• For any rate \(R > C\), every sequence of codes has error probability bounded away from zero.

The key insight is that reliability and rate are not fundamentally at odds — the structure of long random codewords allows reliable communication at nonzero rates. The price for reliability is not rate itself, but rather block length: codes must be long.

0.3 A First Look at Concrete Capacities

Three canonical channels appear throughout this note:

Here \(H_2(p) = -p\log_2 p - (1-p)\log_2(1-p)\) is the binary entropy function.

1. Channels and Codes

1.1 The Discrete Memoryless Channel

Definition (Discrete Memoryless Channel). A discrete memoryless channel (DMC) is a triple \((\mathcal{X}, p(y|x), \mathcal{Y})\) where \(\mathcal{X}\) is a finite input alphabet, \(\mathcal{Y}\) is a finite output alphabet, and \(p(y|x)\) is a channel transition matrix specifying \(p(y|x) = \Pr[Y = y \mid X = x]\) for each \((x, y) \in \mathcal{X} \times \mathcal{Y}\).

The memoryless property: when the channel is used \(n\) times in succession, the joint conditional distribution factorizes as

\[p(y^n \mid x^n) = \prod_{i=1}^n p(y_i \mid x_i).\]

That is, each channel output \(Y_i\) depends only on the corresponding input \(X_i\), not on previous inputs or outputs. This rules out channels with memory (e.g., fading channels, intersymbol interference).

Notation. We write \(x^n = (x_1, \ldots, x_n) \in \mathcal{X}^n\) for an input sequence and \(y^n = (y_1, \ldots, y_n) \in \mathcal{Y}^n\) for an output sequence.

1.2 Codes, Rate, and Error Probability

Definition (\((M, n)\) Code). An \((M, n)\) code for a DMC \((\mathcal{X}, p(y|x), \mathcal{Y})\) consists of: - A message set \(\mathcal{M} = \{1, 2, \ldots, M\}\), - An encoder \(f : \mathcal{M} \to \mathcal{X}^n\), mapping each message to a codeword \(f(m) \in \mathcal{X}^n\), - A decoder \(g : \mathcal{Y}^n \to \mathcal{M}\), mapping each received sequence to a message estimate.

The codebook is the set of codewords \(\mathcal{C} = \{f(1), f(2), \ldots, f(M)\} \subseteq \mathcal{X}^n\).

Definition (Rate). The rate of an \((M, n)\) code is

\[R = \frac{1}{n} \log_2 M \quad \text{bits per channel use.}\]

For a \((2^{nR}, n)\) code (with \(M = 2^{nR}\)), the rate is exactly \(R\).

Definition (Average Error Probability). Given uniform message distribution over \(\mathcal{M}\), the average probability of error is

\[P_e^{(n)} = \frac{1}{M} \sum_{m=1}^M \Pr\bigl[g(Y^n) \neq m \;\big|\; X^n = f(m)\bigr].\]

Remark: The average error criterion is weaker than the maximal error criterion \(P_e^{(n),\max} = \max_{m} \Pr[g(Y^n) \neq m \mid X^n = f(m)]\). Both are used; the Shannon coding theorem holds for both (via expurgation, maximal-error codes can be constructed from average-error codes with at most a factor-of-2 rate loss). We use average error throughout.

1.3 Achievability and Operational Capacity

Definition (Achievable Rate). A rate \(R \geq 0\) is achievable if there exists a sequence of \((2^{nR}, n)\) codes such that

\[P_e^{(n)} \to 0 \quad \text{as } n \to \infty.\]

Definition (Operational Capacity). The operational capacity of the DMC is

\[C = \sup\{R \geq 0 : R \text{ is achievable}\}.\]

The central theorem of channel coding (Shannon, 1948) identifies \(C\) with the maximum mutual information:

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

where the maximum is over all probability distributions on \(\mathcal{X}\), and \(I(X;Y)\) denotes the mutual information Entropy and Divergences (no note yet) between the channel input and output under \(p(x,y) = p(x)p(y|x)\).

2. Channel Capacity: Definition and Key Examples

2.1 Information-Theoretic Definition

Definition (Channel Capacity). The information-theoretic capacity of a DMC \((\mathcal{X}, p(y|x), \mathcal{Y})\) is

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

where \(I(X;Y) = \sum_{x,y} p(x)p(y|x)\log_2 \frac{p(y|x)}{p(y)}\) and \(p(y) = \sum_x p(x)p(y|x)\).

The maximum exists because \(p(x)\) ranges over the compact simplex \(\Delta(\mathcal{X})\) and \(I(X;Y)\) is continuous (in fact, concave) in \(p(x)\) for fixed \(p(y|x)\). The input distribution \(p^*(x)\) achieving the maximum is the capacity-achieving distribution.

2.2 Binary Symmetric Channel

Definition (BSC). The binary symmetric channel with crossover probability \(p \in [0, 1/2]\) has \(\mathcal{X} = \mathcal{Y} = \{0,1\}\) and transition matrix

\[p(y|x) = \begin{cases} 1-p & \text{if } y = x, \\ p & \text{if } y \neq x. \end{cases}\]

graph LR
    X0["0"] -->|"1-p"| Y0["0"]
    X0 -->|"p"| Y1["1"]
    X1["1"] -->|"p"| Y0
    X1 -->|"1-p"| Y1

Proposition (BSC Capacity). \(C_{\mathrm{BSC}}(p) = 1 - H_2(p)\) bits.

Proof. We have

\[I(X;Y) = H(Y) - H(Y|X).\]

Since \(H(Y|X) = \sum_x p(x) H(Y|X=x) = \sum_x p(x) H_2(p) = H_2(p)\) (each row of the BSC has entropy \(H_2(p)\), independent of \(x\)), we need to maximize \(H(Y)\) over \(p(x)\).

\(H(Y) \leq 1\) with equality iff \(Y\) is uniform. Under the BSC, \(\Pr[Y=1] = p(0)(p) + p(1)(1-p)\). Setting \(\Pr[Y=1] = 1/2\) requires \(p(0) = p(1) = 1/2\). Therefore

\[I(X;Y) = H(Y) - H_2(p) \leq 1 - H_2(p),\]

achieved by the uniform input \(p^*(0) = p^*(1) = 1/2\). \(\square\)

The capacity-achieving distribution for the BSC is uniform. This makes sense by symmetry: the BSC treats both input symbols identically, so any asymmetry in \(p(x)\) is wasted.

2.3 Binary Erasure Channel

Definition (BEC). The binary erasure channel with erasure probability \(\epsilon \in [0,1]\) has \(\mathcal{X} = \{0,1\}\), \(\mathcal{Y} = \{0, ?, 1\}\) (with \(?\) denoting erasure), and transition probabilities

\[p(y|x) = \begin{cases} 1-\epsilon & \text{if } y = x, \\ \epsilon & \text{if } y = \;?, \\ 0 & \text{otherwise.} \end{cases}\]

graph LR
    X0["0"] -->|"1-ε"| Y0["0"]
    X0 -->|"ε"| YE["?"]
    X1["1"] -->|"ε"| YE
    X1 -->|"1-ε"| Y1["1"]

Proposition (BEC Capacity). \(C_{\mathrm{BEC}}(\epsilon) = 1 - \epsilon\) bits.

Proof. Compute \(I(X;Y) = H(Y) - H(Y|X)\). Given \(X=x\), the output \(Y\) takes value \(x\) with probability \(1-\epsilon\) and \(?\) with probability \(\epsilon\), so \(H(Y|X=x) = H_2(\epsilon)\) (binary entropy) for each \(x\). Thus \(H(Y|X) = H_2(\epsilon)\).

Now \(\Pr[Y = ?] = \epsilon\) regardless of \(p(x)\) (since both inputs erase with probability \(\epsilon\)). So \(Y\) takes value \(?\) with probability \(\epsilon\) and takes value \(0\) or \(1\) with total probability \(1-\epsilon\). Given that \(Y \neq ?\), the output is \(0\) with probability \(p(0)\) and \(1\) with probability \(p(1)\).

We can write \(H(Y) = H_2(\epsilon) + (1-\epsilon)H(X)\) using the chain rule: condition on whether erasure occurs. Therefore

\[I(X;Y) = H_2(\epsilon) + (1-\epsilon)H(X) - H_2(\epsilon) = (1-\epsilon)H(X) \leq (1-\epsilon) \cdot 1,\]

with equality iff \(H(X) = 1\), i.e., \(p(0) = p(1) = 1/2\). Thus \(C = 1 - \epsilon\). \(\square\)

2.4 AWGN Channel

The additive white Gaussian noise (AWGN) channel is \(Y_i = X_i + Z_i\), where \(Z_i \sim \mathcal{N}(0, \sigma^2)\) i.i.d. and the input satisfies an average power constraint \(\frac{1}{n}\sum_i X_i^2 \leq P\).

Theorem (AWGN Capacity, Shannon 1948).

\[C_{\mathrm{AWGN}} = \frac{1}{2}\log_2\!\left(1 + \frac{P}{\sigma^2}\right) \quad \text{bits per channel use.}\]

Proof deferred: this result requires the concept of differential entropy for continuous distributions, which is outside the scope of this note (treating discrete channels). The Gaussian input \(X \sim \mathcal{N}(0, P)\) is capacity-achieving. At high SNR, \(C \approx \frac{1}{2}\log_2(P/\sigma^2)\) grows logarithmically in power.

2.5 Concavity of Mutual Information and the Capacity-Achieving Distribution

Proposition (Concavity in input distribution). For a fixed DMC \(p(y|x)\), the mutual information \(I(X;Y)\) is a concave function of the input distribution \(p(x)\).

Proof sketch. Write \(I(X;Y) = H(Y) - H(Y|X)\). The term \(H(Y|X) = \sum_x p(x) H(Y|X=x)\) is linear in \(p(x)\) (since \(H(Y|X=x)\) is a fixed function of the channel). The term \(H(Y) = H\!\left(\sum_x p(x) p(\cdot|x)\right)\) is a concave function of \(p(x)\): entropy is concave in the distribution, and the map \(p(x) \mapsto \sum_x p(x) p(\cdot|x)\) is linear. A concave function composed with a linear map is concave. Therefore \(I(X;Y)\) is a sum of a concave function and a linear function, hence concave. \(\square\)

Concavity ensures that the capacity optimization problem \(\max_{p(x)} I(X;Y)\) over the simplex \(\Delta(\mathcal{X})\) has no local optima — any local maximum is global — and can be solved efficiently (e.g., via the Blahut-Arimoto algorithm, Exercise 22).

3. Fano’s Inequality

3.1 Setup

Let \(X\) be a random variable taking values in a finite alphabet \(\mathcal{X}\). Suppose we observe a random variable \(Y\) (not necessarily related to \(X\) through a specific channel model) and form an estimate \(\hat{X} = g(Y)\) for some deterministic function \(g\). Define the error probability

\[P_e = \Pr[\hat{X} \neq X].\]

The Markov chain \(X \to Y \to \hat{X}\) holds (since \(\hat{X}\) is a function of \(Y\) only), so by the data processing inequality Entropy and Divergences (no note yet),

\[I(X; \hat{X}) \leq I(X; Y).\]

Fano’s inequality gives a quantitative lower bound on \(H(X|Y)\) in terms of \(P_e\): if the decoder makes many errors, the channel cannot have been very informative about \(X\).

3.2 Proof

📐 Theorem (Fano’s Inequality). For any estimator \(\hat{X} = g(Y)\) with error probability \(P_e = \Pr[\hat{X} \neq X]\),

\[H(X | Y) \leq H_2(P_e) + P_e \log_2(|\mathcal{X}| - 1).\]

Proof. Introduce the error indicator \(E = \mathbf{1}[\hat{X} \neq X] \in \{0,1\}\).

Step 1: Chain rule, two ways. Apply the chain rule for entropy to \(H(E, X \mid \hat{X})\):

\[H(E, X \mid \hat{X}) = H(X \mid \hat{X}) + \underbrace{H(E \mid X, \hat{X})}_{= 0},\]

since \(E\) is determined by \((X, \hat{X})\). Also,

\[H(E, X \mid \hat{X}) = H(E \mid \hat{X}) + H(X \mid E, \hat{X}).\]

Equating: \(H(X \mid \hat{X}) = H(E \mid \hat{X}) + H(X \mid E, \hat{X})\).

Step 2: Bound each term. First, \(H(E \mid \hat{X}) \leq H(E) = H_2(P_e)\) (conditioning reduces entropy).

Second, expand \(H(X \mid E, \hat{X})\) by conditioning on \(E\):

\[H(X \mid E, \hat{X}) = \Pr[E=0]\underbrace{H(X \mid E=0, \hat{X})}_{=\,0} + \Pr[E=1] H(X \mid E=1, \hat{X}).\]

When \(E=0\) (correct decoding), \(X = \hat{X}\) almost surely, so \(H(X \mid E=0, \hat{X}) = 0\). When \(E=1\) (error), \(X \neq \hat{X}\), so given \(\hat{X}\), the variable \(X\) takes values in \(\mathcal{X} \setminus \{\hat{X}\}\), an alphabet of size \(|\mathcal{X}|-1\). Therefore \(H(X \mid E=1, \hat{X}) \leq \log_2(|\mathcal{X}|-1)\).

Combining: \(H(X \mid E, \hat{X}) \leq P_e \log_2(|\mathcal{X}|-1)\).

Step 3: Assemble. Since \(H(X|\hat{X}) \geq H(X|Y)\) by the data processing inequality (observing \(Y\) is at least as informative as any function \(\hat{X} = g(Y)\)):

\[H(X|Y) \leq H(X|\hat{X}) \leq H_2(P_e) + P_e\log_2(|\mathcal{X}|-1). \qquad \square\]

3.3 Weaker Form and Operational Meaning

Corollary (Weak Fano). Using \(\log_2(|\mathcal{X}|-1) \leq \log_2|\mathcal{X}|\) and \(H_2(P_e) \leq 1\):

\[H(X|Y) \leq 1 + P_e \log_2|\mathcal{X}|.\]

This weaker form suffices for the channel coding converse.

Operational meaning. 🔑 Fano’s inequality says: if the decoder makes few errors (\(P_e \approx 0\)), then \(H(X|Y)\) must be small — the channel output \(Y\) has almost eliminated uncertainty about \(X\). Equivalently, \(H(X|Y) \approx 0\) is a necessary condition for reliable decoding.

The converse direction is also useful: if \(H(X|Y)\) is large, then any decoder must make many errors. This is the key ingredient in the converse proof of Shannon’s theorem.

4. Shannon’s Noisy Channel Coding Theorem

4.1 Statement

Theorem (Shannon’s Channel Coding Theorem, 1948). For a DMC with transition matrix \(p(y|x)\), let

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

Then: 1. (Achievability) For every rate \(R < C\) and every \(\varepsilon > 0\), there exists \(N\) such that for all \(n \geq N\) there exists a \((2^{nR}, n)\) code with \(P_e^{(n)} \leq \varepsilon\). 2. (Converse) For every rate \(R > C\), every sequence of \((2^{nR}, n)\) codes satisfies \(P_e^{(n)} \geq 1 - C/R - 1/(nR) \to 1 - C/R > 0\).

Together: \(C = \max_{p(x)} I(X;Y)\) is simultaneously the operational capacity (supremum of achievable rates).

4.2 Achievability: Random Coding and Jointly Typical Decoding

📐 The achievability proof constructs a sequence of codes (non-constructively) via random coding and analyzes the error probability.

Setup. Fix a rate \(R < C\) and a capacity-achieving distribution \(p^*(x)\). Fix \(\varepsilon > 0\) small enough that \(R < I(X;Y) - 3\varepsilon\) (possible since \(I(X;Y) = C > R\)).

Code generation. Draw \(2^{nR}\) codewords independently, each coordinate i.i.d. from \(p^*(x)\):

\[x^n(m) \sim \prod_{i=1}^n p^*(x_i), \quad m = 1, \ldots, 2^{nR}.\]

This is a random code: the codebook \(\mathcal{C} = \{x^n(1), \ldots, x^n(2^{nR})\}\) is a random variable.

Encoder. \(f(m) = x^n(m)\).

Jointly typical decoder. Given received sequence \(y^n\), declare \(\hat{m}\) if: 1. \((x^n(\hat{m}), y^n) \in \mathcal{T}_\varepsilon^{(n)}(X,Y)\) (jointly typical, see AEP and Typicality), 2. No other codeword \(m' \neq \hat{m}\) satisfies \((x^n(m'), y^n) \in \mathcal{T}_\varepsilon^{(n)}(X,Y)\).

If zero or more than one codewords satisfy condition 1, declare an error.

Error analysis. Fix a message \(m\) (say \(m=1\) WLOG by symmetry). Two error events can occur:

• \(\mathcal{E}_1\): the sent codeword \(x^n(1)\) is not jointly typical with \(y^n\), i.e., \((x^n(1), y^n) \notin \mathcal{T}_\varepsilon^{(n)}\).
• \(\mathcal{E}_2^{(m')}\): a wrong codeword \(x^n(m')\) is jointly typical with \(y^n\), i.e., \((x^n(m'), y^n) \in \mathcal{T}_\varepsilon^{(n)}\) for some \(m' \neq 1\).

By the union bound, \(P_e^{(n)} \leq \Pr[\mathcal{E}_1] + \sum_{m'=2}^{2^{nR}} \Pr[\mathcal{E}_2^{(m')}]\).

Bounding \(\Pr[\mathcal{E}_1]\): The AEP for jointly typical sequences (see AEP and Typicality) states that \((X^n, Y^n) \in \mathcal{T}_\varepsilon^{(n)}\) with probability approaching 1:

\[\Pr[\mathcal{E}_1] \to 0 \quad \text{as } n \to \infty.\]

Bounding \(\Pr[\mathcal{E}_2^{(m')}]\) for \(m' \neq 1\): The wrong codeword \(x^n(m')\) was drawn i.i.d. from \(p^*(x)\) independently of \(y^n\) (since \(m' \neq 1\) and codewords are independent). By the joint typicality lemma (AEP and Typicality), a pair \((x^n, y^n)\) where \(x^n\) is drawn i.i.d. from \(p^*(x)\) independently of \(y^n \sim p^*(y)\) satisfies

\[\Pr[(x^n(m'), y^n) \in \mathcal{T}_\varepsilon^{(n)}] \leq 2^{-n(I(X;Y) - 3\varepsilon)}.\]

Summing over the \(2^{nR} - 1\) wrong codewords:

\[\sum_{m'=2}^{2^{nR}} \Pr[\mathcal{E}_2^{(m')}] \leq (2^{nR}-1) \cdot 2^{-n(I(X;Y)-3\varepsilon)} \leq 2^{n(R - I(X;Y) + 3\varepsilon)}.\]

Conclusion. Since \(R < I(X;Y) - 3\varepsilon\), the exponent \(R - I(X;Y) + 3\varepsilon < 0\), so

\[P_e^{(n)} \leq \Pr[\mathcal{E}_1] + 2^{-n(I(X;Y) - R - 3\varepsilon)} \to 0.\]

🔑 This bound shows that random codes of rate \(R < C\) have average error probability tending to zero. Since this holds for the average over the random code ensemble, there must exist at least one specific code achieving the same error bound (a derandomization argument). \(\square\)

4.3 Converse: Rates Above Capacity Are Impossible

Theorem (Converse). For any sequence of \((2^{nR}, n)\) codes with \(R > C\),

\[P_e^{(n)} \geq 1 - \frac{C}{R} - \frac{1}{nR}.\]

Proof. Let \(M\) be a uniform message, \(X^n = f(M)\) the transmitted codeword, \(Y^n\) the channel output, and \(\hat{M} = g(Y^n)\) the decoded message.

Step 1: Bound \(I(M; Y^n)\). Since \(M \to X^n \to Y^n\) is a Markov chain (the encoder is deterministic, so \(X^n\) is determined by \(M\)) and using the data-processing inequality Entropy and Divergences (no note yet):

\[I(M; Y^n) \leq I(X^n; Y^n).\]

Now use the memoryless property and the chain rule for mutual information:

\[I(X^n; Y^n) = \sum_{i=1}^n I(X_i; Y_i \mid X^{i-1}, Y^{i-1}).\]

Wait — this step requires care. With feedback or dependence between \(X^n\) and previous \(Y\)’s, this does not immediately simplify. For a DMC without feedback, the input \(X_i\) may depend on previous outputs if feedback is used, but for a code (no feedback), \(X^n = f(M)\) is a fixed function of \(M\) only. Hence \(X_i\) is determined by \(M\) and does not depend on \(Y^{i-1}\), so

\[I(X_i; Y_i \mid X^{i-1}, Y^{i-1}) \leq I(X_i; Y_i) \leq C,\]

where the last inequality uses the definition of capacity (\(C = \max_{p(x)} I(X;Y)\) and \(p(X_i | X^{i-1})\) is some marginal on \(\mathcal{X}\)). Therefore

\[I(M; Y^n) \leq I(X^n; Y^n) \leq nC.\]

Step 2: Apply Fano. Since \(M\) is uniform over \(2^{nR}\) messages, \(H(M) = nR\). Also \(\hat{M} = g(Y^n)\), so by the data-processing inequality, \(H(M|Y^n) \leq H(M|\hat{M}) \leq 1 + P_e^{(n)} \cdot nR\) (Exercise 7).

Now write

\[nR = H(M) = I(M; Y^n) + H(M|Y^n) \leq nC + 1 + P_e^{(n)} \cdot nR.\]

Rearranging:

\[P_e^{(n)} \cdot nR \geq nR - nC - 1 = n(R-C) - 1.\]

\[\boxed{P_e^{(n)} \geq 1 - \frac{C}{R} - \frac{1}{nR}.}\]

As \(n \to \infty\), \(P_e^{(n)} \geq 1 - C/R > 0\) since \(R > C\). \(\square\)

4.4 Proof Summary and Interpretation

The two parts together establish:

\[C_{\text{operational}} = \sup\{R: R \text{ achievable}\} = C_{\text{information}} = \max_{p(x)} I(X;Y).\]

5. Error Exponents: Gallager’s E0 Function

5.1 The Question Beyond the Threshold

The coding theorem tells us that for \(R < C\), \(P_e^{(n)} \to 0\), but says nothing about how fast. For practical systems with finite block length \(n\), the rate of decay matters enormously: a code with \(P_e^{(n)} \approx 2^{-100n}\) is far more useful than one with \(P_e^{(n)} \approx 2^{-0.001n}\).

Definition (Error Exponent). For a sequence of \((2^{nR}, n)\) codes, the error exponent (or reliability function) at rate \(R\) is

\[E(R) = \lim_{n\to\infty} -\frac{1}{n}\log_2 P_e^{(n)}.\]

The best achievable error exponent at rate \(R\) is

\[E^*(R) = \sup \{E(R)\text{ over all code sequences with rate } R\}.\]

5.2 Gallager’s E0 Function and the Reliability Function

Definition (Gallager’s E0 function). For \(\rho \in [0,1]\) and input distribution \(p(x)\),

\[E_0(\rho, p) = -\log_2 \sum_{y \in \mathcal{Y}} \left(\sum_{x \in \mathcal{X}} p(x)\, p(y|x)^{\frac{1}{1+\rho}}\right)^{1+\rho}.\]

Definition (Reliability function / Random Coding Exponent). The random coding exponent is

\[E_r(R) = \max_{p(x)} \max_{\rho \in [0,1]} \left[E_0(\rho, p) - \rho R\right].\]

This equals the Legendre-Fenchel transform of \(E_0\) in the \(\rho\) variable, evaluated at rate \(R\).

Theorem (Gallager 1965). For any rate \(R < C\), there exists a sequence of \((2^{nR}, n)\) codes with

\[P_e^{(n)} \leq 2^{-n E_r(R)}.\]

That is, the random coding exponent \(E_r(R)\) is achievable.

Main ideas of the proof. Instead of the union bound used in Section 4.2 (which corresponds to \(\rho = 1\)), Gallager raises the union bound to a power \(\rho \in (0,1]\) before taking the expectation:

\[P_e^{(n)} \leq \left(\sum_{y^n} p(y^n|x^n(1))\left[\sum_{m \neq 1} \Pr[(x^n(m), y^n) \text{ jointly typical}]\right]^\rho\right).\]

Optimizing \(\rho \in [0,1]\) yields the tightest bound. The function \(E_0(\rho, p)\) encapsulates the per-symbol contribution to the exponent, and the rate term \(\rho R\) accounts for the \(2^{nR}\) wrong codewords.

5.3 Sphere-Packing Bound

The sphere-packing bound provides an upper bound on how fast \(P_e^{(n)}\) can decay — it is a converse exponent.

Definition (Sphere-Packing Exponent). The sphere-packing exponent is

\[E_{sp}(R) = \max_{p(x)} \max_{\rho \geq 0} \left[E_0(\rho, p) - \rho R\right].\]

Note that \(E_{sp}(R)\) maximizes over \(\rho \geq 0\) (not just \([0,1]\)), yielding \(E_{sp}(R) \geq E_r(R)\).

Theorem (Sphere-Packing Converse). For any sequence of \((2^{nR}, n)\) codes,

\[P_e^{(n)} \geq \text{poly}(n)^{-1} \cdot 2^{-n E_{sp}(R)}.\]

Heuristic interpretation: The sphere-packing exponent \(E_{sp}(R)\) upper-bounds the achievable error exponent \(E^*(R)\). The name comes from a geometric picture in high-dimensional space: codewords correspond to balls (spheres) of radius determined by the noise, and reliable decoding requires these balls to be disjoint (packing). The maximum number of non-overlapping balls in the output space limits how many codewords can be packed at any rate \(R\).

5.4 Behavior of E(R) Across Rate Regimes

The random coding exponent \(E_r(R)\) has a characteristic shape:

• At \(R = 0\): \(E_r(0) = E_0(1, p^*)\) (the expurgation exponent), positive.
• For \(R \in [0, R_{\text{crit}}]\): \(E_r(R) = E_{sp}(R)\), achieved by \(\rho = 1\) (random coding matches sphere-packing).
• For \(R \in (R_{\text{crit}}, C)\): \(E_r(R) < E_{sp}(R)\); there is a gap that represents room for better codes.
• At \(R = C\): \(E_r(C) = 0\) (exponent vanishes at capacity, consistent with the coding theorem).

6. Channel Capacity Under Constraints

6.1 Cost-Constrained Capacity

Many physical channels impose constraints on the input beyond the alphabet — e.g., transmit power (AWGN), peak amplitude, or average energy.

Definition (Cost-Constrained Capacity). Let \(b : \mathcal{X} \to \mathbb{R}_{\geq 0}\) be a cost function on the input alphabet, and let \(B \geq 0\) be a budget. The cost-constrained capacity is

\[C(B) = \max_{\substack{p(x) \\ \mathbb{E}[b(X)] \leq B}} I(X;Y).\]

The set of feasible distributions \(\mathcal{P}(B) = \{p(x) : \mathbb{E}[b(X)] \leq B\}\) is a closed convex subset of the simplex. Since \(I(X;Y)\) is concave in \(p(x)\), \(C(B)\) is the maximum of a concave function over a convex set — still a convex program.

Properties of \(C(B)\): - \(C(B)\) is a non-decreasing, concave, and continuous function of \(B\). - \(C(0) = I(X^*; Y)\) for the \(p(x)\) concentrated on the minimum-cost symbol \(x^* = \arg\min_x b(x)\) (possibly zero). - \(\lim_{B\to\infty} C(B) = \max_{p(x)} I(X;Y) = C\) (unconstrained capacity).

6.2 Feedback Does Not Increase Capacity

Intuitively, feedback might help the encoder adapt to the channel’s behavior. Surprisingly, feedback provides no capacity gain for DMCs.

Definition (Code with Feedback). A code with (noiseless instantaneous) feedback allows the encoder to observe previous channel outputs: at time \(i\), the encoder computes \(X_i = f_i(M, Y^{i-1})\) based on the message \(M\) and all past outputs \(Y_1, \ldots, Y_{i-1}\).

Theorem (Feedback Capacity = Forward Capacity). For a DMC \((\mathcal{X}, p(y|x), \mathcal{Y})\), allowing noiseless instantaneous feedback does not increase capacity:

\[C_{\text{feedback}} = C = \max_{p(x)} I(X;Y).\]

Proof sketch. Fix any \((2^{nR}, n)\) code with feedback. We bound \(I(M; Y^n)\):

\[I(M; Y^n) = \sum_{i=1}^n I(M; Y_i | Y^{i-1}) \leq \sum_{i=1}^n I(X_i; Y_i | Y^{i-1}).\]

The first equality is the chain rule. The inequality uses the Markov structure \(M \to (X_i, Y^{i-1}) \to Y_i\) conditioned on \(Y^{i-1}\): once we fix \(Y^{i-1}\) (and hence \(X_i\), since \(X_i = f_i(M, Y^{i-1})\) is determined by \(M\) and \(Y^{i-1}\)), the message \(M\) gives no additional information about \(Y_i\) beyond \(X_i\).

Now \(I(X_i; Y_i | Y^{i-1}) \leq I(X_i; Y_i) \leq C\) (conditioning on \(Y^{i-1}\) can only reduce \(I(X_i;Y_i)\) since the channel is memoryless: \(Y_i \perp Y^{i-1} | X_i\)). Wait — actually \(I(X_i; Y_i | Y^{i-1}) \leq \max_{p(x)} I(X;Y) = C\) since for each conditioning value of \(Y^{i-1}\), the conditional distribution of \(X_i\) is some \(p(x)\).

Therefore \(I(M; Y^n) \leq nC\), and the Fano converse applies: \(P_e^{(n)} \geq 1 - C/R - 1/(nR) > 0\) for \(R > C\). \(\square\)

6.3 Additivity: n Uses of the Channel

Proposition (Additivity of DMC Capacity). The capacity of \(n\) independent uses of a DMC is \(nC\), where \(C\) is the single-use capacity.

Proof. Achievability: run \(n\) independent uses of the capacity-achieving code for the single channel; the rate is \(C\) per use, total rate is \(nC\) for \(n\) uses. Converse: \(I(X^n; Y^n) = \sum_{i=1}^n I(X_i; Y_i) \leq nC\) (by memoryless factorization and the capacity definition). The upper bound \(nC\) is tight by the achievability argument. \(\square\)

This result is non-trivial in general network settings (multi-user channels, quantum channels) where additivity can fail. For point-to-point DMCs, it is a direct consequence of the memoryless structure.

7. Connections

7.1 Source-Channel Separation

One of the most practically important consequences of Shannon’s theorem is that source coding and channel coding can be done independently without loss of optimality.

Theorem (Source-Channel Separation). Let \(S^n\) be \(n\) i.i.d. samples from a source with entropy rate \(H\) bits/symbol, and let the channel have capacity \(C\) bits/channel use. Reliable transmission (vanishing probability of error in reconstructing \(S^n\)) is possible if and only if \(H \leq C\).

Moreover, the optimal strategy is to: 1. Compress \(S^n\) to approximately \(nH\) bits using a source code (Shannon’s first theorem). 2. Transmit those \(nH\) bits over the channel at rate \(H \leq C\) using a channel code.

No joint source-channel code can do better asymptotically — separation is optimal for DMCs.

The proof uses both the AEP AEP and Typicality for the source coding step and Shannon’s channel coding theorem for the channel coding step.

7.2 Duality with Source Coding

Shannon’s two fundamental theorems share the same proof technique:

In both cases, the proof counts how many “typical” sequences exist and how they can be assigned without collision. The channel coding theorem replaces the source’s typical set with the joint typical set of input-output pairs.

7.3 Forward Reference: Rate-Distortion

Channel coding asks: how much information can be sent reliably? Rate-distortion theory Rate-Distortion asks the dual question: what is the minimum channel rate needed to represent a source with a given distortion?

The rate-distortion function \(R(D) = \min_{p(\hat{x}|x): \mathbb{E}[d(X,\hat{X})] \leq D} I(X;\hat{X})\) is formally the “inverse” of capacity: it sets a lower bound on the rate of any lossy code at distortion \(D\). The duality is tight — both results follow from the same typical-set machinery, with the “channel” in rate-distortion replaced by a test channel \(p(\hat{x}|x)\) that is optimized to minimize mutual information subject to distortion.

8. Exercises: Algorithmic Applications

import numpy as np

def blahut_arimoto(p_yx, tol=1e-8, max_iter=1000):
    """
    Compute channel capacity via Blahut-Arimoto.
    p_yx: ndarray of shape (|Y|, |X|), channel transition matrix
    Returns: (capacity in bits, capacity-achieving p_x)
    """
    num_y, num_x = p_yx.shape
    p_x = np.ones(num_x) / num_x  # start uniform

    for _ in range(max_iter):
        p_y = p_yx @ p_x  # marginal p(y)
        # log-sum: sum_y p(y|x) log[p(y|x) / p(y)]
        # safe division: add small eps
        eps = 1e-300
        ratio = p_yx / (p_y[:, None] + eps)  # shape (|Y|, |X|)
        log_ratio = np.where(p_yx > 0, np.log2(ratio + eps), 0.0)
        score = np.sum(p_yx * log_ratio, axis=0)  # shape (|X|,)
        # update p_x
        new_p_x = p_x * np.exp(score * np.log(2))  # exp of score in nats
        new_p_x /= new_p_x.sum()
        if np.max(np.abs(new_p_x - p_x)) < tol:
            p_x = new_p_x
            break
        p_x = new_p_x

    # compute capacity
    p_y = p_yx @ p_x
    mi = 0.0
    for x_idx in range(num_x):
        for y_idx in range(num_y):
            if p_yx[y_idx, x_idx] > 0 and p_x[x_idx] > 0:
                mi += (p_x[x_idx] * p_yx[y_idx, x_idx]
                       * np.log2(p_yx[y_idx, x_idx]
                                 / (p_y[y_idx] + 1e-300)))
    return mi, p_x

import numpy as np

def jointly_typical_decoder(codebook, y_n, p_x, p_yx, epsilon):
    """
    codebook: list of codewords, each a list of symbol indices (length n)
    y_n: received sequence, list of symbol indices (length n)
    p_x: input distribution, shape (|X|,)
    p_yx: channel matrix, shape (|Y|, |X|)
    epsilon: typicality tolerance
    Returns: decoded message index (0-based) or -1 on error
    """
    n = len(y_n)
    # compute marginal p_y
    p_y = p_yx @ p_x  # shape (|Y|,)
    # compute joint p_xy and marginal entropies
    H_X = -np.sum(p_x * np.log2(p_x + 1e-300))
    H_Y = -np.sum(p_y * np.log2(p_y + 1e-300))
    # joint entropy H(X,Y)
    p_xy = p_x[None, :] * p_yx  # shape (|Y|, |X|)
    H_XY = -np.sum(p_xy * np.log2(p_xy + 1e-300))
    I_XY = H_X + H_Y - H_XY  # mutual information

    def is_jointly_typical(x_n):
        # empirical log-joint probability
        log_joint = sum(
            np.log2(p_yx[y_n[i], x_n[i]] * p_x[x_n[i]] + 1e-300)
            for i in range(n)
        )
        emp_joint_ent = -log_joint / n
        # empirical log-marginals
        log_marg_x = sum(np.log2(p_x[x_n[i]] + 1e-300) for i in range(n))
        log_marg_y = sum(np.log2(p_y[y_n[i]] + 1e-300) for i in range(n))
        emp_H_X = -log_marg_x / n
        emp_H_Y = -log_marg_y / n
        return (
            abs(emp_joint_ent - H_XY) < epsilon
            and abs(emp_H_X - H_X) < epsilon
            and abs(emp_H_Y - H_Y) < epsilon
        )

    matches = [m for m, x_n in enumerate(codebook) if is_jointly_typical(x_n)]
    return matches[0] if len(matches) == 1 else -1

import numpy as np

def h2(p):
    if p == 0 or p == 1:
        return 0.0
    return -p * np.log2(p) - (1-p) * np.log2(1-p)

crossovers = [0.01, 0.05, 0.1, 0.2, 0.3, 0.5]
for p in crossovers:
    p_yx = np.array([[1-p, p], [p, 1-p]])  # BSC transition matrix
    C_numerical, p_x_opt = blahut_arimoto(p_yx)
    C_analytic = 1 - h2(p)
    print(f"p={p:.2f}: C_num={C_numerical:.6f}, "
          f"C_analytic={C_analytic:.6f}, "
          f"p_x={p_x_opt.round(4)}")

import numpy as np

def simulate_random_bsc_code(n, R, p_flip, num_trials=2000):
    """Estimate error probability for random BSC code."""
    M = int(2 ** (n * R))
    if M < 2:
        return 1.0
    # generate codebook: M codewords of length n, uniform bits
    codebook = np.random.randint(0, 2, size=(M, n))
    errors = 0
    for _ in range(num_trials):
        msg = np.random.randint(0, M)
        sent = codebook[msg]
        # BSC: flip each bit independently
        noise = (np.random.rand(n) < p_flip).astype(int)
        received = (sent + noise) % 2
        # ML decode: minimum Hamming distance
        dists = np.sum(codebook != received, axis=1)
        decoded = np.argmin(dists)
        if decoded != msg:
            errors += 1
    return errors / num_trials

p_flip = 0.1
R = 0.4
for n in [50, 100, 200, 400]:
    Pe = simulate_random_bsc_code(n, R, p_flip)
    print(f"n={n:4d}: P_e = {Pe:.4f}, log2(P_e)/n = {np.log2(Pe+1e-10)/n:.4f}")

References