последовательностей длины
, то
Учитывая, что
получаем из последнего равенства следующую оценку снизу для
Ко
Предположим, что
. Без ограничения общности можно считать, что
Пусть
последовательность длины
Рассмотрим далее вместо блокового кода С код
где знак — означает вычитание по модулю
Если каждому кодовому слову
кода С сопоставить кодовое слово
кода С, то расстояние Хэмминга между кодовыми словами кода С будет совпадать с расстоянием Хэмминга между соответствующими словами кода С. Следовательно, код С имеет те же параметры
что и код С, и содержит К кодовых слов, находящихся на расстоянии
или менее от последовательности
длины
Поэтому вместо кода С с самого начала можно было рассматривать код С, так что мы просто будем считать, что указанные К кодовых слов существуют в коде С. Обозначим через
число таких кодовых слов среди К кодовых слов кода С, находящихся на расстоянии
или менее от последовательности
длины
у которых
компонента равна
Но тогда, как и при определении границы Плоткина, получаем, что сумма
попарных расстояний Хэмминга между указанными выше кодовыми словами определяется равенством
где
Так как расстояние Хэмминга между любым из К кодовых слов и кодовым словом
не превышает
то
достигается в точке
и равен
Отсюда и из неравенств (1.10) и (1.11) получаем
Далее параметр
следует выбрать так, чтобы он минимизировал правую часть последнего неравенства. Однако, поскольку в общем случае это сделать сложно, рассмотрим здесь случай больших
Из леммы 1.1 имеем
Если выбрать отношение
несколько большим, чем
и фиксировать, то при
произведение
будет стремиться к бесконечности, так что при больших
отношение
можно считать равным единице. Таким образом, мы доказали следующую теорему.
Теорема 1.3. Для любой скорости передачи
и любого положительного числа
при достаточно большой длине кода
где
функция, введенная выше в следствии 1.1.
Утверждение 1.10. При фиксированном отношении
и достаточно больших
полученная выше верхняя граница лучше верхней границы (1.8).
Утверждение 1.11. При малых скоростях
и достаточно больших
полученная выше верхняя граница и граница Плоткина почти совпадают.
Идея доказательства. Как указывалось выше (при введении функции
при
. С другой стороны,
при
В следующем разделе будет получена нижняя граница для вероятности ошибки, а в разд. 3.3 — нижняя граница Варшамова-Гилберта для минимального расстояния кодов. На
фиг. 3.1 приведены графики полученных выше верхних границ, а также нижней границы Варшамова — Гилберта при достаточно больших