+ Post New Thread
Results 1 to 20 of 20

8th August 2019, 21:43 #1
 Join Date
 Jul 2019
 Posts
 66
 Helped
 0 / 0
 Points
 322
 Level
 3
Error in Parity bits of Hamming Code
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?

8th August 2019, 23:36 #2
 Join Date
 Sep 2013
 Location
 USA
 Posts
 7,310
 Helped
 1719 / 1719
 Points
 31,607
 Level
 43
Re: Error in Parity bits of Hamming Code
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.

8th August 2019, 23:50 #3
 Join Date
 Jul 2019
 Posts
 66
 Helped
 0 / 0
 Points
 322
 Level
 3
Re: Error in Parity bits of Hamming Code
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?

9th August 2019, 01:35 #4
 Join Date
 Sep 2013
 Location
 USA
 Posts
 7,310
 Helped
 1719 / 1719
 Points
 31,607
 Level
 43
Re: Error in Parity bits of Hamming Code
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.

Advertisement

9th August 2019, 21:14 #5
 Join Date
 Jul 2019
 Posts
 66
 Helped
 0 / 0
 Points
 322
 Level
 3

9th August 2019, 21:25 #6
 Join Date
 Sep 2013
 Location
 USA
 Posts
 7,310
 Helped
 1719 / 1719
 Points
 31,607
 Level
 43
Re: Error in Parity bits of Hamming Code
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.

9th August 2019, 21:28 #7
Awards:
 Join Date
 Jul 2009
 Location
 Aberdyfi, West Wales, UK
 Posts
 13,349
 Helped
 4456 / 4456
 Points
 81,430
 Level
 69
Re: Error in Parity bits of Hamming Code
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.PLEASE  no friends requests or private emails, I simply don't have time to reply to them all.
It's better to share your questions and answers on Edaboard so we can all benefit from each others experiences.

Advertisement

9th August 2019, 21:41 #8
 Join Date
 Jul 2019
 Posts
 66
 Helped
 0 / 0
 Points
 322
 Level
 3
Re: Error in Parity bits of Hamming Code
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?

9th August 2019, 23:39 #9
 Join Date
 Sep 2013
 Location
 USA
 Posts
 7,310
 Helped
 1719 / 1719
 Points
 31,607
 Level
 43
Re: Error in Parity bits of Hamming Code
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.

Advertisement

12th August 2019, 17:16 #10
 Join Date
 Jul 2019
 Posts
 66
 Helped
 0 / 0
 Points
 322
 Level
 3
Re: Error in Parity bits of Hamming Code
Hi Adsee,
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?
ThanksLast edited by rrucha; 12th August 2019 at 17:32.

12th August 2019, 18:46 #11
 Join Date
 Sep 2013
 Location
 USA
 Posts
 7,310
 Helped
 1719 / 1719
 Points
 31,607
 Level
 43
Re: Error in Parity bits of Hamming Code
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/requestretransmit 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) exclusiveor 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.

12th August 2019, 18:57 #12
 Join Date
 Jul 2019
 Posts
 66
 Helped
 0 / 0
 Points
 322
 Level
 3
Re: Error in Parity bits of Hamming Code
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

12th August 2019, 19:10 #13
 Join Date
 Sep 2013
 Location
 USA
 Posts
 7,310
 Helped
 1719 / 1719
 Points
 31,607
 Level
 43
Re: Error in Parity bits of Hamming Code

12th August 2019, 21:26 #14
 Join Date
 Jul 2010
 Location
 Sweden
 Posts
 996
 Helped
 382 / 382
 Points
 7,460
 Level
 20
Re: Error in Parity bits of Hamming Code
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.

12th August 2019, 23:23 #15
 Join Date
 Sep 2013
 Location
 USA
 Posts
 7,310
 Helped
 1719 / 1719
 Points
 31,607
 Level
 43
Re: Error in Parity bits of Hamming Code
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 reencoding 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.

Advertisement

12th August 2019, 23:36 #16
 Join Date
 Jul 2019
 Posts
 66
 Helped
 0 / 0
 Points
 322
 Level
 3
Re: Error in Parity bits of Hamming Code
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 1bit error in parity. I noticed here that even if i change 1 bit in parity, there are cases where the syndrome has 2 1bits. Any idea what can be done? Its SECDED.

13th August 2019, 00:56 #17
 Join Date
 Sep 2013
 Location
 USA
 Posts
 7,310
 Helped
 1719 / 1719
 Points
 31,607
 Level
 43
Re: Error in Parity bits of Hamming Code
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.

13th August 2019, 17:26 #18
 Join Date
 Jul 2019
 Posts
 66
 Helped
 0 / 0
 Points
 322
 Level
 3
Re: Error in Parity bits of Hamming Code
The very first link that you provided (https://codingvision.net/networking/...tionwexample), 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

13th August 2019, 19:09 #19
 Join Date
 Sep 2013
 Location
 USA
 Posts
 7,310
 Helped
 1719 / 1719
 Points
 31,607
 Level
 43
Re: Error in Parity bits of Hamming Code
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
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.
1 members found this post helpful.

13th August 2019, 19:18 #20
 Join Date
 Jul 2019
 Posts
 66
 Helped
 0 / 0
 Points
 322
 Level
 3
Re: Error in Parity bits of Hamming Code
Hi Adsee,
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.
+ Post New Thread
Please login