Порождающий полином Рида — Соломона

Что такое порождающий полином

Порождающий полином (generator polynomial) — многочлен, на который QR-кодер делит данные блока, чтобы получить байты коррекции. Механика предельно конкретная: остаток от деления — это и есть ECC-часть, которая дописывается к блоку. Никакой отдельной «формулы коррекции» в стандарте нет, есть одно деление с остатком.

Считается всё в поле Галуа GF(256), где сложение — это XOR, а умножение идёт по таблицам логарифмов. Благодаря этому каждый коэффициент многочлена всегда остаётся одним байтом, то есть ровно одним кодовым словом QR.

Как он строится

Порождающий полином собирается перемножением простейших двучленов, корнями которых служат последовательные степени порождающего элемента поля:

g(x) = (x − α⁰)(x − α¹)(x − α²) … (x − αn−1)

Здесь n — количество байтов коррекции в блоке, α — порождающий элемент GF(256), то есть двойка. В QR-коде отсчёт корней начинается именно с α⁰; в других реализациях Рида — Соломона встречается старт с α¹, и перепутать их — верный способ получить нечитаемый код.

Минус в скобках можно не замечать: в GF(256) вычитание совпадает со сложением, поэтому запись через плюс равносильна. Проверим на самом маленьком случае — двух байтах коррекции:

• g(x) = (x + 1)(x + 2), потому что α⁰ = 1, α¹ = 2;
• коэффициент при x равен 1 + 2, то есть 1 XOR 2 = 3;
• свободный член равен 1 × 2 = 2;
• итог: g(x) = x² + 3x + 2.

Степень полинома всегда равна числу байтов коррекции. В QR-коде на один блок приходится от 7 до 30 кодовых слов коррекции — значит, используются полиномы степеней от 7 до 30, и их готовые коэффициенты вынесены в таблицы стандарта ISO/IEC 18004. Кодеру остаётся взять нужную строку, а какая именно нужна, определяет пара «версия плюс уровень коррекции».

Как из него получаются байты коррекции

Порядок действий для каждого блока данных:

1. Байты блока становятся коэффициентами многочлена: первый байт — при старшей степени, последний — при нулевой.
2. Многочлен умножается на x в степени n. На практике это просто дописывание n нулевых байтов в хвост — освобождается место под коррекцию.
3. Полученное делится на g(x) в GF(256) столбиком: берётся старший коэффициент делимого, на него умножается весь порождающий полином, результат складывается с делимым через XOR. Шаг повторяется, пока степень не станет меньше n.
4. Оставшиеся n коэффициентов — готовые байты коррекции блока.

Разберём на игрушечном примере: блок из одного байта со значением 5 и два байта коррекции. Дописываем два нуля — получается 5x². Старший коэффициент 5, умножаем на него g(x) = x² + 3x + 2 и получаем 5x² + 15x + 10, поскольку в GF(256) 5 × 3 = 15, а 5 × 2 = 10. Складываем с делимым по XOR: старшие члены гасят друг друга, остаётся 15x + 10. Значит, байты коррекции — 15 и 10.

В настоящем QR всё то же самое, только блок содержит десятки байтов, а степень полинома доходит до тридцати. Дальше блоки данных и блоки коррекции идут на чередование и укладываются в матрицу.

Что происходит при чтении

Ключевое свойство конструкции: правильный блок «данные + коррекция» целиком делится на g(x) без остатка. Это же означает, что подстановка любого из корней α⁰ … αⁿ⁻¹ в многочлен блока даёт ноль.

Декодер этим и пользуется. Он подставляет все n корней и смотрит на результаты — синдромы. Все нули значит, что блок цел, и коррекция не нужна. Ненулевые синдромы несут информацию о том, сколько байтов испорчено, в каких позициях и на какую величину: по ним алгоритм Рида — Соломона восстанавливает исходные значения. Чем выше степень порождающего полинома, тем больше синдромов и тем больше повреждений поддаётся починке.

Отсюда прямая связь с настройками генератора: выбирая уровень H вместо L, вы поднимаете степень порождающего полинома для каждого блока — и вместе с ней запас прочности кода. Попробовать разные уровни можно в конструкторе QR-кодов.

Частые вопросы