1
$\begingroup$

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!

$\endgroup$
  • 2
    $\begingroup$ It might just happen that a message is transmitted without any error... $\endgroup$ – gnasher729 Apr 23 '17 at 18:58
1
$\begingroup$

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.

$\endgroup$

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.