debugMinor
Hamming code -- identical parity bits for different errors
Viewed 0 times
bitsidenticalparitydifferentforcodeerrorshamming
Problem
(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.
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.
Solution
When we say that a Hamming code detects (up to) 2 errors and can correct 1, we mean just that:
-
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.
-
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.
-
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.
-
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.
Context
StackExchange Computer Science Q#47491, answer score: 3
Revisions (0)
No revisions yet.