Channel capacity ($C={\max }_{P_X}I(X;Y)$)

Channel capacity is the best reliable information rate available through a specified communication channel. For a discrete memoryless channel with finite input and output alphabets, fixed transition probabilities $W(y\mid x)$, and no input-cost constraint, it isin bits per channel use, when the mutual information uses base-two logarithms. The maximization varies the input probability distribution, while keeping the communication channel fixed. A large input alphabet or a large output information entropy alone does not determine how much information gets through: the receiver needs information about the input, rather than merely unpredictable output.

The operational meaning comes from the Shannon second coding theorem. A block code represents one of $M$ possible messages by a word of length $n$, giving a rate ${\log }_{2}M/n$ bits per use. Take the message label from the uniform distribution on a finite set of those $M$ choices when measuring average decoding-error probability. For every fixed rate $R<C$, there are sequences of such block codes whose decoding-error probability tends to zero as $n$ grows; a rate above $C$ cannot have vanishing decoding-error probability. This is an asymptotic limit, rather than a promise that an arbitrary finite block code at a rate below $C$ works well. See MIT 18.310, Shannon's Noisy Coding Theorem, sections 1–2.

For a binary symmetric channel with crossover probability $p=0.1$, the binary symmetric channel capacity is approximately $0.53100441$ bits per use. Thus a binary code rate $R=1/2$ lies below the limit, while $R=3/4$ lies above it. At $R=1/2$, two transmitted symbols represent one message bit on average; the redundancy helps distinguish messages after noise. This does not split individual physical symbols into fractional pieces.

The result is useful because it separates two tasks. Computing channel capacity establishes the target imposed by the transition probabilities; constructing an effective block code attempts to approach that target with acceptable delay and decoding effort. The surprise is that reliability can improve indefinitely without forcing every positive rate to disappear. In his 1948 paper, Shannon defines noisy channel capacity in section 12 and develops its operational significance in section 13, Theorem 11. His original formulation uses information per unit time; the fixed-duration channel-use convention here expresses the same rate question per symbol. ^[ref].

Pass the output of a discrete memoryless channel of channel capacity $C$ through an independent finite-alphabet erasure channel with erasure probability $p$. Its capacity becomes $(1-p)C$.

To prove it, let $X$ be the original input, $Y$ the original output, $E$ the erasure indicator, and $Z$ the final output. Since the erasure marker is distinguishable, $E$ is determined by $Z$. It is independent of $X,Y$, so the chain rule for mutual information gives $I(X;Z)=I(X;E,Z)=I(X;Z\mid E)=(1-p)I(X;Y)$. Maximization over the same input distributions proves the formula. For $p<1$ the maximizing distributions are exactly the original channel's maximizers. For $p=1$, every input distribution attains the zero capacity. Input-dependent erasure need not satisfy this scaling identity.

Suppose one row of a finite discrete memoryless channel is a convex combination of other rows: $W(\cdot \mid x_0)={\sum }_j{\alpha }_{j}W(\cdot \mid x_j)$. Deleting input $x_0$ leaves the channel capacity unchanged. Given any input law with mass $t$ on $x_0$, move that mass to the other symbols in proportions ${\alpha }_j$. The output law stays the same. By the concavity of information entropy, $H(W(\cdot \mid x_0))\ge {\sum }_j{\alpha }_{j}H(W(\cdot \mid x_j))$, so this replacement cannot increase conditional entropy $H(Y\mid X)$ and cannot decrease mutual information. Taking maxima proves the claim; the smaller channel is also trivially a restriction of the original one. If the entropy inequality is strict, every positive use of the redundant row is strictly suboptimal compared with its redistribution.

Combine finitely many discrete memoryless channels with disjoint input alphabets and disjoint output alphabets into a block-diagonal channel. The block label $B$ is determined by both input and output. If it has law $\alpha$, the mutual information is at most $H(\alpha )+{\sum }_i{\alpha }_i{C}_i$, attained by using each block's capacity-achieving conditional input law. Put $S={\sum }_i{2}^{C_i}$ and $r_i=2^{C_i}/S$. The expression equals ${\log }_{2}S-d(\alpha ,r)$, so Gibbs inequality proves the displayed capacity, attained for block probabilities ${\alpha }_i=r_i$. Even blocks of capacity zero contribute distinguishable block choices; three disjoint zero-capacity blocks give capacity ${\log }_{2}3$.

For a finite discrete memoryless channel and a deterministic output map $T=g(Y)$, the data processing inequality gives $C_T\le C_Y$. Equality holds exactly when an original capacity-achieving input law satisfies $I(X;Y\mid T)=0$. Sufficiency follows from the gap identity $I(X;Y)=I(X;T)+I(X;Y\mid T)$. For necessity, take an input law maximizing $I(X;T)$. If this maximum is $C_Y$, both inequalities $I(X;T)\le I(X;Y)\le C_Y$ are equalities at that law. Injectivity of $g$ on reachable outputs is a sufficient condition, since $T$ then determines $Y$; it is unnecessary if the discarded distinctions convey no further information about $X$ at some maximizing input law.

For a discrete memoryless channel with $m$ output symbols, suppose every row of the transition matrix is a permutation of every other row and all column sums agree. Such a communication channel hasThe row Shannon entropy is the same for every input, so $H(Y\mid X)$ has that fixed value for every input probability distribution. The remaining term $H(Y)$ is at most ${\log }_{2}m$ by maximum entropy on a finite alphabet.

A uniform input attains the bound. If there are $\ell$ input symbols, the total of all transition probabilities in the matrix is $\ell$; equal column sums must therefore each be $\ell /m$. Multiplication by the uniform input mass $1/\ell$ gives output mass $1/m$ in each column. Hence $H(Y)={\log }_{2}m$, which proves the displayed formula. The cyclic ternary channel capacity, binary symmetric channel capacity, and ternary symmetric channel capacity are concrete applications of this symmetry calculation.

A discrete memoryless channel on the additive group $\mathbb{Z}/3\mathbb{Z}$ maps $x$ to $x$ with probability $1-q$ and to $x+1$ with probability $q$. Every input gives the same conditional entropy $h_2(q)$, whereas the output Shannon entropy is at most ${\log }_{2}3$. A uniform input produces a uniform output since every column of the transition matrix sums to one. Hence the channel capacity is ${\log }_{2}3-h_2(q)$ bits per use. This cyclic-error channel differs from a channel distributing its error probability equally over both other output symbols.

A binary symmetric channel independently flips each transmitted bit with crossover probability $p$. Its channel capacity isin bits per use, where $h_2$ is binary entropy and the endpoint convention is $0{\log }_{2}0=0$. Knowing the input leaves just the uncertainty of the flip, so $H(Y\mid X)=h_2(p)$ for every input probability distribution. Since the output is a bit, $H(Y)\le 1$, and thus $I(X;Y)\le 1-h_2(p)$. A fair input produces a fair output and reaches the bound. This is the two-symbol case of weakly symmetric channel capacity; Eytan Modiano, MIT 16.36, Channel Capacity and Coding, slides 4–5 gives this calculation.

For crossover probabilities $p=0.01,0.1,0.25$, the resulting channel capacities are approximately $0.91920686$, $0.53100441$, and $0.18872188$ bits per use. At $p=0$, the communication channel is noiseless; at $p=1/2$, the output is independent of the input and the capacity is zero. At $p=1$, every bit is inverted, a known reversible rule, and capacity is one again. More generally $C(p)=C(1-p)$, because inverting every received bit exchanges the two crossover probabilities. The existing mutual information figure shows this full symmetric curve.

An uncoded transmission illustrates why the raw bit-error probability is not itself channel capacity. At $p=0.1$, transmitting 100 uncoded bits succeeds on all of them with probability $0.9^{100}\approx 0.00002656$. The probability of at least one error is therefore approximately $0.99997344$. A suitable block code changes which received words count as recoverable evidence of a message; simply repeating uncoded transmission at rate one does not obtain the reliability promised at rates below $C$.

Let $q=\mathrm{Pr}(X=1)$ for the input bit of a binary symmetric channel with crossover probability $p$. The law of total probability givesConsequently its mutual information isHere $p$ specifies the noise and $q$ specifies the input bias; they are different choices. At $p=0.1$ and $q=0.2$, the output has $\mathrm{Pr}(Y=1)=0.26$, giving $H(Y)\approx 0.82674637$ and $I(X;Y)\approx 0.35775078$ bits. With the same noise and the fair input $q=1/2$, the output becomes fair and $I(X;Y)\approx 0.53100441$ bits, attaining binary symmetric channel capacity.

For $p\ne 1/2$, binary entropy reaches one only at output mass $1/2$, and the equation $p+(1-2p)q=1/2$ forces $q=1/2$. Thus the maximizing input is unique in those cases. For $p=1/2$, every input produces the same fair output and zero mutual information, so every input bias is optimal and none transmits information. A fixed input $q=0$ or $q=1$ also carries zero mutual information for every $p$: noise can make its output unpredictable without creating an unknown message to recover.

A binary erasure channel marks its failed transmissions with a special output symbol, whereas a binary symmetric channel changes a bit without announcing whether it changed. At the same nominal failure probability $p=0.1$, the two communication channels therefore leave different uncertainty. With a fair input, an unerased output determines the input exactly, while the erasure flag leaves one bit of conditional entropy. Thus $H(X\mid Y)=p$ and $I(X;Y)=1-p=0.9$ for the binary erasure channel. This is the binary case of capacity of a finite-alphabet erasure channel.

For the binary symmetric channel at $p=0.1$, neither possible received symbol rules out either input, and $H(X\mid Y)=h_2(0.1)\approx 0.46899559$. Its channel capacity is only $1-h_2(0.1)\approx 0.53100441$. A receiver benefits from knowing where information was lost, even when the fraction of affected transmissions is the same.

This comparison concerns the specified transition probabilities, rather than a general ordering of every error mechanism. In particular, at $p=1$, an erasure flag conveys no input information, while deterministic inversion still conveys a full bit. Reporting only an error percentage loses the distinction between hidden corruption, announced loss, and a predictable reversible transformation.

For diagonal transition probability $1-2\alpha$ and each off-diagonal probability $\alpha$,with $0\log 0=0$.