Глава 19. Самодуальные коды и теория инвариантов

19.1. ВВЕДЕНИЕ

Линейный код называется самодуальным, если (см.

§ 1.8). Мы уже убедились, что многие хорошие коды самодуальны, среди них: расширенные коды Голея и некоторые квадратично-вычетные коды. Наиболее важное свойство самодуальных кодов описывается теоремой Глисона (теорема ), которая налагает сильные ограничения на весовую функцию. Эта теорема доказывается посредством мощной техники, развитой в XIX столетии и называемой теорией инвариантов (см. § 19.2, 19.3). Та же самая техника доказывает целый ряд подобных теорем, касающихся разного рода весовых функций (см. § 19.4). Одним из следствий теоремы Глисона является верхняя граница для минимального расстояния самодуального кода (теоремы 13, 17). Однако эта верхняя граница может быть достигнута только при небольших значениях (следствие 16, теорема 17). Тем не менее существуют самодуальные коды, которые удовлетворяют границе Варшамова-Гилберта (теоремы 21, 24).

Большинство результатов этой главы одинаково хорошо применимо к широкому классу кодов, а именно к линейным или нелинейным кодам, удовлетворяющим тому условию, что преобразование спектра расстояний равно самому спектру расстояний (как, например, в коде Нордстрома — Робинсона). Такие коды называются формально самодуальными. Спектр расстояний формально самодуальных кодов, рассматриваемых в этой глве, совпадает с весовым спектром, и поэтому мы будем иметь дело с весовым спектром.

Напомним читателю, что самодуальные коды имеют четную длину и размерность

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

Теорема 1. (Глисон, Пирс и Турин [53].) Предположим, что формально самодуальный код над в котором расстояние между кодовыми словами всегда кратно числу Тогда либо тривиальный -код с весовой функцией Хэмминга

для любого либо имеет место одно из следующих условий:

Доказательство мы опускаем. Коды типа (ii) иногда называются четными самодуальными кодами.

Приведем несколько примеров самодуальных кодов.

Коды типа (i). (E1). Двоичный код представляет собой простейший самодуальный код с весовой функцией

В общем случае код над GF(q) с порождающей матрицей является формально самодуальным с весовой функцией Прямая сумма таких кодов формально самодуальна и имеет весовую функцию, задаваемую уравнением (19.1).

(Е2). -код Нордстрома — Робинсона (§ 2.8 и гл. 15).

(Е3). Расширенный [18, 9, 6] КВ-код (см. § 16.6).

(Е4). Формально самодуальный -код, изображенный на рис. 5.1.

Коды типа (ii). (Е5). [8, 4, 4]-код Хэмминга с весовой функцией

В общем случае любой расширенный КВ-код длины является кодом типа (ii) (теоремы 7, 8 гл. 16).

Напомним, что согласно гл. 5 код над имеет две весовые функции: полную весовую функцию

где равно числу кодовых слов, содержащих нулей, единиц и двоек, и весовую функцию Хэмминга

Коды типа (iii). (Е7). Троичный -код из гл. весовой функцией Хэмминга

(Е8). Троичный -код Голея задаваемый выражением (16.25), с весовыми функциями

В общем случае любой расширенный троичный КВ-код или симметричный код Плесс представляет собой код типа (iii) (согласно условию (16.26) и теоремам 7, 8 и 17 гл. 16).

Коды типа (iv). (Е9). Формально самодуальный [6, 3, 4] КВ-код над Он получается добавлением общей проверки на четность к циклическому коду с порождающим многочленом где - корень степени 5 из единицы. Порождающая матрица этого кода имеет вид

где

Упражнения. (1). Пусть циклический -код. Найти необходимое и достаточное условие, которому должны удовлетворять корни порождающего многочлена чтобы расширенный код был самодуален. [Указание. Рассмотреть случаи ]

(2). Пусть четное число. Показать, что существует РС-код над GF(q) такой, что код самодуален. Показать, что это неверно, если нечетное.

Замечание. Как следует из приводимой ниже теоремы -код и [32, 16, 8]-код РМ второго порядка имеют одинаковые весовые спектры. Однако они не эквивалентны по следующим причинам, (i). Они имеют разные группы автоморфизмов. Согласно теореме 13 гл. 16 группа автоморфизмов КВ-кода включает проективную специальную линейную группу порядка Однако так как 29 и 31 — простые числа-близнецы, то из теоремы Неймана [988, 989] следует, что группа автоморфизмов не больше, чем эта группа. С другой стороны, согласно теореме 24 гл. 13 группа автоморфизмов РМ-кода представляет собой полную аффинную группу порядка Смежные классы этих кодов имеют разные весовые спектры (Берлекэмп и Велч [133]). (iii). Они имеют разные бивесовые функции (см. упражнение (36) гл. 5).

Два неэквивалентных -кода с одинаковым весовым спектром были приведены Фонтейном и Питерсоном [434].