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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.