Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше
Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике
Тогда пропускная способность канала задается равенством
где
Пусть 
любое множество условных вероятностей:
и
Пусть, наконец,
Лемма. Для любого 
имеем
причем равенство достигается тогда и только тогда, когда 
для всех х, у
Доказательство. Из неравенства (1.1.8) для каждого у имеем
причем равенство достигается тогда и только тогда, когда 
для всех х. Заметив, что
видим, что 
непосредственно вытекает из 
Приведенная лемма дает соотношение
где максимум достигается на
Пропускную способность канала можно представить в виде
Алгоритм заключается в следующем:
Шаг. 1. Взять исходное входное распределение 
и положить 
(можно выбрать равномерное распределение.
Шаг 2. Вычислить 
в соответствии с 
Шаг 3. Вычислить 
в соответствии с 
Шаг 4. Сменить индекс 
на 
и перейти к шагу 2.
Чтобы определить правило останова, введем некоторый допуск 
и остановим алгоритм при первом значении индекса 
когда достигается
Осталось доказать, что этот алгоритм сходится к пропускной способности. Теорема. Для описанного выше алгоритма
Доказательство. Пусть
так что из 
следует
Из 
имеем 
где
Из определения в 
для 
вчдно, что два первых члена обращаются в нуль, что дает
Допустим теперь, что пропускная способность достигается на 
так что 
Рассмотрим
Воспользуемся вновь неравенством (1.1.8) и получим
а из 
получим
Заметим, что 
и суммируя 
по 
от 0 до 
получим;
Из неравенства (1.1.8) имеем
и, следовательно,
Верхняя граница в 
конечна и не зависит от 
, следовательно, 
- сходящийся ряд, поэтому
Аналогичные эффективные алгоритмы были разработаны для границы с выбрасыванием 
(Леш [1976]), заданной соотношениями (3.3.13) и (3.3.14), и для границы сферической упаковки 
(Аримото [1976], Леш [1976]), заданной соотношением (3.6.47). Напомним, что граница среднего по ансамблю совпадает с границей сферической упаковки при больших скоростях и легко выводится из 
выходным алфавитом 
и переходными вероятностями 
для 
Пусть 
распределение вероятностей на 
.
и ищем максимум 
по входным распределениям 
Из 
вытекает, что при фиксированном 
функци
на множестве входных распределений 
Теорема Куна-Таккера (см. приложение 3Б) устанавливает необходимые и достаточные условия обращения в максимум 
в точке 
а К выбирается так, чтобы удовлетворялось ограничение
оно превращается в соотношение
получим для 
которые обращают в максимум 
при фиксированном 
справедливо соотношение 
а для тех 
которые обращают в максимум 
при фиксированном 
справедливо соотношение 
Удовлетворив одновременно равенства 
и 
получим значения 
на которых достигается пропускная способность.
и 
Для любого индекса 
введем
