Начнем с первого тезиса. Не кажется ли он вам бредом? Допустим, у нас есть группа {0, 1, 2, 3}. Это каким же в дупель пьяным нужно быть, чтобы при вычислении значения 2 + 3 получить число меньшее или равное 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. Этот вопрос мы уже обсуждали при изучении полиномиальной арифметики, поэтому не будем лишний раз повторяться, а просто приведем законченный пример программной реализации функции сложения/вычитания:

Листинг 2. Функция, реализующая сложение/вычитание в полях Галуа