Битовая операция XOR

Простейшие расчеты показывают, что сложение полиномов по модулю два дает тот же самый результат, что их вычитание, и «волшебным» образом совпадает с битовой операцией XOR. Впрочем, совпадение с XOR – чистая случайность

Вернемся к фиктивному члену x нашего полинома и его коэффициентам. Благодаря их типизации и отсутствию взаимных связей, мы можем осуществлять обработку сколь угодно длинных чисел, просто XOR составляющие их биты на потоке. Это и есть одно из тех достоинств полиномиальной арифметики, которые не видны с первого взгляда, но благодаря которым полиномиальная арифметика стала так широко распространена.

Однако в нашем случае одной лишь полиномиальной арифметикой дело не обходится и для реализации кодера/декодера Рида-Соломона нам потребуется активная помощь со стороны полей Галуа. Что же это за поля такие, спросите вы?

Поля Галуа

В далеких шестидесятых, когда компьютеры были большими, а 20 Мб винчестеры напоминали собой стиральные машины, родилась одна из красивейших легенд о зеленом инопланетном существе, прилетевшем со звёзд и записавшем всю Британскую энциклопедию на тонкий металлический стержень нежно-серебристого цвета, который существо и увезло с собой. Сегодня, когда габариты 100 Гб жестких дисков сократились до размеров сигаретной пачки, такая плотность записи информации уже не кажется удивительной и даже вызывает улыбку. Но! Все дело в том, что инопланетное существо обладало технологией записи бесконечного количества информации на бесконечно крошечном отрезке и Британская энциклопедия была выбрана лишь для примера. С тем же успехом инопланетянин мог скопировать содержимое всех серверов Интернета, нанеся на свой металлический стержень всего одну-единственную риску. Не верите? А зря! Переводим Британскую энциклопедию в цифровую форму, получая огромное-преогромное число. Затем – ставим впереди него запятую, преобразуя записываемую информацию в длиннющую десятичную дробь. Теперь только остается найти два числа A и B, таких, что результат деления A и B как раз и будет равен данному числу с точностью до последнего знака. Запись этих чисел на металлический стержень осуществляется нанесением риски, делящей последний на два отрезка с длинами, кратными величинам А и B соответственно. Для считывания информации достаточно всего лишь измерить длины отрезков А и B, а затем – поделить один на другой. Первый десяток чисел после запятой будет более или менее точен, ну а потом… Потом жестокая практика опустит абстрактную теорию по самые помидоры, окончательно похоронив последнюю под толстым слоем информационного мусора, возникающего из невозможности точного определения геометрических размеров объектов реального мира.

В цифровом мире дела обстоят еще хуже. Каждый программист знает, что на деление целых и вещественных чисел наложены достаточно жесткие ограничения. Помимо того, что деление весьма прожорливая в плане процессорных ресурсов операция, так она еще и математически неточная!

То есть, если c = a * b, то еще не факт, что a == c/b! Таким образом, для практической реализации кодов Рида-Соломона обычная арифметика непригодна и приходится прибегать к помощи особой математики – математики конечных групп Галуа.

Под группой здесь понимается совокупность целых чисел, последовательно пронумерованных от 0 до 2ⁿ - 1, например: {0, 1, 2, 3} или {00h 01h, 02h, 03h, 04h, 05h, 06h, 07h, 08h, 09h, 0Ah, 0Bh, 0Ch, 0Dh, 0Eh, 0Fh}. Группы, содержащие 2ⁿ элементов, называются полями Галуа (Galois Field) и обозначаются так: GF(2ⁿ).

Члены групп в обязательном порядке подчиняются ассоциативному, коммутативному и дистрибьютивному законам, но обрабатываются довольно противоестественным на первый взгляд образом: