Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

My question is how far apart must the code words be if i want to DETECT up to 2 bit errors? I read and read but I can't really find anything about error detecting (without correcting)... I am lost, help!

oh and also.. if I have an 8bit message and I need to detect up to 2bit errors, what is the number of additional bits I have to add?

Thanks in advance!

share|improve this question
    
If you are talking about a linear code, then a parity check matrix will always detect up to $d-1$ errors, but it won't be able to distinguish between any of them. Testing the damaged codeword with the parity check will result in "this word isn't a codeword." –  rschwieb Apr 19 '13 at 13:02

2 Answers 2

up vote 1 down vote accepted

Imagine the codewords as red points deparated by their Hamming distance (there will usually be too many dimensions, but it is just a sketch after all). If the code has distance $d$, then they are all at least that far apart, and quite often they are further. Denote remaining possible words by black points, scattered between the codewords.

Now imagine spheres of radius $d-1$ drawn around each codeword. In each sphere, there is exactly only one red point, although many spheres will be overlapping and will share black points.

Pick one of the codewords to pay attention to. Making $d-1$ errors or less will result in one of the black dots in that codeword's sphere. Potentially there is another red dot that is exactly $d$ away from the first codeword, and if you made the $d$ errors necessary to switch the first codeword to the second, then that cluster of errors would be undetectable: after all, it looks like you got a real codeword! So, you can only reliably detect up to $d-1$ errors.

Any more errors might look like no error at all, or it might look like $d-1$ errors from a different codeword. However, you have no way of knowing how many above $d$ occurred.

share|improve this answer

If a code has minimum distance of 3, it means that every 2 errors will be detected. When 3 errors occur, the result may be a valid codeword and thus 3-error patterns are not always detectable.

So you need a code with a minimum distance of 3.

One such code is the shortened Hamming code (n=12, k=8, d=3), derived from the Hamming code (15,11, 3).

Looking at the tables, it seems like given k=8, n=12 is the minimum block length to get the desired Hamming distance (3).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.