Поле Галуа GF(256)
Поле Галуа GF(256) — конечное множество из 256 значений (ровно один байт) с четырьмя арифметическими операциями, результат которых всегда остаётся байтом. В этой арифметике QR считает коррекцию.
Что такое GF(256) в контексте QR
Поле Галуа GF(256) — множество из 256 значений, то есть ровно всех возможных байтов от 0 до 255, в котором заданы четыре арифметические операции: сложение, вычитание, умножение и деление на всё, кроме нуля. Главное свойство: любая операция над двумя байтами даёт снова байт. Ничего не переполняется, не округляется и не вылезает за границу.
Для QR-кода это не абстракция, а рабочий инструмент. Кодовое слово QR — это один байт. Значит, если считать всю коррекцию ошибок в GF(256), каждое промежуточное значение автоматически укладывается в одно кодовое слово. Никаких «переносов в старший разряд» и потерь точности. Поэтому алгоритм Рида — Соломона в QR живёт именно здесь.
Поле названо в честь Эвариста Галуа — французского математика, погибшего на дуэли в двадцать лет и успевшего заложить основы теории конечных полей. Отсюда и второе имя — конечное поле.
Сложение: обычный XOR
В GF(256) сложение и вычитание — это одна и та же операция, побитовое исключающее ИЛИ. Переносов нет:
- 5 + 3 = 6, потому что 00000101 XOR 00000011 = 00000110;
- 7 + 7 = 0 — любое значение, сложенное с самим собой, обнуляется;
- из этого следует, что вычитание неотличимо от сложения: a − b всегда равно a + b.
Именно поэтому в описаниях Рида — Соломона встречаются формулы вида «остаток от деления вычитается», а в коде стоит один XOR. Это не упрощение и не хитрость программиста — в GF(256) минус буквально равен плюсу.
Умножение и примитивный полином
С умножением сложнее. Байты рассматриваются как многочлены: 5 — это 00000101, то есть x² + 1, а 3 — это x + 1. Многочлены перемножаются как обычно, но коэффициенты складываются по модулю 2. Проверьте на 3 × 3: (x + 1)(x + 1) = x² + 2x + 1, двойка обнуляется, остаётся x² + 1, то есть 5. В GF(256) три на три действительно равно пяти.
Если результат вылез за восемь бит, его сворачивают обратно делением с остатком на примитивный полином. Для QR-кода стандарт ISO/IEC 18004 фиксирует полином x⁸ + x⁴ + x³ + x² + 1 — в шестнадцатеричном виде 11D. Классический пример: 2 в восьмой степени даёт 256, это девять бит, после свёртки получается 29.
На практике никто не умножает многочлены в реальном времени. Число 2 в GF(256) — порождающий элемент: его степени пробегают все 255 ненулевых значений и на 255-й возвращаются к единице. Поэтому генератор один раз строит две таблицы по 256 ячеек — логарифмов и антилогарифмов — и дальше умножение превращается в сложение двух индексов по модулю 255 с двумя обращениями к массиву. Отсюда и скорость: смартфон декодирует код за десятки миллисекунд.
Почему поле обязано быть полем
Слово «поле» здесь не украшение. Оно означает, что деление определено для любого ненулевого элемента: у каждого байта, кроме нуля, есть обратный. А раз есть деление чисел — работает и деление многочленов с остатком.
На этом держится вся схема коррекции. Байты данных блока трактуются как коэффициенты одного большого многочлена, он делится на порождающий полином, и остаток становится байтами коррекции. При чтении декодер подставляет корни этого полинома и по ненулевым остаткам — синдромам — вычисляет, где именно и на сколько байты испорчены. Ни один из шагов невозможен в обычной целочисленной арифметике, где деление даёт дробь.
Где GF(256) встречается кроме QR
Ровно то же поле GF(256) лежит под Data Matrix (в версии ECC200), под коррекцией на компакт-дисках и DVD, под RAID-6, под шифром AES. У других двумерных символик поле своё: PDF417 считает Рида — Соломона в GF(929), то есть кодовое слово там не байт, а число от 0 до 928; Aztec Code выбирает поле по размеру символа — GF(64) для самых маленьких, GF(256) для средних, GF(1024) и GF(4096) для крупных, а служебное сообщение о режиме защищает отдельно в GF(16). Даже там, где поле совпадает с QR, разница остаётся в деталях: примитивный полином у форматов может отличаться, и таблицы логарифмов от Data Matrix не подойдут для QR. Поэтому библиотека, умеющая один формат, не читает другой «сама собой» — ей нужны свои константы.
Для пользователя всё это скрыто: выбирая уровень коррекции в генераторе QR-кодов, вы задаёте, сколько байтов остатка добавить к каждому блоку. Остальное поле Галуа делает молча.
Частые вопросы
Почему именно 256 элементов, а не 1000 или 65536?
Конечное поле существует только тогда, когда число элементов — степень простого числа. 256 = 2⁸, и это ровно один байт. QR-код оперирует восьмибитными кодовыми словами, поэтому совпадение размера элемента поля и размера кодового слова принципиально: каждый байт данных — один элемент, каждый байт коррекции — тоже. Поле на 1000 элементов невозможно математически, а 65536 = 2¹⁶ существует, но потребовало бы двухбайтовых кодовых слов и вдвое более громоздких таблиц.
Чем поле Галуа из QR отличается от того, что дают в вузе?
Ничем по сути и многим по подаче. В курсе алгебры конечные поля вводят через факторизацию кольца многочленов и доказывают общие свойства. В QR-коде используется один конкретный случай — GF(2⁸) с фиксированным примитивным полиномом x⁸ + x⁴ + x³ + x² + 1 — и вся теория сводится к двум таблицам в памяти и паре десятков строк кода. Если вы искали конспект по алгебре, вам нужна общая теория; если разбираетесь, как QR чинит повреждения, достаточно правил «плюс — это XOR» и «умножение через логарифмы».
Почему 3 × 3 = 5, а не 9?
Потому что в GF(256) умножаются не числа, а многочлены над двоичными коэффициентами. Байт 3 — это 00000011, то есть x + 1. Возводим в квадрат: x² + 2x + 1. Коэффициенты берутся по модулю 2, значит 2x исчезает, остаётся x² + 1 — байт 00000101, то есть 5. Обычная девятка получилась бы при сложении с переносом, а переносов в этой арифметике нет. Именно отсутствие переносов и держит все результаты внутри одного байта.
Нужно ли знать GF(256), чтобы делать QR-коды?
Нет. Генератор считает коррекцию сам, а пользователю остаётся выбрать уровень L, M, Q или H и размер печати. Знание пригождается в двух случаях: когда пишете свой кодер и надо понимать, откуда берутся таблицы, и когда разбираетесь, почему код с логотипом читается, а с чуть большим логотипом уже нет. Практические рекомендации по выбору уровня собраны в термине восстановление ошибок QR.
Что будет, если взять неправильный примитивный полином?
Код сгенерируется, будет выглядеть как обычный QR, но не прочитается ни одним сканером. Байты коррекции окажутся посчитаны в другой арифметике, синдромы у декодера не сойдутся, и он либо вернёт ошибку, либо «исправит» данные в мусор. Это одна из типовых ошибок при самостоятельной реализации кодера: матрица собирается верно, маска накладывается верно, а константа поля взята из чужой спецификации.