Ferkans — Interactive Telecom Tutor

The Redundancy–Reliability Tradeoff

Shannon's source coding theorem (Chapter 5) tells us that we can compress a source at any rate $R > H(X)$ with vanishing error probability. But how fast does the error probability vanish? And what if we want to compress at a rate slightly above $H(X)$ — how much "redundancy" do we need to achieve a given reliability? The method of types gives a precise answer: the error probability decays exponentially in blocklength $n$ , and the exponent depends on $R - H(X)$ in a precise way.

Definition:
Source Coding Error Event

A block source code of rate $R$ for a DMS $\{X_i\} \sim P$ assigns to each source sequence $\mathbf{x} \in \mathcal{X}^n$ an index $f(\mathbf{x}) \in \{1, \ldots, 2^{nR}\}$ . The error event is the event that the source sequence cannot be uniquely recovered: $\mathcal{E}_n = \{\mathbf{x} \in \mathcal{X}^n : \mathbf{x} \text{ is not in the codebook}\}.$ The error probability is $P_e^{(n)} = P^n(\mathcal{E}_n)$ .

Theorem: Source Coding Error Exponent

For a DMS with distribution $P$ on $\mathcal{X}$ and a source code of rate $R$ :

If $R > H(P)$ , the optimal error exponent is $E_s(R) = \min_{Q : H(Q) \geq R} D(Q \| P).$ That is, there exists a sequence of codes with $P_e^{(n)} \leq 2^{-nE_s(R)}$ , and no sequence of codes can achieve a strictly larger exponent.
If $R < H(P)$ , then $P_e^{(n)} \to 1$ .

The error occurs when the source sequence has a type $Q$ with $H(Q) > R$ — meaning the type class is too large for the codebook to cover. By Sanov's theorem, the probability of such types is dominated by the one closest to $P$ in KL divergence. The redundancy $R - H(P)$ controls how far the "bad" types are from $P$ , and hence how fast the error decays.

Proof

Error event in terms of types

The optimal code assigns codewords to the $2^{nR}$ most probable sequences. A type- $Q$ sequence has probability $2^{-n(H(Q) + D(Q \| P))}$ and the type class has $\doteq 2^{nH(Q)}$ elements. If $H(Q) \leq R$ , the entire type class fits in the codebook. The error event is thus: $\mathcal{E}_n \subseteq \bigcup_{Q \in \mathcal{P}_n : H(Q) > R} T_Q.$

Apply Sanov's theorem

The set of "bad" distributions is $\mathcal{E} = \{Q : H(Q) \geq R\}$ . By Sanov's theorem: $P_e^{(n)} \leq P^n(\hat{P}_{\mathbf{X}} \in \mathcal{E}) \doteq 2^{-n \min_{Q : H(Q) \geq R} D(Q \| P)}.$

Evaluate the minimization

The optimization $\min_{Q : H(Q) \geq R} D(Q \| P)$ is a convex program (KL divergence is convex in $Q$ , and the entropy constraint defines a convex set). By KKT conditions, the optimal $Q^*$ satisfies: $Q^*(a) = \frac{P(a)^{1/(1+\lambda)}}{\sum_{b} P(b)^{1/(1+\lambda)}}$ for a Lagrange multiplier $\lambda \geq 0$ chosen so that $H(Q^*) = R$ . This is a tilted version of $P$ — a member of the exponential family generated by $P$ .

Example: Error Exponent for a Binary Source

Compute the source coding error exponent $E_s(R)$ for a binary source with $P(0) = 0.3$ , $P(1) = 0.7$ at rate $R = 0.95$ bits/symbol.

Solution

Compute source entropy

$H(P) = -0.3 \log_2 0.3 - 0.7 \log_2 0.7 \approx 0.8813$ bits/symbol. Since $R = 0.95 > H(P)$ , we have redundancy $R - H(P) \approx 0.069$ bits/symbol.

Find the optimal tilted distribution

We need $Q^*$ with $H(Q^*) = 0.95$ that minimizes $D(Q^* \| P)$ . For the binary case, $Q^* = (q, 1-q)$ where $H(q) = 0.95$ . Solving: $q \approx 0.2014$ or $q \approx 0.7986$ . Since $P(0) = 0.3$ , the closer solution is $q \approx 0.7986$ (the one on the same side of the entropy curve that's closer to $P$ ).

Actually, we need the $Q^*$ closest to $P$ in KL divergence. Evaluating both:

$Q_1 = (0.2014, 0.7986)$ : $D(Q_1 \| P) \approx 0.0616$
$Q_2 = (0.7986, 0.2014)$ : $D(Q_2 \| P) \approx 1.135$

So $Q^* = (0.2014, 0.7986)$ and $E_s(0.95) \approx 0.0616$ bits.

Interpret

At rate 0.95 bits/symbol (redundancy of 0.069 bits), the error probability decays as $2^{-0.0616 n}$ . For $n = 100$ : $P_e \leq 2^{-6.16} \approx 0.014$ . For $n = 1000$ : $P_e \leq 2^{-61.6}$ , which is astronomically small. The price of small redundancy is moderate blocklength — but the convergence is exponential.

Source Coding Error Exponent $E_s(R)$

Plot the source coding error exponent $E_s(R)$ as a function of rate for a binary source. Observe how the exponent starts at zero when $R = H(P)$ and increases as redundancy grows. The slider controls the source parameter $p$ .

Parameters

Source parameter

p = P(1)

0.3

Blocklength

n

100

The Redundancy–Reliability Tradeoff

The source coding exponent reveals a fundamental tradeoff: redundancy ( $R - H(P)$ , the excess rate beyond entropy) buys reliability ( $E_s(R)$ , the rate at which errors vanish). At the Shannon limit $R = H(P)$ , the exponent is zero — errors vanish, but only sub-exponentially. Any positive redundancy yields exponential error decay. This is the source coding analogue of the channel coding result that rates below capacity give exponential reliability.

🔧Engineering Note

Practical Implications of Source Coding Exponents

In practice, source codes (Huffman, arithmetic, LZ) operate at rates very close to entropy, so their "exponent" is effectively zero — they rely on large blocklengths for reliability rather than excess rate. The error exponent framework is more relevant for fixed-rate source coding (used in delay-constrained systems like real-time video) where you must choose a rate above entropy and want to know how many source symbols to block together to achieve a target error probability. A practical rule of thumb: to achieve error probability below $10^{-6}$ , you need blocklength $n \geq 6 \log_2 10 / E_s(R) \approx 20 / E_s(R)$ .

Quick Check

For a DMS with entropy $H(P) = 2$ bits and a source code at rate $R = 2$ bits/symbol (zero redundancy), the error probability:

Decays exponentially to zero

Goes to zero, but sub-exponentially

Stays bounded away from zero

Goes to 1

Correction:

Goes to zero, but sub-exponentially

When $R = H(P)$ , the error exponent is zero. The error probability still goes to zero (this is Shannon's theorem), but only polynomially in $n$ , not exponentially.

Key Takeaway

The source coding error exponent $E_s(R) = \min_{Q : H(Q) \geq R} D(Q \| P)$ quantifies the redundancy-reliability tradeoff: coding at rate $R > H(P)$ gives error probability decaying as $2^{-nE_s(R)}$ . The exponent is zero at the Shannon limit and increases with redundancy. This is a direct application of Sanov's theorem to the set of "bad" types.

Error Exponents for Source Coding

The Redundancy–Reliability Tradeoff

Definition: Source Coding Error Event

Theorem: Source Coding Error Exponent

Error event in terms of types

Apply Sanov's theorem

Evaluate the minimization

Example: Error Exponent for a Binary Source

Compute source entropy

Find the optimal tilted distribution

Interpret

Source Coding Error Exponent Es(R)E_s(R)Es​(R)

Parameters

The Redundancy–Reliability Tradeoff

Practical Implications of Source Coding Exponents

Quick Check

Key Takeaway

Definition:
Source Coding Error Event

Source Coding Error Exponent $E_s(R)$