The key thing about Hamming Codes that can be seen from visual inspection is that any given bit is included in a unique set of parity bits. To check for errors, check all of the parity bits. The pattern of errors, called the error syndrome, identifies the bit in error. If all parity bits are correct, there is no error. Otherwise, the sum of the positions of the erroneous parity bits identifies the erroneous bit. For example, if the parity bits in positions 1, 2 and 8 indicate an error, then bit 1+2+8=11 is in error. If only one parity bit indicates an error, the parity bit itself is in error.
When checking for errors the following applies:
From the wiki page on hamming codes:
The decoder simply recalculates the parity on the received data and also XORs in the received parity. If there is an error the result is a 1 since XOR of identical bits results in a 0. Given the parity bits represent the binary positions if you add up the parity positions you end up with the bit that was flipped, since the parity are at binary bit positions they can just be concatenated to produce the error position.
See the following example tutorial to get a more detailed explanation.
Hi,
I read the link that you attached. But in that, it says if a parity bit gets corrupted we dont care about it. I actually want to take care of parity bits as well. I dont want parity bits to get corrupted.
I already said it can and how it is done, but I'm not going to go write the code for you.So can a SECDED code decoder take care of just detecting an error in the parity bit?
That is referring to decoding to get the original data back without the inserted parity.* in this case I corrupted a data bit - if a parity bit gets corrupted there’s no need to correct anything, we only care about the data bits.
I already said it can and how it is done, but I'm not going to go write the code for you.
Once again XOR the received data bits (the ones used to generate the transmitted parity) and the received parity. (rows of Xs for parity bit coverage on wiki page)
Result = 1, there is an error in either in a data bit or the parity bit
Result = 0, no error
Do that for each received parity bit, this generates an error syndrome.
e.g. using the table on the wiki page
suppose parity p1 and p2 both turn out correct and p4 shows an error, then the error syndrome is 0b100, which is 4 which is where the parity bit p4 is located, so only the parity is flipped.
If say p1 and p4 are both showing an error then the error syndrome is 101 and it is data bit d2 that is flipped.
The decoding finds any single bit error in either the parity or the data using the error syndrome, which you can use to correct (flip) that bit.
- - - Updated - - -
FYI you were reading too much into the statement:
That is referring to decoding to get the original data back without the inserted parity.
And just to be clear, this will work with SECDED implementation as well, correct?
Thanks
To decode the [8,4] Hamming code, first check the parity bit. If the parity bit indicates an error, single error correction (the [7,4] Hamming code) will indicate the error location, with "no error" indicating the parity bit. If the parity bit is correct, then single error correction will indicate the (bitwise) exclusive-or of two error locations. If the locations are equal ("no error") then a double bit error either has not occurred, or has cancelled itself out. Otherwise, a double bit error has occurred.
Understood. I just want to detect an error in my parity bit, I do not want to correct it. So I am guessing this works. Also, when I test my code by changing one bit of parity, my final syndrome happens to give me the correct parity by indicating there is one error. So isn't that in some way correcting of the parity bit (in the case when all data bits are transmitted correctly)?
Thanks
Understood. I just want to detect an error in my parity bit, I do not want to correct it. So I am guessing this works. Also, when I test my code by changing one bit of parity, my final syndrome happens to give me the correct parity by indicating there is one error. So isn't that in some way correcting of the parity bit (in the case when all data bits are transmitted correctly)?
It is hard to understand what you want.
A Hamming Code makes no difference between data bits and parity bits regarding error correction. It will correct any single bit error and detect any double bit error. It doesn't matter if the error(s) is in the data bits or in the parity bits.
When you receive a code word, you must process all received bits to detect/correct errors. It is not possible to check only the parity bits.
std_match, you didn't read back far enough in the thread. The OPs intention is to correct the hamming encoded word so they can transmit it further without having to decode then encode again. Not sure what kind of system this is but it almost seems like some kind of node based system where any hop could introduce a bit error and they want to avoid the overhead of repeatedly re-encoding the parity prior to transmitting to the next node. Instead they will fix any single bit error in the data or parity and send the "refreshed" code word.
Why are you discussing bit errors in the syndrome?
The syndrome is not what has bit errors, the data+parity+overall+parity is what has a bit error that can be corrected by calculating an error syndrome on the received data+parity+overall_parity word. The error syndrome is used to determine where the error is to correct it. This correction is not restricted to only one type of bit, any of the bits can be corrected including the overall parity bit.
From all indications I don't think you thoroughly understand the contents of the Wiki page or the example link yet. I think you need to work this out using say the hamming (8,4) code as it is reasonable to work out a bunch of possible scenarios and really understand how the hamming codes works and how you detect and correct errors. Doing it in a spreadsheet is probably the easiest most interactive way to do this.
That is the computed syndrome is the parity calculation (done in the encoder) XOR'd with the received parity.However, in a general case we won’t know which bit is corrupted…so here’s how these parity bits become useful. We use them to create the sindrome, so we arrange these bits like this:
P8P4P2P1
We use cookies and similar technologies for the following purposes:
Do you accept cookies and these technologies?
We use cookies and similar technologies for the following purposes:
Do you accept cookies and these technologies?