3.5. Циклические коды (I)

Циклические коды являются линейными кодами, которые не изменяют своих свойств при циклической перестановке компонент кодовых слоев. Благодаря этому свойству они обладают сравнительно простыми процедурами кодирования и декодирования и, кроме того, имеют удобные алгебраические свойства. Все совершенные линейные коды, коды Рида — Маллера (см. разд. 4.5) и другие коды, построенные еще до того, как Прейндж ввел понятие циклического кода и описал свойства последнего, являются кодами, которые после перестановки компонент или незначительной модификации оказываются циклическими. Все важнейшие блоковые коды, открытые позже, также оказались либо циклическими кодами, либо кодами, получающимися из циклических, либо тесно связанными с последними.

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

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

Резюмируя вышеизложенное, заметим, что сопоставление кодовым векторам классов вычетов

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

Пусть подмножество соответствующее коду С, а именно

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

Кроме того, как указывалось выше,

Из формул (3.16) — (3.18) следует, что для произвольного

Таким образом, из соотношений (3.16) и (3.19) видно, что является идеалом (см. разд. 2.2).

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

и

Из формул (3.16) и (3.17) следует, что Но тогда, согласно определению многочлен должен быть нулевым, так как степень меньше, чем степень Это означает, что делится на . В частности, на должен делиться двучлен поскольку Обратно, пусть произвольный многочлен, который делится на Тогда, согласно формуле (3.19), Пусть степень равна Так как имеется ровно многочленов степени и меньше, которые делятся на то

число классов вычетов, порождаемых идеалом равно Поскольку соответствие между является взаимно однозначным и С содержит векторов, то Далее, если предположить, что существуют два многочлена удовлетворяющих описанным выше свойствам, то из того, что эти многочлены должны делить друг друга и их старшие коэффициенты, равны 1, будет следовать, что эти многочлены совпадают. Это означает, что определяется однозначно. Таким образом, мы доказали следующую теорему [8, 29—31].

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

является необходимым и достаточным условием того, что

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

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

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

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

матрицы Многочлен называется проверочным многочленом кода. Рассмотрим код двойственный к коду С. В силу того что код С вместе с каждым кодовым вектором содержит также вектор для произвольного вектора или, что то же самое,

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

Тогда

где

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

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

Из вышеизложенного следует справедливость следующей теоремы.

Теорема 3.5. Двойственный код циклического также является циклическим. Порождающим многочленом кода является многочлен где проверочный многочлен кода свободный член

Из этой теоремы непосредственно следует, что матрица

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

Поскольку вопросы реализации кодов детально будут рассматриваться в гл. 7, то здесь кратко остановимся лишь на методах кодирования и декодирования, приложимых ко всем циклическим кодам. Условимся, что последние компонент кодового слова являются информационными символами, а первые компонент — проверочными символами (для конкретности смотрим последовательные системы, когда обработка символов ведется последовательно по мере их поступления; случай параллельных систем принципиально не отличается от случая последовательных систем). Представим совокупность информационных символов в виде многочлена -многочлен степени или меньше, коэффициентами которого являются информационные символы]. Совокупность проверочных символов представим в виде многочлена многочлен степени или меньше, коэффициентами которого являются проверочные символы]. Согласно теореме 3.4, многочлен является кодовым тогда и только тогда, когда он делится на порождающий многочлен тогда и только тогда, когда выполняется следующее равенство Из этого равенства видно, что в качестве можно взять остаток из деления на заменив все его коэффициенты на противоположные. Это отображение является линейным и фактически реализует метод нахождения проверочных символов с помощью порождающей матрицы и соотношения (3.4).

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

Пороговые методы декодирования и алгебраические методы декодирования БЧХ-кодов будут описаны в следующей главе. В оставшейся части этого раздела рассмотрим ряд других методов декодирования, которые могут быть использованы при небольших длинах кодов и малых скоростях передачи [8, 32—36]. При этом понадобится следующая теорема.

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

деления на Пусть остаток от деления на Если вес (число ненулевых коэффициентов) остатка меньше или равен то

Доказательство. Пусть остаток от деления на Так как

то а следовательно, кодовый многочлен. Поскольку имеют вес, меньший чем то

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

где степень С другой стороны,

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

В этом случае из сравнения

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

Пример 3.3 [34]. Рассмотрим двоичный циклический код с параметрами Как будет показано ниже в примере 4.2, кодом с такими параметрами является только код Голея. Рассмотрим конфигурации ошибок веса 3. Конфигурации ошибок удобно изображать на окружности длины 23, как показано на фиг. 3.2. Предположим, что на окружности имеются три символа 1, показывающие положение ошибок, и между ними находятся символов Если то, выбрав надлежащим образом можно добиться того, что Предположим, что

Фиг. 3.2.

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

Рассмотрим конфигурации ошибок веса 2. Пусть числа символов 0 между символами 1, определяющими положение ошибок Если то при некотором

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

Если то при некотором

Итак, как видно из вышеизложенного, удовлетворяют нужным условиям. Декодер, основанный на использовании описан в работах [34, 36].

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

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

Утверждение 3.15. 1) Если не содержит в качестве сомножителя то циклический код С длины с порождающим многочленом содержит кодовое слово Подкод кода С, задаваемый порождающим многочленом является четным подкодом кода С.

Краткое доказательство. 1) Так как то . Если то

Но тогда Так как справедливо также и обратное утверждение, то является четным подкодом кода С.