Error correcting codes

Question

I need to use an error correcting technique on short messages (between 100 and 200 bits). Space available to add the redundant bits is constrained to 20-50%.

I will have to implement the coding and decoding in C/C++. So it needs to be either open sourced or sufficiently easy to program. (I have had some experience in the past with decoding algorithms - they are dreadful!)

Can anyone advise of a suitable error code to use (with relevant parameters) ?

Answer 1

Take a look at Reed Solomon error correction.

Sample implementation in C++ is available here.

For a different option look here - see item #11

EDIT: If you want a commercial library - http://www.schifra.com/faq.html

Answer 2

Reed-Solomon encoders are described in the form RS(CAPACITY,PAYLOAD). The capacity is always 2^SYMBOL-1, where SYMBOL is the number of bits in each Reed-Solomon symbol. Quite often, this SYMBOL size is 8 bits (a normal byte). It can typically be anything from 3 to 16 bits. For an 8-bit symbol, the Reed-Solomon encoder will be named RS(255,PAYLOAD).

The PAYLOAD is the number of non-parity symbols. If you want 4 parity symbols, you would specify RS(255,251).

To effectively correct errors in your data block, you must first package the data as symbols (groups of bits, quite often just 8-bit bytes). Your goal is to try to arrange (if possible) for any errors to be clustered into the smallest number of symbols possible.

For example, if an error occurs on average every 8 bits, then an 8-bit symbol will not be appropriate; pretty much every symbol will have an error! You might go for 4-bit symbols and use an RS(15,11) codec -- for up to 11 4-bit symbols at a time, producing 4 parity symbols per block. The smaller the symbol size, the lower the CAPACITY (eg. for a SYMBOL size of 4 bits, 2^4-1 == 15 symbol CAPACITY).

But typically, you would use 8-bit symbols. If you have a more realistic error rate of, say, 10% of your 8-bit symbols being erroneous, then you might use an RS(255,205) -- 50 parity symbols per 255 symbol Reed-Solomon "codeword", with a maximum PAYLOAD of 205 bytes. This gives us ~25% parity, allowing us to correct a codeword containing up to ~12.5% errors.

Using https://github.com/pjkundert/ezpwd-reed-solomon's c++/ezpwd/rs Reed-Solomon API, you would specify this as:

#include <ezpwd/rs>
...
ezpwd::RS<255,205> rscodec;

Put your data in a std::string (it can handle raw 8-bit binary data just fine) or a std::vector and call the API, adding the 50 symbols of parity:

std::string data;
// ... fill data with a fixed size block, up to 205 bytes
rscodec.encode( data );

Send your data, and later on, after you receive the data+parity, recover the original data (and discard the 50 parity symbols):

int corrected = rscodec.decode( data );

If the data could be recovered, the number of symbols corrected will be returned, or -1 if the Reed-Solomon codeword contained too many errors.

Enjoy!