To the beginning

Reed–Solomon codes over field F256/C++

S.I.Khashin

Reed–Solomon error correction code. .

To (bufsize-2*NErr) the information bytes are added 2*NErr control.
bufsize must not be greater than 255! Thus, with bufsize = 255, the maximum number of bug fixes is 127.
If the received buffer of size bufsize to be spoiled no more than NErr bytes, then all the errors can be completely repair.
For example, if 235 information bytes to add 20 control, get the size of the encoded buffer is 255:

    c_form(10, 255);

In module implements three functions:

// Preparing for (de)coding
// Nerr    - the maximal number of errors in buffer
// bufsize - buffer size, <= 255, must be: 2*NErr < bufsize
int c_form ( int NErr, int bufsize );

// The buffer must be a size of bufsize. The first (bufsize-2*NErr) a information for coding.
// After coding, the first 2*NErr bytes are control, the latter is the source information.
void c_code  ( char *buf );

// Decode buf of size (bufsize).
// Returns the number of corrced errors.
// If all errors can not be corrected, returns -1.
// This means that there are more than NErr errors.
int c_decode( char *buf );

Usage example:

char buf[255];
for(int i=0;i<235;i++) buf[i]=i;// fill 235 bytes of information
int NEr = 10;                   // maximal number of errors
c_form(NEr, 255);               // we will correct 10 errors in a buffer of length 255 bytes
                                // 235 informational and 20 control
c_code(buf);                    // Now buf contains 255 code 20 bytes+235 information

for (int i = 0; i < NEr; i++)   // make NEr errors
    buf[3 + 4 * i]++;

int nErr = c_decode(buf);       // Now buf of length 255 contains 235 informational bytes.
                                // The remaining 20 bytes are not used
printf("Nerr = %d\n", nErr);    // Because of the errors we made NErr=10, should be 10.

Remark 1. When coding the control bytes are AT the BEGINNING of the buffer in the positions (0,..2*NErr-1). Behind them are exactly the bytes of the source buffer.

Remark 2. In the limiting case, when NErr = 127 bufsize=255, we obtain in the block length of 255 only 1 information bytes and 254 control. In fact, the encoding in this case is reduced to the repetition of one byte of 255 times.

Speed of encoding and decoding

Encoding speed depends on maksialnoe the number of errors (NErr) almost linearly, at not too large NErr.

The decoding speed of the actual number of errors in a block does not depend on (almost).

At not too large the value of NErr (∼ 40-50) decode time about three times less time coding.

Time (in microseconds) of encoding (Tcod) and decoding (Tdec) of one block of data on the processor Intel(R) Pentium(R) CPU G4500 @3.50GHz according to from the specified maximum number of errors (NErr):