5.2. ВЕСОВОЙ СПЕКТР КОДА, ДУАЛЬНОГО К ДВОИЧНОМУ ЛИНЕЙНОМУ КОДУ

Напомним (из § 1.8), что если линейный код над конечным полем, то дуальный (или ортогональный) код состоит из всех векторов и, скалярное произведение которых с каждым кодовым словом из равно нулю. Если является -кодом, то представляет собой -код.

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

Назовем многочлен весовой функцией кода и обозначим его через

Заметим, что многочлен может быть записан двумя способами

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

Подобным же образом обозначим через число кодовых слов веса в коде Весовой спектр кода тогда равен:

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

(ii). Код {00, 11}, обозначим его через самодуален:

(iii). Рассмотрим [7, 4, 3]-код Хэмминга

Как следует из § 1.9,

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

Рассмотрим сначала случай двоичных кодов (теорема 1).

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

Теорема 1. (Теорема Мак-Вильямс для двоичных линейных кодов). Пусть — двоичный линейный -код, а дуальный к нему -код. Тогда

где равно числу кодовых слов в коде

Кроме того, справедливы следующие тождества, эквивалентные (5.4):

или

Уравнения (5.4) — (5.6) иногда также называются тождествами Мак-Вильямс.

Доказательство теоремы основывается на следующей важной лемме.

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

Лемма 2. Если является двоичным линейным -кодом (т. е. подпространством размерности то

Доказательство леммы 2. Воспользовавшись определением и поменяв порядок суммирования, получаем соответственно

Теперь, если то скалярное произведение всегда равно нулю, и внутренняя сумма поэтому равна Но если то согласно упражнению (32) гл. 1 произведение принимает значения 0 и 1 одинаковое число раз, и поэтому внутренняя сумма равна 0. Следовательно,

Доказательство теоремы 1, Применим лемму для отображения

Тогда мы имеем

Пусть Тогда

Теперь, так как

равно выражению

Если то внутренняя сумма равна Если то она равна Таким образом,

Воспользовавшись теперь уравнением (5.8), получаем:

Примеры. Применим теорему 1 к примерам в начале этого раздела.

что и в самом деле равно Далее

что иллюстрирует тот факт, что эта теорема симметрична относительно выбора ролей кодов и .

(ii). . Поэтому

что действительно верно, так как код является самодуальным.

Упражнения. (1). Проверить, что

(2). Показать, что теорема 1 симметрична относительно выбора ролей кодов т. е. что

[Указание. Положить в уравнении (5.5) и воспользоваться однородностью многочлена

(3). Показать, что весовая функция -кода Хэмминга имеет вид

(4). (а). Показать, что для любого кода с минимальным расстоянием имеется точно векторов веса находящихся на расстоянии 1 от кода векторов веса на расстоянии 1 от кода

(Ь). Учйтывая (а), показать, что для кода Хэмминга

и, следовательно, весовой спектр удовлетворяет следующему рекуррентному соотношению

с начальными условиями

(5). Как известно, расширенный код Голея (§ 2.6) является самодуальным кодом. Проверить это, раскрыв правую часть выражения (5.4) для этого кода.

Взаимосвязь коэффициентов Естествен вопрос: как связаны между собой весовые спектры раз они удовлетворяют формуле (5.5)? Если мы положим

то из (5.5) вытекает, что

где называется многочленом Кравчука.

Дадим формальное определение этих многочленов.

Многочлены Кравчука. Определение. Для любого натурального числа определим многочлен Кравчука следующим образом:

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

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

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

Если же целые числа, причем то это выражение принимает вид

Выпишем несколько первых многочленов:

Дальнейшие их свойства см. в § 5.7.

Числа задаваемые равенством (5.13), интересны также в случае, когда является нелинейным кодом (ср. теоремы 6 и 8). Но для исследования нелинейных кодов нам необходим некоторый новый аппарат.

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

Начнем с того, что напишем уравнение (5.5) для случая, когда

Полагая у— 1, получаем (так как должное равенство

Дифференцируя по у выражение (5.17) и полагая получаем первый момент

Итак, если то средний вес слова в коде равен Продолжая таким же образом, получаем, что

для значений Левая часть тождества (5.18) называется биномиальным моментом коэффициентов

Предположим теперь, что дуальный код имеет минимальное расстояние так что

Если то правая часть соотношения (5.18) не зависит больше от кода. Таким образом,

Этим равенством мы воспользуемся в следующей главе. Оно показывает, что биномиальный момент порядка для не зависит от выбора кода и, в частности, равен моменту -кода, представляющему собой все пространство

Упражнения. (6). Доказать следующий вариант соотношения (5.18):

(7). Если вместо дифференцирования выражения (5.17) по у применим к нему раз оператор и затем положим то получим степенные моменты коэффициентов Для чисел они особенно просты. Показать, что

и

Показать, что в общем случае для

где представляет собой число Стирлинга второго рода (использовать приведенные в гл. 1 соответствующие преобразования биномиальных коэффициентов). Равенства (5 22) часто называются тождествами Плесс.

(8) Показать, что, если неизвестно только коэффициентов а коэффициенты известны, то все могут быть определены. [Указание Коэффициенты при неизвестных в левой части (5 22) образуют матрицу Вандермонда (см. лемму 17 гл. 4).]

(9). Моменты относительно среднего значения, (а) Показать, что (5 17) влечет следующее соотношение

(b). Отсюда вывести справедливость следующего тождества для

где

(c). Показать, что и

(d). Вывести как следствие, что для

Заметим, что правая часть неравенства (5 25) представляет собой момент относительно среднего значения весового спектра для тривиального -кода

Показать, что, если то в (5 25) выполняется равенство

Задача (нерешенная) (5 1) Пусть линейный код. Как и в § 15, пусть обозначает число лидеров смежных классов кода веса и пусть обозначает соответствующее число для дуального кода Сколь однозначно числа опретелякн числа