Binary Symmetric Channel and Binary Erasure Channel: Capacity and Sphere-Packing

Intuition Beginner

Imagine sending a message by flipping coins. You send heads or tails, but the channel flips each coin with probability $p$. This is the binary symmetric channel (BSC). If $p=0$, the channel is perfect — what you send is what arrives. If $p=0.5$, the channel is useless — the output is a fresh coin flip, independent of the input.

Now imagine a different channel. You send heads or tails, but with probability $\alpha$ the channel eats the bit entirely and returns a question mark. You know something was erased, but you do not know what. This is the binary erasure channel (BEC). The BEC is friendlier than the BSC because it tells you when an error happened, instead of silently corrupting the bit.

For the BSC, the capacity is $1-H(p)$ bits per use, where $H(p)$ is the binary entropy. At $p=0.1$, the capacity is $1-0.469=0.531$ bits per use. You lose about half a bit to noise. At $p=0.5$, the capacity is zero.

For the BEC, the capacity is $1-\alpha$ bits per use. At $\alpha =0.1$, the capacity is 0.9. You lose exactly the fraction of bits that get erased. The BEC capacity is always higher than the BSC capacity for the same noise level, because knowing where the errors are is valuable.

The sphere-packing bound explains why capacity is finite. In a space of $n$-bit strings, the number of strings within distance $t$ of any codeword is the volume of a Hamming ball. If you want to correct $t$ errors, the balls around your codewords cannot overlap, so the total number of codewords is bounded by $2^n$ divided by the ball volume.

The BSC and BEC are the workhorse channel models because they capture two fundamentally different types of noise. The BSC models errors — bits that flip silently — which is the hardest noise to handle because you do not know which bits are wrong. The BEC models erasures — bits that disappear but their locations are known — which is easier because you know exactly what is missing. Every practical communication system encounters a mixture of both, and understanding these two extreme cases provides the foundation for handling realistic channels.

Visual Beginner

Figure: a grid of $2^4=16$ points representing all 4-bit strings. Five codewords are marked as filled circles. Hamming balls of radius 1 around each codeword are shaded. The balls are disjoint (no overlap), illustrating the sphere-packing constraint.

Channel	Noise parameter	Capacity (bits/use)	Interpretation
BSC, $p=0$	No errors	1.000	Perfect channel
BSC, $p=0.1$	10% flip	0.531	About half the bits carry information
BSC, $p=0.5$	Random output	0.000	Completely useless
BEC, $\alpha =0$	No erasures	1.000	Perfect channel
BEC, $\alpha =0.1$	10% erased	0.900	Lose only the erased fraction
BEC, $\alpha =0.5$	Half erased	0.500	Half the bits survive

The BEC always has higher capacity than the BSC at the same noise level because erasures are easier to handle than errors.

Worked example Beginner

Consider the BSC with crossover probability $p=0.11$. The capacity is $1-H(0.11)$.

Compute $H(0.11)=-0.11{\log }_2(0.11)-0.89{\log }_2(0.89)=0.11\times 3.184+0.89\times 0.168=0.350+0.150=0.500$ bits.

So the capacity is $1-0.5=0.5$ bits per channel use.

A code of length $n=1000$ can transmit at most about 500 bits of information reliably. Using rate $R=0.5$, we can send $2^{500}$ distinct messages in 1000 channel uses. This is an astronomically large number — far more than the number of atoms in the observable universe — which illustrates the power of channel coding: even through a noisy channel, reliable communication at positive rates allows an exponential number of distinct messages.

Now consider the sphere-packing bound for a code of length $n=7$ correcting $t=1$ error. The volume of a Hamming ball of radius 1 in 7 dimensions is $1+7=8$. The sphere-packing bound gives at most $2^7/8=16$ codewords. The $[7,4]$ Hamming code achieves exactly 16 codewords with minimum distance 3, so it is a perfect code that saturates the bound.

For a larger example, consider $n=23$ and $d=7$ (the Golay code parameters). The ball volume is $1+23+253+1771=2048=2^{11}$. The sphere-packing bound gives at most $2^{23}/2^{11}=2^{12}=4096$ codewords. The binary Golay code achieves exactly this, making it another perfect code. These two codes — the Hamming $[7,4,3]$ and the Golay $[23,12,7]$ — are the only interesting perfect binary codes (beyond the degenerate repetition codes and the full space).

Check your understanding Beginner

Formal definition Intermediate+

Definition (Binary symmetric channel). The BSC with crossover probability $p\in [0,1/2]$ is the channel with input alphabet $\mathcal{X}=\{0,1\}$, output alphabet $\mathcal{Y}=\{0,1\}$, and transition probabilities

$$p(y|x)=\{\begin{array}{ll}1-p& \text{if }y=x\\ p& \text{if }y\ne x.\end{array}$$

Definition (Binary erasure channel). The BEC with erasure probability $\alpha \in [0,1]$ is the channel with input alphabet $\mathcal{X}=\{0,1\}$, output alphabet $\mathcal{Y}=\{0,1,?\}$, and transition probabilities

$$p(y|x)=\{\begin{array}{ll}1-\alpha & \text{if }y=x\\ \alpha & \text{if }y=?\end{array}$$

Theorem (BSC capacity). $C_{\text{BSC}}(p)=1-H_b(p)$ bits per channel use, achieved by the uniform input distribution.

Proof. $C={\max }_{p(x)}I(X;Y)$. For the BSC with input distribution $\mathrm{Pr}[X=0]=q$, $\mathrm{Pr}[X=1]=1-q$:

$$I(X;Y)=H(Y)-H(Y|X)=H(Y)-H_b(p),$$

since $H(Y|X)=H_b(p)$ (the output entropy given the input is the binary entropy of the crossover probability). This is maximised when $H(Y)$ is maximised, which occurs at $q=1/2$ (uniform input), giving $H(Y)=1$. Therefore $C=1-H_b(p)$. $\square$

Theorem (BEC capacity). $C_{\text{BEC}}(\alpha )=1-\alpha$ bits per channel use, achieved by the uniform input distribution.

Proof. $I(X;Y)=H(X)-H(X|Y)$. With uniform input, $H(X)=1$. The conditional entropy $H(X|Y)$: when $Y=?$ (probability $\alpha$), $X$ is unknown, contributing $\alpha \cdot 1$. When $Y=x$ (probability $1-\alpha$), $X=x$ is known, contributing 0. So $H(X|Y)=\alpha$. Therefore $C=1-\alpha$. $\square$

Counterexamples to common slips

• The BSC capacity is not $1-2p$. The capacity involves $H_b(p)$, not $2p$. At small $p$, $H_b(p)\approx p{\log }_2(1/p)$, which is much larger than $2p$.

• The BEC capacity formula $1-\alpha$ only applies to the binary erasure channel. For a $q$-ary erasure channel, the capacity is ${\log }_{2}q\cdot (1-\alpha )$.

• The sphere-packing bound is not tight in general. It gives an upper bound on code size, but the largest achievable codes may be much smaller. Perfect codes (like the Hamming and Golay codes) are exceptions where the bound is tight.

Key theorem with proof Intermediate+

Theorem (Sphere-packing bound). An $(n,M,d)$ code over ${\mathbb{F}}_2$ (length $n$, size $M$, minimum distance $d$) satisfies

$$M\cdot \sum _{i=0}^t\left(\genfrac{}{}{0ex}{}{n}{i}\right)\le 2^n,$$

where $t=\lfloor (d-1)/2\rfloor$.

Proof. The Hamming balls of radius $t$ around each of the $M$ codewords are pairwise disjoint (since any two codewords differ in at least $d$ positions, and $2t+1\le d$ ensures the balls do not overlap). Each ball contains ${\sum }_{i=0}^t\left(\genfrac{}{}{0ex}{}{n}{i}\right)$ points (the codeword itself plus all strings within Hamming distance $t$). The total number of points covered by all balls is $M\cdot {\sum }_{i=0}^t\left(\genfrac{}{}{0ex}{}{n}{i}\right)$, and this cannot exceed the total number of points $2^n$ in the space. $\square$

Theorem (Hamming bound). The Hamming bound is the sphere-packing bound rewritten as a bound on $M$:

$$M\le \frac{2^n}{{\sum }_{i=0}^t\left(\genfrac{}{}{0ex}{}{n}{i}\right)}.$$

A code achieving equality is called perfect. The only interesting perfect binary codes (beyond the repetition codes and the full space) are the Hamming codes and the Golay code.

Bridge. The sphere-packing bound builds toward the channel coding theorem converse in 46.03.03, where Fano's inequality provides the information-theoretic impossibility result that complements the geometric packing constraint derived here. The foundational reason the sphere-packing bound matters is that it converts a geometric constraint (non-overlapping balls in Hamming space) into a rate constraint (the code rate $R=({\log }_{2}M)/n$ is bounded above), and this is exactly the combinatorial shadow of the capacity $C=1-H(p)$ for the BSC. The central insight generalises to the Gilbert-Varshamov lower bound in 40.06.06, where a packing argument in the reverse direction shows that large codes exist, and appears again in 46.07.01 where the weight enumerator gives algebraic control over code size, and putting these together the Hamming bound and Gilbert-Varshamov bound sandwich the maximal code size.

Exercises Intermediate+

Lean formalization Intermediate+

Mathlib lacks channel capacity, the BSC/BEC models, and the sphere-packing bound. Hamming distance exists informally via type-class instances, but the volumetric analysis of Hamming balls (binomial sum bounds) is not connected to the information-theoretic framework. A Codex.InformationTheory.BSC module would need to define the BSC transition matrix, compute $I(X;Y)$ for binary inputs, prove the capacity formula, and derive the sphere-packing bound from counting. This unit ships without formal verification.

Advanced results Master

The Plotkin bound and its relation to sphere-packing

The Plotkin bound gives a tighter constraint than the sphere-packing bound for codes with large minimum distance. For a binary code with $d>n/2$:

$$M\le \frac{2d}{2d-n}.$$

This follows from double-counting the total pairwise distance: ${\sum }_{i<j}d(c_i,c_j)\ge \left(\genfrac{}{}{0ex}{}{M}{2}\right)d$, but also ${\sum }_{i<j}d(c_i,c_j)\le n\left(\genfrac{}{}{0ex}{}{M}{2}\right)/2$ since the average distance between any two points in $\{0,1{\}}^n$ is $n/2$. Combining gives the Plotkin bound.

The Plotkin bound is tighter than the sphere-packing bound when $\delta >1/2$, but the sphere-packing bound is tighter for small $\delta$. Together, they provide complementary constraints on the $(n,M,d)$ trade-off.

The Gilbert-Varshamov bound

The Gilbert-Varshamov lower bound shows that large codes exist:

$$M\ge \frac{2^n}{{\sum }_{i=0}^{d-1}\left(\genfrac{}{}{0ex}{}{n}{i}\right)}.$$

This is proved by a greedy construction: start with an empty code and repeatedly add any vector not within distance $d-1$ of existing codewords. The process continues until the balls of radius $d-1$ cover the entire space.

Asymptotically, the GV bound gives codes with rate $R\ge 1-H_b(\delta )$. Comparing with the sphere-packing upper bound $R\le 1-H_b(\delta /2)$, there is a gap of $H_b(\delta )-H_b(\delta /2)$ between the best known lower and upper bounds on the rate-distance trade-off. Closing this gap is one of the central open problems in coding theory.

Capacity as a function of the noise level

For the BSC, the capacity $C(p)=1-H_b(p)$ is a concave, strictly decreasing function of $p$ on $[0,1/2]$. Its derivative is $C^{\prime }(p)=-{\log }_2\frac{1-p}{p}$, which diverges as $p\to 0^{+}$, reflecting the fact that even tiny noise levels reduce capacity.

The Bhattacharyya parameter $Z(p)=2\sqrt{p(1-p)}$ provides an alternative characterisation of channel quality. For the BSC, $Z(p)\in [0,1]$ with $Z(0)=0$ (perfect) and $Z(1/2)=1$ (useless). The capacity relates to the Bhattacharyya parameter via $C=1-H_b(Z^2/4(1-Z^2/4{)}^{-1})$, though the exact relationship is transcendental. The Bhattacharyya parameter is the key quantity in polar code analysis 46.08.03.

Synthesis. The BSC and BEC are the two canonical channel models of information theory; their capacity formulas $C_{\text{BSC}}=1-H_b(p)$ and $C_{\text{BEC}}=1-\alpha$ are the benchmarks against which all codes are measured. The central insight is that capacity converts noise into a rate penalty, and the sphere-packing bound provides the geometric reason: non-overlapping Hamming balls constrain the packing density. The foundational reason the BEC has higher capacity than the BSC is that erasures preserve the location of errors, and this builds toward polar codes in 46.08.03 where the BEC admits a particularly clean analysis. The sphere-packing bound generalises to the Plotkin and Elias-Bassalygo bounds, appears again in 46.07.01 where algebraic methods tighten the constraints, and putting these together the geometric and algebraic bounds sandwich the achievable rates for binary codes.

Full proof set Master

Proposition (Volume of Hamming ball). The volume of the Hamming ball of radius $t$ in $\{0,1{\}}^n$ is

$$V(n,t)=\sum _{i=0}^t\left(\genfrac{}{}{0ex}{}{n}{i}\right).$$

For $t\le n/2$, this satisfies $2^{n{H}_b(t/n)}/(n+1)\le V(n,t)\le 2^{n{H}_b(t/n)}$.

Proof. The number of binary strings of length $n$ at Hamming distance exactly $i$ from a fixed string is $\left(\genfrac{}{}{0ex}{}{n}{i}\right)$ (choose which $i$ positions to flip). Summing from 0 to $t$ gives the volume.

For the bounds, the dominant term in the sum is $\left(\genfrac{}{}{0ex}{}{n}{t}\right)$ when $t<n/2$. Using the entropy bound $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\le 2^{n{H}_b(k/n)}$ and the lower bound $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\ge 2^{n{H}_b(k/n)}/(n+1)$:

$$\frac{2^{n{H}_b(t/n)}}{n+1}\le \left(\genfrac{}{}{0ex}{}{n}{t}\right)\le V(n,t)\le (t+1)\left(\genfrac{}{}{0ex}{}{n}{t}\right)\le (t+1)2^{n{H}_b(t/n)}.$$

The polynomial factor $(t+1)$ is absorbed into a slightly adjusted exponent for the asymptotic statement. $\square$

Connections Master

• 46.03.01 — Discrete memoryless channels and mutual information; the BSC and BEC are the primary examples.
• 46.03.03 — Fano's inequality provides the converse; the sphere-packing bound provides a combinatorial converse.
• 40.06.07 — Perfect codes achieve the sphere-packing bound with equality; the Hamming and Golay codes are the only interesting examples beyond repetition codes.
• 46.08.03 — Polar codes achieve BSC and BEC capacity with explicit constructions.
• 40.06.06 — The Gilbert-Varshamov bound provides the complementary lower bound on code size.

Historical & philosophical context Master

Shannon introduced the BSC in his 1948 paper (Section 13), deriving the capacity $C=1-H(p)$ and giving the geometric interpretation of codes as sphere packings in Hamming space. The geometric analogy — codewords as non-overlapping spheres, errors as perturbations within a sphere — became the organising picture for coding theory.

The sphere-packing bound was known implicitly in Shannon's work but was first stated explicitly by Hamming in his 1950 paper ("Error detecting and error correcting codes," Bell System Technical Journal 29, pp. 147-160). Hamming used it to prove that his $[7,4,3]$ code was optimal for $d=3,n=7$.

The BEC was introduced by Elias in 1955 ("Coding for noisy channels," IRE Convention Record 3, pp. 37-46). Its clean capacity formula $C=1-\alpha$ makes it the preferred channel model for theoretical analysis, particularly for polar codes where the BEC admits exact analysis of the channel polarization phenomenon.

Bibliography Master

@article{shannon1948,
  author  = {Shannon, C. E.},
  title   = {A Mathematical Theory of Communication},
  journal = {Bell System Technical Journal},
  volume  = {27},
  pages   = {379--423 and 623--656},
  year    = {1948},
}
@article{hamming1950,
  author  = {Hamming, R. W.},
  title   = {Error Detecting and Error Correcting Codes},
  journal = {Bell System Technical Journal},
  volume  = {29},
  pages   = {147--160},
  year    = {1950},
}
@inproceedings{elias1955,
  author    = {Elias, P.},
  title     = {Coding for Noisy Channels},
  booktitle = {IRE Convention Record},
  volume    = {3},
  pages     = {37--46},
  year      = {1955},
}
@book{cover-thomas2006,
  author    = {Cover, T. M. and Thomas, J. A.},
  title     = {Elements of Information Theory},
  edition   = {2nd},
  publisher = {Wiley},
  year      = {2006},
}
@book{macwilliams-sloane1977,
  author    = {MacWilliams, F. J. and Sloane, N. J. A.},
  title     = {The Theory of Error-Correcting Codes},
  publisher = {North-Holland},
  year      = {1977},
}