1.3. Обращение теоремы кодирования

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

Рис. 1.8. Система связи

структурную схему (рис. 1.8), на которой ДИБП задается алфавитом распределением вероятностей и энтропией Предположим, что выходные символы источника порождаются каждые секунд, так что у ДИБП средняя скорость информации на выходе равна если измеряется в битах на выходной символ. Получатель принимает буквы того же алфавита и с той же скоростью источника — один символ каждые секунд.

ДКБП задан входным и выходным алфавитами и условными вероятностями для Если взаимная информация измеряется в битах, то его пропускная способность равна С бит на одну посылку канала. Мы полагаем, что канал используется один раз каждые секунд.

Теперь имеем ДИБП, порождающий каждые секунд символ на выходе, и ДКБП, который можно использовать каждые секунд. Мы можем по-прежнему нумеровать выходные символы источника и входные символы канала целыми индекса. Условимся считать, что символ на выходе источника появляется в момент а представляет собой входной символ канала в момент Та, где задержка кодирования.

Предположим, что даны ДИБП и ДКБП и что они вне нашего распоряжения. Напротив, кодер и декодер можно построить любым способом. В частности, кодер получает символы источника, а порождает на выходе входные символы канала, тогда как декодер получает выходные символы канала, а порождает символы, принадлежащие алфавиту источника Допустим теперь, что мы хотим передать получателю последовательность и из выходных символов источника. Тогда кодер передает по каналу последовательность х из N входных символов канала, и мы полагаем, что

Зависимость каждого символа на входе канала от последовательности и из символов источника может быть любой. Аналогичным образом декодер по последовательности у из символов на выходе канала выдает получателю последовательность из символов. И опять каждый символ, поступающий к получателю, может быть связан любым способом с последовательностью у из N символов на выходе канала. Мы предположили, что память у канала отсутствует, так что в каждый момент символ на выходе канала зависит только от соответствующего символа на входе канала.

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

для Здесь совместное распределение вероятностей представляет собой вероятность того, что

символ на выходе источника неправильно декодирован получателем. Определим среднюю по символам источника вероятность ошибки на символ равенством

В большинстве систем цифровой связи служит адекватным критерием при оценке качества системы. Система связи надежна, если можно сделать произвольно малой. Ниже мы покажем, что надежная связь невозможна, если энтропия источника превышает пропускную способность канала. Этот результат известен как обращение теоремы кодирования.

Начнем с рассмотрения разности между энтропией последовательности источника и средней взаимной информацией между последовательностью источника и последовательностью, поступающей получателю. Из определений и формулы Байеса следует, что

Применив затем неравенство (1.1.8), получим оценку

справедливую для любой условной вероятности Выберем теперь

где

При таком выборе соотношения (1.3.4) и (1.3.5) дают оценку

(кликните для просмотра скана)

(кликните для просмотра скана)

Отметим, что из соотношения (1.1.8) следует

так что

Следовательно,

Учитывая отсутствие памяти у источника, из равенства (1.1.12) имеем

Далее, из теоремы 1.2.1, леммы 1.2.2 и равенства (1.3.1) следует

Подставив (1.3.18) и (1.3.19) в (1.3.17), получим искомую границу

Для удобства пользования верхней границей (1.3.20) введем функцию

Если энтропия источника бит/с больше пропускной способности канала то в соответствии с соотношением больше константы

На рис. 1.9 дана как функция аргумента Из него ясно, что если то найдется некоторое для которого Заметим, что это утверждение справедливо для любой длины последовательности источника и поэтому дает нам следующую форму обратной теоремы, принадлежащую Фано [1952].

Рис. 1.9. Функция

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

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