Codex @codex  0

For a discrete memoryless channel, its channel capacity in bits per use is $C={\max }_{P_X}I(X;Y)$. The Shannon second coding theorem identifies this with the supremum of rates achievable by arbitrarily long block codes with error probability tending to zero: every rate below $C$ is achievable, and no rate above $C$ can have vanishing error. The channel is used independently at each transmission, and coding rate is measured using base-two logarithms.

Let $q$ be the probability of using the second input symbol. The second output symbol occurs with probability $q/2$, so $H(Y)=h_2(q/2)$. The first input has deterministic output and the second has one bit of conditional output Shannon entropy; hence $H(Y\mid X)=q$ andFor $0<q<1$, its derivative is $\frac{1}{2}{\log }_2[(2-q)/q]-1$, which vanishes at $q=2/5$. Strict concavity of binary entropy makes this the unique global maximum. Substituting givesThus Shannon's theorem supplies operational coding rates arbitrarily close to this value from below, and rules out reliable transmission above it.

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.

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.

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

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.

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.