16.6. ДВОИЧНЫЕ КВАДРАТИЧНО-ВЫЧЕТНЫЕ КОДЫ

На рис. 16.3 приведена краткая характеристика свойств двоичных КВ-кодов.

Рис. 16.3 (см. скан) Свойства двоичных КВ-кодов

Примеры двоичных квадратично-вычетных кодов -код Хэмминга (см. с. 464).

(ii). -код с порождающим многочленом и порождающим идемпотентом

(iii). -код Голея (см. с. 465).

(iv). -код с порождающим многочленом Множество квадратичных вычетов по модулю равно

(v). [47, 24, 11]-код с порождающим многочленом

Первый и третий коды с являются совершенными кодами. Если некоторый двоичный самоортогональный код, все веса которого кратны 4, то, как мы увидим в гл. Эта (верхняя) граница значительно больше, чем (нижняя) граница квадратного корня, задаваемая теоремой 1, и КВ-коды длин 8, 24, 32, 48, 80, 104 (а также, возможно, и других длин) достигают этой границы. Этот феномен вызвал существенный поток работ по определению истинного минимального расстояния КВ-кодов, некоторые из которых мы сейчас рассмотрим.

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

Каноническая форма 1 — два циркулянта. Лемма 14. Для любого простого группа содержит подстановку равную произведению двух циклов длины

Доказательство. Как и в § 12.5, координаты на которых действует группа будем задавать ненулевыми векторами где Таким образом, задает координату Будем также задавать элемент группы матрицей Нам надо найти подстановку такую, что для каждого ненулевого вектора равенство

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

Пусть примитивный корень степени из единицы. Тогда примитивный корень из единицы

степени Положим Тогда ясно, что тогда и только тогда, когда

Определим теперь Тогда представляет собой квадратичный вычет по модулю Действительно, где так как

Выберем теперь Собственные векторы подстановки равны: так что

Следовательно, равенство (16.35) выполняется тогда и только тогда, когда что согласно определению X имеет место тогда и только тогда, когда

Например, если то равно подстановке распадающейся в произведение циклов

Пусть произвольная подстановка, равная произведению двух циклов:

Возьмем произвольное кодовое слово и упорядочим его координаты в соответствии с порядком, задаваемым (16.36): Тогда кодовые слова

образуют таблицу вида

где циркулянтные -матрицы. Например, если порождающий идемпотент расширенного -кода то матрица равна:

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

где А — циркулянтная -матрица. Например, матрица (16.38) уже имеет такой вид.

Код с порождающей матрицей вида (16.39) называется дважды циркулянтным кодом. Мы будем использовать это же название для кодов с порождающими матрицами вида (16.45), (16.46) и т. д., которые отличаются от матриц вида (16.39) только наличием окаймлений вокруг различных частей матрицы. В § 16.7 будет показано, что все эти коды представляют собой различные примеры квазициклических кодов. Ниже мы приведем дополнительные свойства таких кодов.

Пример. -код Голея Если то подстановка распадается в произведение следующих двух циклов:

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

кода и трех его циклических сдвигов (с добавлением общей проверки на четность):

Переупорядочивая координаты вектора в соответствии с порядком (16.40), получаем порождающую матрицу кода в виде, показанном на рис. 16.4.

Задача (нерешенная). (16.4). Всегда ли можно найти такой вектор с, что хотя бы одна из матриц или окажется обратимой? Найти общий метод получения канонической формы (16.39) для порождающей матрицы расширенного КВ-кода.

Каноническая форма 2 — два окаймленных циркулянта. Вторая каноническая форма связана с другим элементом группы

Рис. 16.4 Дважды циркулянтная порождающая матрица кода Голея

а именно с подстановкой где образующая циклической группы квадратичных вычетов по модулю Разложение подстановки на циклы равно

где произвольный невычет. (При в качестве можно выбрать —1.) Обозначим через матрицу, получаемую из переупорядочиванием строк и столбцов в соответствии с (16.42).

Пример. Порождающая матрица -кода преобразуется к виду (фактически к виду (16.24) с общей проверкой на четность)

В общем случае записывается в виде

где

Упражнение. (6). (а). Доказать, что циркулянтные матрицы.

(b). Доказать, что если то где матрица, все элементы которой равны 1. Показать также, что в этом случае вес всех строк матриц равен а вес строк матриц С равен

Доказать, что если то и вес всех строк матриц равен а вес всех строк матрицы А равен

Таким образом, если то машца С может быть обратима (матрицы заведомо необратимы, так как вес их строк четен), а если то матрица А может быть обратима. Если это так, то мы сразу приходим к следующей канонической форме порождающей матрицы:

где I — единичная -матрица; циркулянтная

-матрица (здесь ) и a, b и с равны 0 или 1.

Этот код называется (окаймленным) дважды циркулянтным кодом.

Примеры (1). Матрица С, задаваемая равенством (16.43) для равна единичной матрице, так что получаем:

(2). Опять код Голея Первые две строки порождающей матрицы задаваемой равенством (16.39), равны:

Используя (16.42), переупорядочим столбцы следующим образом:

Первые строки матриц получаются из строки, отмеченной звездочкой, и показаны выше. Для того чтобы найти матрицу, обратную матрице С (см. упражнение (7)), запишем первую строку матрицы С в виде многочлена и найдем обратный к нему по модулю Он равен

Чтобы найти матрицу вычислим

где множество невычетов по модулю 11.

Таким образом, порождающая матрица кода может быть выбрана в виде

где циркулянтная матрица, первая строка которой задается многочленом (16.47):

Это эквивалентно определению кода данному на рис. 2.13 (см. упражнение (9)). Таким образом, мы видим, что некоторые двоичные КВ-коды эквивалентны (возможно, окаймленным) дважды циркулянтным кодам. (Та же самая процедура может быть применена к недвоичным кодам.)

Задача (нерешенная). (16.5). Иногда не удается обратить ни одну из матриц С или А (например, при см. Карлин [715]). Возможно ли, однако, и в этих случаях записать порождающую матрицу в виде

Упражнения. (7). Циркулянтные матрицы, (i). Доказать, что алгебра циркулянтных -матриц над полем изоморфна алгебре относительно отображения циркулянтной матрицы

на многочлен

(ii). Сумма и произведение двух циркулянтов есть циркулянт. В частности, где

Матрица А обратима тогда и только тогда, когда многочлен взаимно прост с Обратная матрица, если она существует, равна В, где

Матрица представляет собой циркулянт, соответствующий многочлену

Пусть циркулянт, у которого для всех: Доказать, что

Пусть примитивный корень степени из единицы, лежащий в некотором поле, содержащем поле Доказать, что собственные значения матрицы А равны (см. упражнение (20) гл. 7).

(8). Пусть (соответственно 39) — двоичный -код с порождающей матрицей (соответственно где циркулянты, первая строка которых задается многочленами

(i). Доказать эквивалентность кодов в следующих случаях: если если для всех (т. е. если

многочлен взаимен многочлену если если нечетно; если где взаимно простые числа.

(ii). Доказать, что коды и эквивалентны.

(iii). Доказать, что тогда и только тогда, когда

(9). Доказать, что порождающие матрицы (16.48) и (16.49) кода 24 эквивалентны матрице, приведенной на рис. 2.13.

(10). Пусть код задается порождающей матрицей вида (16.45) при Доказать, что тогда и только тогда, когда

Метод нахождения слов малого веса в коде . (Карлин и Мак-Вильямс [718].) Порождающая матрица вида (16.45) облегчает задачу вычисления минимального расстояния кода 2 или

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

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

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

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

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

Упражнение (11). (i). Доказать, что многочлены инвариантны относительно подстановки и что произвольный многочлен, инвариантный относительно может быть представлен в виде линейной комбинации многочленов

(ii). Доказать, что .

(iii). Доказать, что для всех имеет место равенство при некоторых .

(iv). Таким образом, подкод кода 2, инвариантный относительно подстановки состоит из линейных комбинаций многочленов

Коэффициенты приведены на рис 16 5 (Матрицы на этом рисунке отличны от матриц в (16 44))

Рис. 16.5 Коэффициенты

Тогда матрица

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

тогда

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

Пример.

Чтобы найти первые строки матриц воспользуемся работой Виноградова [1371] для вычислений вычетов и невычетов:

Следовательно, первые строки матриц равны:

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

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

где ортогональная циркулянтная матрица.

Пример. (Продолжение.) Обратным многочлену по модулю является многочлен Таким образом, матрица приводится к виду

Сумма первой, второй и последней строк этой матрицы равна так что представляет собой -код, содержащий слова веса

Для процедура нахождения слов минимального веса аналогична описанной

На рис. 16.6 приведены некоторые отрицательные результаты, полученные на этом пути

Задача (нерешенная). (16.6) Пусть содержит нетривиальные подкоды всегда ли слово минимального веса в попадает в один из подкодов

Рис. 16.6 Верхние границы для минимального расстояния кода

Другой способ использования группы автоморфизмов для нахождения весов кода . Миккельтвейт, Лэм и Мак-Элис [979] предложили другой мощный метод нахождения весового многочлена квадратично-вычетных и других кодов. В его основе лежит следующее утверждение

Лемма 15 Пусть -некоторая подгруппа группы автоморфизмов кода Если число слов веса в коде а — число слов веса в коде инвариантных относительно некоторого элемента из подгруппы Я, то

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

называется силовской подгруппой группы в случае эти подгруппы имеют очень простую структуру Заставляя Я пробегать по подгруппам Силова по лемме 15 можно определить все величины следовательно, по китайской теореме об остатках, все величины (упражнение (8) гл 10) При больших значениях это часто позволяет точно найти величины (см., например, [979])

Упражнение (12) В обозначениях гл 6 для некоторых значений коды 2, приведенные на рис 16 2, удовлетворяют условию Найти эти значения и исследовать образующиеся при этом схемы