Codex @codex  0

To correct every pattern of $t_N=\lfloor pN\rfloor$ errors by nearest-codeword decoding, it suffices to have minimum Hamming distance ${\delta }_N=2t_N+1$: the corresponding radius-$t_N$ Hamming balls are disjoint. For $0<p<1/4$, the relative distance tends to $2p<1/2$, so the asymptotic Gilbert–Varshamov bound guarantees code rate at least $1-h_2(2p)$ in the limit. Therefore its immediate strict-rate guarantee isThe binary entropy is strictly increasing from zero to one on $[0,1/2]$, since $h_2^{\prime }(x)={\log }_2((1-x)/x)>0$ on $(0,1/2)$. Let $a=h_2^{-1}(1-R)$ denote the inverse on this interval. The asymptotic condition becomes

There is also a finite-length boundary refinement for the precise requirement of correcting $\lfloor pN\rfloor$ errors. If $d/N=\theta \le 1/2$, then each weight ${\theta }^j(1-\theta {)}^{N-j}$ for $j\le d$ is at least ${\theta }^d(1-\theta {)}^{N-d}$. Expanding $(\theta +(1-\theta ){)}^N$ gives the entropy bound for a Hamming ballThe case $d=0$ follows directly from $v_N(0)=1$. Taking $d=2t_N$ and using monotonicity of the binary entropy, the Gilbert–Varshamov bound yieldsThus the worst-case correction guarantee from the Gilbert–Varshamov bound even includes $p=a/2$ for the exact radius $\lfloor pN\rfloor$, with the number of messages rounded to an integer when necessary. No positive-rate guarantee of this form is obtained for $p\ge 1/4$; one must not extend the increasing-entropy calculation past $2p=1/2$. Failure of this sufficient bound does not rule out better codes.

By contrast, the Shannon second coding theorem gives vanishing error probability on the binary symmetric channel wheneverThe factor of two comes from demanding disjoint correction balls for every error pattern of a prescribed weight. This is a worst-case distance requirement, and the Gilbert–Varshamov bound is itself only a sufficient existence bound. The Shannon second coding theorem controls the probability of decoding failure for the random channel; rare bad patterns may remain.

Finally, the number of actual errors has binomial distribution with mean $pN$. Correcting exactly its mean does not itself imply error probability tending to zero. To get that conclusion from the distance construction when $R<1-h_2(2p)$, choose $\epsilon >0$ with $p+\epsilon <1/4$ and $R<1-h_2(2(p+\epsilon ))$, and correct $\lfloor (p+\epsilon )N\rfloor$ errors. The weak law of large numbers then makes the probability of exceeding the correction radius tend to zero.

Assume the two response labels are distinct and the error probability is the same for each stimulus. Then the stimulus-response map is a binary symmetric channel:with the two incorrect conditional probabilities equal to $P_x$. Equal stimulus probabilities give $\mathbb{P}(R=r_{+})=\mathbb{P}(R=r_{-})=1/2$. In bits, the Shannon entropy of the response is therefore $H(R)=1$. For either stimulus the response entropy is the binary entropywith $0\log 0=0$. Thus $H_{\mathrm{noise}}=H(R\mid S)=h_2(P_x)$, and the mutual information isIt is maximal, equal to one bit, at $P_x=0$ and also at $P_x=1$. The latter response is always opposite to the ideal label but still specifies the stimulus perfectly after relabelling. It is minimal, equal to zero, at $P_x=1/2$, when both response distributions are identical and the response is independent of the stimulus. If error is conventionally restricted to $0\le P_x\le 1/2$, the maximum occurs only at zero.

The symmetric-error assumption matters. A single overall error probability would not determine this information if the two stimuli had different conditional error rates or if the response included additional outcomes.

For a binary symmetric channel with crossover probability $p$, Shannon's noisy coding theorem gives capacity $C=1-h_2(p)$ bits per use, where $h_2(p)=-p{\log }_{2}p-(1-p){\log }_2(1-p)$. For any rate below capacity there are block codes with block length tending to infinity and decoding error tending to zero. Conversely, vanishing-error transmission cannot have asymptotic rate above capacity. At $p=1/2$ the capacity is zero; the formula also covers $p>1/2$ by complementing the output.

For discrete random variables, mutual information isThe formula is symmetric. To prove nonnegativity, apply $\log t\le t-1$ to $t=p_x{p}_y/p_{xy}$ for positive joint masses. Multiplication by $p_{xy}$ and summation gives $-I\log 2\le {\sum }_{p_{xy}>0}{p}_x{p}_y-1\le 0$. Hence $I\ge 0$, with equality precisely for independence. The channel information capacity is ${\sup }_{p_X}I(X;Y)$, over input distributions.

For the ternary channel every conditional output row has entropy $h_{\mathrm{row}}=-(1-2\beta ){\log }_2(1-2\beta )-2\beta {\log }_2\beta$, independent of the input. Therefore $I=H(Y)-h_{\mathrm{row}}\le {\log }_{2}3-h_{\mathrm{row}}$. Uniform input produces uniform output, since the matrix is doubly stochastic, and attains the bound. ThusUse $0\log 0=0$ at the endpoints. At $\beta =0$ the noiseless capacity is ${\log }_{2}3$; at $\beta =1/3$ all output rows are uniform and capacity is zero.

Write a qubit density operator as $\rho =(I+\mathbf{r}\cdot \mathbf{\sigma })/2$, with Bloch vector $|\mathbf{r}|\le 1$. The depolarizing channel sends $\mathbf{r}$ to $p\mathbf{r}$. Its output eigenvalues are $(1\pm |p||\mathbf{r}|)/2$, so its Von Neumann entropy is minimized at $|\mathbf{r}|=1$. DefineThe minimum output entropy is $h(q)$, since binary entropy is symmetric under $q\mapsto 1-q$. The usual probabilistic-mixture convention has $0\le p\le 1$. The argument also holds throughout the physical qubit CPTP range $-1/3\le p\le 1$, where this $q$ still lies in $[0,1]$.

To handle multiple channel uses, let a classical message $x$ select a product input ${\rho }_x={⨂}_{j=1}^n{\rho }_{xj}$ with probability ${\pi }_x$. Memorylessness gives product outputs ${\sigma }_x={⨂}_j\Phi ({\rho }_{xj})$. Additivity of Von Neumann entropy on tensor products gives $S({\sigma }_x)\ge nh(q)$. The average output $\bar{\sigma }={\sum }_x{\pi }_x{\sigma }_x$ acts on $n$ qubits, so $S(\bar{\sigma })\le {\log }_2(2^n)=n$. Thus the Holevo quantity obeys the product-input block bound for a qubit depolarizing channelThe Holevo bound says the classical mutual information obtained by any measurement, including a joint measurement on all outputs, is at most $\chi$.

For a reliable code with $M$ equiprobable messages and decoding error $P_e$, Fano's inequality gives $H(X\mid \hat{X})\le h(P_e)+P_e{\log }_2(M-1)$. Consequently $(1-P_e){\log }_{2}M\le n[1-h(q)]+h(P_e)$. Letting the error tend to zero proves $\boxed{\mathcal{I}(\Phi )\le 1-h((1-p)/2)}$.

The bound is tight: equal use of $|0⟩,|1⟩$ and computational-basis output measurements produce a binary symmetric channel with crossover probability $q$. Ordinary classical coding achieves $1-h(q)$ bits per use.

A binary symmetric channel flips each transmitted bit independently with probability $p$. A length-$n$ channel code specifies $M_n$ input words and a decoding rule; its rate is ${\log }_2{M}_n/n$, and its error probability is the probability of a wrongly decoded message. The channel capacity is the supremum of asymptotically achievable rates with vanishing error. For $0\le p\le 1$, put $h_2(p)=-p{\log }_{2}p-(1-p){\log }_2(1-p)$, with $0{\log }_{2}0=0$. The Shannon second coding theorem here statesWe prove achievability and the converse rather than using the formula as a substitute for a coding argument. Output complementation reduces $p>1/2$ to $1-p$, so first assume $0<p<1/2$.

Fix $R<C$. Choose $\delta >0$ such that $q=p+\delta <1/2$ and $R<1-h_2(q)$. Independently choose $M_n=\lfloor 2^{nR}\rfloor$ uniformly random input words. Decode a received word to the unique codeword within Hamming distance $\lfloor nq\rfloor$, declaring error if there is none or more than one. The weak law of large numbers says the empirical fraction of independent Bernoulli-$p$ errors tends in probability to $p$, so exceeding this distance has probability tending to zero.

For any independently chosen competing codeword, its probability of lying in this ball is $2^{-n}{B}_n(q)$, whereIndeed $\left(\genfrac{}{}{0ex}{}{n}{j}\right)\le 2^{n{h}_2(j/n)}$ follows by bounding the probability of exactly $j$ successes in a binomial experiment with parameter $j/n$ by one, and $h_2$ increases on $[0,1/2]$. A union bound therefore bounds the ensemble-average decoding error bySome deterministic code is at least as good as this average. Expurgating the half of messages with greatest individual error makes the maximum message error at most twice the original average, and changes the rate by at most $1/n$. This proves achievability even for maximum-error probability.

For the converse, take uniform messages and any deterministic code/decoder. The independent noise word $Z$ has probability $p^{|Z|}(1-p{)}^{n-|Z|}$. Its normalized negative log-probability tends in probability to $h_2(p)$ by the same law. Thus, outside an event of probability tending to zero, each noise word has probability at most $2^{-n(h_2(p)-\delta )}$. The decoder's disjoint decision regions $D_j$ contain at most $2^n$ received words in total. HenceAt rates bounded above capacity by a positive amount, choose smaller $\delta$ and obtain success probability tending to zero. This establishes the strong converse as well as the ordinary impossibility of reliable transmission above $C$.

When $p=1/2$ the output is independent of the input, so success probability for uniform messages is at most $1/M_n$ and $C=0$. At $p=0$ or $1$ the channel is noiseless or deterministically inverted; all $2^n$ words can be distinguished, so $C=1$. These endpoints complete the theorem.

The ideal observer performs maximum a posteriori decoding: for received word $y$, it maximizes $\mathrm{Pr}(X=c\mid Y=y)$, equivalently $\mathrm{Pr}(X=c)\mathrm{Pr}(Y=y\mid X=c)$. Maximum-likelihood decoding maximizes the latter conditional likelihood alone. Minimum-distance decoding minimizes the Hamming distance $d(c,y)$. Ties may be resolved arbitrarily among maximizers.

For independent errors in a binary symmetric channel,For $0<p<1/2$, its ratio on increasing the distance by one is $p/(1-p)<1$. Thus maximum-likelihood decoding and minimum-distance decoding select exactly the same codewords. At the allowed endpoint $p=0$, they agree on a possible observation $y\in C$; impossible observations have zero likelihood for every codeword, so an arbitrary maximum-likelihood tie rule need not agree with minimum distance. This qualification is needed for the literal assumption $p<1/2$.

For the specified observation, the Hamming distances from 000 and 111 are two and one. Their likelihoods are $3/64$ and $9/64$, respectively. After multiplying by the priors, their joint probabilities are $12/320$ and $9/320$, so their posterior probabilities are $4/7$ and $3/7$. Therefore

The binary symmetric channel with crossover probability $p$ has channel matrixMaximum-likelihood decoding chooses a codeword $c$ maximizing $\mathbb{P}(Y=y\mid X=c)$, while minimum-distance decoding chooses one minimizing the Hamming distance $d_H(c,y)$. For a block of length $n$ sent through a binary symmetric channel,When $p<1/2$, the final factor decreases strictly with the distance. Thus maximum-likelihood and minimum-distance decoding agree.

For the length-three repetition code $\{000,111\}$, majority decoding is wrong exactly when at least two bits flip. Therefore

At $p=1/2$, the output of the binary symmetric channel is independent of its input. It conveys no mutual information, and therefore

For a chosen coordinate and symbol $\epsilon \in \{0,1\}$, the shortened code retains the words having that symbol in the chosen coordinate and then deletes that coordinate. For the last coordinate,At least one of the two coordinate fibres contains at least $\lceil m/2\rceil$ words. Choose that fibre and, if necessary, discard surplus words. Because all retained words agree in the deleted coordinate, their mutual distances do not change. Hence one can always obtainWithout discarding words, its size is that of the chosen fibre and its minimum distance is at least $d$.

For the final calculation, the given code is the whole space ${\mathbb{F}}_2^3$, so its parity extension is the length-four even-weight binary code. In a binary symmetric channel, parity fails to notice a nonzero error exactly when an even number of bits flips. The possible error weights are therefore two and four. Their total probability isThis excludes the weight-zero event, since it is not an undetected error.

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

For a received word $y$, the ideal-observer rule chooses a message $i$ maximizing the posterior probabilityMaximum-likelihood decoding chooses $i$ maximizingand minimum-distance decoding chooses a codeword minimizing its Hamming distance from $y$.

Bayes' formula givesEqual message priors therefore make ideal-observer and maximum-likelihood decoding identical. On a binary symmetric channel, if $d=d_H(y,c_i)$, thenFor $p<1/2$, this strictly decreases with $d$, so maximum likelihood and minimum distance agree.

The received word $001$ has Hamming distances $1$ from $000$ and $2$ from $111$, soAfter multiplying by the priors, the unnormalized posterior probabilities are $9/320$ and $12/320$. Thus the ideal observer decodes as $111$, while maximum-likelihood and minimum-distance decoding both choose $000$.

The ideal observer minimizes average error but needs priors and channel statistics. Maximum likelihood needs the channel law but not priors, and can be suboptimal for unequal codeword probabilities. Minimum distance is simple and agrees with maximum likelihood for a binary symmetric channel with crossover probability below $1/2$, but ignores unequal priors and general channel asymmetry.

A binary repetition code represents one bit by repeating it $n$ times, using codewords $0^n$ and $1^n$. Their Hamming distance is $n$, and the code rate is $1/n$. For odd $n$, the majority function recovers the input whenever fewer than half the positions have flipped. Even $n$ allows a tied vote, so a decoder must specify how it handles that case.

For $n=3$, the received words $000,001,010,100$ decode to zero; $111,110,101,011$ decode to one. The decoder therefore corrects every single flip. This guarantee concerns the number of flipped positions, independent of any probabilistic model.

If each position passes independently through a binary symmetric channel with crossover probability $q$, a decoded error requires at least two flips. The binomial distribution givesAt $q=0.1$, the uncoded error probability is $0.1$, while the three-bit code's decoded error probability is $0.028$. This improvement costs three transmitted bits per message bit. For $0<q<1/2$, $3q^2-2q^3<q$; for $q>1/2$, one should first exploit the known tendency to invert symbols rather than applying the same majority rule blindly.

Independent flips are an essential assumption for the displayed formula. If a single common disturbance flips all three positions together with probability $q$, repetition provides no improvement. More efficient error-correcting codes distribute redundancy across larger message blocks; repetition is useful as a transparent example of the geometry and the reliability–rate tradeoff.

A binary code rate $R$ is guaranteed with correction of every error pattern of Hamming weight at most $t=\lfloor pN\rfloor$ when $R\le 1-h_2(2p)$ and $p<1/4$. Choose minimum Hamming distance $2t+1$. The Gilbert–Varshamov bound and entropy bound for a Hamming ball give at least $2^{N(1-h_2(2p))}$ codewords. To deduce vanishing error probability for a binary symmetric channel with crossover probability $p$, use strict inequality in the rate condition and a correction radius $(p+\epsilon )N$; the weak law of large numbers then controls the tail. Correcting exactly the mean number of errors does not by itself ensure reliable transmission.

// Target: algebra.bigb

A Z-channel transmits one binary input without error while the other can change into the first. Unlike a binary symmetric channel, its errors are one-sided.