В начало

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

С.И.Хашин


rdso.h - заголовочный файл
rdso.cpp - реализация.

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


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

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

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

Если в нём испортить любые 10 байтов, то это будет замечено и исправлено.
Большее количество ошибок можно заметить, но исправить уже не удастся.
В этом примере NErr = 10, bufsize = 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)

NErr Tcod Tdec   NErr Tcod Tdec   NErr Tcod Tdec   NErr Tcod Tdec
1 1.636 0.540 33 57.938 19.859 65 88.425 38.185 97 88.242 56.793
2 2.607 1.048 34 57.632 20.325 66 88.715 38.902 98 87.967 57.205
3 4.283 1.553 35 59.036 21.000 67 88.348 39.398 99 87.189 57.663
4 5.620 2.070 36 60.669 21.477 68 89.645 40.092 100 87.418 58.136
5 7.671 2.604 37 62.836 22.152 69 89.828 40.611 101 85.968 58.609
6 10.269 3.146 38 63.217 22.747 70 90.958 41.267 102 85.617 59.433
7 12.363 3.716 39 64.865 23.277 71 90.515 41.740 103 85.693 60.150
8 14.446 4.332 40 65.872 23.979 72 91.644 42.145 104 84.839 60.349
9 15.995 4.900 41 67.352 24.429 73 91.324 42.633 105 84.457 61.325
10 17.490 5.438 42 68.024 25.047 74 92.896 43.282 106 84.030 61.752
11 20.000 6.067 43 70.633 25.604 75 91.705 44.029 107 82.977 62.164
12 21.450 6.582 44 70.328 25.955 76 93.262 44.685 108 82.413 62.698
13 23.933 7.479 45 71.640 26.817 77 92.712 45.166 109 80.963 63.705
14 25.848 8.778 46 73.532 27.351 78 92.987 45.746 110 80.368 64.285
15 27.473 9.352 47 73.029 27.954 79 92.926 46.234 111 79.483 64.789
16 30.540 9.993 48 75.165 28.320 80 92.072 46.539 112 78.278 65.384
17 31.883 10.521 49 76.553 29.182 81 92.041 47.333 113 77.225 66.010
18 33.539 11.219 50 76.370 29.648 82 92.987 48.096 114 76.233 66.238
19 35.362 11.806 51 77.881 30.159 83 92.270 48.233 115 75.974 67.169
20 36.179 12.341 52 77.164 30.907 84 92.285 49.179 116 74.432 67.612
21 38.567 12.932 53 78.888 31.441 85 92.255 49.896 117 73.090 67.978
22 39.551 13.588 54 80.200 31.944 86 91.949 50.400 118 72.128 68.451
23 41.565 14.095 55 80.856 32.654 87 92.438 50.919 119 70.206 69.443
24 43.152 14.622 56 81.985 33.157 88 91.644 51.636 120 68.954 69.382
25 44.739 15.320 57 83.328 33.760 89 91.614 51.773 121 67.642 70.053
26 46.249 15.846 58 83.801 34.378 90 92.316 52.567 122 66.666 70.969
27 47.867 16.350 59 85.861 34.874 91 91.522 53.436 123 65.399 71.335
28 49.316 17.033 60 84.625 35.408 92 90.515 53.726 124 63.843 72.266
29 50.262 17.570 61 87.723 35.995 93 90.714 54.306 125 62.332 72.083
30 51.376 18.097 62 85.861 36.499 94 89.691 54.825 126 60.883 73.181
31 52.887 18.723 63 87.524 37.064 95 90.027 55.237 127 60.837 73.166
32 55.908 19.260 64 87.158 37.842 96 89.035 56.274


free counters