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

Определим полиномиальный (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^n-k Степень остатка всегда меньше степени де­лителя, которая равна п — k. Поскольку кодируемая последователь­ность умножалась на x^n-k, в делимое входят лишь члены степе­ни, не меньшей п—k. Поэтому добавление остатка к частному не изменяет ни одного из членов в обоих многочленах. Выбирая в ка­честве делителя порождающий многочлен, можно добиться того, что результатом всегда будет кодовое слово.

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

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

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

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

Если подать на вход символ 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}