13.6. Граница Элайеса

Мы видели, что граница, полученная с помощью сферической упаковки, является точной при больших скоростях передачи и неточной при малых, а граница Плоткина точна при малых скоростях передачи и неточна при больших. Комбинируя эти границы и используя одну высказанную в 1960 г. плодотворную идею Элайеса, можно получить более строгую границу для средних скоростей. Некоторое уточнение этой границы было предложено Вайнером [1965].

Мы выведем границу Элайеса в двух леммах. В лемме 13.61 на основе границы сферической упаковки мы покажем, что код должен содержать критический шар, включающий много кодовых слов. Затем в лемме 13.61 мы покажем, что среднее расстояние между кодовыми словами этого критического шара мало.

13.61. Лемма. Для заданных числа и кода с блоковой длиной и скоростью существует критический шар радиуса содержащий кодовых слов. С помощью подходящего сдвига кода центр этого критического шара может быть перенесен в точку 0.

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

Шар, содержащий наибольшее число кодовых слов, называется критическим. Если из каждого кодового слова вычесть центр критического шара, то центр критического шара переместится в О, а минимальное расстояние кода не изменится.

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

13.62. Лемм а. Если вес каждого из К кодовых слов не превосходит где расстояние между некоторыми парами из этих К кодовых слов не превосходит

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

где расстояние между буквами входного алфавита. Полный вес по всем кодовым словам определяется выражением где первая строка матрицы Если вес каждого из К кодовых слов не превосходит то полный вес не превосходит и

Найдем теперь вероятностные векторы максимизирующие сумму при условии

Эту задачу будем решать в два этапа. Сначала определим максимум

при условии а затем выберем максимизирующие при условии

Согласно ограничениям на искомый максимум,

и

где . В силу этих условий, для отыскания максимума функции надо рассмотреть функцию

где постоянные множители Лагранжа. Для определения стационарной точки этой функции приравняем к нулю ее частную производную по Так как то для всех к получим

или

Полагая

можно проверить, что одним из решений задачи (13.63) — (13.65) является

Согласно разд. 13.4, - выпуклая функция вероятностного вектора Следовательно, стационарная точка (13.66) является точкой максимума функции условиях (13.63) и (13.64). Для завершения доказательства надо определить максимизирующие при условии Из соображений симметрии выберем для всех Такой выбор задает стационарную точку, а так как выпуклая функция от то выбор является правильным.

Таким образом, максимум полного расстояния при условии достигается, если для всех задается равенством (13.66). Полное расстояние при этом равно а среднее попарное расстояние между различными словами равно

Для эффективного сочетания лемм 13.61 и 13.62 необходимо прежде всего выбрать радиус критического шара. Такое должно минимизировать , где наименьшее целое число, большее или равное При больших блоковых длинах объем быстро растет с ростом так что хорошо выбранное число лишь незначительно превышает наименьшее целое число, для которого

Согласно (13.15) и (13.18),

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

13.67. Теорема. При произвольно выбранных и скорости для достаточно больших

где определяется условиями (13.18) и (13.15), а теоремой (13.49).

Сравнение полученной границы с асимптотической формой границы сферической упаковки (уравнение показывает, что граница Элайеса равномерно более точная, хотя с увеличением скорости разница становится практически неощутимой. Для малых скоростей граница Элайеса стремится к границе Плоткина, так как На рис. 13.2 показана асимптотическая граница Элайеса для двоичного случая.