17.3. ГРАНИЦЫ ДЛЯ A(n, d)

Полученные в § 17 2 оценки для могут быть теперь использованы для оценивания Вначале мы вспомним некоторые результаты, установленные в § 2.2 и 2.3

Для случая точное значение A(n,d) дается теоремой 11

Теорема 10

Теорема 11 (Плоткин и Левенштейн) В предположении, что существуют соответствующие матрицы Адамара, имеют место равенства

В случае, когда невелико, оказывается полезным следующий результат, доказанный в теореме 6 гл. 1

Теорема 12 (Граница сферической упаковки или граница Хэмминга

Эта теорема введением функции может быть усилена.

Теорема 13 (Джонсон)

Доказательство (i) Пусть -код с содержащий нулевой вектор. Обозначим через множество векторов, находящихся на расстоянии от кода для всех для некоторого

Таким образом, Тогда так как если бы нашелся вектор, находящийся на расстоянии или

больше от кода то мы могли бы добавить его к 92 и получить код еще большей мощности. Поскольку множества не пересекаются, то отсюда следует граница сферической упаковки (теорема 12). Для получения оценки (17.11) оценим мощность

(ii). Выберем произвольное кодовое слово и соответствующим сдвигом кода переведем его в начало координат. Кодовые слова веса образуют равновесный код с расстоянием не менее и поэтому число кодовых слов веса не превышает

(iii). Обозначим через множество векторов веса Любой вектор из принадлежит либо либо Каждому кодовому слову веса соответствует векторов веса находящихся от на расстоянии .

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

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

Пусть теперь пробегает по всем кодовым словам; подсчитав общее число точек в множестве получим неравенство (17.14).

Пример.

Но согласно упражнению Следовательно, Отметим для сравнения, что граница сферической упаковки дает только . В следующем разделе мы увидим, что на самом деле

Следствие 14.

Доказательство Согласно следствию 5

Подставляя это неравенство в (17 14), получаем (17.15) Если в (17 13) имеет место равенство, то код называется совершенным (см гл 6) Если же равенство выполняется в (17 15), то код называется почти совершенным (см Геталс и Сновер [504])

Упражнения (9) (а) Показать, что совершенный код является почти совершенным

(Ь) Показать, что почти совершенный код является квазисовершенным

(10) Показать, что укороченный код Хэмминга и выколотый код Препараты (с 455) являются почти совершенными кодами Следовательно, для четных

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

Как показал недавно Линдстрем [844], не существует никаких других почти совершенных двоичных кодов Доказательство очень похоже на доказательство теоремы 33 гл 6

Упражнения (11) Для четного показать, что

[Указание Использовать теоремы 6 и 13 Немного больше можно сказать о значениях

(12) (Джонсон Доказать следующее усиление неравенства (17 14)

где

[Указание. Любой вектор, находящийся на расстоянии от кодового вектора, принадлежит одному из множеств или

(13). Обобщить оценку (17.16).

(14). В предположении, что существуют соответствующие матрицы Адамара, показать, что если то либо равно I, либо четному числу. [Указание. Воспользоваться теоремой II.] Используя рис. ПА.1, показать, что если нечетно и больше 1, то

Задача (нерешенная). (17.4). Верно ли следующее предположение: если то четное число для любых и (Элспас [409])?

Так же как граница для задаваемая выражением (17.14), зависит от величины можно получить границы для зависящие от функции, обозначаемой через Эти оценки довольно сложны, и мы не будем их здесь приводить (см. [697]). Но функция представляет самостоятельный интерес.

Определение. Функция равна максимальному числу двоичных векторов длины находящихся друг от друга на расстоянии Хэмминга по крайней мере и содержащих точно единиц в первых позициях и точно единиц в последних позициях.

Пример. как показывают векторы

(Позиции, занятые единицами, должны быть различными!)

Упражнение. (15). Доказать: Если

при условии, что знаменатель положителен.

(h). (Обобщение теоремы 3.) Предположим, что

для запишем

Тогда

Таблицы значений приведены Бестом и др. [140].