Do you have a question? Post it now! No Registration Necessary
- Subject
- Posted on
- Error correction source code ?
- 09-24-2004
Re: Error correction source code ?
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
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
In newsgroup: comp.arch.embedded
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 ?
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
Site Timeline
- » Reverse current into a lithium battery
- — Next thread in » Embedded Programming
- » Flash memory application
- — Previous thread in » Embedded Programming
- » No Ethernet on RCM6750 after porting code from 5750
- — Newest thread in » Embedded Programming
- » Wifi and wired not talking
- — The site's Newest Thread. Posted in » Raspberry Pi Group