6.4. ПОСТРОЕНИЕ СХЕМ ИЗ КОДОВ ПРИ ...

В этом разделе мы покажем, что если то кодовые слова каждого веса образуют -схему (см. определение в § 2.5). Вначале мы перепишем в несколько ином виде формулу для Из теоремы 3 следует, что если то или 1. Предположим теперь, что известно (обычно это так), так что неизвестными являются коэффициенты где

Теорема 7. Если то для имеет место формула

Доказательство. Проводится аналогично доказательству теоремы 2, за исключением того, что уравнение (6.2) имеет теперь следующий вид:

Если то Поэтому первый и третий члены в выражении (6.4) могут быть объединены в один

Пусть Тогда (6.4) можно переписать так:

Кодовые слова веса образуют t-схему. Пусть — фиксированный вектор пространства веса где Для обозначим через число слов веса в коде которые покрывают вектор .

Теорема 8. Числа удовлетворяют следующим уравнениям:

Доказательство. Пользуясь теоремой 8 гл. 5, подсчитаем двумя способами число векторов веса которые покрывают вектор и в свою очередь покрываются некоторым словом кода

Так как вектор покрывает все векторы, то выражение (6.7) можно представить в виде

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

Уравнения (6.8) имеют такой же вид, что и уравнения (6.5), и поэтому их решение таково:

где

Ясно, что следовательно,

или

Таким образом, мы доказали следующую теорему.

Теорема 9 Если то кодовые слова веса в коде при условии, что образуют -схему, причем параметр задается равенством (6.9).

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

(Е2). По теореме 9 кодовые слова веса в коде Адамара образуют -схему (что согласуется и с упражнением (11) гл. 2 и с примером (i) в конце § 5.5).

(Е3). Подобным образом мы получаем -схемы из слов кода Рида-Маллера первого порядка (и кода Адамара

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

(Е4) Аналогично слова фиксированного веса расширенного кода Голея образуют -схему (см. следствия 23, 25 и теорему 26 гл. 2).

(Е5) Аналогично слова кода Нордстрома-Робинсона дают 3- (16, 6, 4), 3- (16, 8, 3) и -схемы.

Упражнение. (5). Проверить

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

Из выражения (6.9) для получаем, что

Так как задаются равенством (6.6), то имеет место следующее тождество, которому удовлетворяют значения весов в коде:

К тому же если , то

Рассмотрим теперь два случая. Если то выражение (6.10) принимает вид

Аналогично если то (6.10) принимает вид

Упражнение. (6). Вывести формулу (6.12) непосредственно из выражений для задаваемых теоремой 2 и соотношением (6.6). Показать, что равенство (6.12) тривиально для нечетных

В общем случае, так как кодовые слова образуют р-схему для мы имеем, что

Используя выражения для из (6.9) получаем:

Таким образом, мы доказали следующую теорему.

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

Упражнения. (7). Показать, что, если (все ненулевые кодовые слова имеют один и тот же вес то кодовые слова могут образовывать самое большее -схему; при условии, что они образуют такую схему, показать, что и делится на 4.

(8). Показать, что если (т. е. ), то и кодовые слова образуют 3-схему.