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

Начнем с исследования величины максимального числа двоичных векторов длины веса находящихся на расстоянии друг от друга не менее Эта функция важна как сама по себе, так и с точки зрения получения оценок для с помощью теорем 13 и 32. В этом разделе мы рассмотрим границы

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

Теорема 1.

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

Следующий результат обобщает оценку

Теорема 2. (Джонсон [693]; см. также [694-697].)

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

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

Так как расстояние между любыми двумя строками равно по крайней мере 26, то их скалярное произведение рвно самое большее Следовательно, сумма не превышает

С другой стороны, эта сумма равна также

Если -число единиц в столбце матрицы X, то вклад этого столбца в сумму равен Следовательно,

Но (общее число единиц в матрице X) и сумма минимальна, если все и в этом случае

Следовательно, из (17.2) имеем

Решая это неравенство относительно получаем (17.1). Так как числа должны быть целыми, то полученную оценку можно немного усилить.

Теорема 3. Предположим, что и определим целые числа посредством равенства (Это равно общему числу единиц во всех кодовых словах.) Тогда справедливо неравенство

Доказательство. Минимум суммы при условии, что и что целые положительные числа, достигается, когда

Этот минимум равен так что из (17.2) имеем Примеры. По теореме 2

и код показывает, что

Снова по теореме 2

Но если то, применяя теорему 3, имеем так что и неравенство (17.3) нарушается. Следовательно, Код показывает, что Следующая рекуррентная оценка полезна в тех случаях, когда неприменима теорема 2 (и также в некоторых случаях, когда она применима).

Теорема 4.

Доказательство. Рассмотрим все кодовые слова, у которых стоит 1 в координате. Если эту координату отбросить, то получается код длины с расстоянием не менее , слова которого имеют вес Следовательно, число таких кодовых слов не более чем Таким образом, общее число единиц в первоначальном коде удовлетворяет неравенству

Следствие 5.

Доказательство. Применим вначале несколько раз теорему 4 и затем воспользуемся теоремой

На практике теорема 4 применяется до тех пор, пока не достигается известное значение . Пример.

Теперь применим теорему 2:

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

На самом деле в обеих этих оценках выполняются равенства (см. рис. ПА.3).

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

[Указание. Воспользоваться теоремой

Иногда (17.6) дает более хороший результат, чем (17.4). Задача (нерешенная). (17.1). В каком порядке надо применять оценки (17.4), (17.6) и (17.1) при заданных значениях чтобы получить наименьшую оценку для

Упражнения. (3). Несколько простых примеров. Показать, что

(4). Предполагая, что -матрица Адамара существует, показать, что

[Указание. Использовать коды из гл. 2 на с. 57].

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

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

причем равенство достигается тогда и только тогда, когда существует система Штейнера (ср. § 2.5).

Таким образом, из известных фактов о системах Штейнера (см. Чин [277], Колленс [300], Дембовский [370], Деннистон [372], Дуайен и Роза [386], Ханани [595—600], Ди Паола и др. [1020], Вигт [1423, 1424]) вытекают соответствующие результаты о величине Так, например, системы Штейнера существуют для всех равных степени простого числа [370, гл. 6], и поэтому

Аналогично унитарные поляры проективных геометрий [370, с. 104] дают равенство

Упражнение (6) показывает также, что определение величины является в общем случае очень трудной проблемой. Так, например, из (17.10) следует, что причем равенство достигается тогда и только тогда, когда существует проективная плоскость порядка 10.

Следующие результаты приводятся без доказательств.

Теорема 6. (Шонхейм [1158]; см. также Форт и Хедлунд [446], Шонхейм [1161], Спенсер [1259] и Свифт [1294].)

Теорема 7. (Калбфлейш и Стэнтон [708], Брауэр

Задача (нерешенная). (17.2). Найти величину если

Теорема 8. (Ханани [595-598].)

если и только если или ;

если и только если или

Доказательства теорем 6—8 заключаются в явном построении кодов, достигающих этих границ.

Теорема 9. (Ердеш и Ханани [411], Вильсон [1420-1422].)

(a). Для произвольного фиксированного существует число такое, что для всех

если и только если или Кроме того,

(b). Если степень простого числа, то

(см. также работы Оллтопа [21—24] и Роковской [1122]).

Но даже если ни одна из приведенных выше теорем не применима, имеется все же достаточно хороший метод получения нижних оценок надо построить код длины с минимальным расстоянием 26, а затем рассмотреть множество всех кодовых слов веса Например, в -коде Голея имеется 2576 кодовых слов веса 12, и поэтому получаем, что (На самом деле имеет место равенство.)

В общем случае можно воспользоваться векторами веса до в любом смежном классе кода длины с расстоянием 26 Например, использование смежных классов кода Голея приведенных в упражнении 13 гл 2, показывает, что

Равновесные коды имеют ряд практических применений (см Ковер [310], Фрейман [456], Гилберт [483], Ксяо [666], Кауц и Элспас [752], Маракл и Волвертон [911], Накамура и др [983] Нейман [98b, 987], Шварц [1169] и Танг и Лью [1307]) Но в общем о них известно немного

Задача (нерешенная) (17 3) Найти хорошие методы кодирования и декодирования равновесных кодов (см Ковер [310])

Упражнение (7) Из оценок (17 4) и (17 1) следует, что

Показать, что

[Указания (i) Методом проб и ошибок построить соответствующую матрицу, показывающую, что

(ii) В любой матрице, реализующей число единиц в столбце не более чем

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

(iv) Предположим, что столбцы 2 и 3 содержат 3 пары единиц Без ограничения общности можно считать, что первые 3 строки выглядят следующим образом

Обозначим через число строк, начинающихся с последовательностей 110, 101, 100, 000 соответственно Тогда следовательно, Но следовательно, и всего имеется не более 12 строк

(v) Предположим, что никакие два столбца не содержат 3 пар единиц Тогда число единиц в каждом столбце не превышает 5 и, значит, число строк не превышает 12 Ибо, если 1-й столбец содержит 6 единиц или более, то, рассматривая строки с единицей в первой координате, нетрудно убедиться, что найдется столбец, скалярное произведение которого с первым столбцом не менее

Упражнение (8) (Трудное) Показать, что Величина изучалась также в работах Нивена [996] и Стэнтона и др [1270]