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

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.