5.5. ТЕОРЕМА МАК-ВИЛЬЯМС ДЛЯ НЕЛИНЕЙНЫХ КОДОВ

Весовая функция элемента групповой алгебры

Пусть — произвольный элемент групповой алгебры такой, что

Назовем -вектор где

весовым спектром элемента С. Это понятие является естественным обобщением понятия весового спектра кода. Конечно, Как и в § 5.2, для элемента С определим также его весовую функцию:

Определение. Сопряженным к элементу С назовем элемент С алгебры задаваемый формулой

где отображение было определено в § 5.4. Предположим, что

так что

(Коэффициенты с пропорциональны преобразованию Адамара коэффициентов см. § 2.3.) Тогда весовой спектр элемента С задается вектором где

а весовая функция С

Как и в теореме 1, многочлен задается линейным преобразованием многочлена

Теорема 3.

что эквивалентно с учетом (5 15) равенствам:

Эта теорема и теорема 5 могут быть интерпретированы как теоремы Мак-Вильямс для нелинейных кодов

Доказательство. Соотношение (5 32) эквивалентно также равенству

В силу (5 30) левая часть этого равенства равна

согласно соотношениям (5 9) и (5 11) из §

Для любого -вектора такого, что

назовем вектор его преобразованием Мак-Вильямс. По теореме 3 оно может быть получено либо по формуле (5 31), либо по формуле (5 33)

Упражнения (17) Показать, что при

(18) Показать, что

(19) Показать, что

(20) Пусть линейный -код, и предположим, что смежный класс содержит векторов веса Используя равенство (5 31), показать, что преобразование от чисел равно где равно числу слов веса ортогональных вектору равно числу слов веса не ортогональных Следовательно, показать, что

Спектр расстояний в нелинейном коде. Пусть теперь — линейный или нелинейный -код. Этому коду соответствует элемент

групповой алгебры

Упражнение. (21). Показать, что, если код — линейный, то

Таким образом, теорема 1 является частным случаем теоремы 3.

Пусть линейный или нелинейный код. Пусть Если мы представим как элемент

то весовой спектр равен где

Лемма 4. Вектор представляет собой спектр расстояний кода . Доказательство.

Следовательно,

Применяя теорему 3 к элементу групповой алгебры получаем следующий результат.

Теорема 5. Преобразование Мак-Вильямс спектра расстояний кода равно

Доказательство. Утверждение вытекает из теоремы 3 и равенства

Свойства чисел

Теорема

Доказательство. Согласно определению и упражнению (12), получаем, что

Этот простой с виду результат оказался очень полезным (см. границу линейного программирования, § 17.4). Теорема 12 гл. 21 дает другое доказательство этого результата.

Теорема 7. (а). Если то

(b). для всех и для веса

(c). для некоторого и веса

Доказательство. Утверждение очевидно, а утверждения (b) и (с) следуют из (5.36) и (5.31).

Дуальное расстояние и ортогональные таблицы

Определение. Дуальным расстоянием кода называется число такое, что для всех Если код линейный, то минимальное расстояние дуального кода

Заметим, что при таком определении остаются справедливыми все соотношения (5.18) — (5.25) и упражнения (6) — (9) для спектра расстояний нелинейных кодов.

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

Теорема 8. Любые столбцов матрицы содержат каждый -вектор точно раз, и является наибольшим числом, удовлетворяющим этому свойству.

Замечание. Матрица с таким свойством называется ортогональной таблицей с ограничениями, двумя уровнями, силой и индексом (см. § 11.8).

Доказательство. Для доказательства первой половины вспомним, что из теоремы 7 следует равенство для всех векторов и веса Условие для всех и веса 1 влечет, что каждый столбец матрицы имеет нулей и единиц. Далее условие для всех и веса 2 влечет, что любые два столбца матрицы содержат каждую пару точно раз. Ясно, что подобные рассуждения можно продолжать вплоть до векторов и веса . С другой стороны, так как то имеется вектор и веса такой, что

Примеры (i) Рассмотрим (11, 12, 6)-код Адамара Так как это симплексный код, содержащий нулевое слово, то его спектр расстояний совпадает с весовым спектром

Преобразованный спектр получается из многочлена

и имеет следующий вид

Заметим, что Кроме того, в соответствии с теоремой 6 Эта таблица показывает, что

Список всех кодовых слов [12] находится в верхней половине рис. 2.1. Для иллюстрации теоремы 8 заметим, что в любых двух столбцах этой матрицы каждый из векторов встречается 3 раза

(ii) На рис 5 1 изображен -код. (см. упражнение (22) гл 15)

Рис. 5.1 Нелинейный (8, 16, 2) код

В этом коде спектры весов и расстояний снова совпадают

Преобразованный спектр получается из многочлена Но после упрощения этот многочлен

оказывается равным Поэтому для этого кода кроме того,

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

Упражнения. (22). Показать, что если

и

Заметим, что в общем случае, мы не можем найти С, если известно только

Рассмотрим нелинейный (16, 256, 6)-код Нордстрома—Робинсона (см. § 2.8). Еще раз получаем, что (см. рис. 2.19). Этот код также обладает тем свойством, что хотя и довольно трудно доказать это непосредственно. Это будет следовать из результатов гл. 15.

(23). Пусть 4? — код и С определяется выражением (5.34). (i). Показать, что если и только если линейный код.

(ii). Показать, что если и только если линейный самодуальный код.