# Extended Hamming Code (8,4)

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?

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.

• Wonderful explanation. Yes i recalaclualted YH(trans) and it is 1110. However i am still not sure about how to figure out number of erroneous bit was even or odd? Can you may be provide just a little more insight in tp that. anyways you have provided a very nice explanation i must say and it would be perfect if you can just tell me how to figure out that number erroneous bit was even or odd? Kittos !! :) Nov 1, 2013 at 11:47
• The extended Hamming code has the property that all the legal codewords have an even number of 1s. So if the received word has an odd (resp. even) number of 1s, you can tell at a glance that that an odd (resp. even) number of bit errors has occurred. Nov 1, 2013 at 13:58

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)$$

• Yes i understand what you are saying but what say i get a syndrome s= 1101 which is present in the the matrix so how can i detect that there was a 3 bit error in . I hoe you understand what i am trying to say. It would be very kind if you can post a simple example. Nov 1, 2013 at 10:46
• @Loraloper see the matrix. Nov 1, 2013 at 11:20
• Or just to add one thing if your syndrome is not present in your parity check matrix does that mean that your error is more than 1 bit ? am i right? if yes can i further make a check that weather the error is of 2 bit or 3 bit? Nov 1, 2013 at 11:21
• Error detection tells you only if there is an error or not. It doesnt say how many bits are erroneous. If you want to correct errors it is another story. One can also obtain the syndrome "0000" with a single error occured in the channel.. Nov 1, 2013 at 11:43
• Does the extended stratifies the Hamming bound ? Feb 23, 2017 at 22:17