1.4.3. Верхняя граница Элайса

Используя идеи доказательства верхних границ Хэмминга и Плоткина, Элайс получил новую границу для минимального расстояния, которая оказалась лучше обеих исходных границ по крайней мере при средних скоростях [2,4]. Эта граница в дальнейшем получила название границы Элайса. Рассмотрим -ичный блоковый код С длины с К кодовыми словами, скоростью и минимальным расстоянием Хэмминга

Предположим, что все последовательности длины из перенумерованы каким-либо образом числами от 1 до Пусть — произвольное целое положительное число и — число кодовых слов кода С, находящихся на расстоянии Хэмминга или менее от последовательности длины Поскольку каждое кодовое слово находится на расстоянии или менее

последовательностей длины , то

Учитывая, что получаем из последнего равенства следующую оценку снизу для Ко

Предположим, что . Без ограничения общности можно считать, что Пусть последовательность длины Рассмотрим далее вместо блокового кода С код где знак — означает вычитание по модулю Если каждому кодовому слову кода С сопоставить кодовое слово кода С, то расстояние Хэмминга между кодовыми словами кода С будет совпадать с расстоянием Хэмминга между соответствующими словами кода С. Следовательно, код С имеет те же параметры что и код С, и содержит К кодовых слов, находящихся на расстоянии или менее от последовательности длины Поэтому вместо кода С с самого начала можно было рассматривать код С, так что мы просто будем считать, что указанные К кодовых слов существуют в коде С. Обозначим через число таких кодовых слов среди К кодовых слов кода С, находящихся на расстоянии или менее от последовательности длины у которых компонента равна Но тогда, как и при определении границы Плоткина, получаем, что сумма попарных расстояний Хэмминга между указанными выше кодовыми словами определяется равенством

где

Так как расстояние Хэмминга между любым из К кодовых слов и кодовым словом не превышает то

Поскольку как и раньше, связаны между собой неравенством

то следует оценить сверху Возьмем произвольное действительное число и найдем максимум при следующих ограничениях:

Поскольку, как следует из формул (1.12) и (1.13), то

где Ограничения на имеют следующий вид:

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

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

достигается в точке

и равен

Отсюда и из неравенств (1.10) и (1.11) получаем

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

Если выбрать отношение несколько большим, чем и фиксировать, то при произведение

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

Теорема 1.3. Для любой скорости передачи и любого положительного числа при достаточно большой длине кода

где функция, введенная выше в следствии 1.1.

Утверждение 1.10. При фиксированном отношении и достаточно больших полученная выше верхняя граница лучше верхней границы (1.8).

Утверждение 1.11. При малых скоростях и достаточно больших полученная выше верхняя граница и граница Плоткина почти совпадают.

Идея доказательства. Как указывалось выше (при введении функции при . С другой стороны, при

В следующем разделе будет получена нижняя граница для вероятности ошибки, а в разд. 3.3 — нижняя граница Варшамова-Гилберта для минимального расстояния кодов. На

фиг. 3.1 приведены графики полученных выше верхних границ, а также нижней границы Варшамова — Гилберта при достаточно больших