16.7. ДВАЖДЫ ЦИРКУЛЯНТНЫЕ И КВАЗИЦИКЛИЧЕСКИЕ КОДЫ

Дважды циркулянтные коды были определены в предыдущем параграфе как коды, порождающая матрица которых имеет вид

где А — циркулянтная матрица, первая строка которой задается многочленом а числа и с равны 0 или 1 То же самое название мы будем использовать для различных кодов, получающихся из кода с порождающей матрицей (16 55), например для кода, получающегося при выбрасывании первой строки или первого и последнего столбцов матрицы (16 55) В результате последнего преобразования из матрицы (16 55) получаем матрицу

где -матрицы Матрица (16 56) порождает дважды циркулянтный код, который мы в этом параграфе будем обозначать через Некоторые из свойств кода указаны в упражнении (8)

Упражнение (13) Показать, что код допускает чрезвычайно простое кодирование сообщение переходит в кодо слово

Квазициклические коды. Код называется квазициклическим, если для некоторого целого числа каждый циклический сдвиг кодового слова на позиций опять является кодовым словом Очевидно, что циклический код является квазициклическим при Выписывая столбцы матрицы (16 56) в порядке видим, что дважды циркулянтный код является

квазициклическим кодом с Например, матрица (16.46) перепишется в виде

что определяет квазициклический код с Из леммы 14 и равенства (16.44) также следует, что двоичный КВ-код с одной вычеркнутой координатой или любой расширенный код эквивалентны квазициклическому коду с

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

Теорема 16. Если такое простое число, что 2 является примитивным элементом поля и если для выполняется неравенство

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

Доказательство. Выберем так, чтобы его вес был нечетным числом, меньшим чем Число таких кодов равно

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

Пусть типичное слово кода согласно упражнению Следовательно, веса имеют одну и ту же четность. Заметим также, что код содержит слово 1 (сумма строк матрицы (16.56)). Если вес многочлена нечетен и меньше чем то при заданном слово является кодовым точно для одного кода а именно того для которого

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

Таким образом, каждое слово вес которого меньше чем принадлежит точно одному коду Остальная часть доказательства является стандартной (ср. с теоремой 31 гл. 17).

К сожалению, в настоящее время имеется только предположение о том, что существует бесконечно много простых чисел для которых 2 является примитивным элементом поля Если бы

это было доказано, то, выбирая в теореме 16 достаточно большие к, мы могли бы утверждать, что некоторые достаточно длинные коды лежат на границе Варшамова-Гилберта. Однако, и не имея такого результата, Касами использовал теорему 16 для доказательства существования кодов весьма близких к границе Варшамова-Гилберта - (см. [730]).

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

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

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

Например, если то

что, конечно, эквивалентно расширенному коду Хэмминга (16.46). При как мы видели в упражнении (8), получаем -код Голея.

Упражнение. (14). Доказать, что код самодуален и все его веса кратны 4.

При код является -кодом, а при -кодом; в обоих случаях, как будет показано в гл. 19,

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

Код можно рассматривать также как расширенный циклический код над GF(4). Пусть примитивный кубический корень из единицы такой, что Заменим и на т. е. установим соответствие

Упражнение. (15). Доказать, что это отображение переводит в расширенный циклический код над Порождающий идемпотент кода равен

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

Пример. Рассмотрим код, первая строка порождающей матрицы которого равна

(Это код Голея.) Указанное отображение переводит эту строку в следующий вектор над полем

Прибавляя вектор 1 и умножая на а, получаем порождающий идемпотент расширенного кода

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

меняющую местами обе половины.

(17). Доказать, что 3) как код над инвариантен относительно группы и обобщенной перестановки при взаимной замене и

Задача (нерешенная). (16.7). Имеет ли место для минимального расстояния кода граница квадратного корня, аналогичная теореме 1?

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

Рис. 16.7 Хорошие дважды циркулянгяые коды