Полиномиальная арифметика
Полиномиальной арифметике посвящен шестой раздел третьего тома "Искусства программирования" Дональда Кнута, где полиному дается следующее определение: "Формально говоря, полином над S представляет собой выражение вида: u(x)= unxn + … + u1x + u0, где коэффициенты un,…, u1, u0 — элементы некоторой алгебраической системы S, а переменная x может рассматриваться как формальный символ без определяющего значения. Будем полагать, что алгебраическая система S представляет собой коммутативное кольцо с единицей. Это означает, что S допускает операции сложения, вычитания и умножения, удовлетворяющие обычным свойствам: сложение и умножение являются ассоциативными и коммутативными бинарными операциями, определенными на S, причем умножение дистрибуьютивно по отношению к сложению. Существует так же единичный элемент по сложению 0 и единичный элемент по умножению 1, такие, что a + 0 == a и a * 1 == a для всех a из S. Вычитание является обратной по отношению к сложению операцией, но о возможности деления как операции, обратной по отношению к умножению, ничего не предполагается. Полином 0xn + m + … + 0x n + 1 + unxn + … + u1x + u0
рассматривается как идентичный unxn + … + u1x + u0, хотя формально он отличается от него".
Таким образом, вместо того, чтобы представлять информационное слово D, кодовое слово C
и остаток от деления R в виде целых чисел (как это делалось нами ранее), мы можем связать их с соответствующими коэффициентами двоичного полинома, выполняя все последующие математические манипуляции по правилам полиномиальной арифметики. Выигрыш от такого преобразования на первый взгляд далеко не очевиден, но не будем спешить, а лучше преобразуем любое пришедшее нам в голову число (например, 69h) в двоичный полином. Запустив "Калькулятор" или любое другое подходящее приложение по вашему вкусу, переведем наше число в двоичный вид (при соответствующих навыках эту операцию можно выполнить и в уме, см. "Техника и философия хакерских атак" Криса Касперски[Y64] [n2k65] ): 69h à 1101001.
Ага, крайний правый коэффициент равен единице, затем следуют два нулевых коэффициента, потом единичный коэффициент… короче говоря, получается следующее: 1x6 + 1x5 + 0x4 + 1x3+ 0x2 + 0x + 1. По сути говоря, битовая строка "1101001" является одной из форм записи вышеуказанного полинома, — ненаглядной с точки зрения неподготовленного человека, но удобной для машинной обработки. Постойте, но если 69h уже
представляет собой полином, то в чем разница между сложением полиномов 69h и 27h и сложением целых чисел 69h и 27h?! Разница несомненно есть. Как еще показал Ницше: фактов нет, а есть одни лишь интерпретации. Интерпретация же чисел и полиномов различна и математические операции над ними выполняются по совершенно независимым правилам.
Коэффициенты в полиномиальной арифметики строго типизированы и коэффициент при xk имеет иной тип нежели при xm (конечно, при том условии, что k ¹ m). А операции над числами различных типов категорически не допустимы! Все коэффициенты обрабатываются независимо, а возникающий при этом перенос в старший разряд (заем из старшего разряда) попросту не учитывается. Покажем это на примере сложения чисел 69h и 27h (листинг 2.11). Сложение, выполненное по правилам полиномиальной двоичной арифметики (слева) и сложение, выполненное по правилам обычной арифметики (справа). :
Листинг 21.11. Пример сложения чисел 69h и 27hСложение, выполненное по правилам полиномиальной двоичной арифметики (слева) и сложение, выполненное по правилам обычной арифметики (справа)
1101001 (69h) 1101001 (69h)
+0100111 (27h) +0100111 (27h)
––––––– –––––––
1001110 (4Eh) 10010000 (90h)
Простейшие расчеты показывают, что сложение полиномов по модулю два, дает тот же самый результат, что их вычитание и "волшебным" образом совпадает с битовой операцией XOR (исключающее ИЛИ). Впрочем, совпадение с этой операциейXOR — чистая случайность, но вот эквивалентность сложения и вычитания заставляет заново пересматривать привычную природу вещей, вспоминая задачки из серии "у Маши было одно яблоко, Петя отнял у нее его, затем ей подарил еще одно, спрашивается: сколько всего яблок у Маши осталось? А сколько у нее было бы, если бы первое яблоко осталось не отнятым?".
С точки зрения арифметики по модулю два ответ: один и ноль соответственно. Да! Не отними бы Петя у Маши яблоко, 1 + 1 == 0 и бедная Маша вообще осталась бы ни с чем. Так что мальчики, почаще отнимайте яблоки и девушек — учите их компьютерной грамотности!
Впрочем, мы отвлеклись. Ладно, оставим в покое половые разборки между Петей и Машейчленами молодежи ив вернемся к фиктивному члену x
нашего полинома и его коэффициентам. Благодаря их типизации и отсутствию взаимных связей, мы можем осуществлять обработку сколь угодно длинных чисел, просто выполняя на потоке операцию XOR (исключающее ИЛИ)'я над составляющимие их битамиы на потоке. Это и есть одно из тех достоинств полиномиальной арифметики, которые не видны с первого взгляда, но благодаря которым полиномиальная арифметика стала так широко распространена.
Однако, в нашем случае одной лишь полиномиальной арифметикой дело не обходится и для реализации кодера/декодера Рида-Соломона нам потребуется активная помощь со стороны полей Галуа. Что же это за поля такие, спросите Вы?
