What gets through a noisy channel?
A short source code reduces the expected number of bits before transmission. It does not by itself stop a channel from changing those bits. Here we study an explicit noisy channel, calculate what one use reveals about its input, and compare that calculation with a small error-correcting code.
Definition 7.1.1
(Binary symmetric channel)
Let be the input, a noise bit independent of , and , where is addition modulo two. Suppose , . This is a binary symmetric channel: each input bit is flipped with probability , regardless of its value. Put ; the input distribution is a separate choice from the channel parameter .
The quantities we compute are entropies of finite random variables.
Definition 7.1.2
(Binary entropy and mutual information)
For define binary entropy
with by continuity. For finite random variables, and . All logarithms here are base two, so these quantities are in bits. A conditional distribution for an input value of zero probability does not contribute to the sum.
A one-use calculation
Theorem 7.1.3
(Maximizing mutual information for one use)
For the channel above,
The upper bound is attained by , for every .
Proof
(Output law, conditional entropy and the peak of )
The output is one precisely when or . Independence therefore gives
Thus is the first entropy in the formula. Conditional on either input value, the output distribution is a possibly relabeled distribution, so . For , : increases up to and decreases afterward. With continuous endpoint values, . Choosing makes the output uniform, attaining the bound.
Proof X-ray
The channel and input have different roles
Independence of and is used twice: to compute the output law, and to see that the conditional output law given is the noise law, possibly relabeled. The key move is that does not depend on , so maximizing over inputs reduces to maximizing the single entropy . The argument closes because equals at whatever is; at every gives , and the bound is attained trivially. A uniform output alone does not show that the output reveals the input: the conditional uncertainty must also be subtracted.
The maximum is a one-use mutual-information result. A theorem relating this value to reliable communication rates over long blocks requires a coding theorem and its hypotheses; that theorem is not proved here. Nor does one observed bit have a fractional number of possible values: mutual information is an average property of a joint distribution.
Endpoints and a numerical example
If , ; if , . Both have maximum one bit of mutual information per use: a known deterministic flip is reversible. If , the output is independent of the input and for every . Thus the graph of is symmetric about ; it is not a measure that decreases monotonically all the way from to .
Worked example 7.1.4
(A quarter of bits flip)
For and a fair input, the output is fair and bits, since . With , the input is constant: , so . Output randomness by itself is not information about a constant input.
Worked example 7.1.5
(The endpoint : every bit flips)
Here , so and . Given , the output is certain, so . Hence , which is one bit at , in agreement with . The receiver simply complements each bit.
Common mistake
(Information is not monotone in the flip probability)
It is tempting to read as a measure of how bad the channel is. But , so gives the same maximum bits as . The worst case is , not .
A three-use repetition code
Send a message bit three times as and decode by majority vote.
Proposition 7.1.6
(Error probability of majority decoding)
Assume the three noise bits are mutually independent, their joint vector is independent of , and each has flip probability . Then majority decoding of the three-fold repetition code errs with probability
Proof
(Count the noise patterns of weight two or three)
The decoded bit is wrong exactly when at least two of the three bits flip. By independence, each noise pattern of weight has probability , whatever is. The three patterns of weight two and the one pattern of weight three give .
For this is , below the single-use error probability . For it is strictly smaller, because ; at both are . When , the same majority rule can be worse; if the channel parameter is known, complementing received bits first changes the effective flip probability to .
Common mistake
(Comparing error probabilities at different rates)
The repetition code uses three channel uses per message bit. Its lower error probability is therefore not a comparison at equal transmission rate with sending each bit once, and it says nothing by itself about how close a code can come to the one-use value .
Worked example 7.1.7
(Majority decoding when )
Without correction for the known parameter, the error probability is , worse than the single-use error . Complementing every received bit first gives a channel with flip probability , and majority decoding then errs with probability .
Counterexample mode
Identical marginals do not make independent errors
Suppose all three noise bits equal one common Bernoulli variable with flip probability . Each individual bit still flips with probability , but either all three flip or none do. Majority decoding then has error probability , which can differ from : for it is instead of . The product calculation used independence across uses.
Exercises
Quick check
(For and any , compute and .)
Solution · Answer
The output is uniform: . Both and are one bit, so .
Quick check
(For and , write an exact expression for .)
Solution · Answer
The output-one probability is . Hence .
Quick check
(Compute the three-use repetition error probability at and compare it with .)
Solution · Answer
It is .
Quick check
(Why can have positive information even though every transmitted bit is flipped?)
Solution · Answer
The receiver can invert the known deterministic flip. A fair input and its complemented output determine each other, giving one bit of mutual information per use.
Further reading
MIT OpenCourseWare, Information Theory Lecture 8 discusses the binary symmetric channel and the relation between mutual information and channel coding. The latter relation goes beyond the one-use proof above.