# Calculate number of error-correcting code check bits

To design a code with $$m$$ data bits and $$r$$ check bits which allow all single-bit errors to be corrected, the formula $$(n + 1) 2^m \leq 2^n$$ with $$n = m + r$$ and $$(m + r + 1) \leq 2^r$$ is used. Why is $$+ 1$$ used here, doesn't $$n$$ contain already all possible codewords?

Consider a binary code $$C$$ of length $$n$$ (each codeword consists of $$n$$ bits), containing $$2^m$$ codewords, and allowing all single-bit errors to be corrected.

Let $$x \in C$$, and let $$B_x$$ denote all words at distance at most $$1$$ from $$x$$, that is $$x$$ itself, as well as any word obtained by flipping a single coordinate. Any word in $$B_x$$ could result from a transmission of $$x$$ followed by at most one error. Since $$C$$ allows all single-bit errors to be corrected, for any $$y \in B_x$$, the only codeword within distance $$1$$ from $$y$$ must be $$B_x$$. In other words, the balls $$B_x$$ are disjoint.

Since there are $$2^m$$ balls $$B_x$$, each one contains $$n+1$$ words, the balls are disjoint, and there are $$2^n$$ possible words, we deduce that $$(n+1)2^m \leq 2^n$$. This is the so-called sphere-packing bound or Hamming bound.