Глава 13. Скорость передачи информации для оптимальных кодов

13.1. Граница сферической упаковки Хэминга — Рао для больших скоростей

Как метрика Хэмминга, так и метрика Ли определяют расстояния между точками в -мерном пространстве слов над алфавитом из букв. В любой из этих метрик шар радиуса с центром С определяется как множество всех точек, расстояние от которых до точки С не превосходит Поверхность этого шара (сфера радиуса множество точек, расстояние которых до центра С равно точно число точек на сфере обозначается через По определению число точек, принадлежащих шару, называется объемом шара. Ясно, что Пусть Так как расстояние является аддитивной функцией на множестве координат, то производящая функция на множестве координат мультипликативна и поэтому Значит, в метрике Хэмминга

а в метрике Ли

В любом случае можно определить помощью разложения в степенной ряд по Для метрики Хэмминга так что

Для метрики Ли аналогичная формула имеет значительно более сложный вид.

Если расстояние между любыми двумя кодовыми словами то любая точка находится на расстоянии не более чем от одной кодовой точки. Если скорость передачи кода, то он содержит кодовых слов. Все сферы радиуса с центрами в кодовых словах не пересекаются. Следовательно, или

Неравенство (13.11) называется границей по объему или границей сферической упаковки. Это неравенство появилось в работе Рао [1947] по экспериментальным конструкциям. К кодам с исправлением ошибок его впервые применил Хэмминг [1950].

Одним из приложений границы сферической упаковки является теорема 13.12, согласно которой двоичный БЧХ-код с большой скоростью передачи не хуже любого другого кода с той же скоростью и той же блоковой длиной.

13.12. Теорема. Если

то любой код с блоковой длиной и скоростью содержит кодовые слова с весом Хэмминга

Доказательство. Мы утверждаем, что

Единственной нетривиальной частью этого утверждения является неравенство Так как

то

(согласно предположению теоремы 13.12). Следовательно, так что и теорема 13.12 вытекает из неравенства (13.11).

Иногда бывает полезной другая форма неравенства (13.11)

При фиксированном для больших это дает

где

Для вычисления этого предела необходимо получить асимптотически точную оценку величины V Одну из таких оценок дает лемма 13.16, которая является модификацией более общих границ Чернова [1952] и Феллера [1943].

13.16. Лемма. Если

Эскиз доказательства. Для произвольного имеем

Мы утверждаем, что существуют такие значения что

Если соотношение (13.161) выполняется, то

так что

Так как монотонно неубывающая функция от для то найдутся значения удовлетворяющие (13.162), а из (13.162) вытекает (13.161). Следовательно, существует некоторое значение скажем для которого

и тогда

Значение минимизирующее выражения обращает в нуль производную

Отсюда

Подставив эти выражения в формулы леммы 13.16, получим

При этом уравнение (13.15) принимает вид

Рис. 13.1. Двоичный симметричный канал.

Рис. 13.2. Асимптотические границы корректирующей способности для двоичного симметричного канала без обратной связи.

Если положить то читатель, знакомый с теорией информации, узнает в этом выражении для пропускную способность двоичного симметричного канала, показанного на рис. 13.1.

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

Тогда соотношение (13.14) запишется в виде

где наименьшее из расстояний между кодовыми словами. Неравенства (13.19) дают асимптотические формулы для границы сферической упаковки. В случае двоичного симметричного канала, представленного на рис. 13.1, функции соответствует верхняя кривая, изображенная на рис. 13.2.