Motivation
Compression and error correction ask different questions. A source code removes predictable structure from a message. A channel code introduces structure so that a receiver can distinguish messages after noise. Counting the number of output symbols alone cannot measure how much information survived: a channel might produce a fair random bit independent of its input. Its output entropy would be one bit, yet it would communicate nothing about the input.
The relevant quantity is the reduction in uncertainty about the input after observing the output. We develop that quantity for finite alphabets, then connect it to the probability of a decoding error. The resulting converse is useful because it applies to every encoder and decoder satisfying the model, including ones whose algorithms we have never seen. It gives a necessary rate bound; constructing codes that attain that bound is a separate theorem.
We use base-two logarithms and the finite entropy definitions from the prefix-code chapter. All random variables have finite ranges, and terms of the form are zero.
Definitions
Definition 3.3.1
(Finite channel)
A finite channel from alphabet to alphabet is a collection of probabilities with for each input . An input distribution produces the joint law . The channel specifies what happens for each input; choosing how often to use inputs is additional data.
Definition 3.3.2
(Conditional entropy and mutual information)
The conditional entropy is
The chain rule follows by substituting in the entropy sum and splitting the logarithm. Define mutual information by
The second equality follows from the chain rule, and gives symmetry. It is not a definition that requires a uniform input. The binary entropy function is , with its continuous endpoint values zero.
Definition 3.3.3
(Binary symmetric and binary erasure channels)
A binary symmetric channel, or BSC, with crossover probability has , where is an independent Bernoulli random variable of parameter . We take . A binary erasure channel, or BEC, with erasure probability returns the input bit with probability and a distinct symbol otherwise, independently of the input. An erasure reveals its location; a flipped bit does not.
Definition 3.3.4
(Memoryless block codes)
For memoryless uses, the conditional law is . The inputs need not be independent. A block code in this chapter chooses a message uniformly from possibilities, encodes it deterministically as , and estimates it by a deterministic function . Its average error probability is , and its rate is bits per use. We bound average error under this uniform-message convention; that is not automatically a maximum-over-messages guarantee.
Theorem/proposition
Theorem 3.3.5
(Information retained by a binary channel)
Mutual information is nonnegative and is zero exactly when and are independent. For a BSC with input ,
For a BEC, . A uniform binary input attains each upper bound. These are maximizations of one-use mutual information; the coding interpretation requires an additional achievability argument.
Theorem 3.3.6
(Fano's inequality and a necessary BSC rate bound)
For the block-code model above,
For memoryless BSC uses with crossover probability , every such code therefore satisfies
Consequently, for a sequence of codes with and , the limit superior of their rates is at most .
Proof sketch or proof idea
Proof
(Nonnegativity and the two binary channels)
Expanding the definitions gives
This is the divergence of the joint law from the product of its marginals. The divergence inequality proved in the entropy chapter makes it nonnegative, with equality precisely when the two distributions agree. No term with positive numerator has zero denominator, since positive joint mass implies both marginals are positive. The equality condition is exactly independence. Applying the same argument within each conditional distribution also gives , and hence conditioning cannot increase entropy: . In particular .
In the BSC, the output-one probability is . For either fixed input, the output entropy is , so . Subtract this from to obtain the formula. A binary variable has entropy at most one, by the divergence comparison with the uniform law. A uniform input makes the output uniform and attains the bound, including the endpoints.
In the BEC, observing a nonerasure determines , so the corresponding conditional entropy is zero. An erasure is independent of the input and leaves its original distribution unchanged, so its conditional entropy is . Averaging gives and the formula follows. This proof describes exactly what the erasure symbol tells the receiver, instead of treating it as an ordinary input bit.
Proof
(Fano’s inequality by an error indicator)
Put when the decoder is wrong and otherwise. Since is determined by and , the chain rule gives
The first term is at most . When , the message is the known value , so its remaining entropy is zero. When and the output is fixed, at most messages remain possible. Entropy on at most values is at most , again by divergence from a uniform distribution on those values. Averaging proves Fano's inequality, including error probability zero. Conditional laws on zero-probability events can be omitted.
Fano's inequality now combines with the memoryless structure of the channel.
Proof
(The memoryless BSC rate bound)
For the memoryless BSC, the conditional noises are independent once the entire input is fixed. Therefore . Because the encoder is deterministic and the channel depends on the message only through its encoded word, also . By repeated chain rule and conditioning reducing entropy,
It follows that . This step allows correlated inputs, as actual codewords generally have. Finally,
We used and . Rearrangement gives the finite-block bound. Dividing by for sufficiently late terms in a sequence with proves the rate conclusion. No assumption that encoded coordinates are independent has entered this argument.
Proof X-ray
Where uniformity, memorylessness and Fano enter
Uniformity of is used once, in . Memorylessness is used once, in : given the codeword, the noise bits are independent and each contributes . Determinism of the encoder lets this value hold conditional on rather than only on .
The key move is to bound by subadditivity instead of computing it. Subadditivity holds for every joint law, so the codeword coordinates may be correlated in any way; only the bound for a binary output enters. Fano's inequality supplies the remaining slack , and the argument closes by rearranging one linear inequality in . The counterexample under common mistakes shows that, for correlated noise, it is the memoryless step that fails, not the subadditivity step.
Processing an observation cannot create information
There is a related structural fact that explains why choosing a clever decoder cannot evade an information bound. Suppose have a finite joint law with the property that, conditional on , the variable is independent of . In other words, after is known, the rule producing has no further access to . This is the Markov condition . Deterministic processing is an important special case, but randomized processing using fresh independent randomness is also covered.
Theorem 3.3.7
(Data-processing inequality)
If is a Markov chain of random variables with finite ranges, then .
Proof
(Two expansions of one chain rule)
The chain rule for mutual information, obtained by expanding the conditional entropies, gives the same quantity in two ways:
Conditional independence makes the first conditional mutual information zero. Nonnegativity of the second then proves the data-processing inequality . Both ingredients matter: merely saying that is computed later does not guarantee the Markov condition if its computation also sees additional information about .
For a concrete comparison, take a BEC of erasure probability one half and replace every erasure with a fresh fair guessed bit. The resulting binary output differs from the input with probability one quarter: an error requires an erasure and then an incorrect guess. Each channel use is now a BSC with crossover probability one quarter if all guesses and erasures are independent across uses. With a uniform input, the original observation retains one half bit, while the guessed-bit observation retains approximately bit. The loss occurs because the replacement conceals which observations were erasures. Keeping the erasure flag would preserve that additional information.
Data processing is not a statement that decoding cannot reduce an error probability. A code constrains the possible input blocks, and a decoder can use those constraints to turn a noisy block into an accurate message estimate. The inequality says that this final estimate cannot contain more mutual information about the message than the entire observed block already contained. Fano's inequality connects the quality of that estimate to the information that must have been present. The two arguments thus complement one another: one controls the observation, and the other controls what successful decoding would require.
Worked examples
Worked example 3.3.8
(A random output can contain no information)
Let be a uniform bit and take a BSC with . Then is also uniform, but each output is independent of the input: all four input-output pairs have probability . Thus , and . If and the receiver guesses , the error probability is , consistent with Fano's bound .
Worked example 3.3.9
(Erasure versus substitution at the same event probability)
Take a uniform input and event probability . The BEC retains bit per use. The BSC retains , approximately bit per use. Their event probabilities are equal, but the erasure explicitly identifies the damaged observation. To check the BSC number, . Replacing erasures by guessed bits discards useful information; it does not preserve the channel model.
Worked example 3.3.10
(A finite-block obstruction)
Suppose a length- BSC code with has equally likely messages. Then
Hence . The inequality rules out a claimed error probability of at that block length and message count, regardless of the decoder's ingenuity. The approximate decimal is only a display aid; the exact entropy expression is the bound. This converse alone neither constructs a better code nor determines the smallest possible error.
The rate bound can also be written when , where . At a fixed positive rate , it gives , without assuming an error limit exists. For , this lower bound alone does not force the error to approach one; such a general conclusion requires a stronger converse, which has not been proved here. When , this particular bound does force .
Common mistakes
Common mistake
(Output entropy is not transmitted information)
Output uncertainty and transmitted information must be distinguished. A fair random output independent of the message maximizes binary output entropy while conveying nothing. At the other extreme, a constant input has zero entropy and therefore zero mutual information even through a noiseless channel: the channel could carry information, but that chosen input distribution does not use it.
Common mistake
(Memoryless does not mean independent codeword coordinates)
Memorylessness is a conditional statement about outputs given inputs. It does not assert that the coordinates of a chosen codeword are independent or that the unconditional outputs are independent. The entropy subadditivity step deliberately avoids that assumption. Using without proving independence would invalidate the converse for many codes.
Counterexample mode
Independent noise at each coordinate is a real hypothesis
Suppose one fair bit is added to every coordinate, so for all . Each individual coordinate looks like a BSC with crossover probability , yet the block channel is not memoryless. Encode one data bit as . From the output the receiver computes with no error. Here , whereas the memoryless step would give , a false conclusion. Likewise, encoding data bits as gives rate with zero error, contradicting the memoryless zero-rate bound. The joint noise law matters, not just its one-coordinate marginals.
Summary
Mutual information measures the dependence retained by a channel, rather than the randomness of its output. Fano's inequality turns a decoder's error probability into a bound on residual message uncertainty. Memoryless binary noise bounds the information available over a block, producing a necessary rate condition for vanishing average error. The argument leaves achievability, efficient construction and stronger converses as separate questions.
Exercises
Quick check
(For a noiseless binary channel with input-one probability , compute mutual information and identify the maximizing input.)
Compare with when the output equals the input.
Solution · Answer
Here , so and . Its maximum is one bit, attained at . The endpoint inputs are constant and give zero.
Quick check
(A uniform input passes through a BEC with erasure probability . Compute and .)
Condition separately on an erasure and on a received bit.
Solution · Answer
On an erasure the uncertainty is one bit, and otherwise it is zero. Thus and bit.
Quick check
(Let be uniform on four messages. A deterministic decoder has error probability . What upper bound does Fano give on ? Why is the value not just ?)
Apply Fano with and .
Solution
The upper bound is , approximately bits. The error indicator only says whether the guess is wrong; when it is wrong there can still be three possible messages. The second term accounts for that uncertainty. Fano gives an upper bound, not necessarily an equality.
Quick check
(For a sequence of memoryless BSC codes of fixed positive rate , derive an asymptotic positive lower bound on average error from the finite-block inequality. Does it prove error tends to one?)
Substitute into the finite-block inequality.
Solution
Substituting gives . Thus . The bound is strictly below one for , so it does not prove convergence to one. When and rate stays positive, this particular bound does force error to one; the general above-capacity case requires additional work for that conclusion.
For the broader channel-coding setting, see Venkatesan Guruswami's introductory coding-theory notes. The present finite-alphabet derivations make the model and the limited converse proved here explicit.