Базис циклического кода, формирование кодовых комбинаций.

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

Рассмотрим циклический сдвиг кодовой комбинации:

Такая циклическая перестановка при представлении комбинаций в виде полиномов соответствует умножению данного полинома на . Чтобы степень полученного полинома не превышала член заменяется единицей. Поэтому .

Например, имеем кодовую комбинаццию: . Образуем циклический сдвиг на один разряд: . Заменив на единицу, имеем , т. е. сдвинутую на один разряд исходную кодовую комбинацию.

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

Таблица 7.2

Пример 7.8. Сформировать базис циклического кода (7,4) с Для формирования первой разрешенной комбинации базиса следует взять кодовую комбинацию с соответствующую образующему полиному (Ясно, что она будет делиться без остатка на образующий полином.)

Итак, первая разрешенная комбинация имеет

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

Тогда производящая матрица циклического кода (7,4) имеет вид:

Все остальные кодовые комбинации можно определить линейной композицией комбинации базиса (ср. с производящей матрицей (7,3)).

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

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

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

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

Пример 7.9. Задана кодовая комбинация простого семиэлементного кода Надо образовать циклический код (9,7). Это код, у которого — степень образующего многочлена (число проверочных элементов) равна 2.

Из табл 7 1

Повысим степень полинома на два:

Определим группу проверочных разрядов в виде остатка от деления на Значение остатка будет Найдем полином разрешенной кодовой комбинации

Кодовая комбинация имеет вид 100101110.

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

Тогда

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

что соответствует кодовой комбинации 111110001 Выделить позиции информационных элементов здесь нельзя. Поэтому на практике используется первый способ построения циклического кода.