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

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

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

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

где многочлен степени 3. Тогда

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

Полученный результат легко обобщить на произвольный -код, для которого делит Наименьшее значение для которого делит обычно задает наибольшую полезную длину кода. Причина этого состоит в том, что два информационных символа, расположенные друг от друга на расстоянии приведут к одним и тем же проверочным символам, так что полученный код будет характеризоваться кодовым расстоянием 2. Заметим также, что наибольшее возможное значение лтах равно где степень порождающего многочлена. Это вытекает из того, что определяется как самый короткий цикл, который производится регистром сдвига, задаваемым когда на вход

его поступает единственный символ 1. Поскольку этот регистр содержит ячеек, он может находиться не более чем в различных ненулевых состояниях. Поэтому наибольшее значение Для некоторых многочленов циклы могут быть существенно короче, чем Читатель может легко проверить и убедиться, например, что многочлен порождает цикл длиной 9.

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