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.

I have a sequence of bits $$ 111011011110 $$ and need to detect two errors(without correction) using Hamming codes. Hamming codes contain a control bit in each $2^n$ position. Hence I should put this control bits in their positions.

$$ 0010110011011110 $$

I've found a simple explanation of how to count the code for a sequence of bits. It says that each control bit responds for the following bits using these rules: First control bit responds for $2^n$ position and each following bit through $2^n$ . So the first bit responds for the first, third, fifth and etc. bits. The second control bit responds for 2nd, 3rd, 6th, 7th, 10th, 11th and etc. bits. Third control bit(which is on the 4th position) responds for 4th, 5th, 6th, 7th, 12th, 13th etc. bits. And so on. The value of each of the controls bits is counted as a modulo sum of the bits, which this control bit responds for.

Here is an illustration of what I mean:

enter image description here

Assuming this rule is right, the last 16th bit(after control bits addition) is not under the responsibility of any of the control bits.

So the question is: How can I detect double error(only detect, not correct) for the given sequence of bits using the Hamming code?

share|improve this question
    
Your diagram seems to indicate a new codeword starts at position $16$ since the pattern repeats,. Thus, the first $15$ bits include $4$ parity bits (using the nomenclature that is standard in coding theory will help get better answers), and so you have what is called a $[15,11]$ Hamming code. There is no way of detecting that two errors with this code. In order to detect two errors, you need to modify your scheme so that the $16$th bit is a parity check on _all_ $15$ previous bits (including the parity bits at positions $1,2,4,8$, and the next codeword starts at position $17$. –  Dilip Sarwate Apr 17 '13 at 11:41
    
@Dilip, the code whose parity check matrix is the $4\times15$ matrix whose columns are all the nonzero 4-bit strings --- isn't that the $[15,11]$ Hamming code? And isn't its minimal distance $3$? So it should be able to detect (though not correct) $2$ errors, right? –  Gerry Myerson Apr 17 '13 at 13:04
2  
@GerryMyerson With a $[15,11]$ Hamming code (more generally, $[2^m-1,2^m-1-m]$ Hamming code) of minimum distance $3$, one can detect that two or fewer errors have occurred. More generally, a code of minimum distance $d$ can detect all patterns of $d-1$ or fewer errors. But if the Hamming code is also being used for error correction simultaneously (which is the most common case in textbooks), then two errors cannot be detected; the decoder will think it is a single error, and the decoder output will be the wrong codeword. (continued) –  Dilip Sarwate Apr 17 '13 at 13:33
3  
@GerryMyerson Yes, and that can be interpreted as saying "I want to detect that two errors have occurred, only detect, not correct..." and that is not possible with the Hamming code. One can detect that the received word is not a valid codeword and so one or more errors have occurred, but one cannot say in which instances of invalid received words two errors have occurred and in which instances one (or more than two) errors have occurred. All that can be said is that this received word is invalid, and so one or more errors have occurred. –  Dilip Sarwate Apr 18 '13 at 3:10
2  
Chiming in to support Dilip. You need the extended Hamming code with minimum distance four to detect that two errors have occurred. You can then rule out the possibility of a single error by the Hamming codes failure to correct. –  Jyrki Lahtonen Apr 18 '13 at 11:39
show 7 more comments

2 Answers

up vote 1 down vote accepted

As discussed, you cannot find out if exactly two errors appeared: The Hamming code is a perfect code of minimum distance $3$. Thus, if you have a codeword $c$ which after two errors is transmitted as the codeword $e$, there is always another codeword $c'$ with differs from $e$ only in a single position (since in the perfect Hamming code, the Hamming balls of radius $1$ centered at the codewords cover the Hamming space).

For detecting if a transmitted word $e$ is erroneous, you can apply the standard method for linear codes: Take a parity-check matrix $H$ of the Hamming code. Then compute the product $He$. If it is not the zero vector, you know for sure that $e$ is not a codeword, which means that there is at least one error. By the minimum distance $3$ of the Hamming code, you will detect all cases where a single or two errors appeared (but you don't know the exact number), and some of the cases with more errors.

share|improve this answer
    
that explanation worked fine. Thank you! –  innocent_rifle Apr 24 '13 at 9:49
add comment

This is handled well by Wikipedia, which states:

Hamming codes have a minimum distance of 3, which means that the decoder can detect and correct a single error, but it cannot distinguish a double bit error of some codeword from a single bit error of a different codeword. Thus, they can detect double-bit errors only if correction is not attempted.

To remedy this shortcoming, Hamming codes can be extended by an extra parity bit.

share|improve this answer
3  
While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. –  Lord_Farin Apr 19 '13 at 14:08
1  
@user73324: This is good information. It would be better to add this to the answer than in a comment. –  robjohn Apr 19 '13 at 20:30
add comment

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.