Error correction source code ?

Do you have a question? Post it now! No Registration Necessary

Translate This Thread From English to

Threaded View
Hello all,
I'm looking for efficient & quick error correction algorithms, adequate for
RF transmission of short messages (some tens of bytes). Correction of 1-2
wrong bits would be enough. Any tested source code routines around ?
Cheers,
Robert



Re: Error correction source code ?

Quoted text here. Click to load it
for
Hamming codes (as used by Teletext) might suit as they are quick to encode
and decode. A (7, 4) Hamming code lets you correct one bit in four and
detect two errored bits. The disadvantage is that it doubles the amount of
data that is sent (or received). If the data are interleaved too, then it
can reduce the effects of burst noise.

More efficient error correction algorithms, like Reed-Solomon, require more
calculation.

    Andrew



Re: Error correction source code ?
By author:    "Robert Lacoste" <see-www-alciom-com-for-email-adress>
In newsgroup: comp.arch.embedded
Quoted text here. Click to load it

You're not saying what computation engine you have available.  This
can make a huge difference in terms of what can be considered
"efficient and quick"; e.g. modern microprocessors can do cheap
multiplication whereas microcontrollers typically can't.  If you have
1K of memory a 256-byte table is not an option, but if you have a 4 MB
system it's a drop in the bucket.  If you have an FPGA or a DSP chip
involved some things get completely different, etc.

Another data point which would be useful is how much overhead you're
willing to tolerate, and the exact number of bits you care about
(actually knowing the bit error rate expected and desired would be
golden.)  It also helps to know if your noise model is random or
bursty (and if so, what are the expected burst lengths), since bursty
errors generally require slightly different algorithms.

Hamming codes have already been mentioned; a 64-bit Hamming code with
an 8-bit syndrome will correct any one bit and detect a 2-bit error.
It gives you 8 bytes of data for the price of 9.  Hamming codes are
bad if you have bursty errors, unless you interleave multiple
instances.

    -hpa



Re: Error correction source code ?
Quoted text here. Click to load it
Encoders need only do the syndrome calculation.
Decoders have to do the syndrome calculation and then
get out of it the error pattern.
The fastest way to do that are tables ( ROM ), less memory
consumption have algorithms like Meggitt but they are much
slower.
For a Mitsubishi-6502 ( bus = 2,45 MHz ):
(15,9) burst error correction ; 3 bit burst ;
       ROM-decoder:
       code 150 bytes ; table 128 bytes ; encoder/decoder each 250usec
(15,8) shortned burst error correction ; 3 bit burst ;
       ROM-decoder:
       code 150 bytes ; table 64 bytes ; encoder/decoder each 250usec
(23,12) Golay ; 3 bit
       ROM-decoder:
       code 230 bytes ; table 4k byte ; encoder/decoder each 500usec
       ( there are tables with 3k and two tables 2,5k possible that
            are not much slower )
       systematic search decoder:
       code 450 bytes ; decoder 0,6 - 90msec        
(31,21) BCH ; 2 bit
       code ? bytes ; table 4k byte ; decoder 600usec ( on a
                              68HC908 bus = 2,45MHz )
Golay and the BCH(31,21) have been used for pagers.

Notation:
(31     : data + parity = 31 bits
   ,21) : data = 21 bits
"3 bit" means the flipped bits may be anywhere.
"3 bit burst" the 1 - 3 bits have to be consecutive bits.

A more detailed description and code can be found at
http://www.embeddedFORTH.de
but text is in german and some of the code is FORTH.

MfG  JRD

Re: Error correction source code ?
Many thanks ! Now I just need to remember how to read Forth...

Quoted text here. Click to load it



Re: Error correction source code ?
Take a look at:
http://www.eccpage.com /

Randy Haas

Site Timeline