4.2. Принцип построения циклических кодов

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

Неприводимые многочлены в теории циклических кодов играют роль образующих полиномов. В приложении 2 представлены все неприводимые полиномы до 9-й степени включительно, которые обознач где порядковый номер неприводимого полинома данной степени при расположении по признаку возрастания соответствующих им двоичных чисел. Чтобы понять принцип построения циклического кода, умножаем комбинацию простого А-значного кода на одночлен а затем делим на образующий полином степень которого равна В результате умножения на степень каждого одночлена, входящего в повышается на При делении произведения на образующий полином получается частное такой же степени, как и Результат умножения и деления можно представить как

где остаток от деления на

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

Умножая обе части равенства (4.3) на и производя некоторые перестановки, получаем

В (4.4) знак минус перед заменен знаком плюс, так как вычитгние по модулю два сводится к сложению.

Таким образом, кодовая комбинация циклического -значного кода может быть получена двумя способами [4]:

1) умножение кодовой комбинации простого кодата одночлен и добавление к этому произведению остатка полученного в результате деления произведения на образующий полином

2) умножение кодовой комбинации простого А-значного кода на образующий полином

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

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

Пример. Дано и образующий полином третьей степени Следовательно, кодовые комбинации циклического кода будут иметь по семь разрядов. Требуется записать произвольную кодовую комбинацию циклического кода (7,4) первым способом. Возьмем произвольную четырехразрядную комбинацию Найдем произведение Произведем деление:

Следовательно, остаток

Таким образом, в соответствии со сформулированным выше правилом найдем комбинацию, принадлежащую циклическому коду (7.4):

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

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

В результате деления получится остаток Следовательно, комбинация циклического кода (7,4) запишется следующим образом:

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

Таблица 29 (см. скан)

Итак, простую четырехсимвольную комбинацию можно представить семисимвольиым циклическим кодом

Результаты расчетов для всего множества кодовых комбинаций этого кода сведены в табл. 29.