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

6.7.1. Алгебраическая структура циклических кодов

6.7.2. Свойства двоичного циклического кода

6.7.3. Кодирование в систематической форме

6.7.4. Логическая схема для реализации полиномиального деления

6.7.5. Систематическое кодирование с (n-k)-разрядным регистром сдвига

6.7.6. Обнаружение ошибок с помощью (n-k)-разрядного регистра сдвига

Важным подклассом линейных блочных кодов являются двоичные циклические коды (cyclic codes). Код легко реализуется на регистре сдвига с обратной связью; на подобных регистрах сдвига с обратной связью вычисляется синдром; алгебраическая структура циклического кода естественным образом позволяет эффективно реализовать методы декодирования. Итак, линейный код (n, k) называется циклическим, если он обладает следующим свойством. Если n-кортеж является кодовым словом в подпространстве S, тогда , полученный из U с помощью циклического сдвига, также является кодовым словом в S. Или, вообще, , полученный i циклическими сдвигами, является кодовым словом в S.

Компоненты кодового слова можно рассматривать как коэффициенты полинома .

(6.54)

Полиномиальную функцию U(X) можно рассматривать как «заполнитель» разрядов кодового слова U, т.е. вектор n-кортежа описывается полиномом степени или меньше. Наличие или отсутствие каких-либо членов в полиноме означает наличие 1 или 0 в соответствующем месте n-кортежа. Если -й компонент отличен от нуля, порядок полинома равен . Удобство такого полиномиального представления кодового слова станет более понятным по мере дальнейшего обсуждения алгебраических свойств циклических кодов.

6.7.1. Алгебраическая структура циклических кодов

В кодовых словах, выраженных в полиномиальной форме, циклическая природа кода проявляется следующим образом. Если U(X) является кодовым словом, представленным полиномом порядка , то — остаток от деления на — также является кодовым словом. Иными словами,

(6.55,a)

или, умножая обе части уравнения на ,

, (6.55,б)

что в модульной арифметике можно описать следующим образом.

по модулю (6.56)

Здесь «х по модулю у» означает остаток от деления х на у. Ниже справедливость выражения (6.56) демонстрируется для случая i = 1.

К последнему выражению прибавим и вычтем или, поскольку мы пользуемся арифметическими операциями по модулю 2, можем прибавить дважды.

Поскольку порядок равен , этот полином не делится на . Таким образом, используя уравнение (6.55,а), можно записать следующее.

по модулю

Обобщая, приходим к уравнению (6.56).

по модулю

Пример 6.7. Циклический сдвиг вектора кода

Пусть U = 1 1 0 1 для n = 4. Выразите кодовое слово в полиномиальной форме и, используя уравнение (6.56), выполните третий циклический сдвиг кодового слова.

Решение

полином записан в порядке возрастания степени

, где

Разделим на и найдем остаток, используя полиномиальное деление.