16.2. ОПРЕДЕЛЕНИЕ КВАДРАТИЧНО-ВЫЧЕТНЫХ КОДОВ

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

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

лежат в поле При этом

Обозначим через кольцо Определение. Квадратично-вычетными кодами называются циклические коды (или идеалы) кольца порожденные соответственно многочленами

Иногда называются пополненными КВ-кодами, а -кодами с выбрасыванием.

Ясно, что В двоичном случае 2 представляет собой подкод кода 2, состоящий из всех кодовых слов четного веса, подкод кода состоящий из всех кодовых слов четного веса

Подстановка на множестве координат кольца индуцируемая отображением при некотором фиксированном невычете переводит коды (а также друг в друга, так что эти коды эквивалентны Размерность кодов равна а размерность кодов равна (см рис. 16 1)

Пример. Если то порождающий многочлен кода 2 равен где так что код 2 равен [7, 4, 3]-коду Хэмминга. 2 представляет собой -подкод с порождающим многочленом Код эквивалентен [7, 4, 3]-коду Хэмминга с порождающим многочленом (Отметим, что различные выборы элемента а приводят к перестановке кодов

Рис. 16.1 Свойства квадратично вычетных кодов

Коды Голея. Мы уже упоминали в § 2.6 и 6.10 о существовании двух совершенных кодов Голея, а именно [23, 12, 7] двоичного кода и [11, 6, 5] троичного кода Одно из определений кода было дано в гл. 2. Мы дадим теперь другое его определение как КВ-кода, одновременно определив также и код

Определение. Код Голея является КВ-кодом 3 (или при Код Голея является КВ-кодом 3 (или при Параметры этих кодов соответственно равны [23, 12, 7] и [11, 6, 5]. (В § 16.7 будет доказана эквивалентность двух данных определений кода Она вытекает также из следствия 16 гл. 20).

Над (см. рис. 7.1) имеет место разложение

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

Над имеет место разложение

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

Другие примеры приведены на рис. 16.2. (В некоторых случаях указаны верхние и нижние границы для

Граница квадратного корня для минимального расстояния.

Теорема 1. Если минимальное расстояние кодов 3 или то Если то эту границу можно усилить следующим образом:

Доказательство. Пусть слово минимального ненулевого веса в коде 3. Если невычет, то слово минимального веса в коде Следовательно, произведение должно лежать в пересечении т. е. быть кратным многочлену

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

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

Рис. 16.2. Таблица расширенных квадратично-вычетных кодов

Пример. Минимальное расстояние [7, 4, d] квадратично-вычетного кода над удовлетворяет условию 3 (и если то

Примеры кодов, приведенные на рис. 16.2, показывают, что минимальное расстояние часто больше, чем граница, задаваемая теоремой 1.

Задачи (нерешенные). (16.1). Заполнить пробелы на рис. 16.2; расширить обе таблицы и вычислить аналогичные таблицы для других значений

(16.2). Как ведет себя минимальное расстояние КВ-кодов при