4.2. ДИСКРЕТНЫЕ КАНАЛЫ БЕЗ ПАМЯТИ

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

Рис. 4.2.1. Переходные вероятности в двоичном симметричном канале. (Здесь и на некоторых последующих рисунках в десятичных дробях, целая часть которых равна нулю, нуль опускается)

Канал описывается переходными вероятностями заданными для По определению, является условной вероятностью приема целого числа при условии, что задан вход канала — целое число

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

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

Более формально это можно выразить следующим образом: канал является каналом без памяти, если существуют такие переходные вероятности что (4.2.1) справедливо для всех всех и всех

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

Для последовательностей длины 2 равенство (4 2 1) дает Вероятность обозначает вероятность приема двух нулей при условии, что были переданы два нуля.

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

Вероятность приема числа была выписана в виде чтобы подчеркнуть, что она является функцией как распределения на входе, так и переходных вероятностей канала.

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

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

В § 4.4 и 4.5 мы вернемся к задаче численного отыскания пропускной способности.

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

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

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

Равенство в (4.2.4) имеет место, если входы статистически независимы, а равенство в (4.2.5) имеет место, если входы независимы и имеют распределение вероятностей, определенное (4.2.3).

Доказательство.

Так как канал является каналом без памяти, то можно использовать (4.2.1), что дает

Величина является случайной величиной и правая часть (4.2.8) равна среднему значению суммы N случайных величин. Она равна сумме средних значений, независимо от того, являются ли входы статистически независимыми или нет. Но среднее значение равно так что

Это означает, что одно из выражений в (4.2.6) равно сумме энтропий; займемся теперь другим выражением Из (2.3.10) имеем

Подставляя (4.2.9) и (4.2.10) в (4.2.6), получаем

откуда следует (4.2.4).

Равенства в (4.2.10) и, следовательно, в (4.2.4) имеют место тогда и только тогда, когда выходные буквы статистически независимы. Если входные буквы статистически независимы, т. е.

то совместная вероятность равна

и отсюда следует статистическая независимость выходов.

Определение С означает, что при всех таким образом, (4.2.5) следует из (4.2.4). Более того, если входы статистически независимы и выбираются так, чтобы максимизировать каждую информацию то при всех и (4.2.5) удовлетворяется с равенством.

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