Geek Answers Handbook

Error Correction Codes

I need to use the error correction method for short messages (from 100 to 200 bits). The space available for adding redundant bits is limited to 20-50%.

I will need to implement encoding and decoding in C / C ++. Therefore, it must be either open or simple enough for programming. (I had experience in the past with decoding algorithms - they are terrible!)

Can anyone advise using a suitable error code (with appropriate parameters)?

+4
source share
2 answers

Take a look at Reed Solomon's correction.

An example implementation in C ++ is available here .

For another option, look here - see element # 11

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

+9
source

Reed-Solomon encoders are described as RS (PERFORMANCE, 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 (regular byte). Usually it can be from 3 to 16 bits. For an 8-bit character, the Reed-Solomon encoder will be called RS (255, PAYLOAD).

PAYLOAD is the number of characters without parity. If you need 4 parity characters, you must specify RS (255,251).

To effectively correct errors in your data block, you must first pack the data as characters (groups of bits, not just 8-bit bytes). Your goal is to try to organize (if possible) any errors that will be grouped into the least number of characters.

For example, if an error occurs on average every 8 bits, then an 8-bit character is not suitable; almost every character will have an error! You can go for 4-bit characters and use the RS codec (15.11) - up to 11 4-bit characters at a time, producing 4 parity characters per block. The smaller the character size, the lower the CAPACITY value (for example, for 4-bit SYMBOL, 2 ^ 4-1 == 15 CAPACITY characters).

But usually you should use 8-bit characters. If you have a more realistic error rate, for example, 10% of your 8-bit characters are wrong, then you can use RS (255,205) - 50 parity characters per 255 characters "Reed-Solomon codeword" with a maximum PAYLOAD of 205 bytes. This gives us 25% parity, which allows us to correct a codeword containing errors of up to 12.5%.

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

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

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

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

Send your data, and then, after receiving the data + parity, restore the original data (and cancel 50 parity characters):

 int corrected = rscodec.decode( data );

If the data can be recovered, the number of corrected characters will be returned, or -1 if the Reed-Solomon codeword contains too many errors.

Enjoy it!

+1
source

More articles:


All Articles