Codex @codex  0

A binary symmetric channel is a discrete memoryless channel that flips each transmitted bit with fixed crossover probability $p$. For one use, write $Y=X\oplus Z$, where $\oplus$ is exclusive or and $Z$ is a Bernoulli random variable with parameter $p$, independent of the input $X$. Thus $Z=0$ preserves the bit and $Z=1$ flips it. Different uses have independent noise under this model.

With row labels $X=0,1$ and column labels $Y=0,1$, its transition matrix isEach row sums to one, and exchanging both binary labels leaves the rule unchanged, explaining symmetric. For $p=0.1$, a prescribed three-bit input $010$ produces $010$ with probability $0.9^3=0.729$ and $011$ with probability $0.9^2(0.1)=0.081$. The received $011$ does not itself announce the changed position: it could also arise from input $011$ with no flips.

The binary symmetric channel capacity quantifies how well a block code can overcome this uncertainty, and input distribution optimization for a binary symmetric channel shows why a fair input attains the best information rate. A completely noisy binary symmetric channel has $p=1/2$ and carries no input information; a known flip on every use, $p=1$, is instead reversible.

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

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.

For a fixed finite discrete memoryless channel $W$, the function $p\mapsto I_p(X;Y)$ is concave on the input probability simplex. Indeed, the induced output law $q=pW$ is linear in $p$, the output Shannon entropy $H(q)$ is concave, and $H(Y\mid X)={\sum }_{x}p(x)H(W(\cdot \mid x))$ is linear. Their difference is therefore concave. Equivalently, at a mixture $p=\lambda p_1+(1-\lambda )p_2$, the concavity gap is $\lambda D(q_1\Vert q)+(1-\lambda )D(q_2\Vert q)\ge 0$ by Gibbs inequality. Thus every local maximum is a global maximum, and averaging over symmetries of the fixed channel cannot decrease mutual information.

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.

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.

The capacity of a discrete memoryless channel is $C={\max }_{P_X}I(X;Y)$, in bits per channel use. For the binary symmetric channel with crossover probability $p$, $H(Y\mid X)=h(p)$ and $H(Y)\le 1$. A uniform input makes the output uniform, attainingFor the binary erasure channel, let $E$ be its erasure indicator. This flag is visible in the output and independent of the input. If there is no erasure, the output reveals the input; otherwise it reveals nothing. Consequentlyagain attained by a uniform input. These formulas include crossover probabilities zero and one, and complete erasure.

Let $\bar{\ell }=\mathbb{E}|c(X)|$. The Huffman encoder emits an average of $w\bar{\ell }$ binary digits per minute. Shannon's noisy-channel coding theorem states that for a discrete memoryless channel of capacity $K$, every information rate strictly below $K$ bits per use is achievable with error probability tending to zero as block length grows; rates above $K$ are not achievable for unrestricted messages.

Thus a channel code carrying the Huffman bitstream reliably with buffering and arbitrarily long blocks can be chosen wheneverThe strict inequality supplies positive coding and buffering slack. Huffman's expected-length bound is $H(X)\le \bar{\ell }<H(X)+1$ for a nontrivial finite source. Therefore the simpler bound $r>w(H(X)+1)/K$ is sufficient without knowing its exact Huffman lengths.

Distinguish this bitstream construction from the absolute source-channel limit. The noiseless source coding theorem permits long source blocks to be compressed to any rate above $H(X)$ bits per source symbol, with arbitrarily small overhead. Together with channel coding, this gives the sharper limiting requirement $rK>wH(X)$; $rK<wH(X)$ is impossible by the source-channel converse. Further compression can exploit redundancy remaining in a single-symbol Huffman stream, so $w\bar{\ell }/K$ need not be the universal minimum channel symbol rate. At $K=0$ a positive-entropy source cannot be sent reliably at a finite rate.

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.

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.

There are two possible messages and three channel uses, givingConditional on either transmitted message, a decoding error occurs exactly when at least two of the three bits are flipped. The discrete memoryless channel makes these flips independent, each with probability $\epsilon =1/10$. Their count therefore has a binomial distribution with parameters $3,\epsilon$. Majority-vote decoding of a repetition code givesInterchanging the two bit values leaves the binary symmetric channel and majority decision unchanged, so $\mathbb{P}(\text{error}\mid W=b)=7/250$ as well. Both the maximum conditional error and the average error, for any message prior, are therefore $0.028$. The probability of correct decoding for each message is $243/250=0.972$. These are finite-block error probabilities; a channel-capacity statement alone would not determine them.

The channel capacity is the supremum of reliable communication rates: a rate $R$ bits per use is achievable if block encoders and decoders using $n$ channel uses can transmit $M_n$ messages with error probability tending to zero and $\mathrm{liminf}{n}^{-1}{\log }_2{M}_n\ge R$.

A discrete memoryless channel has fixed transition probabilities $W(y|x)$ on finite input and output alphabets, andIts single-letter capacity formula iswith logarithms to base two. The Shannon second coding theorem identifies this maximum with the operational reliable rate.

For the binary erasure channel, use output symbols $0,1,e$, where $e$ is a recognizable erasure flag. Given input $x$, the output is $x$ with probability $1-p$ and $e$ with probability $p$. If $\mathrm{Pr}(X=1)=a$, the output probabilities are $(1-p)(1-a),(1-p)a,p$. Thus, writing $h_2$ for binary entropy,and $I(X;Y)=(1-p)h_2(a)$. Its maximum is attained by the uniform input $a=1/2$, givingIn particular the noiseless and complete-erasure endpoints have capacities one and zero. The erasure flag reveals which positions were lost; it does not reveal the erased input values.

A discrete memoryless channel is specified by discrete input and output alphabets and a transition probability $W(y|x)$, with $W(y|x)\ge 0$ and ${\sum }_{y}W(y|x)=1$. Its successive outputs are conditionally independent given the inputs, with the same transition rule at every use:Operationally, its channel capacity is the supremum of communication rates in bits per use attainable by increasingly long block codes with decoding error probability tending to zero. For finite alphabets, the equivalent Shannon characterization iswhere $H$ is Shannon entropy, $H(Y|X)$ is classical conditional entropy, and the maximization is over the input probability distribution.

For the channel in question, the transition matrix, with input symbols indexing rows, isEvery row has the same Shannon entropy, namely the binary entropy $h_2(1/3)$. Consequently $H(Y|X)=h_2(1/3)$ for every input probability distribution. Since the output has three symbols, the maximum entropy on a finite alphabet givesChoose a uniform input. Each column of $W$ sums to one, so $P_Y(y)=1/3$ for every output symbol and the upper bound is attained. FinallyThus the cyclic ternary channel capacity isachieved by a uniform input probability distribution. This is a weakly symmetric channel capacity calculation: the matrix rows are permutations and the column sums agree. The channel is not the usual ternary symmetric-error channel, since an error has only one possible changed output for each input.

The Shannon second coding theorem says that a memoryless channel permits transmission at any fixed code rate $R<C$ with error probability tending to zero as block length tends to infinity. Conversely, a sequence of codes with error probability tending to zero cannot have a limiting rate above $C$. The channel capacity, in bits per use, isFor a finite discrete memoryless channel with transition probabilities $W(y\mid x)$, the supremum is a maximum and its mutual information isFor a general memoryless channel, mutual information is the relative entropy of the joint input-output law with respect to the product of its marginal laws; the same supremum is taken over the admissible input laws.

For the binary symmetric channel, write $Y=X\oplus Z$ with independent noise $Z$ having Bernoulli distribution of parameter $p$. Given either input bit, the output conditional entropy is $h_2(p)$. ThusAn input with uniform distribution makes the output have uniform distribution, attaining $H(Y)=1$. The binary symmetric channel capacity is therefore