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

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

Определение

Исправить конечное поле ${ Displaystyle GF (q)}$, элементы которого мы называем символы. Для построения полиномиальных кодов мы идентифицируем строку ${ displaystyle n}$ символы ${ Displaystyle а_ {п-1} ldots а_ {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 г (х) = х ^ {2} + х + 1}$. Этот код состоит из следующих кодовых слов:

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

${ Displaystyle х ^ {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.}$

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

${ 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 д ^ {н-м}}$ кодовые слова. Действительно, по определению ${ displaystyle p (x)}$ является кодовым словом тогда и только тогда, когда оно имеет форму ${ Displaystyle р (х) = г (х) cdot q (х)}$, куда ${ displaystyle q (x)}$ (в частное) имеет степень меньше, чем ${ displaystyle n-m}$. Поскольку есть ${ Displaystyle д ^ {н-м}}$ такие коэффициенты доступны, существует такое же количество возможных кодовых слов. Следовательно, простые (незакодированные) слова данных должны иметь длину ${ displaystyle n-m}$

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

Вместо этого часто используется следующий метод для создания систематический код: дано слово данных ${ 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 х ^ {м} d (х) = г (х) cdot q (х) + г (х), ,}$

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

${ Displaystyle р (х): = х ^ {м} d (х) -r (х), ,}$

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

1. ${ Displaystyle р (х) = г (х) cdot q (х)}$, который делится на ${ displaystyle g (x)}$. Особенно, ${ displaystyle p (x)}$ - допустимое кодовое слово.
2. С ${ Displaystyle г (х)}$ имеет степень меньше, чем ${ 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 г (х) = х ^ {2} + х + 1}$, мы получаем следующее присвоение слов данных кодовым словам:

• 000 ↦ 00000
• 001 ↦ 00111
• 010 ↦ 01001
• 011 ↦ 01110
• 100 ↦ 10010
• 101 ↦ 10101
• 110 ↦ 11011
• 111 ↦ 11100

Расшифровка

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

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

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

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

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

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

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

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

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

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

Рекомендации

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