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

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

Определение

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

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

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

Пример

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

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

$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).$

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

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

$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.$

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

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

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

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

$00000,\quad 00111,\quad 01110,\quad 01001,$

$11100,\quad 11011,\quad 10010,\quad 10101.$

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

Кодирование

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

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

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

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

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

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

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

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

Пример

Для приведенного выше кода с $n=5$, $m=2$и генераторный полином $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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

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