Порождающий многочлен

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

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

Порождающий многочлен g(x) — это многочлен степени r = n − k, где n — длина кодового слова, а k — длина информационного слова. Он является делителем двучлена xⁿ − 1 (или xⁿ + 1 в поле характеристики 2) и обладает следующими свойствами:

• Все кодовые слова циклического кода являются кратными порождающему многочлену. То есть, если информационное слово представлено многочленом m(x) степени не выше k − 1, то кодовое слово c(x) вычисляется как c(x) = m(x) · g(x).
• Порождающий многочлен является единственным многочленом минимальной степени среди всех ненулевых кодовых слов.
• Корни порождающего многочлена (в поле Галуа GF(2^m)) являются элементами, определяющими проверочную матрицу кода.

Математическая основа

Циклические коды, для которых строится порождающий многочлен, работают в конечных полях (полях Галуа). Наиболее распространённым является поле GF(2), где коэффициенты многочленов принимают значения 0 или 1, а операции сложения и умножения выполняются по модулю 2. В этом случае порождающий многочлен g(x) имеет вид:

g(x) = g₀ + g₁x + g₂x² + ... + gᵣxʳ,

где g₀ = 1 (так как многочлен должен быть нормированным, то есть старший коэффициент равен 1). Все коэффициенты gᵢ принадлежат {0, 1}.

Порождающий многочлен выбирается таким образом, чтобы он был делителем xⁿ − 1. Это гарантирует, что циклический сдвиг любого кодового слова также является кодовым словом. Для нахождения порождающего многочлена часто используется разложение xⁿ − 1 на неприводимые множители в поле GF(2). Порождающий многочлен представляет собой произведение одного или нескольких таких неприводимых множителей.

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

Выбор параметров кода

Для заданных n и k необходимо найти многочлен степени r = n − k, который делит xⁿ − 1. Если n = 2^m − 1 (для некоторого m), то код называется примитивным. В противном случае код является непримитивным.

Разложение двучлена

Двучлен xⁿ − 1 раскладывается на неприводимые многочлены над GF(2). Например, для n = 7:

x⁷ − 1 = (x + 1)(x³ + x + 1)(x³ + x² + 1).

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

Пример

Для кода Хэмминга (7, 4) параметры: n = 7, k = 4, r = 3. Порождающий многочлен может быть g(x) = x³ + x + 1 или g(x) = x³ + x² + 1. Оба многочлена имеют степень 3 и делят x⁷ − 1.

Кодирование с использованием порождающего многочлена

Систематическое кодирование

В систематическом коде информационные символы остаются неизменными в начале кодового слова, а проверочные символы добавляются в конец. Для этого используется следующая процедура:

1. Информационное слово представляется в виде многочлена m(x) степени k − 1.
2. Вычисляется произведение m(x) · xʳ, что эквивалентно сдвигу информационных битов на r позиций влево.
3. Вычисляется остаток r(x) от деления m(x) · xʳ на g(x).
4. Кодовое слово c(x) = m(x) · xʳ + r(x).

В этом случае c(x) делится на g(x) без остатка, что является необходимым условием для кодового слова.

Несистематическое кодирование

В несистематическом коде кодовое слово получается простым умножением: c(x) = m(x) · g(x). При этом информационные символы не выделяются явно, что усложняет декодирование.

Декодирование и обнаружение ошибок

Синдром

При приёме кодового слова v(x) (возможно, искажённого ошибкой) вычисляется синдром s(x) как остаток от деления v(x) на g(x). Если s(x) = 0, то считается, что ошибок нет. В противном случае синдром указывает на наличие ошибки и позволяет её локализовать.

Исправление ошибок

Для исправления ошибок используется проверочный многочлен h(x), который удовлетворяет соотношению g(x) · h(x) = xⁿ − 1. Синдром и структура порождающего многочлена позволяют определить позицию и значение ошибки. В двоичных кодах ошибка может быть только в одном бите, поэтому достаточно найти её позицию.

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

Код Хэмминга (7, 4)

• g(x) = x³ + x + 1 (или x³ + x² + 1).
• Исправляет одну ошибку.

Код БЧХ (15, 7)

• g(x) = x⁸ + x⁷ + x⁶ + x⁴ + 1.
• Исправляет до двух ошибок.

Код Рида-Соломона (255, 223)

• Порождающий многочлен строится в поле GF(256) и имеет степень 32.
• Исправляет до 16 ошибок.

Применение

Порождающие многочлены широко применяются в:

• Цифровой связи: коды Рида-Соломона используются в спутниковой связи, цифровом телевидении (DVB), системах хранения данных (CD, DVD, Blu-ray).
• Системах хранения данных: коды БЧХ и Рида-Соломона применяются в RAID-массивах, NAND-флеш-памяти.
• Криптографии: некоторые алгоритмы, такие как CRC (циклический избыточный код), основаны на порождающих многочленах и используются для контроля целостности данных.
• Телекоммуникациях: в стандартах Wi-Fi, Ethernet, Bluetooth для обнаружения ошибок.

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

• Порождающий многочлен для CRC (Cyclic Redundancy Check) часто выбирается из стандартных многочленов, таких как CRC-32 (0x04C11DB7), используемый в Ethernet и ZIP-архивах.
• В кодах Рида-Соломона порождающий многочлен может быть построен как произведение g(x) = (x − αⁱ)(x − αⁱ⁺¹)...(x − αⁱ⁺ᵈ⁻²), где α — примитивный элемент поля, а d — минимальное кодовое расстояние.
• Теория порождающих многочленов тесно связана с теорией конечных полей и алгебраической геометрией, что позволяет создавать коды с высокой корректирующей способностью.

Источники

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