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

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

Определение

Зафиксируем конечное поле , элементы которого мы называем символами . Для целей построения полиномиальных кодов мы отождествляем строку символов с полиномом ${\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 m}$ ${\displaystyle g(x)}$ ${\displaystyle n}$ ${\displaystyle g(x)}$

Пример

Рассмотрим полиномиальный код над с , , и генераторным полиномом . Этот код состоит из следующих кодовых слов: ${\displaystyle GF(2)=\{0,1\}}$ ${\displaystyle n=5}$ ${\displaystyle m=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 m}$ ${\displaystyle q^{n-m}}$ ${\displaystyle p(x)}$ ${\displaystyle p(x)=g(x)\cdot q(x)}$ ${\displaystyle q(x)}$ ${\displaystyle n-m}$ ${\displaystyle q^{n-m}}$ ${\displaystyle n-m}$

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

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

Пример

Для приведенного выше кода с , и полиномом-генератором мы получаем следующее назначение слов данных кодовым словам: ${\displaystyle n=5}$ ${\displaystyle m=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 m}$

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

Свойства полиномиальных кодов

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

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

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

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

Конкретные семейства полиномиальных кодов

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

Ссылки

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