Впрочем, если как следует подумать головой, частично призвав на помощь и другие части тела, можно сообразить, что умножать информационное слово на порождающий полином вовсе не обязательно, можно поступить гораздо хитрее:

n  Добавляем к исходному информационному слову D справа k нулей, в результате чего у нас получается слово длины n = m + r и полином X^r*D, где m – длина информационного слова.

n  Делим полученный полином X^r*D на порождающий полином G и вычисляем остаток от деления R, такой что: X^r*D = G*Q + R, где Q – частное, которое мы благополучно игнорируем за ненадобностью, – сейчас нас интересует только остаток.

n  Добавляем остаток R к информационному слову D, в результате чего получаем симпатичное кодовое слово C, информационные биты которых хранятся отдельно от контрольных бит. Собственно, тот остаток, который мы получили в результате деления, и есть корректирующие коды Рида-Соломона. Между нами говоря, способ кодирования, при котором информационные и контрольные символы хранятся раздельно, называется систематическим кодированием и такое кодирование весьма удобно с точки зрения аппаратной реализации.

n  Мысленно прокручиваем предыдущие пункты, пытаясь обнаружить, на какой же стадии вычислений происходит выход за разрядную сетку и… такой стадии нет! Остается лишь отметить, что информационное слово + корректирующие коды можно записать как: T = X^r*D + R = G*Q.

Декодирование полученного слова T осуществляется точно так же, как уже и было описано ранее. Если при делении T (которое в действительности является произведением G на Q) на порождающий полином G образуются остаток, то слово T искажено и, соответственно, наоборот.

Теперь вопрос на засыпку. Как вы собираетесь осуществлять деление полиномов в рамках общепринятой алгебры? В целочисленной арифметике деление определено не для всех пар чисел (вот, в частности, 2 нельзя разделить на 3, а 9 нельзя разделить на 4, без потери значимости, естественно). Что же касается «плавучки», то ее точность еще та (в смысле точность катастрофически недостаточная для эффективного использования кодов Рида-Соломона), к тому же она достаточно сложна в аппаратной реализации. Ладно, в IBM PC с процессором Pentium быстродействующий математический сопроцессор всем нам дан по дефолту, но что делать разработчикам ленточных накопителей, винчестеров, CD-приводов, наконец? Пихать в них четвертый Пень?! Нет уж, увольте, лучше воспользоваться специальной арифметикой – арифметикой конечных групп, называемых полями Галуа. Достоинство этой арифметики в том, что операции сложения, вычитания, умножения и деления определены для всех членов поля (естественно, исключая ситуацию деления на ноль), причем число, полученное в результате любой из этих операций, обязательно присутствует в группе! Т.е. при делении любого целого числа A, принадлежащего множеству 0…255, на любое целое число B из того же множества (естественно, B не должно быть равно нулю), мы получим число C, входящее в данное множество. А потому потерь значимости не происходит, и никакой неопределенности не возникает!

Таким образом, корректирующие коды Рида-Соломона основаны на полиномиальных операциях в полях Галуа и требуют от программиста владения сразу несколькими аспектами высшей математики из раздела теории чисел. Как и все «высшее», придуманное математиками, поля Галуа есть абстракция, которую невозможно ни наглядно представить, ни «пощупать» руками. Ее просто надо принять как набор аксиом, не пытаясь вникнуть в его смыл, достаточно всего лишь знать, что она работает, вот и все. А еще есть полиномы немеряных степеней и матрицы в пол-Европы, от которых нормальный системщик не придет в восторг (увы, программист-математик скорее исключение, чем правило).