Binary symmetric channel ($Y=X\oplus Z,Z\sim \mathrm{Bernoulli}(p)$)

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.

An error is undetected by codeword-membership checking when the received word is a different valid codeword. For a linear code this occurs exactly when the nonzero channel-error vector is itself a codeword.

At crossover probability $p=1/2$, the two rows of the transition matrix of a binary symmetric channel coincide. Its output is then independent of its input and its capacity is zero.

If $p<1/4$, choose $p<\delta <1/4$. Binary codes of relative minimum distance above $2\delta$ have positive asymptotic rate by a greedy packing bound, and nearest-codeword decoding fails only when more than $\delta n$ channel errors occur. That probability tends to zero.