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

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

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

5.1. КОД С ТОЧКИ ЗРЕНИЯ РАСШИРЕНИЯ ПОЛЯ

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

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

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

Над расширением поля проверочная матрица оказалась -матрицей. Используя эту матрицу, кодовое слово можно определить как вектор над такой, что в расширении поля он дает нулевое произведение с

или

Теперь мы подошли к идее представления кодовых слов в виде многочленов: кодовое слово с представляется многочленом

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

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

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

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

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

где

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

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

которое для выбранного выше частного вида матрицы можно записать в виде

Это соотношение в точности совпадает с утверждением, что все элементы являются корнями кодового многочлена с Рассматриваемый код определяется как множество многочленов с степени не выше и таких, что для всех выполняется равенство

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

Например, выберем некоторый примитивный элемент а поля и примем длину кода равной 15. Для построения проверочной матрицы кода над выберем

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

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

Хотя этого сразу не видно, строки данной проверочной матрицы линейно независимы, и, следовательно, она определяет двоичный -код. Минимальное расстояние этого кода равно 5 (хотя это тоже не очевидно). Этот код можно также представить в виде множества многочленов над степени не выше 14, таких, что в расширении каждый многочлен удовлетворяет равенствам с Иначе говоря, кодовые слова являются многочленами с корнями в

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