9. Внешняя граница для области пропускной способности

Хотя в некоторых случаях выпуклая оболочка — внутренняя граница, определенная выше, — действительно является областью пропускной способности, однако это бывает далеко не всегда. Галлагер (R. G. Gallager) с помощью тонких вычислений показал, что для двоичного умножающего канала внутренняя граница находится строго внутри области пропускной способности. Однако при частичном обращении теоремы 3 можно получить некоторую внешнюю границу для области пропускной способности. Пусть имеется некоторый код, начинающийся в нулевой момент времени с сообщений и на обоих концах. Пусть и — полученные блоки на обоих концах канала (т. е. последовательности из букв) после операций в канале и пусть — следующие переданные и полученные буквы. Рассмотрим изменение в неопределенности сообщений на обоих концах канала, даваемое следующей полученной буквой. Например, на конце 2 это изменение есть

(некоторые очевидные преобразования опущены)

Имеет место соотношение так как при добавлении введенных условий энтропия не может возрасти и

Аналогично так как есть некоторая функция от получаемая при кодировании. Отсюда

Полученный результат действительно приводит к обращению теоремы 1, если только случайные величины независимы, так как в этом случае последнее выражение сводится к виду . К сожалению, в общем случае кодирования не являются обязательно независимыми. Действительно, следующие могут быть функционально связаны с полученными X и Y и, следовательно, быть зависимыми.

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

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

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

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

Рис. 8.

Отсюда ясно, что для любой точки лежащей с той же стороны от линии что и область , в частности, для любой точки самой области имеем (так как наименьшее расстояние равно Кроме того, по крайней мере одна из величин будет не меньше (В прямоугольном треугольнике по крайней мере один катет не меньше гипотенузы, деленной на

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

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

точек где

и совместные распределения вероятностей произвольны.

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

Выясним теперь некоторые свойства внешней границы.