Channels and capacity

A binary symmetric channel flips each bit with probability 0.15. You might guess that it can carry 0.85 bits per use, because 85 bits in 100 arrive intact. The correct value is 0.390 bits per use [S:36:163]. Noise costs more than the raw error rate suggests.

How fast can you send a message through noise? The answer is the channel capacity, the largest rate at which the channel can carry information with vanishing error [S:36:162]. A code rate is the number of message bits a code sends per use of the channel: a code that sends k message bits in n uses has rate k/n. The capacity is the largest rate the channel can support, and it belongs to the channel rather than to any code [S:36:164]. A rate of 0.390 bits per use means that a thousand uses carry at most about 390 message bits, which is less than half of what a perfect channel would carry. !A binary symmetric channel. A sent bit arrives unchanged with probability 0.85 and flipped with probability 0.15, whichever bit was sent. The receiver sees the output and not the arrow, so every received bit is evidence rather than a fact. That ambiguity is what the capacity subtracts. Status: schematic.

Capacity. The capacity is the largest mutual information between the input and the output, taken over every possible distribution on the input [S:36:162]. For a binary symmetric channel with flip probability f, the best input is a fair coin. The capacity is $1-H(f)$, where H is the entropy of a coin with heads probability f, using the same H as Section 16.1. !Capacity against flip probability. The capacity 1 - H(f) falls from 1 bit at f = 0 to 0 at f = 0.5; at f = 0.15 it is 0.390 bits per use. The straight line is the naive guess 1 - f, which gives 0.85 at the same point. The gap is the price of not knowing which bits were flipped, and it is paid on every use of the channel. Status: synthetic.

$$\text{capacity}=1-H(f)$$ !Capacity as a threshold on rates. At f = 0.15 the capacity is 0.390 bits per use, and no code communicates reliably above it. The repetition code sends one message bit in three uses, a rate of 0.333, below the threshold; an uncoded bit has rate 1, far above it. A rate below the threshold is achievable, though the theorem does not promise that this particular code is the one that achieves it. Status: schematic.

The equation says that you start with one bit per use and subtract the uncertainty that the noise adds. At f = 0 the channel is perfect and the capacity is 1 bit. At f = 0.5 the output is independent of the input, and the capacity is 0.

The units are bits per channel use. One use is one transmission of a single bit, so a capacity of 0.390 says that every use carries about four tenths of a bit of genuine message. A code that reaches that rate spends the remaining room on redundancy, the extra bits that let the receiver correct the noise.

The naive guess describes a different channel: one that erases each bit with probability 0.15 and tells the receiver which positions are gone. That channel's capacity is exactly $1-0.15=0.85$ bits per use. The binary symmetric channel does not tell the receiver which bits were flipped: it sees a bit and must decide whether to trust it. The uncertainty about whether a flip occurred is $H(f)$, not f, and that entropy is the quantity the capacity subtracts.

The coding theorem. The noisy-channel coding theorem states both directions. Reliable communication at any rate beyond the capacity is impossible, and reliable communication at every rate up to capacity is possible [S:36:28]. For any error target, a long enough block code and decoder exist whose error probability is below that target [S:36:164]. The theorem is an existence statement, not a recipe for building the code.

Worked example. Let f = 0.15. The entropy of the noise is $H(0.15)=0.610$ bits, so the capacity is $1-0.610=0.390$ bits per use [S:36:163]. Now try a repetition code: send each bit three times and take the majority. Its rate is one message bit per three uses, or 0.333, which is below the capacity.

It fails when two or three of the three copies flip. Three patterns have exactly two flips, because the unflipped copy can be first, second or third, so the probability is $3f^2(1-f)+f^3=3f^2-2f^3$.

At f = 0.15 the repetition code has error probability 0.0608, against 0.15 for an uncoded bit. It cuts the error by a factor of about 2.47, but it cuts the rate by a factor of three. The rate 0.333 sits below the capacity 0.390, so the theorem guarantees that a better code exists.

The gap between the naive 0.85 and the true 0.390 is the price of not knowing which bits are wrong. A receiver that knows which positions are missing pays only for the missing bits, and the erasure channel above charges exactly that. A receiver that sees a flipped bit cannot tell it from a correct one, so it must hedge on every bit it receives.

Capacity is a promise about the limit of long blocks. It needs long blocks, a good code and a decoder that can keep up, and it says nothing about delay or cost. It also assumes that the channel model is correct; a real channel whose noise depends on earlier bits or changes over time can sit far from the number this formula gives. The promise is about what is possible in the limit, not about what is easy in a particular machine. For a file transfer the delay is invisible, but for a live call it is not.

The formal statement. A discrete memoryless channel has an input alphabet, an output alphabet and a transition probability for each pair. Its capacity is

$$C=\underset{P_X}{\max }I(X;Y),$$

where the maximum runs over every distribution on the input [S:36:162]. The noisy-channel coding theorem has two directions. For every rate below C and every error target there is a long enough block code whose maximal block error is below that target. For every rate above C the error probability tends to one [S:34:447].

The derivation for the binary symmetric channel. Let the input be a bit and let the channel flip it with probability f. Condition on the input: the output is either the input or its complement, so the conditional entropy is the entropy of a two-outcome distribution with probabilities f and $1-f$. That entropy is $H(f)$, and it does not depend on the input distribution. Therefore

$$I(X;Y)=H(Y)-H(f)\le 1-H(f).$$

The equation says that you start with at most one bit of output entropy and subtract the uncertainty the noise injects. Equality needs the output to be uniform, and a fair input bit makes it uniform. So the maximum is $1-H(f)$ [S:36:163].

The edge case. A rate below capacity does not mean a small error at a short blocklength. The repetition code of L1 has rate one third, below the capacity 0.390, and still errs with probability 0.0608 on blocks of three. The theorem promises a sequence of codes whose blocklength grows, not a promise about any particular short code [S:34:447]. L1's sentence that a better code exists is true, and the word "exists" is doing more work than it appears to do.

What L1 hid, and why that was safe. L1 wrote the capacity as one minus the entropy of the noise, which is a formula for the symmetric channel. The definition is a maximum over input distributions, and the best input is not always uniform: for a Z channel the optimal input favours the symbol that noise cannot damage [S:36:163]. L1's channel was symmetric, so the uniform input was optimal and the maximisation could stay invisible.

L1 also treated capacity as a property of the channel alone. The maximum is over inputs, so it is a property of the channel and of the allowed inputs together. Constraints on the input, such as an average power limit, change the answer.

Where the analogy breaks. "Capacity is the speed limit" suggests a limit that applies to every journey. This limit applies to a sequence of journeys whose length grows without bound. A driver below the limit can still crash on a short road, and the repetition code is that crash. The limit is real, and it is asymptotic.

Original sources. Shannon introduces the equivocation and rejects the naive subtraction of the error rate, because the receiver does not know which positions are wrong [S:156:20]. He then defines capacity as the maximum rate and states the fundamental theorem for a discrete channel with noise [S:156:22]. That definition turns a question about noise into a maximisation over input distributions. MacKay writes capacity as the maximum mutual information and derives the binary symmetric formula [S:36:162].

An open question. The asymptotic rate is settled. The exact finite-blocklength limit is not: computing the largest code size at a given blocklength and error probability is doubly exponential by exhaustive search, so the field sandwiches the value between bounds [S:34:464]. The normal approximation with the channel dispersion is close but not exact [S:34:447]. Matching upper and lower bounds across a family of channels, or a proof that the remaining term has the predicted size, would settle it.

A frontier result. Polar codes and LDPC codes reach about ninety percent of the fundamental limit at control-plane blocklengths and about ninety-five percent at data-stream blocklengths [S:34:465]. They depend on the theorem twice: capacity is the target, and performance is reported as a fraction of it. The dispersion term is what makes that fraction meaningful at a stated blocklength.

The converse in one line. Fano's inequality bounds the conditional entropy of the input given the output by a function of the block error probability. Feed that bound into the mutual information and let the error vanish; the rate cannot exceed capacity [S:34:448]. The achievability direction needs a random code and a typical-set decoder, which this layer does not reproduce.

What to read next. Read Shannon Sections 12 and 13 for the definition and the theorem [S:156:20]. Read MacKay Chapter 9 for the binary symmetric channel and the proof sketch [S:36:162]. Read Polyanskiy Chapter 22 for the strong converse, the dispersion and the finite-blocklength bounds [S:34:447]. Read the last one with the first: Shannon gives the limit, and the modern chapter gives the price of approaching it in a finite block.