1.5.3. Граница сферической упаковки

Выше была получена верхняя граница для вероятности ошибки, и мы не рассматривали нижней границы вероятности ошибки в формуле (1.14). Вывод нижней границы, называемой границей сферической упаковки, несколько отличается от вывода верхней границы и детально рассмотрен в работах Галлагера [10] и Шеннона, Галлагера и Берлекэмпа [21]. Поэтому здесь мы только сформулируем результаты, относящиеся к нижней границе.

Теорема 1.8. (Граница сферической упаковки.) Для любого кода длины со скоростью передачи в дискретном канале без памяти

где

и определяется формулой (1.16). Функции стремятся к нулю с ростом и определяются равенствами

где - наименьшая ненулевая переходная вероятность канала, число входных символов. Доказательство опускается.

Как видно из формул (1.47), (1.51) и (1.59), величина входит в показатели экспонент как верхней, так и нижней границ для вероятности ошибки и играет основную роль в поведении этих границ. Введем для этой величины специальное обозначение

Как известно из работы Шеннона, Галлагера и Берлекэмпа, теорему кодирования можно упростить, если ввести выпуклую вверх функцию примыкающую сверху к Так,

например, через функция задаваемая формулой (1.59), может быть выражена следующим образом:

В действительности функция очень часто используется вместо поскольку для большого числа каналов Функцию называют внешним замыканием.

Граница сферической упаковки в области малых скоростей является неточной. В этой области скоростей следует пользоваться следующей прямолинейной границей.

Теорема 1.9. (Прямолинейная граница.)

Фиг. 1.7. Типичные графики функций для двоичного симметричного канала.

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

Пусть значение котором Тогда для любого кода со скоростью вероятность ошибки удовлетворяет неравенству

где функции, стремящиеся к нулю с ростом Доказательство опускается.

Поведение кривых для двоичного симметричного канала показано на фиг. 1.7.