Поля Галуа
В далеких шестидесятых, когда компьютеры были большими, а двадцати мегабайтовые винчестеры емкостью в 20 Мбайт напоминали собой стиральные машины, родилась одна из красивейших легенд о зеленом инопланетном существе, прилетевшим со звезд, и записавшим всю Британскую энциклопедию на тонкий металлический стержень нежно-серебристого цвета, который существо и увезло с собой. Сегодня, когда габариты 100 ГГб жестких дисков сократились до размеров сигаретной пачки, такая плотность записи информации уже не кажется удивительной и даже вызывает улыбку. Но! Все дело в том, что инопланетное существо обладало технологией записи бесконечного количества информации на бесконечно крошечном отрезке и Британская энциклопедия была выбрала лишь для примера. С тем же успехом инопланетянин мог скопировать содержимое всех серверов Интернета, нанеся на свой металлический стержень всего одну-единственную риску. Не верите? А зря! Переводим Британскую энциклопедию в цифровую форму, получая огромное преогромное число. Затем — ставим впереди него запятую, преобразуя записываемую информацию в длиннющую десятичную дробь. Теперь только остается найти два числа A и B, таких, что результат деления A и B
как раз и будет равен данному числу с точностью до последнего знака. Запись этих чисел на металлических стержень осуществляется нанесением риски, делящей последний на два отрезка с длинами, кратными величинам А и B
соответственно. Для считывания информации достаточно всего лишь измерить длины отрезков А и B, а затем — поделить один на другой. Первый десяток чисел после запятой будет более или менее точен, ну а потом… Потом жестокая практика "опустит" абстрактную теорию по самые помидоры, окончательно похоронив последнюю под толстым слоем информационного мусора, возникающего из невозможности точного определения геометрических размеров объектов реального мира.
В цифровом мире дела обстоят еще хуже. Каждый программист знает, что на деление целых и вещественных чисел наложены достаточно жесткие ограничения.
Помимо того, что деление весьма прожорливая в плане процессорных ресурсов операция, так она еще и математически неточная! То есть, если c = a * b, то еще не факт, что a == c/b! Таким образом, для практической реализации кодов Рида-Соломона обычная арифметика непригодна и приходится прибегать к помощи особой математики — математики конечных групп Галуа.
Под группой здесь понимается совокупность целых чисел, последовательно пронумерованных от 0 до 2n – 1, например: {0, 1, 2, 3} или {00h 01h, 02h, 03h, 04h, 05h, 06h, 07h, 08h, 09h, 0Ah, 0Bh, 0Ch, 0Dh, 0Eh, 0Fh}. Группы, содержащие 2n элементов, называются полями Галуа (Galois Field) и обозначаются так: GF(2n).
Замечание
На самом же деле, полями Галуа называют любые конечные поля, но в данном контексте мы будем говорить лишь о тех полях, количество членов которых равно 2n.
Члены групп в обязательном порядке подчиняются ассоциативному, коммутативному и дистрибуьютивному законам, но обрабатываются довольно противоестественным на первый взгляд образом:
1. Сумма двух любых членов группы всегда присутствует в данной группе.
2. Для каждого члена "а" группы существует тождественный (identity)
ему член, обычно записываемый как "e", удовлетворяющий следующему условию: a + e = e + a = a.
3. Для каждого члена "a" группы, существует обратный (inverse) ему член " –a", такой что: a + –a == 0.
Начнем с первого тезиса. Не кажется ли он вам бредом? Допустим, у нас есть группа {0, 1, 2, 3}. Это в какоим же состояниив дупель пьяным нужно быть, чтобы при вычислении значения 2 + 3 получить число меньшее или равное 3?! Оказывается, сложение в полях Галуа осуществляется без учета переноса и сумма двух членов группы равна: c = (a + b) % 2n, где операция ""%" обозначает взятие остатка.
Применительно к нашему случаю: (2 + 3) % 4 == 1. У математиков это называется "сложением по модулю 4".
Естественно, вас интересует: а применяется ли сложение по модулю на практике или используется лишь в абстрактных конструкциях теоретиков? Хороший вопрос! Сложение по модулю мы машинально выполняем десятки раз на дню, даже не задумываясь о том, что это и есть сложение без учета переноса. Вот, например, проснувшись в шесть вечера по утру, вы просидели за компьютером девять часов кряду, а потом неожиданно бросили взгляд на свои наручные часы. Какое положение занимала часовая стрелка в это время, при условии, что часы идут точно? Искомое значение со всей очевидностью представляет собой сумму 6 и 9 по модулю 12 и равно оно: (6 + 9) % 12 == 3. Вот вам наглядный пример практического использования арифметики Галуа. А теперь давайте в порядке эксперимента вычтем из числа 3 число 6… (если не догадалисываясь как это правильно сделать, то — возьмите в руки часы).
Теперь самое главное: раз, результат деления одного члена группы на другой, естественно, неравный нулю член, в обязательном порядке должен присутствовать в данной группе, то несмотря на то, что деление осуществляется в целых числах оно будет точным. Точным, а не округленным! Следовательно, если c = a * b, то a == c/b. Другими словами, умножение и деление непротиворечивым образом определено для всех членов группы, конечно, за исключением невозможности деления на нуль, причем, расширения разрядной сетки при умножении не происходит!
Конечно, это не совсем обычное умножение (и далеко не во всяком поле Галуа дважды два будет рано четырем), однако, никто и не требует от арифметики Галуа ее соответствия "здравому смыслу" и "житейскому опыту". Главное, — что она работает, причем работает хорошо. И существование жестких дисков, CD-ROM/DVD приводов — лучшее тому подтверждение, ибо все они так или иначе используют эту арифметику в своих целях.
Как уже говорилось, в вычислительной технике наибольшее распространение получили поля Галуа с основанием 2, что объясняется естественностью этих полей с точки зрения машинной обработки, двоичной по своей природе.
Для реализации кодера/декодера Рида-Соломона нам потребуются четыре базовых арифметических операции: сложение, вычитание, умножение и деление. ДалееНиже они будут рассмотрены во всех подробностях.
