Порождающие полиномы¶

Порождающий полином — это многочлен, используемый в теории кодирования для построения циклических кодов, а также в криптографии и других областях дискретной математики. Порождающий полином однозначно определяет структуру кода, его корректирующие свойства и способ кодирования. В контексте циклических кодов порождающий полином является делителем двучлена \(x^n - 1\) (или \(x^n + 1\) в зависимости от поля) и задаёт множество всех кодовых слов как идеал кольца многочленов по модулю этого двучлена.

¶Определение и основные свойства

Пусть задано конечное поле \(GF(q)\) (поле Галуа из \(q\) элементов, где \(q\) — степень простого числа). Циклический код длины \(n\) над \(GF(q)\) — это линейное подпространство размерности \(k\) в пространстве всех векторов длины \(n\), инвариантное относительно циклического сдвига координат. Каждому кодовому слову \((c_0, c_1, \dots, c_{n-1})\) ставится в соответствие многочлен \(c(x) = c_0 + c_1 x + \dots + c_{n-1} x^{n-1}\). Кодовые слова образуют идеал в кольце \(R_n = GF(q)[x] / (x^n - 1)\), то есть замкнуты относительно умножения на \(x\) по модулю \(x^n - 1\).

Порождающим полиномом \(g(x)\) циклического кода называется ненулевой многочлен наименьшей степени в этом идеале. Он обладает следующими свойствами:

• \(g(x)\) делит \(x^n - 1\) без остатка.
• Степень \(g(x)\) равна \(r = n - k\), где \(k\) — размерность кода.
• Все кодовые многочлены кратны \(g(x)\): \(c(x) = m(x) g(x)\), где \(m(x)\) — информационный многочлен степени не выше \(k-1\).
• Порождающий полином единственен с точностью до умножения на ненулевую константу из \(GF(q)\); обычно выбирают нормированный (со старшим коэффициентом 1).

¶Пример: код Хэмминга

Код Хэмминга длины 7 над полем \(GF(2)\) (двоичный код) имеет порождающий полином \(g(x) = x^3 + x + 1\). Этот многочлен делит \(x^7 - 1\) (над \(GF(2)\) вычитание совпадает со сложением), так как \(x^7 - 1 = (x^3 + x + 1)(x^4 + x^2 + x + 1)\). Степень \(g(x)\) равна 3, размерность кода \(k = 7 - 3 = 4\). Кодовые слова — все многочлены, кратные \(g(x)\) по модулю \(x^7 - 1\).

¶Классификация порождающих полиномов

Порождающие полиномы классифицируются по нескольким признакам:

¶По типу кода

• БЧХ-коды (Боуза — Чоудхури — Хоквингема). Порождающий полином строится как наименьшее общее кратное минимальных многочленов для заданного набора корней — степеней примитивного элемента поля. Например, для двоичного БЧХ-кода с конструктивным расстоянием \(d\) порождающий полином содержит все минимальные многочлены для \(\alpha^{m_0}, \alpha^{m_0+1}, \dots, \alpha^{m_0+d-2}\), где \(\alpha\) — примитивный элемент поля \(GF(2^m)\).
• Коды Рида — Соломона. Частный случай БЧХ-кодов над полем \(GF(q)\), где \(n = q - 1\). Порождающий полином имеет вид \(g(x) = (x - \alpha^{m_0})(x - \alpha^{m_0+1}) \dots (x - \alpha^{m_0+d-2})\), где \(\alpha\) — примитивный элемент поля. Степень \(g(x)\) равна \(d-1\), размерность \(k = n - d + 1\).
• Коды с повторением. Для кода длины \(n\) с повторением каждого бита \(r\) раз порождающий полином — \(g(x) = 1 + x + x^2 + \dots + x^{r-1}\) (при условии, что \(n\) кратно \(r\)).
• Коды чётности. Простейший код с одной проверкой на чётность имеет порождающий полином \(g(x) = x + 1\) (над \(GF(2)\)), так как \(x^n - 1 = (x+1)(x^{n-1} + x^{n-2} + \dots + 1)\) при нечётном \(n\).

¶По полю

• Двоичные порождающие полиномы — над \(GF(2)\). Коэффициенты — 0 или 1, арифметика по модулю 2. Примеры: \(x^3 + x + 1\), \(x^4 + x^3 + 1\).
• Недвоичные — над \(GF(q)\) для \(q > 2\). Например, над \(GF(3)\) порождающий полином может иметь коэффициенты 0, 1, 2. Для кодов Рида — Соломона часто используют поле \(GF(256)\) (байтовое поле).

¶По структуре корней

Порождающий полином можно задать через его корни в расширении поля. Если \(g(x)\) имеет корни \(\alpha^{i_1}, \alpha^{i_2}, \dots, \alpha^{i_r}\) (где \(\alpha\) — примитивный элемент поля \(GF(q^m)\)), то \(g(x) = \prod_{j=1}^r (x - \alpha^{i_j})\). Корни определяют корректирующую способность кода: минимальное расстояние кода не меньше числа последовательных корней (теорема БЧХ).

¶Применение порождающих полиномов

¶Кодирование

Кодирование с помощью порождающего полинома выполняется двумя основными способами:

1. Систематическое кодирование. Информационный многочлен \(m(x)\) умножается на \(x^{n-k}\), затем вычисляется остаток \(r(x) = m(x) x^{n-k} \mod g(x)\). Кодовое слово: \(c(x) = m(x) x^{n-k} + r(x)\). При этом первые \(k\) коэффициентов \(c(x)\) совпадают с информационными символами, а последние \(n-k\) — проверочные.
2. Несистематическое кодирование. Кодовое слово получается как \(c(x) = m(x) g(x)\). В этом случае информационные символы не выделяются явно.

¶Декодирование

Порождающий полином используется для построения проверочного полинома \(h(x) = (x^n - 1) / g(x)\). Проверочная матрица кода строится на основе коэффициентов \(h(x)\). Алгоритмы декодирования (например, алгоритм Берлекэмпа — Месси для БЧХ-кодов) используют корни порождающего полинома для локализации и исправления ошибок.

¶Криптография

В криптосистеме Мак-Элиса (McEliece) порождающий полином входит в состав секретного ключа. Код Гоппы, используемый в этой системе, задаётся порождающим полиномом над полем \(GF(2^m)\). Порождающий полином также применяется в криптосистеме Нидеррайтера (Niederreiter) и в постквантовых криптосхемах на основе кодов.

¶Цифровая обработка сигналов

Порождающие полиномы используются в циклических избыточных кодах (CRC — Cyclic Redundancy Check) для обнаружения ошибок в каналах передачи данных. Например, CRC-32 имеет порождающий полином \(x^{32} + x^{26} + x^{23} + x^{22} + x^{16} + x^{12} + x^{11} + x^{10} + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1\) (над \(GF(2)\)). В этом случае кодирование сводится к вычислению остатка от деления сообщения на порождающий полином.

¶Построение порождающего полинома

Для заданного набора параметров (длина кода \(n\), размерность \(k\), минимальное расстояние \(d\)) порождающий полином строится следующим образом:

1. Выбирается поле \(GF(q)\) и примитивный элемент \(\alpha\).
2. Определяется множество корней: \(\alpha^{m_0}, \alpha^{m_0+1}, \dots, \alpha^{m_0+d-2}\) (для БЧХ-кода).
3. Для каждого корня находится минимальный многочлен \(m_i(x)\) — многочлен наименьшей степени над \(GF(q)\), корнем которого является \(\alpha^i\).
4. Порождающий полином вычисляется как \(g(x) = \text{НОК}(m_{m_0}(x), m_{m_0+1}(x), \dots, m_{m_0+d-2}(x))\).

Для кодов Рида — Соломона минимальные многочлены имеют степень 1, поэтому \(g(x) = \prod_{i=m_0}^{m_0+d-2} (x - \alpha^i)\).

¶Пример: построение двоичного БЧХ-кода длины 15

Поле \(GF(2^4)\) с примитивным элементом \(\alpha\), удовлетворяющим \(\alpha^4 + \alpha + 1 = 0\). Пусть \(m_0 = 1\), \(d = 3\). Корни: \(\alpha^1, \alpha^2\). Минимальные многочлены:

• Для \(\alpha^1\): \(m_1(x) = x^4 + x + 1\).
• Для \(\alpha^2\): \(m_2(x) = x^4 + x + 1\) (так как \(\alpha^2\) и \(\alpha^1\) сопряжены в поле \(GF(2^4)\)).

Порождающий полином: \(g(x) = (x^4 + x + 1)(x^4 + x + 1) = x^8 + x^4 + x^2 + x + 1\) (над \(GF(2)\)). Степень 8, размерность \(k = 15 - 8 = 7\). Код исправляет одну ошибку (так как \(d=3\)).

¶Интересные факты

• Порождающие полиномы циклических кодов тесно связаны с теорией конечных полей и теорией идеалов в кольцах многочленов. В частности, каждый циклический код соответствует идеалу, порождённому \(g(x)\).
• Для кодов Рида — Соломона, используемых в компакт-дисках (CIRC-код), порождающие полиномы имеют вид \((x - \alpha^0)(x - \alpha^1) \dots (x - \alpha^{d-2})\).
• В стандарте QR-кодов (QR Code) применяются коды Рида — Соломона с порождающими полиномами, построенными над полем \(GF(256)\); степень порождающего полинома зависит от уровня коррекции ошибок (от 7 до 68).
• Порождающий полином CRC-32 (используемый в Ethernet, ZIP, PNG) был разработан в 1975 году и является одним из наиболее распространённых в вычислительной технике.

¶Критика и ограничения

• Порождающие полиномы не всегда позволяют построить код с максимально возможным минимальным расстоянием для заданных \(n\) и \(k\) (проблема оптимальности кодов). Для некоторых параметров существуют коды, не являющиеся циклическими, но имеющие лучшие корректирующие свойства.
• Вычисление порождающего полинома для длинных кодов (например, \(n > 10^5\)) требует значительных вычислительных ресурсов, особенно при работе с большими полями.
• В криптографии коды на основе порождающих полиномов (например, в системе Мак-Элиса) уязвимы к атакам, использующим структурные свойства кода, хотя в постквантовой криптографии они остаются перспективными.

¶Источники

• Блейхут Р. Теория и практика кодов, контролирующих ошибки. — М.: Мир, 1986.
• Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. — М.: Мир, 1976.
• Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. — М.: Связь, 1979.
• Лидл Р., Нидеррайтер Г. Конечные поля. — М.: Мир, 1988.
• ГОСТ Р 34.11-2012 (Информационная технология. Криптографическая защита информации. Функция хэширования) — содержит упоминания порождающих полиномов для CRC.