Extended Hamming Code (8,4)

Question

I just finished learning some basic concepts about Hamming code. Now I see this extended Hamming code and they say that you can "detect" up to 3 bits of error. Now, say, my actual codeword was $X=10100011$ and I received $Y=10011011$ (3 bits of error) and my transpose of parity check matrix $H(t)$ is below

  1110
  0111
  1101
  1011
  1000
  0100
  0010
  0001

Now from the rule I understand in (7,4) Hamming code was to compute syndrome which in this case would be S=1111 which is not present in the parity check matrix so that is probably not correct. So, can someone guide me with an example on how to detect 3 bit error per code in (8,4) Hamming code?

Answer 1

Please recheck your calculations. I got $YH^T=1110$, which is also the first row of $H^T$. This means that your $Y$ is within Hamming distance one of the legal codeword $Z=00011011$.

What they mean when they say that a code of minimum distance four can detect it when $\le 3$ bits are in error is the following (does somebody actually phrase it that way? I wouldn't, but that is besides the point here). If the number or bit errors $t$ is in the range $1\le t\le3$, then the received word is guaranteed not to be a legal codeword. And that you can detect by calculating the syndrome (assuming the code is linear). It does not promise that you could ascertain that exactly one, two or three errors occur. The Hamming code has minimum distance three, but any sequence of seven bits is within Hamming distance one from a valid codeword. In other words, the covering radius of the Hamming code is equal to one. The covering radius of the $(8,4)$ extended Hamming code is two meaning that any sequence of 8 bits is within Hamming distance two of a valide codeword. But the Hamming codes are special in this sense. Usually it is difficult to find the covering radius of a code.

To conclude: with the extended Hamming code the best you can do is the following.

-Ccalculate the syndrome of the received word, if its all zeros, then assume that no errors occurred (or the number of errors was at least four) - If the syndrome is non-zero, check whether it is a column of the check matrix (or a row, if you use transpose check matrix). If it is you assume that a single bit was in error, and can correct it. If not, you conclude that some two bits (but you don't know which).

In the case of the extended Hamming code you can always be sure whether the number of errorneous bits was even or odd (can you figure out how?). The usual practice (aka Maximum Likelihood decoding) is to assume that the number of errors is as low as possible, but it may, of course have been higher.

Answer 2

With Hamming codes of minimum distance $d$, you can detect up to $d-1$ errors and correct up to $\lfloor d-1\rfloor/2$. If no errors occur, you will be able to decode the information bits correctly via syndrome decoding. Syndrome decoding will tell you exactly what $4$ information bits are sent. If the syndrome that you calculated does not exit in your parity check matrix then, the codeword that is received should be erroneous.

It seems that increasing the codeword length from $7$ to $8$ increased the minimum distance from $d=3$ to $d=4$ so the maximum number of errors that can be detected are also incread by $1$, which was initially $d-1=2$

$$ \mathrm{H}=\left(\begin{array} 00 \,\, 1\,\, 1\,\, 1\,\,1\,\, 0\,\, 0\,\, 0\\1\,\, 0\,\, 1 \,\, 1\,\,0\,\,1\,\,0\,\,0\\1\,\,1\,\,0\,\,1\,\,0 \,\,0\,\,1\,\,0\\1\,\,1\,\,1\,\,0\,\,0\,\,0\,\,0\,\,1 \end{array} \right)$$