Lower limit on the number of check bits needed to correct single errors

Question

I was going through Andrew S. Tannenbaum's computer networks book, and on page 206 of it, he has derived the number of check bits needed to correct single bit errors. The derivation goes as follows:

For m data bits, there are 2^m legal messages. Each of these messages has n illegal codewords at a distance on 1 from it. These are formed systematically by inverting each of the n-bit codeword formed from it. Thus, each of the 2^m legal messages requires n+1 bit patterns dedicated to it....

Can someone please explain the last line to me? For an n-bit codeword, we can only flip n bits to get illegal codewords. When does that additional 1 come from?

I am very new to coding theory, so please excuse if this is a very naive question.

Thanks!

Answer 1

The comment by @gnasher is right. Moreover, if the code was $k$ error correcting with $m$ data bits, each of the $2^m$ legal messages would require $$ 1+n+\binom{n}{2}+\cdot+\binom{n}{k}=\sum_{j=0}^k \binom{n}{j} $$ bit patterns dedicated to it, where $\binom{n}{j}$ is the number of words at Hamming distance $j$ from a given word.