Post by thread:[PIC] Hamming ECC again... In C, this time

Just wrote this for a friend who needed to do simple error- correction. I've previously posted (4,7) Hamming encode/decode routines in assembly language, but he needed it in C, so... It's two small tables and two lines of code. Maybe someone else will find it useful. const uint8 encode[16] = {0x00, 0x31, 0x52, 0x63, 0x64, 0x55, 0x36, 0x07, 0x78, 0x49, 0x2A, 0x1B, 0x1C, 0x2D, 0x4E, 0x7F} const uint8 fixbits[8] = {0x00, 0x90, 0xA0, 0x81, 0xC0, 0x82, 0x84, 0x88} uint8 transmit(uint8 x) { return encode[x]; } uint8 receive(uint8 x) { return x ^ fixbits[(encode[x & 0x0F] ^ x) >> 4]; } The transmit() function takes as input a 4-bit number (0x00-0x0F) and returns a 7-bit codeword (original input unchanged in bits 0-3, three check bits in bits 4-6, and bit 7 clear). The receive() function takes as input a 7-bit codeword (0x00-0x7F) with up to two errors. If the codeword contains no errors, the function returns the codeword unchanged (original data in bits 0-3, correct check bits in bits 4-6, bit 7 clear). If the codeword contains one error, the function returns a corrected codeword (original data in bits 0-3, correct check bits in bits 4-6, but bit 7 set to indicate that an error was detected). If the codeword contains two errors, the function returns garbage in bits 0-6, but with bit 7 set to indicate that an error was detected. -Andy === Andrew Warren - spam_OUTfastfwdTakeThisOuTix.netcom.com

{Quote hidden}>-----Original Message----- >From: .....piclist-bouncesKILLspam@spam@mit.edu [piclist-bouncesKILLspammit.edu] >Sent: 07 April 2005 03:15 >To: microcontroller discussion list - Public. >Subject: [PIC] Hamming ECC again... In C, this time > > >Just wrote this for a friend who needed to do simple error- >correction. I've previously posted (4,7) Hamming encode/decode >routines in assembly language, but he needed it in C, so... > >It's two small tables and two lines of code. Maybe someone else will >find it useful. > > const uint8 encode[16] = {0x00, 0x31, 0x52, 0x63, > 0x64, 0x55, 0x36, 0x07, > 0x78, 0x49, 0x2A, 0x1B, > 0x1C, 0x2D, 0x4E, 0x7F} > > const uint8 fixbits[8] = {0x00, 0x90, 0xA0, 0x81, > 0xC0, 0x82, 0x84, 0x88} > > uint8 transmit(uint8 x) > { > return encode[x]; > } > > uint8 receive(uint8 x) > { > return x ^ fixbits[(encode[x & 0x0F] ^ x) >> 4]; > } > >The transmit() function takes as input a 4-bit number (0x00-0x0F) and >returns a 7-bit codeword (original input unchanged in bits 0-3, three >check bits in bits 4-6, and bit 7 clear). > >The receive() function takes as input a 7-bit codeword (0x00-0x7F) >with up to two errors. If the codeword contains no errors, the >function returns the codeword unchanged (original data in bits 0-3, >correct check bits in bits 4-6, bit 7 clear). If the codeword >contains one error, the function returns a corrected codeword >(original data in bits 0-3, correct check bits in bits 4-6, but bit 7 >set to indicate that an error was detected). If the codeword >contains two errors, the function returns garbage in bits 0-6, but >with bit 7 set to indicate that an error was detected. > >-Andy That's been added to my usefull code snippets collection, thanks for posting! Maybe a stupid question, but if bit 7 is set after calling receive(), how would you tell if the data had been corrected or was garbage? Regards Mike ======================================================================= This e-mail is intended for the person it is addressed to only. The information contained in it may be confidential and/or protected by law. If you are not the intended recipient of this message, you must not make any use of this information, or copy or show it to any person. Please contact us immediately to tell us that you have received this e-mail, and return the original to us. Any use, forwarding, printing or copying of this message is strictly prohibited. No part of this message can be considered a request for goods or services. =======================================================================

Wow... That is clean... --- James. {Quote hidden}> -----Original Message----- > From: .....piclist-bouncesKILLspam.....mit.edu > [EraseMEpiclist-bouncesspam_OUTTakeThisOuTmit.edu] On Behalf Of Andrew Warren > Sent: 2005 Apr 06, Wed 19:15 > To: microcontroller discussion list - Public. > Subject: [PIC] Hamming ECC again... In C, this time > > Just wrote this for a friend who needed to do simple error- > correction. I've previously posted (4,7) Hamming > encode/decode routines in assembly language, but he needed it > in C, so... > > It's two small tables and two lines of code. Maybe someone > else will find it useful. > > const uint8 encode[16] = {0x00, 0x31, 0x52, 0x63, > 0x64, 0x55, 0x36, 0x07, > 0x78, 0x49, 0x2A, 0x1B, > 0x1C, 0x2D, 0x4E, 0x7F} > > const uint8 fixbits[8] = {0x00, 0x90, 0xA0, 0x81, > 0xC0, 0x82, 0x84, 0x88} > > uint8 transmit(uint8 x) > { > return encode[x]; > } > > uint8 receive(uint8 x) > { > return x ^ fixbits[(encode[x & 0x0F] ^ x) >> 4]; > } > > The transmit() function takes as input a 4-bit number > (0x00-0x0F) and returns a 7-bit codeword (original input > unchanged in bits 0-3, three check bits in bits 4-6, and bit > 7 clear). > > The receive() function takes as input a 7-bit codeword > (0x00-0x7F) with up to two errors. If the codeword contains > no errors, the function returns the codeword unchanged > (original data in bits 0-3, correct check bits in bits 4-6, > bit 7 clear). If the codeword contains one error, the > function returns a corrected codeword (original data in bits > 0-3, correct check bits in bits 4-6, but bit 7 set to > indicate that an error was detected). If the codeword > contains two errors, the function returns garbage in bits 0-6, but > with bit 7 set to indicate that an error was detected. > > -Andy > > === Andrew Warren - fastfwdspam_OUTix.netcom.com > > -

Michael Rigby-Jones <@spam@piclistKILLspammit.edu> wrote: > > Just wrote this for a friend who needed to do simple error- > > correction. > > That's been added to my usefull code snippets collection, thanks for > posting! Maybe a stupid question, but if bit 7 is set after calling > receive(), how would you tell if the data had been corrected or was > garbage? Mike: Not a stupid question at all. The answer is... You don't; you can use the code to correct one-bit errors OR you can use it to detect one- and two-bit errors. You can't do both, because a two-bit error in one codeword can look identical to a one-bit error in another. For example: From the encode[] array, you can see that the codeword for "0000" is 0000 0000, and the codeword for "0001" is 0011 0001. If we receive 0011 0000, is that: 0011 0001 with a one-bit error in bit 0, or 0000 0000 with an error in both bit 4 and bit 5? -Andy === Andrew Warren - KILLspamfastfwdKILLspamix.netcom.com

In message <RemoveME42543516.8095.63A48DTakeThisOuTgeneric.my-fqdn.de>> "Andrew Warren" <spamBeGonefastfwdspamBeGoneix.netcom.com> wrote: > Just wrote this for a friend who needed to do simple error- > correction. I've previously posted (4,7) Hamming encode/decode > routines in assembly language, but he needed it in C, so... Nicely done.. Only one thing though: > const uint8 fixbits[8] = {0x00, 0x90, 0xA0, 0x81, > 0xC0, 0x82, 0x84, 0x88} > > uint8 receive(uint8 x) > { > return x ^ fixbits[(encode[x & 0x0F] ^ x) >> 4]; > } You're declaring fixbits as an 8-byte array. That means your array elements are numbered 0 to 7. Now, if x = 10 (say), because you're ANDing by 0x0F (to get the low nibble), this code will try and get the low 4 bits (range 0-15), meaning it'll try and get entry 10 from fixbits[8]. Which doesn't exist. End result? The program jumps off into never-never land. If I'm right (not sure if I am or not...) then this line: return x ^ fixbits[(encode[x & 0x0F] ^ x) >> 4]; should be changed to return x ^ fixbits[(encode[x & 0x07] ^ x) >> 4]; (change: ^^^^^^) I'll have a quick look at the code later... it looks like it'll compile under gcc on Linux pretty painlessly. Later, -- Phil. | Acorn Risc PC600 Mk3, SA202, 64MB, 6GB, TakeThisOuTphilpemEraseMEspam_OUTphilpem.me.uk | ViewFinder, 10BaseT Ethernet, 2-slice, http://www.philpem.me.uk/ | 48xCD, ARCINv6c IDE, SCSI ... "Bother", said Pooh, as he accidentally deleted his message base.

Philip Pemberton <RemoveMEpiclistTakeThisOuTmit.edu> wrote: > Nicely done.. Only one thing though: > > > const uint8 fixbits[8] = {0x00, 0x90, 0xA0, 0x81, > > 0xC0, 0x82, 0x84, 0x88} > > > > uint8 receive(uint8 x) > > { > > return x ^ fixbits[(encode[x & 0x0F] ^ x) >> 4]; > > } > > You're declaring fixbits as an 8-byte array. That means your array > elements are numbered 0 to 7. Now, if x = 10 (say), because you're > ANDing by 0x0F (to get the low nibble), this code will try and get the > low 4 bits (range 0-15), meaning it'll try and get entry 10 from > fixbits[8]. Which doesn't exist. End result? The program jumps off > into never-never land. Phil: You've misread my code. If x = 10, then the code will try to get entry 10 from the encode[16] array, not from the fixbits[8] array. Since all the entries in the encode[] array have bit 7 cleared to 0, and x also has bit 7 cleared to 0, the "^x" will leave bit 7 cleared, and the ">> 4" is guaranteed to produce a number in the range 0-7... And it's THAT number that gets used as an index into the fixbits[8] array. -Andy === Andrew Warren - fastfwdEraseME.....ix.netcom.com

James Newtons Massmind <EraseMEpiclistmit.edu> wrote: > > you can use the code to correct one-bit errors OR you can use it > > to detect one- and two-bit errors. You can't do both, because a > > two-bit error in one codeword can look identical to a one-bit > > error in another. > > I take it that one could not set bit 7 only when there is a > non-correctable error? Correct, James. With my simple Hamming code, it's impossible to differentiate between a correctable one-bit error and a non- correctable two-bit error (or, for that matter, between zero errors and three errors). -Andy === Andrew Warren - RemoveMEfastfwdEraseMEEraseMEix.netcom.com

> Correct, James. With my simple Hamming code, it's impossible > to differentiate between a correctable one-bit error and a > non- correctable two-bit error (or, for that matter, between > zero errors and three errors). Still and all, when bit 7 is set, you know there was an error and the data may, or may not be corrected. A single bit error will always be detected (and corrected) and the percentage chance that a multibit error could get through undetected is next to nothing. A very nice thing to have. --- James.

James Newtons Massmind wrote: and quoted Andy: {Quote hidden}>>Correct, James. With my simple Hamming code, it's impossible >>to differentiate between a correctable one-bit error and a >>non- correctable two-bit error (or, for that matter, between >>zero errors and three errors). > > > Still and all, when bit 7 is set, you know there was an error and the data > may, or may not be corrected. A single bit error will always be detected > (and corrected) and the percentage chance that a multibit error could get > through undetected is next to nothing. I'm not exactly sure how you're wanting to use bit 7, James, but perhaps a slight improvement over the Hamming (4,7) algorithm is a "Hamming (4,8)" algorithm, which AFAIK does not exist. In the (4,7) algorithm, the 4 data bits are assigned the hamming indices of 3,5,6, and 7. It'd be instructive (read: I think it'd work but am too lazy to verify) to experiment with hamming indices of 3, 5, 10 and 12. These indices require 4 bits - hence the data plus hamming code take a total of 8 bits (and you get to use/waste bit 7!). What's interesting about the indices I've suggested is that they all have two binary 1's. All encodings are at least 3-hamming bits apart. I *think* this implies that you can distinguish between a correctable 1-bit error and an (uncorrectable) 2-bit error. Many 3-bit errors are detectable. BTW, the 16 possible encodings are: 00 31 52 63 A4 95 F6 C7 C8 F9 9A AB 6C 5D 3E 0F This is analogous to Andy's encode[] array. Generating the analogous fixbits requires more effort than I'm willing to expend at the moment. I can say that the lower nibble of indices 0,3,5,10 and 12 should be 0,1,2,4 and 8 respectively. The other indices of fixbits need to deal with multi-bit errors. All 2-bit errors are detectable, but I'm pretty sure they're not all correctable. For example, a 31 transmitted as a 38 can be detected as an error and possibly be corrected by xoring the 38 with a '9'. This would occupy the last index in the fixbit array (since (encode[8]^0x39)>>4 is 0x0f. However, something like a 52 transmitted as a 54 requires the same position in the fixbit array, but the correction of a '9' applied to 54 would be wrong... Anyway, my conclusion based on this very meager analysis is that a Hamming (4,8) encoding doesn't buy anything more than the Hamming (4,7) encoding. Perhaps there are fewer 3-bit errors that are misinterpreted as valid data with the (4,8), but I don't know. Or perhaps there are a better choice of hamming indices, but I don't know that either. Scott

Scott Dattalo <RemoveMEscottspam_OUTKILLspamdattalo.com> wrote: > I'm not exactly sure how you're wanting to use bit 7, James, but > perhaps a slight improvement over the Hamming (4,7) algorithm is > a "Hamming (4,8)" algorithm, which AFAIK does not exist. It's been a few decades since I last delved into this for the design of ECC-based memory systems, but one thing I do remember is that you can always convert a single-error-correcting Hamming code into a SECDED code (single error correcting, double error detecting) by adding a parity bit. The theory is this: All valid code words are (a minimum of) Hamming distance 3 apart. Any single-bit error is distance one from a valid word, and the correction algorithm converts the received word to the nearest valid one. If a double error occurs, the parity of the word is not affected, but the correction algorithm still corrects the received word, which is distance two from the original valid word, but distance one from some other valid (but wrong) word. It does this by flipping one bit, which may or may not be one of the erroneous bits. Now the word has either one or three bits flipped, and the original double error is now detected by the parity checker. Note that this works even when the parity bit itself is involved in a single-bit or double-bit error. It isn't hard to work out all the combinations. -- Dave Tweed

>-----Original Message----- >From: RemoveMEpiclist-bouncesTakeThisOuTspammit.edu [EraseMEpiclist-bouncesspamspamBeGonemit.edu] >Sent: 08 April 2005 00:10 >To: 'Microcontroller discussion list - Public.' >Subject: RE: [PIC] Hamming ECC again... In C, this time > > >> Correct, James. With my simple Hamming code, it's impossible >> to differentiate between a correctable one-bit error and a >> non- correctable two-bit error (or, for that matter, between >> zero errors and three errors). > >Still and all, when bit 7 is set, you know there was an error >and the data may, or may not be corrected. A single bit error >will always be detected (and corrected) and the percentage >chance that a multibit error could get through undetected is >next to nothing. > >A very nice thing to have. Agreed. I suppose the addition of a checksum at the end of a data packet would allow you to essentialy ignore bit 7. If any single bit errors have been corrected, the checksum will match. A little more overhead, but with Scott et al's equally cunning CRC functions it won't be a great deal. I'm planning on having a play with some of the cheap wireless modules sometime soon, this sounds perfect for a simple error correction scheme. Regards Mike ======================================================================= This e-mail is intended for the person it is addressed to only. The information contained in it may be confidential and/or protected by law. If you are not the intended recipient of this message, you must not make any use of this information, or copy or show it to any person. Please contact us immediately to tell us that you have received this e-mail, and return the original to us. Any use, forwarding, printing or copying of this message is strictly prohibited. No part of this message can be considered a request for goods or services. =======================================================================