Полиномиальный код

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

Зафиксируем конечное поле , элементы которого мы называем символами . Для целей построения полиномиальных кодов мы отождествляем строку символов с полиномом${\displaystyle GF(q)}$${\displaystyle n}$${\displaystyle a_{n-1}\ldots a_{0}}$

${\displaystyle a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}.\,}$

Зафиксируем целые числа и пусть будет некоторым фиксированным многочленом степени , называемым порождающим многочленом . Полиномиальный код, сгенерированный с помощью , — это код, кодовые слова которого являются в точности многочленами степени, меньшей той, которая делится (без остатка) на .${\displaystyle m\leq n}$${\displaystyle g(x)}$${\displaystyle м}$${\displaystyle g(x)}$${\displaystyle n}$${\displaystyle g(x)}$

Рассмотрим полиномиальный код над с , , и генераторным полиномом . Этот код состоит из следующих кодовых слов:${\displaystyle GF(2)=\{0,1\}}$${\displaystyle n=5}$${\displaystyle м=2}$${\displaystyle g(x)=x^{2}+x+1}$

${\displaystyle 0\cdot g(x),\quad 1\cdot g(x),\quad x\cdot g(x),\quad (x+1)\cdot g(x),}$

${\displaystyle x^{2}\cdot g(x),\quad (x^{2}+1)\cdot g(x),\quad (x^{2}+x)\cdot g(x),\quad (x^{2}+x+1)\cdot g(x).}$

Или написано явно:

${\displaystyle 0,\quad x^{2}+x+1,\quad x^{3}+x^{2}+x,\quad x^{3}+2x^{2}+2x+1,}$

${\displaystyle x^{4}+x^{3}+x^{2},\quad x^{4}+x^{3}+2x^{2}+x+1,\quad x^{4}+2x^{3}+2x^{2}+x,\quad x^{4}+2x^{3}+3x^{2}+2x+1.}$

Поскольку полиномиальный код определен над двоичным полем Галуа , полиномиальные элементы представляются в виде суммы по модулю -2, а окончательные полиномы имеют вид:${\displaystyle GF(2)=\{0,1\}}$

${\displaystyle 0,\quad x^{2}+x+1,\quad x^{3}+x^{2}+x,\quad x^{3}+1,}$

${\displaystyle x^{4}+x^{3}+x^{2},\quad x^{4}+x^{3}+x+1,\quad x^{4}+x,\quad x^{4}+x^{2}+1.}$

Эквивалентно, выраженные в виде строк двоичных цифр, кодовые слова имеют вид:

${\displaystyle 00000,\quad 00111,\quad 01110,\quad 01001,}$

${\displaystyle 11100,\quad 11011,\quad 10010,\quad 10101.}$

Это, как и любой полиномиальный код, действительно является линейным кодом , т. е. линейные комбинации кодовых слов снова являются кодовыми словами. В таком случае, когда поле — GF(2), линейные комбинации находятся путем взятия XOR кодовых слов, выраженных в двоичной форме (например, 00111 XOR 10010 = 10101).

В полиномиальном коде с длиной кода и порождающим полиномом степени будет ровно кодовых слов. Действительно, по определению, является кодовым словом тогда и только тогда, когда оно имеет вид , где ( частное ) имеет степень меньше . Поскольку такие частные имеются , существует то же самое количество возможных кодовых слов. Поэтому простые (незакодированные) слова данных должны иметь длину${\displaystyle GF(q)}$${\displaystyle n}$${\displaystyle g(x)}$${\displaystyle м}$${\displaystyle q^{нм}}$${\displaystyle p(x)}$${\displaystyle p(x)=g(x)\cdot q(x)}$${\displaystyle q(x)}$${\displaystyle нм}$${\displaystyle q^{нм}}$${\displaystyle нм}$

Некоторые авторы, такие как (Lidl & Pilz, 1999), обсуждают отображение только как назначение от слов данных к кодовым словам. Однако это имеет тот недостаток, что слово данных не появляется как часть кодового слова. ${\displaystyle q(x)\mapsto g(x)\cdot q(x)}$

Вместо этого для создания систематического кода часто используется следующий метод : дано слово данных длины , сначала умножается на , что приводит к сдвигу на позиций влево. В общем случае не будет делиться на , т. е. это не будет допустимым кодовым словом. Однако существует уникальное кодовое слово, которое можно получить, отрегулировав самые правые символы . Чтобы вычислить его, вычислите остаток от деления на :${\displaystyle d(x)}$${\displaystyle нм}$${\displaystyle d(x)}$${\displaystyle x^{м}}$${\displaystyle d(x)}$${\displaystyle м}$${\displaystyle x^{m}d(x)}$${\displaystyle g(x)}$${\displaystyle м}$${\displaystyle x^{m}d(x)}$${\displaystyle x^{m}d(x)}$${\displaystyle g(x)}$

${\displaystyle x^{m}d(x)=g(x)\cdot q(x)+r(x),\,}$

где имеет степень меньше . Кодовое слово, соответствующее слову данных , тогда определяется как${\displaystyle r(x)}$${\displaystyle м}$${\displaystyle d(x)}$

${\displaystyle p(x):=x^{m}d(x)-r(x),\,}$

Обратите внимание на следующие свойства:

1. ${\displaystyle p(x)=g(x)\cdot q(x)}$, которое делится на . В частности, является допустимым кодовым словом.${\displaystyle g(x)}$${\displaystyle p(x)}$
2. Так как имеет степень меньше , то самые левые символы согласуются с соответствующими символами . Другими словами, первые символы кодового слова совпадают с исходным словом данных. Остальные символы называются контрольными цифрами или контрольными битами .${\displaystyle r(x)}$${\displaystyle м}$${\displaystyle нм}$${\displaystyle p(x)}$${\displaystyle x^{m}d(x)}$${\displaystyle нм}$${\displaystyle м}$

Для приведенного выше кода с , и полиномом-генератором мы получаем следующее назначение слов данных кодовым словам:${\displaystyle n=5}$${\displaystyle м=2}$${\displaystyle g(x)=x^{2}+x+1}$

• 000 ↦ 000 00
• 001 ↦ 001 11
• 010 ↦ 010 01
• 011 ↦ 011 10
• 100 ↦ 100 10
• 101 ↦ 101 01
• 110 ↦ 110 11
• 111 ↦ 111 00

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

Если предположить, что кодовое слово не содержит ошибок, то систематический код можно расшифровать, просто удалив цифры контрольной суммы. ${\displaystyle м}$

Если есть ошибки, то перед декодированием необходимо выполнить исправление ошибок. Эффективные алгоритмы декодирования существуют для определенных полиномиальных кодов, таких как коды BCH .

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

Более конкретные свойства полиномиального кода часто зависят от конкретных алгебраических свойств его порождающего полинома. Вот несколько примеров таких свойств:

• Полиномиальный код является циклическим тогда и только тогда, когда порождающий полином делит .${\displaystyle x^{n}-1}$
• Если порождающий полином примитивен , то полученный код имеет расстояние Хэмминга не менее 3, при условии, что .${\displaystyle n\leq 2^{m}-1}$
• В кодах БЧХ генераторный полином выбирается таким образом, чтобы иметь определенные корни в поле расширения, что обеспечивает высокое расстояние Хэмминга.

Алгебраическая природа полиномиальных кодов с умело выбранными генераторными полиномами также часто может быть использована для поиска эффективных алгоритмов исправления ошибок. Это касается кодов BCH .

• Циклические коды – каждый циклический код также является полиномиальным кодом; популярным примером является код CRC .
• Коды БЧХ – семейство циклических кодов с большим расстоянием Хэмминга и эффективными алгебраическими алгоритмами исправления ошибок.
• Коды Рида–Соломона — важное подмножество кодов БЧХ с особенно эффективной структурой.

• У. Дж. Гилберт и У. К. Николсон: Современная алгебра и ее приложения , 2-е издание, Wiley, 2004.
• Р. Лидл и Г. Пильц. Прикладная абстрактная алгебра, 2-е издание. Wiley, 1999.