3.6. Циклические коды (II)

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

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

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

Если один из этих корней, то остальные корни Пусть порядок элемента Согласно теореме 2.13, показатель равен так что

Поскольку то из части 2 утверждения 2.54 следует, что Следовательно,

Обозначим через Из формулы (3.22) и части 2 утверждения 2.54 следует, что

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

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

Пример 3.4. Пусть Выберем Как следует из утверждения 2.60, в этом случае Но тогда Используя конкретное представление поля и элемент а из задачи 2.59, получим, что Построенный здесь код является примером БЧХ-кода, исправляющего двойные ошибки (произвольные БЧХ-коды будут описаны в разд. 4.1).

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

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

или, что то же самое,

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

которая обладает тем свойством, что вектор удовлетворяет условию (3.24), т. е. является кодовым тогда и только тогда, когда

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

Пример 3.5. Пусть — примитивный элемент поля минимальный многочлен элемента а. Тогда Пусть С — циклический -код с порождающим многочленом Согласно равенству (3.24), каждый кодовый вектор Должен удовлетворять следующему условию:

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

то

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

Очевидно, что Если вектор, компоненты которого равны 1, а остальные равны 0, то удовлетворяет соотношению (3.24) и, следовательно, является кодовым. Таким образом, минимальное расстояние кода С в точности равно 3. Этот код лежит на границе Хэмминга и является совершенным. Код С называется двоичным циклическим кодом Хэмминга; коды, эквивалентные С, называют просто двоичными кодами

Хэмминга. Если в матрице коэффициентов из (3.25) каждый элемент заменить на вектор-столбец, получающийся транспонированием вектор-строки, который является представлением в базисе то получится матрица размера с элементами из поля у которой все столбцы различные и ненулевые. Следовательно, утверждение 3.13 дает нумератор весов кода С. Если в случае взять в качестве минимального многочлена элемента а многочлен то получим

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

Утверждение 3.16. В примере 3.5 оценка была получена на основании равенства (3.25). Однако эту оценку можно также получить исходя из того, что если где то

Краткое доказательство. Сначала заметим, что Так как минимальный многочлен примитивного элемента а, то является примитивным, а следовательно,

Пример 3.6. Пусть -примитивный многочлен степени над полем Рассмотрим двоичный циклический код длины с порождающим многочленом Так как порождающий многочлен двойственного кода также является примитивным многочленом (см. утверждение 2.58), то двойственный код является кодом Хэмминга из примера 3.5. Рассматриваемый код имеет информационных символов и состоит из кодовых векторов. Многочлены являются различными кодовыми векторами. В самом деле, допустим, что Тогда Но это противоречит тому, что примитивный многочлен. Следовательно, кодовыми векторами являются нулевой вектор, вектор и все циклические сдвиги последнего. Проверочным многочленом этого кода является Если ненулевой кодовый вектор и то из (3.21) имеем

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

Если при некотором то, согласно (3.26), вектор должен быть нулевым, но по предположению ненулевой вектор, поскольку при всех Так как число -мерных ненулевых двоичных векторов над равно то для произвольного вектора над найдется ровно одно такое целое число что

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

в свою очередь равно Если то число символов 1 среди равно а следовательно, вес любого ненулевого кодового слова равен Таким образом, рассматриваемый код является эквидистантным (это можно было бы также показать, используя результаты примера 3.5 и утверждение 3.11). Этот код называют кодом максимальной длины. В разд. 4.3 будет описан алгоритм порогового декодирования кодов максимальной длины.

Для примера рассмотрим случай, когда При этом Согласно (3.21), матрица имеет следующий вид:

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

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

Таким образом, использование вместо элемента элемента у приводит лишь к некоторой перестановке компонент кодовых векторов. Это означает, что построенные в обоих случаях коды эквивалентны, имеют одинаковую весовую структуру, а следовательно, и одинаковую способность исправлять независимые

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

Утверждение 3.17. Пусть многочлен степени такой, что Тогда, если С — циклический код с порождающим многочленом то

Утверждение 3.18. Пусть — кодовое слово -ичного циклического кода С. Тогда вектор получающийся из циклической перестановкой компонент также принадлежит коду С.

Краткое доказательство. Если представление в виде многочлена, то представление в виде многочлена. Утверждение следует из того, что если то

Методы декодирования циклических кодов, основанные на утверждении 3.18 и теореме 3.6, описаны в работах [33, 37].