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

Followup to: By author: "Robert Lacoste" 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

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

but text is in german and some of the code is FORTH.

MfG JRD

Many thanks ! Now I just need to remember how to read Forth...

"Rafael Deliano" a écrit dans le message de news: snipped-for-privacy@t-online.de...

Take a look at:

Randy Haas