6.5. ДУАЛЬНЫЙ КОД ТАКЖЕ ПОРОЖДАЕТ СХЕМЫ

В этом разделе будем считать, что является любым двоичным линейным колом, удовлетворяющим следующему свойству: для некоторого все кодовые слова любого фиксированного веса образуют -схему.

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

Лемма 11. Число не зависит от выбора множества

Доказательство. Пусть обозначает число слов кода веса которые содержат точно единиц на позициях из множества Из § 2.5 следует, что не зависит от выбора

Тогда то же самое справедливо и для

Пусть обозначает укороченный код, полученный удалением позиций множества из слов кода имеющих нули во всех этих позициях. Таким образом, представляет собой -код. Кроме того, код дуален коду (см. рис. 1.11 и 1.13).

Следствие 12. Весовой спектр кода не зависит от выбора множества

Доказательство Достаточно воспользоваться теоремой 1 гл. 5.

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

Замечание. Если то, для того чтобы код порождал -схемы, он должен быть кодом с повторением. Тогда код

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

Доказательство. Так как то код содержит кодовые слова некоторого веса о, где и по условию теоремы эти кодовые слова образуют -схему.

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

Наша первая цель — показать, что .

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

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

Это можно сделать, так как (см. § 2.5). Итак, что снова приводит к противоречию. Поэтому

Предположим теперь, что где Но это невозможно в силу (а), так как -схема автоматически является -схемой. Тем самым мы доказали, что

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

Число векторов которые содержат единицы на позициях из равно в точности числу слов веса в коде Но по следствию 12 это число не зависит от выбора множества и поэтому векторы образуют -схему. Следовательно, кодовые слова веса образуют дополнительную к ней схему (§ 2.5).

Пример. (продолжение). По теореме 9 кодовые слова симплексного кода образуют -схему. По теореме 13 кодовые слова каждого веса в коде Хэмминга также образуют -схему.

Объединяя теоремы 9 и 13, мы получаем следующий результат.

Следствие 14. Пусть — линейный код с параметрами Параметр определен выше (см. § 6.4), и пусть

Если или то кодовые слова веса кода образуют -схему, где при условии, что

Задача (нерешенная). всех известных нам нетривиальных примерах число меньше, чем них последнее условие теоремы не является необходимым. Так ли это всегда?