Calculate number of error-correcting code check bits

Question

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?

Answer 1

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.