17.4. ГРАНИЦЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Иногда для получения хороших оценок мощности кода с заданным спектром расстояний можно использовать линейное программирование. Мы начнем этот раздел с краткого описания линейного программирования. Затем будут даны приложения, сначала для произвольных двоичных кодое, а затем для равновесных кодов. Асимптотические результаты, справедливые для больших излагаются в § 17.7.

Линейное программирование (см., например, Симоньяр [1211] или Фикен [428]). Оно изучает методы нахождения максимума (или минимума) линейной формы, называемой целевой функцией, которая удовлетворяет некоторым линейным ограничениям. Типичная задача выглядит так.

Задача. (I). Прямая задача линейного программирования. Найти действительные числа так, чтобы максимизировать целевую функцию

при условии, что эти числа удовлетворяют неравенствам

Имеется двойственная задача связанная с этой, в которой число переменных равно числу ограничений в прямой задаче, а число ограничений равно числу переменных в прямой задаче.

Задача. (II). Двойственная задача линейного программирования. Найти действительные числа так, чтобы минимизировать

при условии, что эти числа удовлетворяют неравенствам

Обе задачи удобно формулировать на матричном языке:

(I). Максимизировать при условии, что

(II). Минимизировать при условии, что

Вектор называется допустимым решением задачи (I) или (I), если он удовлетворяет соответствующим неравенствам, и оптимальным решением, если он также максимизирует Аналогичные определения справедливы для задачи (II). Основные факты, которые нам понадобятся, приведены в следующих трех теоремах.

Теорема 15. Если допустимые решения задач (I) и (II) соответственно, то Доказательство. Условия

приводят к неравенству

Аналогично из условий

вытекает, что . Поэтому

Теорема 16. (Теорема двойственности.) Пусть допустимые решения задач (I) и (II) соответственно. Тогда оба решения оптимальны, если и только если

Доказательство. (Необходимость.) Предположим, что но не оптимально. Тогда существует допустимое решение у задачи (I) такое, что что противоречит предыдущей теореме. Вторая половина доказательства опущена (см. [1211]).

Теорема 17. (Теорема о дополнительной нежесткости.) Пусть являются допустимыми решениями задач (I) и (II)

соответственно. Тогда оба решения оптимальны, если и только если для каждого

и для каждого

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

Доказательство может быть предоставлено читателю.

Применения к кодам (Дельсарт [350—352]). Пусть двоичный -код, в котором расстояния между кодовыми словами принимают значения Пусть спектр расстояний кода т. е. среднее число кодовых слов, находящихся на расстоянии от фиксированного кодового слова (см. § 2.1). Таким образом, в остальных случаях. Кроме того,

Преобразованный спектр задается формулой (теорема 5 гл. 5)

где многочлен Кравчука (см. § 5.2).

Кроме того,

Теперь нам будет весьма полезна теорема 6 гл. 5 (или теорема 12 гл. 21), которая утверждает, что

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

Задача. (III). Найти числа максимизирующие

при условии, что

Следовательно, имеет место следующая теорема.

Теорема 18. (Первый вариант границы линейного программирования для кодов.) Если — оптимальное решенне задачи (III), то величина является верхней границей для объема кода

Заметим, что задача (III) всегда имеет, конечно, следующее допустимое решение: для всех

Помимо (17.25) и (17.26) часто можно использовать другие ограничения на числа Мы проиллюстрируем на примере.

Пример. (Оптимальность кода Надлера.) Найдем максимально возможный код длины 12, исправляющий две ошибки. Если к такому коду добавить общую проверку на четность, то мы получим код длины 13 с минимальным расстоянием 6, расстояния между различными словами которого принимают только значения 6, 8, 10 и 12; предположим, что код содержит кодовых слов.

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

Тогда и все числа равны нулю, кроме (возможно) Неравенства (17.26) принимают вид:

(Всего имеется только 6 различных неравенств — см. упражнение (43) гл. 5.)

Может быть найдено и другое неравенство. Ясно, что (если мы выберем , то нетрудно видеть, что число векторов веса 12 равно самое большее одному). Кроме того,

(Легко доказать это непосредственно). Наконец, если

Поэтому, конечно,

Суммирование по всем дает новое неравенство

В действительности оказываются достаточными ограничение (17.28) и первые два ограничения (17.27), так что мы рассмотрим следующую задачу:

максимизировать при условии, что

и

Двойственная задача такова:

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

и

Допустимыми решениями обеих этих задач являются следующие решения:

На самом деле, так как соответствующие целевые функции равны

то согласно теореме 16 решения (17.31) и (17.32) оптимальны. (Эти решения легко получаются вручную, если воспользоваться симплекс-методом, см. [428] или [1211].)

Следующие рассуждения показывают, что (17.31) — единственное оптимальное решение. Пусть обозначает другое оптимальное решение прямой задачи. Все числа задаваемые (17.32), положительны и удовлетворяют первым трем ограничениям (17.30) со знаком равенства, а четвертому — нет. Следовательно, по теореме 17 числа , должны удовлетворять ограничениям (17.29) прямой задачи со знаком равенства, и причем Эти уравнения имеют единственное решение

Таким образом, -единственное оптимальное решение. Решение (17.31) удовлетворяет также и другим ограничениям (17.27), и, следовательно, по теореме 18 код имеет самое большее, 32 кодовых слова. Таким образом, мы доказали, что любой код длины 12, исправляющий двойные ошибки, имеет не более 32 кодовых слов. Эта граница достигается кодом Надлера из § 2.8.

Заметим, что этот метод дал нам спектр расстояний кода Кроме того, так как первые два условия (17.27) выполняются со знаком равенства, то в преобразованном спектре Но в коде встречаются всего три ненулевых значения расстояния. Следовательно, согласно теореме 6 гл. 6 код инвариантен относительно расстояния и для всех векторов (Эти замечания относятся только к расширенному коду а не к исходному коду длины 12.)

Если получаемая методом линейного программирования граница оказывается нечетным числом, скажем, нечетное, то эта оценка может быть иногда уменьшена с помощью следующего рассуждения (см. Бест и др. [140]). Если предположить, что то из выражения (5.36) получаем

Внутренняя сумма содержит нечетное число элементов и поэтому не равна нулю. Следовательно, т. е. мы можем заменить (17.26) более сильным условием

Следующий пример показывает, как это используется. Пример. Пусть — максимальный код длины , исправляющий одиночные ошибки, и пусть — расширенный

код длины 9 с расстоянием 4, имеющий спектр расстояний Условия (17.26) таковы:

и, кроме того, мы можем добавить следующие ограничения:

которые доказываются так же, как и неравенства (17.28). С помощью линейного программирования мы находим, что наибольшее значение суммы чисел удовлетворяющих условиям (17.34) и (17.35), равно так что

Предположим, что Тогда имеет место неравенство (17.33) и правая часть (17.34) может быть умножена на 20/21. Теперь линейное программирование дает следующий результат:

так что Поскольку в гл. 2 приводился -код, отсюда получаем, что Таким способом были получены многие оценки, приведенные на рис.

Вернемся к общему случаю и рассмотрим задачу, двойственную задаче (III). Это позволит нам получить аналитические границы. Двойственная задача такова.

Задача (IV). Найти числа минимизирующие

при условии, что

Переход к двойственной задаче имеет то преимущество, что любое допустимое решение задачи (IV) согласно теореме 15 является верхней границей для объема кода. В то же время только оптимальное решение задачи (III) дает верхнюю оценку. Оказалось, что допустимое решение задачи (IV) проще всего выражать посредством многочлена, который мы обозначим через Лемма 19. Пусть

Тогда представляет собой допустимое решение задачи (IV), если и только если для для

Доказательство.

Из предыдущего замечания мы сразу же получаем следующую теорему.

Теорема 20. (Второй вариант границы линейного программирования для кодов.) (Дельсарт [350].) Предположим, что мы можем найти многочлен степени не более удовлетворяющий следующим свойствам. Если разложение по многочленам Кравчука имеет вид

то должен удовлетворять условиям

Тогда, если — произвольный код длины расстояния между различными словами которого принимают значения то

Следствие Если многочлен

удовлетворяет условиям для

то

Из теоремы 17 вытекает, что любой код, для которого в (17.43) имеет место равенство, должен удовлетворять следующим дополнительным свойствам.

Теорема 22. Пусть являются допустимыми решениями задач (III) и (IV) соответственно. Они являются оптимальными решениями тогда и только тогда, когда

и

Примеры. (1). Мы начнем с очень простого примера и покажем, что код, дуальный к коду Хэмминга, оптимален. Для этого мы воспользуемся следствием 21, чтобы показать, что код длины с минимальным расстоянием может иметь самое большее кодовых слов. (Конечно, это следует также из теоремы Выберем многочлен

так что для Поскольку

условия следствия 21 выполняются, и поэтому согласно оценке (17.44)

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

(2). Код Адамара из гл. 2 с параметрами оптимален: (другой частный случай теоремы 11а). Чтобы показать это, воспользуемся следствием 21 с

(3). Найдем теперь границу для объема кода с минимальным расстоянием используя линейный многочлен скажем, где Нам нужно, чтобы выполнялись неравенства и значение было минимально возможным. Наилучший выбор — положить т. е. Тогда неравенство (17.44) дает следующую оценку: Итак, мы получили более слабую версию границы Плоткина из теоремы 11.

Упражнение. (16). (Дельсарт.) Получить из следствия 21 границу сферической упаковки. [Указание. Пусть Положим

где многочлен Ллойда (см. теорему 32 гл. 6). Воспользуемся следствием 18 гл. 5, чтобы показать, что

Пример. (4). (Граница Синглтона (Дельсарт).) Чтобы выполнялись условия следствия 21, можно положить для Таким образом, мы имеем

Коэффициенты определяются следующим образом (теорема 20 гл. 5):

Для получения последнего равенства мы воспользовались упражнением (41) гл. 5. Заметим, что для Следовательно, верно утверждение:

если произвольный двоичный -код, то

Полученное неравенство является обобщением границы Синглтона (гл. 1, теорема 11) для нелинейных кодов.

Упражнения. (17). Показать, что если -код над полем то

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

при условии, что знаменатель положителен. Неравенство (17.46) известно как граница Грея — Рэнкина (см. работы Грея [561] и Рэнкина [1090, 1091]). [Указание. Образовать -код выбирая по одному кодовому слову из каждой пары дополнительных векторов кода Тогда расстояния в коде принимают ненулевые значения в диапазоне Далее воспользоваться многочленом где а — соответствующим образом подобранная константа.]

Заметим, что для конференс-матричных -кодов из § 2.4 в условии (17.46) имеет место равенство, однако коды не могут быть разбиты на пары дополнительных векторов (см. задачу (нерешенную) (2.2)).

(19). Показать, что каждое допустимое решение задачи (III) удовлетворяет неравенству

(20). (Мак-Элис [944]). Другой вариант следствия 21: если многочлен

удовлетворяет условиям

то

[Указание. Положить и воспользоваться следствием 18 из гл. 5.]

(21). ([944]). Для четного выбрать в качестве квадратный многочлен с и вновь сделать упражнение (11).

(22). ([944]). Для значений выбрать

где и показать, что Показать, в частности, что

Задача (нерешенная). (17.5). Дать комбинаторное доказательство того, что

Граница линейного программирования для равновесных кодов. (Дельсарт [352].) Для равновесных кодов также справедлива граница линейного программирования. Пусть обозначает двоичный код длины веса с расстоянием 26. Тогда

Обозначим через спектр расстояний кода 3). Как следует из теории схем отношений (см. теорему 12 гл. 21), преобразованные величины неотрицательны, где

и коэффициенты определяются равенствами

а многочлен

представляет собой многочлен Эберлейна (см. § 21.6).

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

Пример. Когда переменные должны удовлетворять дополнительному ограничению, а именно (см. приложение А) (так как не превышает числа векторов веса 8, отличных от фиксированного вектора веса 8 и находящихся друг от друга по крайней мере на расстоянии 10). С помощью линейного программирования можно получить, что при заданных ограничениях максимум суммы равен 68 и достигается, когда

Таким образом,

Задача (нерешенная) (17.6). Существует ли код с таким спектром расстояний?

Именно таким путем были получены значения, приведенные на рис. ПА.З и помеченные там буквой Для оценки величины также можно использовать границу линейного программирования (см. Бест и др. [140]).