error correcting codes aimed at slow CPUs transmitting to fast CPUs

Question

I'm looking for a forward error-correcting code that is relatively easy/fast to encode on a microcontroller; decode will be done on a PC so it can be more complicated.

I don't know that much about error-correcting codes and except for the simple Hamming codes they seem to all be more complicated than I can handle.

Any recommendations?

edit: I'm going to cut things short and accept Carl's answer... I guess there were two things I didn't mention:

(1) I don't strictly need the error correction, it's just advantageous for me, and I figured that there might be some error correction algorithm that was a reasonable benefit for a minimal cost. Hamming codes are probably about the right fit and even they seem like they might be too costly for my encoding application.

(2) The greater advantage than the error correction itself is the ability to resync properly to packets that follow an error. (if I get out of sync for a long time, that's bad) So I think it's just better if I keep things simple.

Answer 1

The problem with error correcting codes is that they'll let you recover from single bit or maybe 2 bit errors, but usually not detect or patch up major damage.

Thus, my recommendation would be instead to divide your data streams up into blocks (1 KB, 10 KB, ... 1 MB at most) and calculate a checksum for each block. Then, when the data arrives on the other CPU, you can ascertain whether it is correct and request retransmission of that block if not. So the receiving computer would either acknowledge and wait for the next block, or negative-acknowledge and expect a re-send.

Yes, we're implementing a subset of TCP/IP here. But there's a reason this protocol was so successful: It works!

For a checksum, I'd recommend CRC-32. It requires a table of (I think) 256 32-bit numbers and some reasonably easy computation (array indexing, OR and XOR, mostly) so it's fairly easy for a "dumb" CPU to compute.

Answer 2

http://en.wikipedia.org/wiki/Low-density%5Fparity-check%5Fcode

or probably better

http://en.wikipedia.org/wiki/Turbo%5Fcode

Answer 3

I haven't quite gotten straight how much overhead you can afford. In your comment you say a 16-bit error detection/correction code is about right, but you don't specify how large of a block you're thinking of attaching that to. To be meaningful, you should probably express the allowable overhead as a percentage. 16 bits of error correction for 64 bits of data is a lot different from 16 bits of error correction of a kilobyte of data..

If you can afford something like 15-20% overhead or so, you can probably use a convolutional code with Viterbi decoder. This is highly assymetrical -- the convolutional coder is quite simple (basically a shift register, with output taps leading to XOR's). A really large one might use a 16-bit register with a half dozen or so XOR's.

Fortunately you have a heavier-duty computer to handle the decoding, because a Viterbi decoder can be a fearsome beast. Especially as you use a larger encoder to reduce the overhead, the size of the decoder explodes. The size of the decoder is exponential with respect to the size of the code group.

Turbo codes were mentioned. These can make better use of available bandwidth than convolutional codes with Viterbi decoders -- but they use a considerably more complex encoder -- a minimum of two convolutional coders of a specific type (recursive systematic convolutional encoders). As such, they don't seem to fit your specification as well.