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.

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.

For a discrete random variable with probabilities $p_i$, its Shannon entropy in bits is $H(X)=-{\sum }_i{p}_i{\log }_2{p}_i$, with $0{\log }_{2}0=0$. Gibbs inequality states thatwith equality exactly when $p=q$. If $q_i=0<p_i$, the left side is infinite. Otherwise apply $-\ln u\ge 1-u$ to $u=q_i/p_i$ for $p_i>0$:Equality requires $q_i=p_i$ on the support and no remaining mass outside it. In particular, comparison with the uniform probability distribution on two outcomes gives binary Shannon entropy at most $1$.

Write $q=1-p_1$. For $q>0$, grouping the last two outcomes givesEquality holds if $p_2=p_3$; if $q=0$ it also holds, and then both are zero. Thus equality holds exactly when $p_2=p_3$.

For the discrete memoryless channel, assume $\alpha ,\beta \ge 0$ and $\alpha +\beta \le 1$, and set $w=1-\alpha -\beta$. Both conditional output probability distributions have Shannon entropy $H(w,\alpha ,\beta )$. The third output has probability $\beta$ regardless of the input; the first two have total probability $1-\beta$. Their Shannon entropy is maximized by making them equal, which a uniform input achieves. Hence the channel capacity isand thereforeThe usual zero-times-log convention includes $\beta =1$, when $C=0$. If $w=\alpha$, the rows coincide and every input achieves zero mutual information; otherwise the uniform input is the unique maximizing input.

If $p>1/2$, complementing every received bit converts the channel into a binary symmetric channel with crossover probability $1-p<1/2$. This deterministic and invertible output relabelling does not change the channel capacity. Since $h_2(p)=h_2(1-p)$,Thus the capacity rises again from zero as $p$ increases beyond $1/2$, reaching one at $p=1$, where every bit is flipped deterministically and can be recovered by complementation.

For a discrete memoryless channel with input $X$ and output $Y$, its information capacity iswhere $I(X;Y)$ is the mutual information and the maximum is over all input distributions. Capacity is measured in bits when logarithms have base two.

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.