ГЛАВА X. ЦИКЛИЧЕСКИЕ КОДЫ

1. Элементарные сведения из теории циклических кодов

Хаффмен [172-173] при изучении дискретных линейных фильтров установил, что получающиеся на их выходе двоичные последовательности наделены особенностями, присущими комбинациям групповых кодов. Кроме того, он показал, что такие схемы могут быть использованы для деления и умножения многочленов, а также для генерирования псевдослучайных последовательностей. Эти работы, по-видимому, и послужили толчком к детальному изучению как самих линейных переключательных схем (линейных дискретных фильтров), так и выяснению их связи с одним специфическим подмножеством линейных кодов — циклическими кодами.

Систематические исследования в этих направлениях были начаты Прейнджем [140], а основные положения этого раздела теории кодирования приобрели особую стройность после того, как Прейндж и Питерсон установили связь между циклическими кодами и идеалами. Основу этой главы составляет материал, изложенный в [29], а также результаты оригинальных работ Радчен-ко А.Н, Мирончикова Е. Т. и Колесника В. Д. [105, 106, 125, 126, 145, 146].

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

Например, множество комбинаций

(X.1.1)

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

При исследовании циклических кодов каждой -значной комбинации ставят в соответствие один из многочленов степени множества

(X.1.2)

где для интересующего нас бинарного случая и , если символ комбинаций равен нулю, и , если он равен единице.

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

(X.1.3)

(X.1.4)

Пример. Трехзначные комбинации множества в соответствии с (X.1.2) запишутся так:

(X.1.5)

Сумма двух комбинаций (многочленов), например и равна

(X.1.6)

Произведение выбранных многочленов определяется таким образом:

(X.1.7)

но , поэтому

(X.1.8)

Учитывая, что , окончательно получим

(X.1.9)

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

Например, множество полиномов, соответствующих трехзначным комбинациям (X.1.1), образуют идеал:

(X.1.10)

Проверим это обстоятельство. Выберем из (X.1.5) какой-нибудь полином, например (комбинация 001), и умножим на него каждый из полиномов (X.1.10):

(X.1.11)

Полученное множество многочленов с точностью до перестановки совпадает с (X.1.10). Для краткости письма здесь и в дальнейшем специально не оговаривается то, что умножение полиномов проводится по модулю полинома .

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

Порождающий многочлен обладает рядом характерных особенностей:

1) имеет наименьшую степень среди многочленов данного идеала;

2) свободный член всегда отличен от нуля;

3) любой многочлен идеала делится на без остатка;

4) является делителем двучлена

5) если степень многочлена равна k, то совпадает с векторным пространством . т. е. является линейным кодом, содержащим различных бинарных комбинаций ;

6) один из базисов циклического кода совпадает с комбинациями, соответствующими полиномам , где .

Умножение полинома на соответствует циклическому сдвигу вправо на i шагов коэффициентов полинома (от к ), что и предопределяет метод синтеза базиса циклического кода. Так, например, для мы имеем

(X.1.12)

Линейные формы кода (X.1.12) имеют вид

(X.1.13)

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

Пусть

(X.1.14)

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

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

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

Помимо в теории циклических кодов весьма важную роль играет так называемый генераторный полином

(X.1.15)

который ортогонален полиномам идеала .

Отсюда следует, что

(X.1.16)

( — произвольный полином из ).

Легко заметить, что степень полинома равна , а его свободный член всегда отличен от нуля. Так, например, для и (X.1.12) мы имеем

(X.1.17)

Отмеченные свойства полиномов и составляют основу синтеза кодирующих и декодирующих устройств циклических кодов.