Глава 17. Границы для объема кода

17.1. ВВЕДЕНИЕ

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

В этой главе будут приведены верхние и нижние оценки величины как для небольших значений (см. рис. ПА.1, ПА.2), так и для больших значений (см. рис. 17.7). Для больших наилучшей верхней границей является граница Мак-Элиса - Родемича — Рамсея — Велча (теоремы 35 и 36), которая получена посредством существенного использования линейного программирования (см. § 17.4). Эта граница значительно улучшает границу Элайеса, долгое время являвшуюся наилучшей (теорема 34) Наилучшей нижней оценкой для больших является граница Варшамова — Гилберта (теорема 30), но между верхней и нижней оценками имеется все еще значительное расхождение (см. задачу (нерешенную) (17.9)).

Один из возможных путей исследования величины состоит в изучении множеств кодовых слов, имеющих один и тот же

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

На рис. ПА.З представлена таблица небольших значений величины Наилучшими верхними границами для являются границы Джонсона (§ 17.2), которые используются в § 17.3 для получения верхних оценок для Метод линейного программирования, применимый и для больших и для маленьких значений а также для оценки описан в § 17.4.

Другой важной функцией является наибольшее число кодовых слов в произвольном линейном двоичном коде длины с минимальным расстоянием

Ясно, что . В § 17.5 приведена верхняя граница Грайсмера, применимая только для оценки величины . В § 17.6 описан интересный способ построения линейных кодов, которые иногда достигают границы Грайсмера. Это построение использует антикоды, являющиеся кодами, у которых ограничено сверху расстояние между кодовыми словами (и поэтому антикод может содержать повторяющиеся кодовые слова). Замечательная таблица значений в диапазоне была составлена Хелгертом и Стинаффом [636], и поэтому подобная таблица здесь не приводится. Для больших наилучшие известные оценки для совпадают с оценками для

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

Упражнение. (1). Показать, что решение любой из этих проблем дает решение другой. Более точно показать, что если известны значения то известны и значения и наоборот. Сформулировать подобный результат для линейных кодов.

Почти всю эту главу можно читать независимо от других глав. Следующие статьи, относящиеся к границам, не упоминаются где-нибудь в другом месте в этой главе и включены для полноты: Бомбах и др. [64], Бартоу [74, 75], Бассалыго [76], Бергер 105], Шакраварти [259], Фрейман [457], Хатчер [626], Джоши 700], Левенштейн [823, 824], Леви [830], Мак-Дональд [868], Мак-Элис и Рамсей [948], Мирваагнес [980], Питерсон [1037], Сакс [1140], Сидельников [1209, 1210], Стрейт [1283] и Велч и др. [1399].