Сумма двух любых членов группы всегда присутствует в данной группе;

2) для каждого члена «а» группы существует тождественный (identity) ему член, обычно записываемый как «e», удовлетворяющий следующему условию: a + e = e + a = a;

3) для каждого члена «a» группы, существует обратный (inverse) ему член «-a», такой, что: a + –a == 0.

Начнем с первого тезиса. Не кажется ли он вам бредом? Допустим, у нас есть группа {0, 1, 2, 3}

Оказывается, сложение в полях Галуа осуществляется без учета переноса и сумма двух членов группы равна: c = (a + b) % 2ⁿ, где операция «%» обозначает взятие остатка. Применительно к нашему случаю: (2 + 3) % 4 == 1. У математиков это называется «сложением по модулю 4».

Естественно, вас интересует: а применяется ли сложение по модулю на практике или используется лишь в абстрактных конструкциях теоретиков? Хороший вопрос! Сложение по модулю мы машинально выполняем десятки раз на дню, даже не задумываясь о том, что это и есть сложение без учета переноса. Вот, например, проснувшись в шесть вечера по утру, вы просидели за компьютером девять часов кряду, а потом неожиданно бросили взгляд на свои наручные часы. Какое положение занимала часовая стрелка в это время, при условии, что часы идут точно? Искомое значение со всей очевидностью представляет собой сумму 6 и 9 по модулю 12 и равно оно: (6 + 9) % 12 == 3. Вот вам наглядный пример практического использования арифметики Галуа. А теперь давайте в порядке эксперимента вычтем из числа 3 число 6… (если не догадываетесь, как это правильно сделать, – возьмите в руки часы).

Теперь самое главное: раз результат деления одного члена группы на другой, естественно, не равный нулю, член в обязательном порядке должен присутствовать в данной группе, то несмотря на то, что деление осуществляется в целых числах, оно будет точным. Точным, а не округленным! Следовательно, если c = a * b, то a == c/b. Другими словами, умножение и деление непротиворечивым образом определено для всех членов группы, конечно, за исключением невозможности деления на нуль, причем расширения разрядной сетки при умножении не происходит!

Конечно, это не совсем обычное умножение (и далеко не во всяком поле Галуа дважды два будет рано четырем), однако никто и не требует от арифметики Галуа ее соответствия «здравому смыслу» и «житейскому опыту». Главное – что она работает, причем работает хорошо. И существование жестких дисков, CDROM/DVD приводов – лучшее тому подтверждение, ибо все они так или иначе используют эту арифметику в своих целях.

Как уже говорилось, в вычислительной технике наибольшее распространение получили поля Галуа с основанием 2, что объясняется естественностью этих полей с точки зрения машинной обработки, двоичной по своей природе.

Для реализации кодера/декодера Рида-Соломона нам потребуются четыре базовых арифметических операции: сложение, вычитание, умножение и деление. Ниже они будут рассмотрены во всех подробностях.

Сложение и вычитание в полях Галуа

Сложение по модулю два в полях Галуа тождественно вычитанию и реализуется битовой операцией XOR.

Умножение в полях Галуа

Открыв учебник математики за третий класс (если мне не изменяет память), мы найдем, что умножение представляет собой многократное сложение и, коль скоро сложение в полях Галуа мы выполнять уже научились, мы имеем все основания считать, что реализация функции умножения не создаст особого труда. Так? А вот и нет! Я всегда знал, что дважды два равно четырем, до конца никогда не верил в это и, впервые столкнувшись с полями Галуа, понял, насколько был прав. Выяснилось, что существуют и такие математики, где дважды два не равно четырем, а операция умножения определяется не через сложение, а совсем по-другому.

Собственно, функция «настоящего» умножения Галуа настолько сложна и ресурсоемка, что для упрощения ее реализации приходится прибегнуть к временному преобразованию полиномов в индексную форму, последующему сложению индексов, выполняемому по модулю GF, и обратному преобразованию суммы индексов в полиномиальную форму.

Что такое индекс? Это - показатель степени при основании два, дающий искомый полином. Например, индекс полинома 8 равен 3 (2³ = 8), а индекс полинома 2 равен 1 (2¹ = 2). Легко показать, что a * b = 2ⁱ * 2^j = 2^(i+j). В частности, 2 * 8 = 2³ * 2¹ = 2⁽³⁺¹⁾ = 2⁴ = 16. Составим следующую табличку и немного поэкспериментируем с ней:

Таблица 1. Таблица полиномов (левая колонка) и соответствующих им степеней двойки (правая колонка)

До сих пор мы оперировали понятиями привычной нам арифметики, и потому добрые две трети полей таблицы остались незаполненными. В самом деле, уравнения типа 2^x = 3 в целых числах не разрешимы и ряд индексов не соответствует никаким полиномам! Так-то оно так, но в силу того, что количество полиномов всякого поля Галуа равно количеству всевозможных индексов, мы можем определенным образом сопоставить их друг другу, закрыв глаза на то, что с точки зрения обычной математики такое действие не имеет никакого смысла. Конкретная схема сопоставления может быть любой, главное - чтобы она была внутренне непротиворечивой, то есть удовлетворяла всем правилам групп, перечисленным выше (см. «Поля Галуа»).

Естественно, поскольку от выбранной схемы сопоставления напрямую зависит и конечный результат, обе стороны (кодер и декодер Рида-Соломона) должны соблюдать определенные договоренности. Однако различные кодеры/декодеры Рида-Соломона могут использовать различные схемы сопоставления, несовместимые друг с другом.

В частности, декодер Рида-Соломона, встроенный в CD-ROM привод, выполняет умножение по следующей таблице. Встретив такую таблицу в дизассемблерном листинге исследуемой вами программы, вы сможете быстро и надежно отождествить использующие ее функции:

Таблица 2. Lock-up-таблица для GF(256) Первая слева колонка – полиномы/индексы (обычно обозначается, как i), вторая – таблица степеней примитивного полинома 2 (обычно обозначается как alpha_of), третья – индексы, соответствующие данному полиному (обычно обозначается как index_of)