Hamming code -- identical parity bits for different errors

Question

(7,4) Hamming Code (HC) detects all 2-bit errors and corrects all 1-bit errors.

However, there can be 2-, 3- or 4-bit errors that come with the same parity bits as that of 1-bit errors.

Eg.: Let the data be $1011$. So - the parity bits are

$P_1=0$

$P_2=1$

$P_4=0$

, the message transmitted is $0110011$ and the message received is $1000011$.

HC, assuming a 1-bit error, $1000011$ can accurately correct this to the transmitted data, which is $1011$.

But then, suppose the receiver received $1010101$. This has the same parity bits as
$1000011$, and HC, assuming a 1-bit error, would "correct" this as $0101$ which is wrong.

A particular set of parity bits can also hold for 2-, 3- or 4- bit errors.

How does the algorithm handle this?

The possibilities I can think of are:

a.) Takes this as a 1-bit error and just corrects it: in this case, a corrupt bit sequence is transmitted.

b.) corrects it as a 1-bit error, as it does in (a) above, and runs another detection algorithm, say checksum, to make sure.

How does Hamming code work this?

TIA.

Answer 1

When we say that a Hamming code detects (up to) 2 errors and can correct 1, we mean just that:

1. There is an error-detection algorithm that returns NO if there are no errors and returns YES if there are one or two errors. There is absolutely no guarantee when there are more errors.

2. There is an error-correction algorithm that gets a possibly corrupted word and outputs the original codeword, assuming that there was at most one error. There is absolutely no guarantee when there are more errors.

In real life we cannot always guarantee that there are at most X errors in every block, and this is handled by an "outer code", for example the checksum that you mention.

Answer 2

there can be 2-, 3- or 4-bit errors that come with the same parity bits as that of 1-bit errors.

When detecting or correcting an error, the entire 7 bit code word is used, not just the 3 parity bits, so it doesn't matter if different error patterns produce the same 3 parity bits, because the other 4 bits will be different.

the message transmitted is 0110011 and the message received is 1000011.

That's a 3 bit error (the first 3 bits are toggled), and in this case, Hamming code will fail to detect an error, and assume the data is 0011 (instead of 1011).

How does the algorithm handle this?

It doesn't. If using (7,4) Hamming code for error detection, it's only guaranteed to detect a 1 or 2 bit error, and it will detect most but not all 3 or more bit errors. If using Hamming code for error correction, it can only correct a 1 bit error.

A single bit error correction will always produce a code word that appears to have zero errors, but if there was more than 1 bit in error and a single bit correction is done, the single bit correction results in at least 3 bits in error. For example assume 0000011 is received, and it's a 2 bit error that should have been 0000000. A single bit error correction will produce 1000011, resulting in a 3 bit error that appears to have zero errors.

Wiki article:

http://en.wikipedia.org/wiki/Hamming(7,4)

There are 128 possible 7 bit code words. 16 of these are valid code words that appear to have zero errors. The remaining 112 code words have at least 1 bit in error, and as mentioned in the wiki article, (7,4) Hamming code cannot distinguish between single-bit errors and two-bit errors, and fails to detect some patterns with 3 or more bits in error when they map into a valid code word.

The 16 valid code words that appear to have zero errors, in code word order:

data    codeword

0000    0000000
0111    0001111
1110    0010110
1001    0011001
0101    0100101
0010    0101010
1011    0110011
1100    0111100
0011    1000011
0100    1001100
1101    1010101
1010    1011010
0110    1100110
0001    1101001
1000    1110000
1111    1111111

In this set of 16 valid code words, 1 has zero bits set, 1 has all seven bits set, 7 have three bits set and 7 have four bits set. In the set of 112 invalid code words, 7 have one bit set, 7 have 6 bits set, 21 have 2 bits set, 21 have 5 bits set, 28 have three bits set, and 28 have four bits set. Note that at least 3 bits have to be toggled to convert from one of the 16 valid code words to another valid code word, this is referred to as the minimum distance which in this case is 3. This is why (7,4) Hamming code can detect 2 bit errors, because no 2 bit error can result in a valid code word.