С.И.Хашин
!Код написан давно, недостатки вижу, возможно, немного улучшу (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)
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 |