1.4.2. Верхняя граница Плоткина

В области малых значений верхняя граница Хэмминга является довольно грубой. При малых более точной, чем граница Хэмминга, является верхняя граница Плоткина [16], определяемая следующей теоремой.

Теорема 1.2. Если существует -ичный блоковый код длины с общим числом кодовых слов К и минимальным расстоянием

Доказательство. Эта граница получается путем оценки сверху среднего расстояния между кодовыми словами [4]. Пусть кодовые слова кода, существование которого предполагается в теореме, и пусть компонента кодового слова Сумма попарных расстояний Хэмминга между кодовыми словами определяется следующими равенствами:

где функция равна 1, если и равна 0, если Пусть число равных символов канала среди компонент Тогда имеют место следующие равенства:

где если если Обозначим через максимум квадратичной формы при следующих условиях: (здесь будем считать, что переменные х, принимают действительные значения). Методом индукции по покажем, что В случае справедливость последнего равенства проверяется легко. Полученные с использованием метода неопределенных множителей Лагранжа значения при которых достигается экстремум рассматриваемой квадратичной формы, должны удовлетворять следующим условиям:

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

так как число пар различных кодовых слов равно Теорема 1.2 доказана.

Аналогичная граница может быть получена и для расстояния Ли [4]. Из вывода границы Плоткина можно видеть, что кодами, минимальное расстояние которых достигает границы Плоткина, могут быть лишь коды, в которых расстояние между любыми двумя различными кодовыми словами одно и то же; такие коды называются эквидистантными. Примерами двоичных эквидистантных кодов являются коды, состоящие из последовательностей максимальной длины (см. пример 3.4), и коды, получающиеся из матриц Адамара.