Searching \ for '[PIC] Hamming ECC again... In C, this time' in subject line. ()
Make payments with PayPal - it's fast, free and secure! Help us get a faster server
FAQ page: www.piclist.com/techref/microchip/time.htm?key=time
Search entire site for: 'Hamming ECC again... In C, this time'.

Exact match. Not showing close matches.
PICList Thread
'[PIC] Hamming ECC again... In C, this time'
2005\04\06@221329 by Andrew Warren

face
flavicon
face
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_OUTfastfwdTakeThisOuTspamix.netcom.com

2005\04\07@040504 by Michael Rigby-Jones

picon face


{Quote hidden}

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.
=======================================================================

2005\04\07@041755 by Alan B. Pearce

face picon face
>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).

Now that would make an interesting way to obfuscate a hex download for a
bootloader :))))

2005\04\07@142112 by James Newtons Massmind

face picon face
Wow... That is clean...

---
James.



{Quote hidden}

> -

2005\04\07@151700 by Andrew Warren
face
flavicon
face
Michael Rigby-Jones <@spam@piclistKILLspamspammit.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 - KILLspamfastfwdKILLspamspamix.netcom.com

2005\04\07@165636 by James Newtons Massmind

face picon face
> 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.
>

I take it that one could not set bit 7 only when there is a non-correctable
error?

---
James.



2005\04\07@171059 by Philip Pemberton

face picon face
In message <RemoveME42543516.8095.63A48DTakeThisOuTspamgeneric.my-fqdn.de>>          "Andrew Warren" <spamBeGonefastfwdspamBeGonespamix.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,
TakeThisOuTphilpemEraseMEspamspam_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.

2005\04\07@172920 by Andrew Warren

face
flavicon
face
Philip Pemberton <RemoveMEpiclistspamTakeThisOuTmit.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 - fastfwdEraseMEspam.....ix.netcom.com

2005\04\07@173542 by Andrew Warren

face
flavicon
face
James Newtons Massmind <EraseMEpiclistspammit.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 - RemoveMEfastfwdEraseMEspamEraseMEix.netcom.com

2005\04\07@191018 by James Newtons Massmind

face picon face
> 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.



2005\04\07@212713 by Scott Dattalo

face
flavicon
face
James Newtons Massmind wrote:

 and quoted Andy:

{Quote hidden}

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

2005\04\07@234524 by Dave Tweed

face
flavicon
face
Scott Dattalo <RemoveMEscottspam_OUTspamKILLspamdattalo.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

2005\04\08@042143 by Michael Rigby-Jones

picon face


>-----Original Message-----
>From: RemoveMEpiclist-bouncesTakeThisOuTspamspammit.edu [EraseMEpiclist-bouncesspamspamspamBeGonemit.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.
=======================================================================

More... (looser matching)
- Last day of these posts
- In 2005 , 2006 only
- Today
- New search...