Идеалы многочленов и классы вычетов.

Рассмотрим многочлены f(X) от одного неизвестного (переменного) X с коэффициентами из некоторого поля F:

Степенью многочлена называется наибольшая степень X в слагаемом с ненулевым коэффициентом. Степень нулевого многочлена равно 0. Многочлен называется нормированным, если коэффициент при наивысшей степени X равен 1. Многочлены можно складывать и умножать обычным путем. Они образуют кольцо.

Если r(x), s(x) и t(x) – многочлены и r(x)s(x) = t(x), то говорят, что многочлен t(x) делится на многочлен r(x) или что многочлен r(x) является делителем многочлена t(x).

Неприводимый многочлен – многочлен p(x) степени n, который не делится ни на какой многочлен степени, меньшей, чем n, но большей чем 0.

НОД двух многочленов – нормированный многочлен наибольшей степени, который является делителем для обоих многочленов.

Два многочлена являются взаимно простыми, если их НОД равен 1.

Степень произведения двух многочленов равна сумме их степеней. Ненулевой многочлен степени 0 является элементом поля и поэтому имеет обратный элемент, но многочлены более высоких степеней не имеют обратных.

Если s(x) делится на r(x) и r(x) делится на s(x), то они отличаются самое большее множителем, который является элементом поля.

Пример:

ax², bx², а и в – элементы поля.

Для любой пары многочленов s(x) и d(x) существует единственная пара многочленов q(x) и r(x), таких, что

где q(x) – частное, r(x) – остаток и степень r(x) меньше степени d(x).

Пример:

GF(2)

x3(+)x2(+)1 / x(+)1

x3(+)x2 / x2

---------------------------------

x3(+)x2(+)1= (x(+)1) x2(+) 1

s(x) d(x) q(x) r(x)

В предположении, что делитель имеет первую степень, т.е. d(x) = x - a, можно получить несколько важных результатов о свойствах кольца многочленов.

Пусть

Поскольку многочлен r должен иметь степень, меньшую, чем степень делителя, он должен иметь степень равную 0, т.е. должен быть элементом поля. Подставляя в это равенство a вместо x получим

Если f(a) = 0, т.е. если a – корень многочлена f(x), то r=0 и многочлен (x-a) является многочленом f(x). Таким образом, каждому корню многочлена f(x) однозначно соответствует множитель первой степени. Поскольку степень произведения многочленов равно сумме степеней множителей, степень f(x) по крайней мере не меньше числа корней многочлена f(x).

НОД d(x) двух многочленов r(x) и s(x) всегда может быть представлен в виде

где a(x) и b(x) – многочлены.

Теорема 4: Совокупность многочленов образует идеал тогда и только тогда, когда она содержит все многочлены, кратные некоторому многочлену.

Идеал, состоящий из всех многочленов, кратных f(x) обозначается через (f(x)). Кольцо классов вычетов, образованных по этому идеалу, называется кольцом многочленов по модулю f(x).

Теорема 5: Каждый класс вычетов по модулю многочлена f(x) степени n содержит либо 0, либо многочлен степени, меньшей, чем n. Нуль является элементом идеала, а многочлены степеней, меньших, чем n, принадлежат различным классам вычетов.

Пример:

Идеал из чисел, кратных 3:

0 3 -3 6 -6 9 -9 … ® {0}

1 4 -2 7 -5 10 -8 … ® {1}

2 5 -1 8 -4 11 -7 … ® {2}

Классы вычетов по модулю x²+1 и GF(2):

0 x²+1 x(x²+1) (x+1)(x²+1) … ® {0}

1 x² x³+x+1 x³+x²+x … ® {1}

x x²+x+1 x³ x³+x²+1 … ® {x}

x+1 x²+x x³+1 x³+x² … ® {x+1}

Два многочлена являются взаимно простыми, если их НОД равен 1.

Пример:

ax², bx², а и в – элементы поля.

Для любой пары многочленов s(x) и d(x) существует единственная пара многочленов q(x) и r(x), таких, что

где q(x) – частное, r(x) – остаток и степень r(x) меньше степени d(x).

Пример:

GF(2)

x3(+)x2(+)1 / x(+)1

x3(+)x2 / x2

---------------------------------

x3(+)x2(+)1= (x(+)1) x2(+) 1

s(x) d(x) q(x) r(x)

Пусть

НОД d(x) двух многочленов r(x) и s(x) всегда может быть представлен в виде

где a(x) и b(x) – многочлены.

Пример:

Идеал из чисел, кратных 3:

0 3 -3 6 -6 9 -9 … ® {0}

1 4 -2 7 -5 10 -8 … ® {1}

2 5 -1 8 -4 11 -7 … ® {2}

Классы вычетов по модулю x²+1 и GF(2):

0 x²+1 x(x²+1) (x+1)(x²+1) … ® {0}

1 x² x³+x+1 x³+x²+x … ® {1}

x x²+x+1 x³ x³+x²+1 … ® {x}

x+1 x²+x x³+1 x³+x² … ® {x+1}

Полиномиальные коды.

Определим полиномиальный (n, k)-код как множество всех многочленов степени n—1 или меньше, делящихся на g(x). Степень g(x) равна . Например, если

то множество многочленов вида

образует (6, 3)-код. Заметим, что существует ровно восемь различных многочленов в соответствии с восемью различными способами выбора коэффициентов а₀, а₁, а₂ в поле GF (2). Один из способов применения этого кода состоит в том, чтобы взять а₀, а₁, а₂ в качестве информационных символов и выполнить соответствующие умножения. Результат будет

Устройство, производящее это умножение, показано на рис. 1. Хотя такой метод кодирования вполне пригоден, его недостаток состоит в том, что полученный код обычно оказывается несистематическим. (В данном примере код является систематическим в позициях 1, 5, 6; однако в общем случае это не так.)

Полиномиальные (n, k)-коды обладают тем свойством, что их всегдаможно сделать систематическими в первых k позициях. В рассматриваемом примере положим

b₀= а₀, b₂ = а₀ + а₁, b₂ = а₁ + а₂.

Решив систему уравнений относительно a_i и подставив результат в (*), получим кодовый многочлен вида

с(x) =b₀+ b₁x +b₂x²+ (b₁ + b₂)x³ + (b_o+b₁)x⁴ + (b_o+b₁+b₂)x⁵.

Этот кодовый многочлен имеет обычный вид кода с проверками на четность, и можно заметить, что если поменять местами первый и второй проверочные символы, то полученный код будет совпадать с (6, 3)-кодом с проверками на четность. С тем же успехом можно выбрать и другое множество информационных символов.

Рис. Схема для умножения произвольного многочлена

a_o+ a₂x +a₂x² на g(x) = 1+x+x³

Например, выбрав последние три символа, получим

c(x) = (b₀+b₂) + (b_o + b₁ + b₂)x + (b₁ + b₂)x² + b₀x ³ + b₁x ⁴ + b₂ x ⁵ (**)

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

Очевидно, как построить кодер для каждого из систематических вариантов полученного кода. Вначале нужно выразить элементы a_i в виде линейных комбинаций элементов b_i, а затем использовать схему на рис. 1 для осуществления соответствующих умножений.

Второй метод, который, по существу, является объединением этих двух шагов, состоит в следующем. Предположим, что умножаем многочлен b₀ + b₁x + b₂x² на x ³, получая b₀х³ + b₁х⁴+ b₂х⁵. Разделив полученный многочлен на 1 + х + х³, найдем частное (b_o+ b₂) + b₁x + b₂x² и остаток (b₀+b₂) + (b₀ + b₁ + b₂)x+ (b₁ + b₂)x². Заметим, что, прибавив остаток к делимому, получим кодовое слово (**) в систематическом виде. Эта процедура состоит в применении алгоритма Евклида, согласно которому

делимое = (частное) (делитель) + остаток.

В случае общего (n, k)-кода предварительное умножение всегда производится на xⁿ^-^k Степень остатка всегда меньше степени делителя, которая равна п — k. Поскольку кодируемая последовательность умножалась на xⁿ^-^k, в делимое входят лишь члены степени, не меньшей п—k. Поэтому добавление остатка к частному не изменяет ни одного из членов в обоих многочленах. Выбирая в качестве делителя порождающий многочлен, можно добиться того, что результатом всегда будет кодовое слово.

Содержимое ячеек	сдвиг

b₂	b₂
b₁	b₁ + b₂	b₂
b_o + b₂	b_o+b₁+b₂	b₁+ b₂

Рис. Схема для одновременного умножения на х³ и деления на 1+x+x³

Схема, реализующая этот алгоритм для (6, 3)-кода, показана на рис. 2. При использовании этой схемы последовательность b₂, b₁, b₀ подается на вход по одному символу за такт. Содержимое различных ячеек после каждого сдвига показано на рис. 2. После трех сдвигов остаток (три проверочных символа) запоминается в трех ячейках регистра сдвига. Произведя длинные операции деления, можно удостовериться в том, что согласно этой схеме операции сдвига и вычитания повторяются на каждом шаге. При необходимости частное может быть получено в виде последовательных членов в цепи обратной связи.

Рис. Регистр обратной связи и соответствующая последовательность состояний при поступлении на вход одного символа 1

Полезной может оказаться еще одна точка зрения. Сделаем, чтобы схема, изображенная на рис. 2, начала работать таким образом, чтобы в самой левой ячейке появился символ 1. Производя в схеме несколько сдвигов и не подавая ничего на ее вход, будем получать содержимое регистров, показанное на рис. 3. Можно заметить, что полученные тройки совпадают со столбцами проверочной матрицы, и если остановиться после семи шагов, то полученная матрица будет совпадать с проверочной матрицей (7, 4)-кода Хемминга. Сделав меньше семи шагов, получим проверочную матрицу укорочения этого кода. Заметим также, что, произведя больше семи сдвигов, получим уже встречавшиеся тройки. Полученную матрицу по-прежнему можно рассматривать как проверочную матрицу кода, однако кодовое расстояние теперь уменьшилось до 2, поскольку один и тот же столбец повторился несколько раз. Работу согласно схеме на рис. 2 можно также рассматривать с помощью порождающей матрицы. Порождающая матрица (7, 4)-кода Хемминга имеет вид

1 1 0 1 0 0 0 0 1 1 0 1 0 0 1 1 1 0 0 1 0 1 0 1 0 0 0 1

Если подать на вход символ 1 и сделать один сдвиг, то в соответствующих ячейках появится набор 1 1 0. После второго сдвига появится набор 0 11, после третьего 1 1 1 и после четвертого 1 0 1. Эти четыре тройки совпадают с четырьмя строками проверочной части порождающей матрицы. При вводе в регистр последовательности 1 0 0 0 (начиная с самого правого символа) получим проверочную последовательность 1 1 0. Аналогично при вводе в регистр последовательности 0 0 0 1 появятся проверочные символы 101. Кроме того, рассматриваемое устройство является линейным, так что при вводе в регистр последовательности 1 0 0 1 результатом будет 0 11. Эти проверочные символы возникают при сложении первой и четвертой строк порождающей матрицы.

Циклические коды.

При некоторых значениях п полиномиальные коды обладают свойством цикличности. Это значит, что циклическая перестановка
символов кодового слова вновь приводит к кодовому слову. При-
чина наличия такого свойства может быть проиллюстрирована на
примере уже рассмотренного порождающего многочлена 1+x+x³.

Заметим прежде всего, что 1+x+x³ точно делит многочлен 1—х⁷. Это можно проверить непосредственным делением или с помощью схемы на рис. 3. Напомним, что эта схема порождает цикл длиной 7. Поэтому, если подать на вход символ 1, осуществить сдвиг семь раз и затем подать еще один символ 1 (т.е. разделить х⁷—1), второй входной символ сократит содержимое регистра и в качестве остатка получится нулевой многочлен.

Предположим теперь, что взято кодовое слово (7, 4)-кода, порожденного многочленом 1 + х + х³, и сдвинуто циклически на один элемент вправо. Это значит, что каждый символ передвинут на одно место вправо и самый правый символ переведен на левый конец. Математически это эквивалентно умножению на х и замене х⁷ на 1, т. е. приведению многочлена по модулю х⁷—1. Предположим, что выбрано кодовое слово, самый правый символ которо-го) равен 1. Это кодовое слово может быть записано в виде

с(х) = (1+ х + х³)р(х),

где р(х) — многочлен степени 3.

Тогда хс(х)≡ хс(х) — (х⁷—1) тоd (х⁷— 1).

Поскольку х⁷—1 делится на 1 + х + х³, многочлен в правой части этого равенства очевидно делится на 1+х+х³. Поэтому циклический сдвиг данного кодового слова снова дает кодовое слово. Заметим, что если самый правый символ кодового слова равен 0, то циклический сдвиг эквивалентен умножению на х и наше утверждение по-прежнему справедливо.

Полученный результат легко обобщить на произвольный (n, k)-код, для которого g(x) делит хⁿ—1. Наименьшее значение п, для которого g(x) делит хⁿ—1, обычно задает наибольшую полезную длину n_max кода. Причина этого состоит в том, что два информационных символа, расположенные друг от друга на расстоянии n+1, приведут к одним и тем же проверочным символам, так что полученный код будет характеризоваться кодовым расстоянием 2. Заметим также, что наибольшее возможное значение nmах равно 2^m-1, где m — степень порождающего многочлена. Это вытекает из того, что n_max определяется как самый короткий цикл, который производится регистром сдвига, задаваемым g(x), когда на вход его поступает единвтенный символ 1. Поскольку этот регистр содержит m ячеек, он может находится не более чем в 2^m-1 различных ненулевых состояниях. Поэтому наибольшее значение n_max=2^m-1. Для некоторых многочленов циклы могут быть существенно короче, чем 2^m-1. Можно легко проверить и убедиться, что, например, многочлен 1+x³+x⁶ порождает цикл длиной 9.

Полиномиальные коды, для которых n< n_max, как, например, рассмотренный (6, 3)-код, называются укороченными циклическими или псевдоциклическими кодами. Для любого значения n всегда можно найти некоторый многочлен степени n делящийся на g(x). Использовав этот многочлен, можно рассмотреть класс перестановок, получающихся при умножении кодового слова на x и приведении результата по модулю этого многочлена. Хотя эта процедура, очевидно, приводит к кодовому слову, она не находит до сих пор существенного применения. Обычно укороченные циклические коды, рассматриваются как циклические путем добавления в конце кодового слова подходящего числа нулевых символов.

Код C называется циклическим кодом, если это (i) линейный код и циклический сдвиг на любое число разрядов кодового слова, является также кодовым словом. Например, если a₀ a₁ … a_n_-1 принадлежит C, то и a_n_-1 a₀ a₁ … a_n_-2принадлежит C.

Циклические коды были впервые исследованы Prange (1957). Было доказано, что практически любой специальный линейный код открытый ранее (напр. Хэмминга, Голея, Рида-Маллера) может быть преобразован в циклический.

Например, двоичный код {000, 101, 011, 011} циклический.

Двоичный линейный код {0000, 1001, 0110, 1111} не циклический, но он эквивалентен циклическому коду, т.к. перестановка 3 и 4 бита дает циклический код {0000, 1010, 0101, 1111}

Задачи

Определить циклический ли код, эквивалентен ли циклическому коду?

(i) двоичный код {0000, 1100, 0110, 0011, 1001}

(ii) двоичный код {00000, 10110, 01101, 110011}

(iii) троичный код {0000, 1122, 2211}

⇐ Предыдущая 1 2 3 45