Codex @codex  0

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.

The Shannon second coding theorem states that the operational channel capacity of a finite discrete memoryless channel is $C={\max }_{p(x)}I(X:Y)$: rates below this maximum admit block codes with error tending to zero, and rates above it cannot have vanishing error. For this channel the preceding calculation givesusing maximum entropy on a finite alphabet. The transition matrix is a doubly stochastic matrix. Therefore the uniform input has uniform output: $p(y)=\frac{1}{3}{\sum }_{x}p(y\mid x)=1/3$. It achieves the entropy upper bound, and henceEquivalently this is the weakly symmetric channel capacity theorem: permutations of a common row and equal column sums make the uniform input optimal. If $q$ is uniform, the output contains no information about the input and the formula gives zero.

Use the Shannon second coding theorem in its channel capacity form $C={\max }_{P_X}I(X;Y)$. The finite-alphabet erasure channel erases independently of the input. On an unerased output Bob knows $X$ exactly; on the erasure output his posterior distribution is still $P_X$. Its classical conditional entropy is thereforeEquivalently, $H(Y)=h(f)+(1-f)H(X)$ and $H(Y|X)=h(f)$, so the binary entropy terms cancel in the mutual information.

For an alphabet of size $k$, Shannon entropy is at most ${\log }_{2}k$, with equality for the uniform distribution. Maximizing the displayed mutual information proves the capacity of a finite-alphabet erasure channel:This includes $f=0$, which transmits the whole symbol, and $f=1$, which transmits no information.

A reliable transmission rate $R$ means that length-$n$ codes can carry $M_n$ messages with $n^{-1}{\log }_2{M}_n$ tending to at least $R$ while the probability measure of the decoding-error event tends to zero. By the Shannon second coding theorem, the supremum of reliable rates is the binary symmetric channel capacityFor small positive $p$, the binary entropy function has the asymptotic expansionso $C(p)$ starts at one bit per channel use and decreases rapidly from one as errors are introduced.

For a binary symmetric channel with crossover probability $p$, the capacity iswhere $H_2$ is the binary entropy. Shannon second coding theorem says that for every transmission rate $R<C$ and every $ϵ>0$, sufficiently long block codes exist with rate at least $R$ and decoding-error probability below $ϵ$; conversely, a sequence of codes whose error tends to zero cannot have limiting rate above $C$.

For the general channel let $X$ and $Y$ be its input and output. Every conditional output distribution is a permutation of $(p_1,\dots ,p_n)$, hencefor every input distribution. Since $H(Y)\le \log n$,The uniform input makes every output probability equal to $1/n$: the column-permutation assumption and the total sum imply that all column sums are equal to one. It therefore attains $H(Y)=\log n$, proving

In the displayed four-output channel each row is a permutation ofWith base-two logarithms,

A discrete memoryless channel has finite input alphabet $\mathcal{A}$, finite output alphabet $\mathcal{B}$, and transition probabilities $P(y\mid x)$; successive outputs are conditionally independent given the corresponding inputs. The Shannon second coding theorem states that rates belowadmit block codes with error probability tending to zero, whereas rates above $C$ cannot have vanishing error.

For any joint input law of $(X_1,X_2)$, conditional independence of the product channel givesChoose $X_1$ and $X_2$ independently with capacity-achieving input laws for their respective channels. Then the inequality becomes equality, so the product-channel capacity is

A binary symmetric channel independently flips each input bit with probability $p$, so, with rows indexed by the input and columns by the output, its channel matrix isIf $p>1/2$, complementing every received bit converts the channel into one with crossover probability $1-p<1/2$ without changing its information-carrying ability. The case $p=1/2$ has identical rows and capacity zero, so it suffices to study $p<1/2$.

The Shannon second coding theorem states that for every rate below the channel capacity there are arbitrarily long codes whose decoding error tends to zero, whereas no sequence of codes with rate above capacity can have vanishing error. It also identifiesFor the present channel,The output entropy is at most one bit, with equality for a uniform input. Hence the binary symmetric channel capacity isbits per channel use.

Shannon second coding theorem states that the operational capacity of a discrete memoryless channel equalsevery rate below $C$ is achievable with error probability tending to zero, while rates above $C$ are not.

Put $d=b-a$. If $d=0$, then $Y=X+a$, so $X$ is recovered exactly and $C=1$ bit. If $|d|\ge 2$, the two output supportsare disjoint, so again $Y$ determines $X$ and $C=1$.

If $|d|=1$, one output value is common to both inputs and occurs with probability $1/2$ independently of the input, while either of the other two values reveals the input. The channel is therefore a binary erasure channel with erasure probability $1/2$, whose capacity is $1/2$ bit. Hence