5.2. ПОЛИНОМИАЛЬНОЕ ОПИСАНИЕ ЦИКЛИЧЕСКИХ КОДОВ

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

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

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

Циклический сдвиг может быть записан через умножение в этом кольце:

Итак, если кодовые слона некоторого кода задаются в виде многочленов, то код является подмножеством кольца Такой код является циклическим, если вместе с каждым кодовым словом с он содержит кодовый многочлен X с

Теорема 5.2.1. Подмножество кольца образует циклический тогда и только тогда, когда он обладает следующими двумя свойствами:

1) 9 образует подгруппу кольца по сложению;

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

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

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

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

Теорема 5.2.2. Циклический код состоит из всех произведений порождающего многочлена на многочлены степени не выше —1.

Доказательство. Согласно теореме 5.2.1, все такие многочлены принадлежат коду, так как принадлежит коду. Далее,

если некоторый многочлен с принадлежит коду, то, согласно алгоритму деления,

где и многочлен

является кодовым, так как оба многочлена в правой части принадлежат коду, а код линеен. Но степень многочлена меньше наименьшей степени ненулевого многочлена в коде. Следовательно, Теорема 5.2.3. Циклический код длины с порождающим многочленом существует тогда и только тогда, когда делит

Доказательство. Согласно алгоритму деления,

где стенень многочлена меньше степени мпогочлена Тогда

и, следовательно,

Из теоремы 5.2.1 вытекает, что первый многочаен в правой части является кодовым многочленом. Тогда также является кодовым многочленом степени ниже, чем стенень Единственный такой кодовый многочлен равен Таким образом, делит Далее, каждый многочлен, делящий может быть выбран в качестве порождающего многочлена циклического кода. Это завершает доказательство.

Согласно теореме 5.2.3, для порождающею многочлена любого циклического кода выполняется равенство

при некотором многочлене Многочлен называется проверочным многочленом. Каждое кодовое слово с удовлетворяет равенству

так как

для некоторого многочлена

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

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

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

где выбирается так, чтобы выполнялось условие

Это требование означает, что

и степень многочлена меньше степени многочлена Следовательно,

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

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

Синдромный многочлен зависит только от и не зависит ни от ни от

Итак, мы ввели следующие многочлены:

Теорема 5.2.4. Пусть минимальное расстояние циклического кода Каждому многочлену ошибок веса меньше, чем соответствует единственный синдромный многочлен.

Доказательство. Предположим, что веса меньше, чем и что им соответствует один и тот же синдромный многочлен. Тогда

и

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

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

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

Рис. 5.1. Таблица значений синдромов.

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