Представление полинома в виде суммы в двоичной и 16-ричной системе счислений.

Хотя арифметическое деление, описанное в предыдущем разделе, очень похоже на схему расчета контрольной суммы, называемой CRC, сам же алгоритм CRC несколько более сложен, и, чтобы понять его, нам необходимо окунуться в теорию целых чисел. 6 4. Полиномиальная арифметика Ключевым словом, которое Вы будете постоянно слышать при работе с CRC, является слово "полином". Все CRC алгоритмы основаны на полиномиальных вы числениях, и для любого алгоритма CRC можно указать, какой полином он исполь зует. Что это значит? Вместо представления делителя, делимого (сообщения), частного и остатка в ви де положительных целых чисел (как это было сделано в предыдущем разделе), можно представить их в виде полиномов с двоичными коэффициентами или в виде строки бит, каждый из которых является коэффициентом полинома. Например, десятичное число 23 в шестнадцатеричной системе счисления имеет вид 17, а в дво ичном – 10111, что совпадает с полиномом: 1*x^4 + 0*x^3 + 1*x^2 + 1*x^1 + 1*x^0 или, упрощенно: x^4 + x^2 + x^1 + x^0 И сообщение, и делитель могут быть представлены в виде полиномов, с которы ми как и раньше можно выполнять любые арифметические действия; только теперь нам придется не забывать о иксах. Предположим, что мы хотим перемножить, на пример, 1101 и 1011. Это можно выполнить, как умножение полиномов: (x^3 + x^2 + x^0)(x^3 + x^1 + x^0) = (x^6 + x^4 + x^3 + x^5 + x^3 + x^2 + x^3 + x^1 + x^0) = x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0 Теперь для получения правильного ответа нам необходимо указать, что Х равен 2, и выполнить перенос бита от члена 3*x^3. В результате получим: x^7 + x^3 + x^2 + x^1 + x^0 Все это очень похоже на обычную арифметику, с той лишь разницей, что осно вание у нас лишь предполагается, а не строго задано. Что же из этого следует? А то, что если мы считаем, "X" нам не известен, то мы не можем выполнить пере нос. Нам не известно, что 3*x^3 – это то же самое, что и x^4 + x^3, так как мы не знаем, что X = 2. В полиномиальной арифметике связи между коэффициентами не установлены, и, поэтому, коэффициенты при каждом члене полинома становятся строго типизированными — коэффициент при x^2 имеет иной тип, чем при x^3. Если коэффициенты каждого члена полинома совершенно изолированы друг от друга, то можно работать с любыми видами полиномиальной арифметики, просто меняя правила, по которым коэффициенты работают. Одна из таких схем для нам чрезвычайно интересна, а именно, когда коэффициенты складываются по моду лю 2 без переноса – то есть коэффициенты могут иметь значения лишь 0 или 1, пе ренос не учитывается. Это называется "полиномиальная арифметика по модулю 2". Возвращаясь к предыдущему примеру: (x^3 + x^2 + x^0)(x^3 + x^1 + x^0) = (x^6 + x^4 + x^3 + x^5 + x^3 + x^2 + x^3 + x^1 + x^0) = x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0 По правилам обычной арифметики, коэффициент члена 3*x^3 распределяется по другим членам полинома, используя механизм переноса и предполагая, что X = 2. В "полиномиальной арифметике по модулю 2" нам не известно, чему равен "X", переносов здесь не существует, а все коэффициенты рассчитываются по моду лю 2. В результате получаем: = x^6 + x^5 + x^4 + x^3 + x^2 + x^1 + x^0 Как пишет Д. Кнут [Knuth81, стр.400] : "Читатель может подметить сходство между полиномиальной арифметикой и арифметикой высокой точности (multiple precision arithmetic) (раздел 4.3.1.), когда основание b заменяется на x. Основное различие со Элементарное руководство по CRCалгоритмам обнаружения ошибок 7 стоит в том, что коэффициент uk члена xk в полиномиальной арифметике считается ма лой величиной, или величиной, не связанной с ближайшими коэффициентами xk 1 (и xk+1), поэтому перенос от одного члена к другому в ней отсутствует. Фактически, поли номиальная арифметика по модулю b во многом аналогична арифметике высокой точ ности по основанию b за исключением подавления всех переносов." Таким образом, полиномиальная арифметика по модулю 2 – это фактически двоичная арифметика по модулю 2 без учета переносов. Хотя полиномы имеют удобные математические средства для анализа CRC алгоритмов и алгоритмов кор рекции ошибок, для упрощения дальнейшего обсуждения они будут заменены на непосредственные арифметические действия в системе, с которой они изоморфны, а именно в системе двоичной арифметики без переносов.