s1  =         GF_mult_by_alpha[ s1 ^ input[i] ];

    sm1 = GF_mult_by_alpha_inverse[sm1 ^ input[i] ];

};

Листинг 7. Ключевой фрагмент декодера Рида-Соломона, вырванный из IBM 3370

err_i = GF_log_base_alpha[ GF_divide[s1][s0] ];    // вычисляем синдром ошибки

input[err_i] ^= s0;                         // исправляем сбойный байт

Ну что, слабо нам разобраться: как он работает? Что касательно переменной s0 - с ней все предельно ясно: она хранит контрольную сумму, рассчитанную по тривиальному алгоритму. Как вы, наверное, помните, сложение в полях Галуа осуществляется логической операцией XOR, и потому: s0 += input[i].

Назначение переменной s1 выяснить сложнее, и чтобы понять суть разворачивающегося вокруг нее метаболизма, мы должны знать содержимое таблицы GF_mult_by_alpha. Несмотря на то, что по соображениям экономии бумажного пространства она здесь не приводится, ее имя говорит само за себя: содержимое s1 суммируется с очередным байтом контролируемого потока данных и умножается на так называемый примитивный член, обозначаемый как alpha, и равный двум. Другими словами: s1 = 2 . (s1 + input[i]).

Допустим, один из байтов потока данных впоследствии будет искажен (обозначим его позицию как err_i), тогда индекс искаженного байта можно определить тривиальным делением s1 на s0. Почему? Так ведь выражение s1 = 2 . (s1 + input[i]) по своей сути есть не что иное, как завуалированное умножение информационного слова на порожденный полином, динамически генерируемый на основе своего примитивного члена alpha. А контрольная сумма информационного слова, хранящаяся в переменной s0, фактически представляет собой то же самое информационное слово, только представленное в более «компактной» форме. И, как уже говорилось в предыдущей статье: если ошибка произошла в позиции x, то остаток от деления кодового слова на порожденный полином будет равен k = 2x. Остается лишь по известному k вычислить x, что в данном случае осуществляется путем обращения к таблице GF_log_base_alpha, хранящей пары соответствий между k и 2x. Коль скоро позиция сбойного байта найдена, его можно исправить путем XOR с рассчитанной контрольной суммой s0 (input[err_i] ^= s0). Конечно, сказанное справедливо только для одиночных ошибок, а искажения двух и более байт на блок данный алгоритм исправить не в силах. Собственно, для этого и присутствует третий байт контрольной суммы - sm1, защищающий декодер от «политнекорректных» попыток исправления ошибок, когда их больше одной. Если выражение s1/s0 == sm1 . s0 становится ложным, контроллер винчестера может засвидетельствовать факт наличия множественных ошибок, констатируя невозможность их исправления.

Однако, как хорошо известно, дефекты магнитной поверхности имеют тенденцию образовывать не одиночные, а групповые ошибки. И, чтобы хоть как-то компенсировать слабость корректирующего алгоритма, парни из IBM прибегли к чередованию байт. Винчестер IBM 3370 имел чередование 3:1, то есть сначала шел первый байт первого блока, за ним первый байт второго блока, за ним – первый байт третьего и только потом - второй байт первого блока. Такой трюк усиливал корректирующую способность винчестера с одной одиночной ошибки, до трех последовательно искаженных байт... Однако если разрушению подвергались не соседние байты, то корректирующая способность вновь опускалась до значений в один искаженный байт на блок, но вероятность такого события была несравненно меньше.