Обратная теорема кодирования

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

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

Доказательство. Выберем так, чтобы для было бы справедливо неравенство . Это возможно, поскольку значение определено как нижний предел от Предположим, что для такого имеется код, который отображает последовательности состоящие из букв сообщения, в последовательности X из букв сигнала на входе канала и отображает последовательности У из букв выходного сигнала в последовательности воспроизводимых сообщений. Переходные вероятности канала образуют функцию Кроме того, заданы кодирующие и декодирующие функции, определяемые как Наконец, источник задает вероятности последовательностей сообщений т. Посредством кодирующей функции задается множество вероятностей Р (X) последовательностей на входе канала. Если пропускная способность канала равна С, то средняя взаимная информация между последовательностями на входе и выходе канала должна удовлетворять соотношению

так как — максимально возможное значение при варьировании Поскольку X является функцией — функция У, то аналогично

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

Этим заканчивается доказательство теоремы.

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