1.4. Верхние границы для минимального расстояния кодов

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

расстояния [2, 4, 10]. Рассмотрение этих границ, кроме того, позволит ознакомить читателей с некоторыми принципиальными идеями теории информации.

Вначале получим границу Чернова [4], которая будет необходима в дальнейшем.

Лемма 1.1. Пусть Тогда

где

Доказательство. Пусть ясно, что Если , то

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

Так как при для всех

и, следовательно, Отсюда и из формулы (1.5) получаем

Положим Значение при котором достигается экстремум функции находится из уравнения

Отсюда следует, что экстремум достигается в точке Поскольку исследуемая функция является монотонно убывающей при и монотонно

возрастающей при то в точке она достигает минимума. Так как то . В точке рассматриваемая функция равна

Отсюда и из формулы (1.6) получаем доказательство леммы 1.1.

Введенная выше функция при совпадает с энтропией