Continue to Site

Welcome to EDAboard.com

Welcome to our site! EDAboard.com is an international Electronics Discussion Forum focused on EDA software, circuits, schematics, books, theory, papers, asic, pld, 8051, DSP, Network, RF, Analog Design, PCB, Service Manuals... and a whole lot more! To participate you need to register. Registration is free. Click here to register now.

Error in Parity bits of Hamming Code

Status
Not open for further replies.

rrucha

Member level 3
Joined
Jul 17, 2019
Messages
66
Helped
0
Reputation
0
Reaction score
0
Trophy points
6
Activity points
675
Parity bits are inserted in between data in Hamming Code. While transmission from sender to receiver, it could so happen that along with the data bits (or even without the data bits getting affected) the parity bit could flip. Usually on the receiver side, we only check if the data got transmitted correctly or not. I want to check if my parity bits were transmitted correctly if there was an error in transmission. Is there any way to do this?
 

When checking for errors the following applies:

From the wiki page on hamming codes:
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:

Hi,

Thanks for the reply. There could be a case when our data is intact and correct but one of our parity bit flipped. So when we compare the parity bits, how do we know that the data is transmitted correctly and its the parity bit thats under an issue? How do we implement this while we code the encoder and decoder?
 

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.
 

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.
 

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.

If you XOR the received parity and the receive data that encoded that parity bit then you end up with an error syndrome bit, which just so happens to be 1 if there is an error, if no other parity bit produces an error then the parity bit is in error as parity bits are inserted at binary positions. You have to extrapolate that from how the encode/decode works it's not explicitly stated, but is implied that is what is happening.
 

The parity bits are included in the check as it moves along the bits.
If you mean your original data also has a parity bit, for example in some serial data links, the parity bit would have to be included in the Hamming correction, making a longer result but given that Hamming can only correct single bit errors anyway, I can't see much advantage in doing that.

Brian.
 

And just to be clear, I am working on SECDED, not hamming per se

- - - Updated - - -

Hi Brian,

Thank you for your reply. I am mking use of SECDED. And I want to use only one encoder in my design and the decoder needs to take care of checking if parity bits are correct or incorrect because this information is relayed to further blocks in the design. I do not wish to go on adding encoders at every step. So can a SECDED code decoder take care of just detecting an error in the parity bit?
 

So can a SECDED code decoder take care of just detecting an error in the parity bit?
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:
* 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.
That is referring to decoding to get the original data back without the inserted parity.
 

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.

Hi Ads-ee,

That makes a lot of sense. I was under the impression that if a parity bit is flipped, there will be a confusion whether its the parity bit thats in error or the data bit.
But as you mentioned, if only 1 parity bit is flipped it means the parity is in error. For a data bit to be in error, 2 parity bits need to be flipped. That makes sense now.

And just to be clear, this will work with SECDED implementation as well, correct?

Thanks
 
Last edited:

And just to be clear, this will work with SECDED implementation as well, correct?

Thanks

You can't fix a double bit error so the overall parity won't help you "fix" anything all you can do at that point is detect the error and flag/drop/request-retransmit of the data.

If the overall parity has an error then you check the error syndrome, which will either indicate an error position or no error indicating the overall parity is in error. This is still only correcting a single bit.

This can be found near the bottom of the hamming wiki page
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)?

Thanks

I don't follow what you are tyring to say here.

overall parity correct... may have a doiuble bit error or no error
overall parity incorrect... overall parity is in error (parity bits are correct), a parity or data bit is incorrect.
 

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.
 

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.
 

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.

Exactly!
Update: the given method does not seem to work with SECDED. There is an extra parity bit here that XORs all the data and parity bits. This is causing an issue. I cannot just look at the syndrome and say if 1 of its bit is 1, it means there is a 1-bit error in parity. I noticed here that even if i change 1 bit in parity, there are cases where the syndrome has 2 1-bits. Any idea what can be done? Its SECDED.
 

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.
 

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.

The very first link that you provided (https://codingvision.net/networking/hamming-error-correction-w-example), calls data+parity the syndrome (I am merely talking about the bit stream I get after recalculating the parity by using received data and received parity bits) . Its just nomenclature. I completely understand the concepts of hamming code, otherwise I wouldn't be working on it. I am having trouble with SECDED because there is an extra parity bit here. I encoded and decoded Hamming code in which when I calculate parity bits on decoder side by XORing the received data bits along with the parity; in this case, error in parity is when only one of the parity bits received will be 1.
In case of SECDED, there is an extra parity bit; even though I change a parity bit that I transmit, there are cases where this last parity bit is 1 along with another parity bit. So I devised a way to inidicate this by having different cases: Some of them involving masking of the last parity bit. I just want to know if there is a way to work with detecting parity error in SECDED.

Thanks
 

First of all your statement "The very first link that you provided, calls data+parity the syndrome" is incorrect the linked text reads as follows
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
That is the computed syndrome is the parity calculation (done in the encoder) XOR'd with the received parity.

You seem to be missing the point that the "extra" parity has nothing to do with hamming codes. The extra parity is just that it's an extra parity of the entire hamming code to allow detection of double bit errors. It's applied after hamming parity is computed. It's not included in the syndrome, you use it before you even start decoding.

I've suggested before you should try working this out on paper or in a spreadsheet. Insert a double bit error and see how that affects the overall parity. If you work it out you'll see it immediately...change one bit the overall parity changes now change two bits what will happen?.

To make it easier to determine double bit errors, you might want to play with hsaio codes which are minimum odd weight codes. They have a convenient characteristic in that the double error detect requires just looking at the received computed syndrome and seeing if it has an even number of 1s or not. If there are an even number of 1s there is a double bit error. All single bit errors result in an odd number of parity bits being set.
 
Hi Ads-ee,

Thank you for your reply. Yes, I am doing just that. I am using the code I have and giving it different combinations. I will come up with a conclusion. Thanks for all your help.
 

Status
Not open for further replies.

Part and Inventory Search

Welcome to EDABoard.com

Sponsor

Back
Top