8. Выпуклая оболочка G как внутренняя граница области пропускной способности

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

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

Кроме того, вероятность ошибки при этом коде не превосходит , так как вероятность наступления какого-либо из двух событий (ошибки в какой-либо из двух частей кода) не превосходит суммы вероятностей этих событий. Можно построить такой смешанный код для любых достаточно больших Следовательно, выбирая их достаточно большими, можно аппроксимировать любое среднее взвешенное от данных скоростей так, что при этом вероятность ошибки будет экспоненциально быстро стремиться к нулю. Отсюда следует, что можно присоединить к множеству точек, полученных с помощью задания различных распределений вероятностей на входных буквах, все точки, принадлежащие выпуклой оболочке этого множества. Этот метод действительно добавляет в некоторых случаях новые точки, как, например, в канал с несовместимой передачей по двум направлениям (табл. 1). Смешивая в равной пропорции коды для распределений вероятностей на входных буквах, дающих точки (0,1) и (1,0), получаем точку (1/2, 1/2). Пара скоростей, соответствующая этой смеси, не может быть получена ни при каком распределении вероятностей для одной буквы. Изложенное можно суммировать в виде следующей теоремы:

Теорема 3. Пусть есть выпуклая оболочка множества точек

где пробегают различные значения распределения вероятностей. Все точки принадлежат области пропускной способности канала. Для любой точки и любого можно найти коды, скорости передачи для которых отличаются

соответственно от не более чем на а вероятности ошибок по обоим направлениям не превосходят для всех достаточно больших и некоторого положительного

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

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

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

Приписывая вероятности буквам и положив если и 0 в остальных случаях, получим некоторую точку на горизонтальной оси, совпадающую с проекцией данной точки или лежащую правее ее. Поступая аналогично, можно найти точку х, такую, что, приписывая буквам вероятности и положив получим некоторую точку на вертикальной оси, совпадающую с проекцией или лежащую выше ее. Заметим также, что, положив получим точку (0,0). Следовательно, смешивая соответствующим образом коды, полученные для этих четырех распределений вероятностей, можно аппроксимировать любую точку четырехугольника, определяемого соответствующими парами скоростей и, в частности, любую точку прямоугольника с вершиной в точке Из этих замечаний следует, что выпуклая оболочка — область, типичная форма которой показана на рис. 7. Она ограничена горизонтальным отрезком, выпуклой кривой, вертикальным отрезком

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

Довольно интересно попытаться точнее оценить скорость уменьшения вероятности ошибки с возрастанием длины кода

Рис. 7.

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