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?
Best Answer
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.