5

Take the [8,4] extended code for example. Note that extended binary Hamming codes are 3-error-detecting.

All single-bit errors are correctly decoded, while double-bit errors are detected but not correctable.

But how exactly does the code behave when the error is 3-bit? Does it always decode the received word to a wrong codeword (decoder error), or does it always detect but not correct such errors (i.e. treat 3-bit and 2-bit errors the same), or does it behave either way depending on the specific received word?

Thanks!

P.S. Here's the motivation for my above question: for a [7,4] (2-error-detecting) Hamming code, 2-bit errors will result in a decoder error, i.e. the received word will be decoded to a wrong codeword.

ryang
  • 38,879
  • 14
  • 81
  • 179

1 Answers1

6

The eight-bit words can be classified into three types.

  1. Words of the $[8,4,4]$ extended Hamming code. There are 16 of these, and they have even weight.
  2. Words that are distance 1 from a codeword. There are 128 of these, and they have odd weight.
  3. Words that are distance 2 from a codeword. There are 112 of these, and they have even weight. Each such word is equidistant from four codewords.

From this it is clear that if there are three errors in transmission of a codeword, the received word will have odd weight, and therefore will fall into class 2. It will therefore be decoded as if it were distance 1 from a codeword. That is, it will always be decoded to the wrong codeword.

Added: As for decoding, suppose we use the parity check matrix $$H=\begin{bmatrix}1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0\\ 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0\\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\end{bmatrix}$$ and regard the first seven bits as coming from the $[7,4,3]$ Hamming code with the eighth bit as parity check bit. Given received word $w,$ we compute $Hw,$ which is a four-bit word. If the received word is a codeword, $Hw$ will equal $0000.$ If the received word has odd weight, bit $1$ of $Hw$ will be set, and the decoder will assume one error. Under this assumption, if $Hw=1000$ then the error was in bit $8;$ otherwise, the last three bits of $Hw$ are the binary encoding of the position of the error. Finally, if the received word has even weight but is not a codeword, then $Hw$ will not equal $0000$ but its first bit will not be set. The decoder will then report a noncorrectable error.

Will Orrick
  • 18,220