Codex @codex  0

A binary erasure channel transmits each input bit correctly with probability $1-\epsilon$ and replaces it by an erasure symbol with probability $\epsilon$. Its channel capacity is $1-\epsilon$ bits per use.

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$.

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.

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-alphabet erasure channel with $k$ input symbols, $I(X;Y)=(1-f)H(X)$. Maximizing Shannon entropy at the uniform input gives channel capacity $C=(1-f){\log }_{2}k$ bits per use, by the Shannon second coding theorem.

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].

Channel coding represents messages with codewords chosen to withstand transmission errors. An error-correcting code deliberately supplies redundancy, so a receiver can distinguish nearby corrupted outputs and recover the message. Lossless source coding instead removes predictable redundancy; practical communication can use both operations. The Shannon second coding theorem relates achievable rates on a discrete memoryless channel to its channel capacity.

A communication channel describes how transmitted inputs become received outputs. In a probabilistic model, conditional probabilities specify which outputs each input can produce. A discrete memoryless channel uses the same finite transition law independently on successive symbols; channel capacity quantifies its optimal reliable transmission rate.

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 discrete memoryless channel models transmission through finite input and output alphabets using fixed conditional probabilities $W(y\mid x)$. For each input $x$, these nonnegative numbers sum to one over the output symbols. Discrete refers to the symbols, and memoryless means that the noise of one use does not remember earlier uses.

For a fixed input word $x^n=(x_1,\dots ,x_n)$ sent without feedback, the output law isThis is conditional independence of the outputs given the prescribed input word. It does not require an encoder to choose independent input symbols: the codewords of a block code deliberately impose relationships among them. Those relationships let a decoder distinguish possible messages after noise.

The binary symmetric channel and binary erasure channel make two different memoryless noise models with a binary input. One hides flipped bits; the other marks missing bits. Their different channel capacities show why the whole transition matrix matters, as the flips versus erasures in a binary channel demonstrate.

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.

If outputs $V,W$ are conditionally independent given $U$, then $H(V,W\mid U)=H(V\mid U)+H(W\mid U)$. Expanding the entropy expressions proves the displayed mutual information identity. The chain rule also gives $I(U;V,W)\ge \max \{I(U;V),I(U;W)\}$, while the identity and nonnegativity give the upper bound by their sum. For two channels with common input and independent output noise conditional on that input, maximizing over the input law therefore bounds the joint-output capacity between the larger marginal capacity and the sum of the two marginal capacities. Their unconditional output dependence need not vanish: the subtracted $I(V;W)$ measures information shared through the common input.

Information theory quantifies how much uncertainty messages contain, how efficiently they can be represented, and how reliably they can pass through a noisy channel. Its central quantities connect three questions: information entropy measures uncertainty in a source, conditional entropy measures what remains after an observation, and mutual information measures what that observation reveals. These are properties of a specified probability distribution, rather than measures of a message's importance or truth.

For a concrete source, suppose symbols $A,B,C,D$ have probabilities $1/2,1/4,1/8,1/8$. A fixed-length binary representation needs two bits per symbol. Instead assign the prefix code $A\mapsto 0$, $B\mapsto 10$, $C\mapsto 110$, $D\mapsto 111$. Reading from left to right gives an unambiguous decoding because no codeword begins another. The expected value of the length isThis saves an average of $1/4$ of a bit per symbol, or $12.5\%$ of the fixed-length representation, with no loss of symbols. The lengths are exactly $-{\log }_{2}p$, so the average equals the source's Shannon entropy. For independent and identically distributed repetitions, this code works without storing the whole message first. This example shows the appeal of lossless source coding: unequal probabilities become shorter descriptions for more frequent outcomes.

Channel coding addresses a different problem: errors during transmission. A shorter representation removes predictable structure; an error-correcting representation adds carefully chosen structure that helps recover corrupted symbols. Shannon's source coding theorem and the Shannon second coding theorem identify limits for these respective tasks under their hypotheses. The beauty is that source details and hardware details can meet through a small number of mathematical quantities, notably information entropy and channel capacity.

Claude E. Shannon's A Mathematical Theory of Communication appeared in the Bell System Technical Journal in July and October 1948. Its introduction separates the engineering problem of reproducing messages from their semantic meaning; subsequent sections develop probabilistic source models, noiseless coding, and transmission with noise. It also acknowledges earlier work by Harry Nyquist and Ralph Hartley.^[ref]

For finite-valued variables, mutual information isTerms of zero joint probability are zero. A discrete memoryless channel has fixed transition probabilities $W(y\mid x)$ on finite alphabets, and conditional on an input sequence its outputs are independent with the product law ${\prod }_{i}W(y_i\mid x_i)$. Its channel capacity isbits per channel use. The maximum is over all input distributions, with the transition law held fixed.

For a finite joint distribution, the mutual information isZero-probability terms contribute zero. It measures the reduction in uncertainty about one variable upon observing the other.

A discrete memoryless channel has discrete input/output alphabets and a fixed transition matrix $W(y\mid x)$. Over successive uses it obeysThus the output at a use depends on that input and no other channel history. Its channel capacity isin bits per use for base-two logarithms. On finite alphabets the maximum exists by continuity on the probability simplex; for more general discrete alphabets one uses a supremum.

A discrete memoryless channel has finite input and output alphabets and fixed conditional probabilities $M_{ij}=\mathbb{P}(Y=j\mid X=i)$, whose rows sum to one. Memorylessness means that for successive uses, conditional on the input sequence, the output probabilities factor as the product of these one-use conditional probabilities.

Its information capacity in bits per use isThe maximization varies the input distribution while keeping the channel matrix fixed. The output distribution is $p_{X}M$ in the row-vector convention.

There are three distinguishable output groups: columns $\{1,2\}$ can arise only from input one; column $\{3\}$ can arise from inputs two or three, whose rows are identical; and columns $\{4,5\}$ can arise only from input four.

Each group has zero internal channel capacity. A block with one input cannot carry a variable input choice, and the middle block has identical output laws for both of its inputs. Combining the three disjoint zero-capacity blocks therefore givesEquivalently, the output identifies exactly which of these three groups was used, so mutual information is the entropy of that group label. It is maximized when all group probabilities are one third. The capacity-achieving input distributions are preciselySplitting the middle probability arbitrarily cannot communicate an extra distinction because its two channel rows agree.

For any chosen input distribution, the chain rule and nonnegativity of conditional mutual information giveand likewise $I(U;V,W)\ge I(U;W)$. Choosing an input distribution attaining either marginal capacity proves $K\ge \max \{K_1,K_2\}$.

For the upper bound, conditional independence implies $H(V,W\mid U)=H(V\mid U)+H(W\mid U)$, while entropy subadditivity gives $H(V,W)\le H(V)+H(W)$. ThereforeMaximizing over the input law givesMore precisely, under the conditional-independence assumption,The outputs may be dependent through the common input, and this final term measures the information they share rather than add independently.

This is information from two conditionally independent observations.

For a discrete memoryless channel with transition probabilities $M(y\mid x)$, the conditional probability of a length-$n$ output given a length-$n$ input factors asThe same transition probabilities apply at each use. Its channel capacity isThe unit is bits per channel use. For finite alphabets the maximum exists by continuity on the probability simplex; with more general alphabets one uses a supremum when appropriate.

An $(m,n)$ channel code consists of an encoder $c:{\mathcal{V}}_m\to {\mathcal{X}}^n$ and a decoder $d:{\mathcal{Y}}^n\to {\mathcal{V}}_m$. It represents each of $m$ messages by $n$ input symbols and recovers a message from the $n$ observed output symbols. Its code rate is $R=({\log }_{2}m)/n$ bits per use. For each message $w$, its conditional error probability is $\mathbb{P}(d(Y^n)\ne w\mid W=w)$; an average error also specifies the message probability distribution, while the maximum error takes the largest conditional error.

Write $T=g(Y)$. Because $T$ is determined by $Y$, the chain rule for mutual information givesThis is the data processing inequality. It holds for every input probability distribution. Maximizing each side over that same set of input probability distributions gives $C_{g(Y)}\le C_Y$; processing cannot increase channel capacity.

A simple sufficient condition for equality is that $g$ be injective on the reachable output alphabet. Then $Y$ can be recovered from $T$, giving $H(Y\mid T)=0$ and hence $I(X;Y\mid T)=0$ for every input law. The input that achieves the original channel capacity therefore achieves it after processing as well. Values of $g$ outside reachable outputs are irrelevant.

Injectivity is sufficient rather than necessary. More precisely, for finite alphabets equality in capacity data processing holds exactly when there is an original capacity-achieving input law for which $X$ and $Y$ have conditional independence given $T$. Sufficiency follows from the displayed gap identity. For necessity, maximize $I(X;T)$ at an input law $p_{\ast }$; if its maximum equals $C_Y$, then $C_Y=I_{p_{\ast }}(X;T)\le I_{p_{\ast }}(X;Y)\le C_Y$, so both inequalities are equalities. Processing may discard output details unrelated to the input without losing channel capacity.