ГЛАВА 5

ЦИКЛИЧЕСКИЕ КОДЫ

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

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

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

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

5.1. код с точки зрения расширения поля 113

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

Г 1 О О 1 О 1 Г

Н = 0 10 1110

0 0 10 11 1

Переходя в расширение поля, эту матрицу можно записать более компактно. Столбцы матрицы Н можно отождествить с элементами поля GF (8). В многочленах, представляющих элементы поля, используем элементы первой строки матрицы в качестве коэффициентов при z", второй - в качестве коэффициентов при z, а третьей - в качестве коэффициентов при z. Тогда, используя для построения поля GF (8) многочлен р (z) = z -- z ~f 1 и выбирая z в качестве представителя примитивного элемента а, перепишем матрицу Н в виде

Н = [а" аР- а? а" а!

Над расширением поля GF (8) проверочная матрица оказалась (1 х7)-матрицей. Используя эту матрицу, кодовое слово можно определить как вектор над GF (2), такой, что в расширении поля GF (8) он дает нулевое произведение с W:

сН = О,

Е CfL = 0. 1=0

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

и операция умножения кодового слова на проверочную матрицу превращается в операцию вычисления многочлена с (х) в точке X = а. Условие того, что с (х) представляет кодовое слово, превращается в равенство с (а) 0. Иначе говоря, двоичный многочлен с (х) является кодовым словом тогда и только тогда, когда а является корнем многочлена с (х). Представление многочленами (7,4)-кода Хэмминга образует множество всех многочленов над GF (2) степени не выше 6, таких, что а из GF (8) является корнем каждого из них.

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

что проверочная матрица линейного кода содержит п столбцов и что число п-k строк этой матрицы делится на т. Каждая группа из т строк такой матрицы может быть представлена в виде одной строки, содержащей элементы из GF (О - Таким образом, первые m строк становятся одной строкой фп, рщ), а матрица Н сводится к матрице

Рп • • • Рш

Н ==

Рп • - Рг

С г (п - h)/m строками. Вместо [(я - к) X т]-матрицы над GF {д) мы получили (/• X п)-матрицу над GF (д). Мы, конечно, ничего не изменили при таком представлении, а только сделали его более компактным.

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

Y? У

Т2 У2

уГ тГ"

у?- тГ

где п = V" - 1 и Yj- GF (д") для всех / = 1, г.

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

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

сН = О,

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

/1-t

IiCiyi = 0, j = l,...,r.

Это соотношение в точности совпадает с утверждением, что все элементы у, у,, являются корнями кодового многочлена с (х). Рассматриваемый код определяется как множество многочленов с (х) = 5j"=oCiJc степени не выше п - 1 и таких, что для всез / = 1, г выполняется равенство с {у) = Q,