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

Некоторые из кодов, описанных в пятой главе, эквивалентны циклическим кодам, и наиболее простые способы технической реализации этих кодов получаются именно при такой их трактовке. Многообещающие новые коды, описываемые в следующих главах, являются циклическими. Кажется реальной перспектива нахождения новых циклических кодов, хорошо приспособленных для обнаружения и исправления ошибок, В этой главе описывается значительная часть общей теории и технических приемов кодирования и проведения проверок на четность, приложимых ко всем циклическим кодам. Довольно подробно обсуждаются методы обнаружения ошибок. В конце главы дается полное описание методики кодирования и исправления ошибок для циклических кодов Хэмминга. Это описание служит введением в общую методику кодирования и исправления ошибок для кодов Боуза — Чоудхури и кодов Файра, описываемых в следующих двух главах.

8.1. Циклические коды и идеалы

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

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

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

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

Теорема 8.1. В алгебре многочленов по модулю подпространство является циклическим подпространством тогда и только тогда, когда оно является идеалом.

Доказательство. Доказательство теоремы основано на том, что умножение на эквивалентно циклическому сдвигу вектора, ибо

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

Если подпространство V — идеал и элемент принадлежит V, то произведение также принадлежит V, и поскольку это циклический сдвиг вектора V, то V — циклическое подпространство.

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

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

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

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

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

Пример. Дан многочлен над полем Галуа Многочлен порождает циклический -код. Элементы

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

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

Легко проверить, что Этот код эквивалентен -коду Хэмминга, так как матрица И содержит в качестве столбцов все различные ненулевые последовательности длины 3.

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

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

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

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

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

Код, среди корней каждого кодового вектора которого содержатся — корень многочлена порождается многочленом

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

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

Отсюда

и степень равна 10.

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

Тогда все элементы находятся среди корней многочленов и поэтому

так что степень равна 20.

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

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

Приведем два способа практического отыскания минимальной функции для заданного элемента поля на примере элемента где а — корень примитивного многочлена (См. табл. 6.1.)

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

2. Известно, что степень многочлена равна 4. Пусть Подставляя вместо вместо вместо и вместо получаем

или

откуда Еще один способ приводится Албертом ([1], теорема 5.25).