В начало

Код Рида-Соломона над полем из 256 элементов/C++

С.И.Хашин

!Код написан давно, недостатки вижу, возможно, немного улучшу (2017-10-11).

Код Рида—Соломона - это код обнаруживающий и исправляющий ошибки.

К (bufsize-2*NErr) информационных байтов добавляем 2*NErr контрольных.
bufsize не должно быть больше 255! Таким образом, при bufsize=255 наибольшее количество исправляемых ошибок равно 127.
Если в полученном буфере размером bufsize будут испорчены не более NErr байтов, то все ошибки можно будет полностью восстановить.
Например, если к 235 информационным байтам добавить 20 контрольных, получим размер закодированного буфера равным 255:

    c_form(10, 255);  // будем исправлять 10 ошибок, в буфере длиной 255 байт 

В модуле реализовано три функции:

// 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 );

Пример использования:

char buf[255];
for(int i=0;i<235;i++) buf[i]=i;// заполнили 235 информационных байтов
int NEr = 10;                   // максимальное количесто ошибок
c_form(NEr, 255);               // будем исправлять 10 ошибок, в буфере длиной 255 байт 
                                // 235 информационых и 20 контрольных
c_code(buf);                    // Тепрь buf длиной 255 содержит 20 кодовых байт+235 информационных

for (int i = 0; i < NEr; i++)   // насажаем NEr ошибок
    buf[3 + 4 * i]++;

int nErr = c_decode(buf);       // Теперь buf длиной 255 содержит 235 байт исходной информации
                                // Оставшиеся 20 байт не используются
printf("Nerr = %d\n", nErr);    // Так как ошибок мы сделали NErr=10, должно быть напечатано 10.

Замечание 1. При кодировании контрольные байты лежат В НАЧАЛЕ буфера, в позициях (0,..2*NErr-1). За ними лежат в точности байты исходного буфера.

Замечание 2. В предельном случае, когда NErr = 127 и bufsize=255, получаем в блоке длиной 255 только 1 информационный байт и 254 контрольных. Фактически, кодирование в этом случае сводится к повторению одного байта 255 раз.

Скорость (де)кодирования

Скорость кодирования зависит от максиального количества ошибок (NErr) практически линейно, при не слишком большом NErr.

Скорость декодирования от фактического количества ошибок в блоке не зависит (почти).

При не слишком большой величине NErr (∼ 40-50) время декодирования примерно втрое меньше времени кодирования.

Время (в микросекундах) кодирования (Tcod) и декодирования (Tdec) одного блока данных на процессоре Intel(R) Pentium(R) CPU G4500 @3.50GHz в зависимости от заданного максимального количества ошибок (NErr)