1.2. Взаимная информация и пропускная способность канала

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

модели. Ясно, что соображения согласованности с нашим предыдущим определением информации накладывают следующие граничные условия.

1. Если события независимы то наступление события не дает никакой информации об а. Иначе говоря,

2. Если наступление указывает с определенностью на то, что и а наступило то наступление дает нам полную информацию относительно а. Таким образом,

Указанные два граничные условия окажутся удовлетворенными, если мы определим взаимную информацию между событиями следующим соотношением:

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

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

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

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

По определению, выражение (1.2.2) — условие отсутствия памяти. Теперь введем, наиболее часто используемый тип ДКБП.

Определение. Двоичный симметричный канал (ДСК) представляет собой ДКБП, у которого а условные вероятности имеют вид

Это иллюстрируется диаграммой на рис. 1.4.

Рис. 1.4. Двоичный симметричный канал

Рис. 1.5. Канал с аддитивным гауссовским шумом

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

Определение. Канал без памяти с дискретным входом и аддитивным гауссовским шумом представляет собой канал без памяти

с дискретными входным и выходным алфавитами и условной плотностью вероятностей

где

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

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

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

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

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

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

Пример. (ДСК.) По соображениям симметрии пропускная способность приведенного на рис. 1.4 ДСК с переходной вероятностью достигается на входных вероятностях канала

Поэтому

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

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

Лемма 1.2.1.

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

Доказательство. Нижняя граница находится с помощью неравенства следующим образом:

причем равенство нулю справедливо тогда и только тогда, когда для всех у и х.

Верхняя граница для вытекает из соотношения

Из (1.1.8) следует, что

причем равенство достигается тогда и только тогда, когда для всех Подстановка последнего неравенства в качестве первого члена в соотношение (1.2.11) дает желаемый результат

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

для каждого Средняя взаимная информация между входной последовательностью длины N и соответствующей выходной последовательностью длины N равна

где

Поскольку рассматривается канал без памяти, средняя взаимная информация между и соответствующим символом на выходе равна

где Имеем следующий результат.

Лемма 1.2.2.

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

Доказательство. Из леммы 1.2.1 следует

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

Тогда, в силу равенства

имеем

причем равенство достигается тогда и только тогда, когда при всех . Поэтому равенство достигается, когда выходные случайные величины независимы. Это определенно имеет место, если входные случайные величины независимы, поскольку у канала отсутствует память. Неравенство, задающее верхнюю границу, следует из неравенства причем равенство достигается в соответствии с (1.2.8) тогда и только тогда, когда максимум средней взаимной информации достигается на входном распределении

Лемма 1.2.3. Рассмотрим три случайные величины с совместной вероятностью для Введем среднюю гзаимную информацию для каждой пары случайных величин Допустим, как это показано на рис. 1.6, что входной случайной величиной одного из

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

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

и

Рис. 1.6. Последовательно включенные каналы

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

где мы опять воспользовались неравенством Заметим далее, что по формуле Байеса

где последнее равенство представляет собой следствие соотношения (1.2.19). Объединяя (1.2.22) с (1.2.23), получим

Второе неравенство получается аналогичным способом Лемму 1.2.3 легко обобщить на последовательности различных длин в последовательно соединенных устройствах. В частном случае ДКБП 2 на рис. 1.6 будет детерминированным устройством, отображающим входную величину у в выходную величину о.

Рис. 1.7. Система обработки данных

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

Можно считать, что кодер в целом работает с последовательностью и длины и порождает выходную последовательность х длины Аналогичным образом можно считать, что и декодер работает с последовательностью у длины N и выдает на выходе последовательность длины Рассматривая последовательности как одиночные символы на входах и выходах, из леммы 1.2.3 получим неравенства

и

Объединяя эти неравенства, получаем теорему об обработке данных.

Теорема 1.2.1. Теорема об обработке данных. Для системы, приведенной на рис. 1.7, справедливо неравенство

Указанный результат справедлив в предположении, что каждая последовательность оказывает влияние на последующие последовательности так, как это показано на рис. 1.7, т. е. и связана с

только через х, последняя связана с только через у, так что при и Из леммы 1.2.2 мы получаем, кроме того, что для системы (см. рис. 1.7)

где С — пропускная способность ДКБП

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

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

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