3
$\begingroup$

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?

$\endgroup$

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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 !! :) $\endgroup$
    – Loraloper
    Commented Nov 1, 2013 at 11:47
  • $\begingroup$ 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. $\endgroup$ Commented Nov 1, 2013 at 13:58
1
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Loraloper
    Commented Nov 1, 2013 at 10:46
  • $\begingroup$ @Loraloper see the matrix. $\endgroup$ Commented Nov 1, 2013 at 11:20
  • $\begingroup$ 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? $\endgroup$
    – Loraloper
    Commented Nov 1, 2013 at 11:21
  • $\begingroup$ 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.. $\endgroup$ Commented Nov 1, 2013 at 11:43
  • $\begingroup$ Does the extended stratifies the Hamming bound ? $\endgroup$
    – Maman
    Commented Feb 23, 2017 at 22:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .