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

редактировать

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

Содержание

1 Определение
2 Пример
3 Кодирование
- 3.1 Пример
4 Декодирование
5 Свойства полиномиальных кодов
6 Конкретные семейства полиномиальных кодов
7 Ссылки

Определение

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

an - 1 xn - 1 + ⋯ + a 1 x + a 0. {\ displaystyle a_ {n-1} x ^ {n-1} + \ cdots + a_ {1} x + a_ {0}. \,}

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

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

Пример

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

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

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

x 2 ⋅ g (x), (х 2 + 1) ⋅ g (x), (x 2 + x) ⋅ g (x), (x 2 + x + 1) ⋅ 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).}

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, x 2 + x + 1, x 3 + x 2 + x, x 3 + 2 Икс 2 + 2 Икс + 1, {\ Displaystyle 0, \ quad x ^ {2} + x + 1, \ quad x ^ {3} + x ^ {2} + x, \ quad x ^ {3 } + 2x ^ {2} + 2x + 1,}

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, x 4 + x 3 + 2 x 2 + x + 1, x 4 + 2 x 3 + 2 x 2 + x, x 4 + 2 x 3 + 3 x 2 + 2 x + 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.}

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} {\ displaystyle GF (2) = \ {0,1 \}}$ $GF (2) = \ {0,1 \}$ , полиномиальные элементы представлены в виде суммы по модулю -2, а окончательные многочлены:

0, x 2 + x + 1, x 3 + x 2 + Икс, Икс 3 + 1, {\ Displaystyle 0, \ quad x ^ {2} + x + 1, \ quad x ^ {3} + x ^ {2} + x, \ quad x ^ {3} +1, }

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

x 4 + x 3 + x 2, x 4 + x 3 + x + 1, x 4 + x, x 4 + x 2 + 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.}

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

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

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

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

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

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

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

Кодирование

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

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

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

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

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

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

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

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

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

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

Пример

Для приведенного выше кода с $n = 5 {\ displaystyle n = 5}$ $n = 5$ , $m = 2 {\ displaystyle m = 2}$ $m = 2$ и порождающий многочлен $g (x) = x 2 + x + 1 {\ displaystyle g (x) = x ^ {2} + x + 1}$ $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 {\ displaystyle m}$ $m$ цифр контрольной суммы.

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

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

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

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

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

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

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

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

Ссылки

WJ Гилберт и В.К. Николсон: Современная алгебра с приложениями, 2-е издание, Wiley, 2004.
R. Lidl и G. Pilz. Прикладная абстрактная алгебра, 2-е издание. Wiley, 1999.