Взаимная информация

 

Определим теперь информацию, содержащуюся в одном ансамбле относительно другого, например, в принятом сигнале относительно переданного сообщения. Для этого рассмотрим сообщение двух дискретных ансамблей A и B, вообще говоря, зависимых. Его можно интерпретировать как пару ансамблей сообщений, либо как ансамбли сообщения и сигнала, с помощью которого сообщение передаётся, либо как ансамбли сигналов на входе и выходе канала связи и т. д. Пусть P(a_k, b_l)совместная вероятность реализаций a_k и b_l. Cовместной энтропией ансамблей A и B будем называть:

(2.6)

Введём также понятие условной энтропии:

(2.7)

где P(a_{k /} b_l)- условная вероятность a_k, если имеет место b_l, здесь математические..

Из теоремы умножения вероятностей следует, что .

(2.8)

Для условной энтропии справедливо двойное неравенство:

(2.9)

Рассмотрим два крайних случая:

1. Равенство имеет место в том случае, когда, зная реализацию , можно точно установить реализацию . Другими словами, содержит полную информацию об .

2. Другой крайний случай, когда имеет место, если события и независимые. В этом случае знание реализации не уменьшает неопределённости , т.е. не содержит ни какой информации об А.

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

(2.10)

Подставляя в эту формулу значения H(A) и H(A/B) выразим взаимную информацию через распределение вероятностей:

(2.11)

Если воспользоваться теоремой умножения , то можно записать в симметричной форме т.к. :

(2.12)

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

Сформулируем основные свойства взаимной информации:

1. , причём равенство имеет место тогда и только тогда, когда и независимы между собой

2. , то есть содержит столько же информации относительно , сколько содержит относительно . Это свойство вытекает из симметрии выражения. Поэтому можно также записать:

(2.13)

3. , причём равенство имеет место, когда по реализации можно точно установить реализацию .

4. , причём равенство имеет место, когда по реализации можно точно установить реализацию .

5. Полагая и учитывая, что получим:

(2.14)

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

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

Если - среднее время передачи одного сообщения, то разделив на формулы H(A/B) и I(A, B) и обозначая:

, , (2.15)

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

Рассмотрим пример: если - ансамбль сигналов на входе дискретного канала, а - ансамбль сигналов на его выходе, то скорость передачи информации по каналу.

(2.16)

- производительность источника передаваемого сигнала .

“производительность канала”, то есть полная собственная информация о принятом сигнале за единицу времени.

 

 

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

 

Эффективное кодирование дискретных сообщений

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

, (2.17)

где - число кодовых символов, a - число сообщений, передаваемых в секунду.

Будем рассматривать для простоты только двоичный код, при котором алфавит состоит из символов 0 и 1. Тогда бит. Поэтому, необходимое условие сводится к тому, что:

(2.18)

Но это отношение представляет среднее число кодовых символов, приходящихся на одно элементарное сообщение. Таким образом, для возможности кодирования и однозначного декодирования сообщения необходимо, чтобы среднее число двоичных символов на сообщение было не меньше энтропии . Является ли это условие достаточным?

Одна из основных теорем теории информации утверждает, что оно “почти достаточно”. Точнее, содержание теоремы кодирования для источника заключается в том, что передавая двоичные символы со скоростью симв/с можно закодировать сообщения так, чтобы передавать их со скоростью:

(сообщений в секунду),

где - сколь угодно малая величина.

Эта теорема почти тривиальна, если источник передаёт сообщения независимо и равновероятно. В этом случае и, если ещё к тому же -целая степень двух , то .

Таким образом можно закодировать сообщения любого источника с объёмом алфавита , затрачивая двоичных символов на элементарное сообщение. Если, однако, сообщения передаются не равновероятно, и (или) не независимо, то и возможно более экономное кодирование с затратой символов на сообщение. Относительная экономия символов при этом окажется равной . Таким образом, избыточность определяет достижимую степень ”сжатия сообщения”.

Рассмотрим несколько примеров.

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

Разумеется, таким же равномерным кодом можно закодировать и буквы в связном русском тексте, и именно так часто поступают на практике. Но можно обойтись значительно меньшим числом символов на букву. Для русского литературного текста и, следовательно, возможен способ эффективного кодирования (или кодирования со сжатием сообщения), при котором в среднем на букву русского текста будет затрачено немногим более 1, 5 двоичных символа, то есть на 70% меньше, чем при примитивном коде.

Существует довольно много способов сжатия сообщений или сокращения избыточности текста. Так, например: ”Эта фр. напис. сокращ. и тем не м. мож. надеят., что Вы пойм. её прав.” В предыдущей фразе удалось уменьшить число букв, а следовательно и символов, если её кодировать равномерным кодом почти на 40%.

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

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

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

Разработано много методов эффективного кодирования для различных источников. Задача эффективного кодирования наиболее актуальна не для передачи текста, а для других источников со значительно большей избыточностью. К ним относятся, например, телевизионные передачи (промышленное телевидение), некоторые телеметрические системы, в которых возможно сжатие в десятки раз, фототелеграфия.

Тема 2.4. Информация в непрерывных сигналах

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

Разобьём область значений на небольшие интервалы протяжённостью . Вероятность того, что лежит в интервале , + , то есть , приблизительно равна , причём приближение тем точнее, чем меньше интервал . Степень неожиданности такого события равна . Если значения в пределах конечного интервала заменить значениями в начале интервала, то непрерывный ансамбль заменится дискретным, а его энтропия определится как:

Будем теперь увеличивать точность определения значения , уменьшая интервал . В пределе, при должна получиться энтропия непрерывной случайной величины:

(2.19)

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

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

(2.20)

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

 

(2.21)

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

(2.22)

Здесь - определённая ранее дифференциальная энтропия , а - условная дифференциальная энтропия. Легко убедиться, что основные свойства взаимной информации остаются справедливыми и в данном случае.

В качестве примера найдём дифференциальную энтропию случайной величины с нормальным распределением вероятности:

, (2.23)

где математическое ожидание, а - дисперсия .

Подставив (2.23) в (2.20), найдём:

Первый интеграл по общему свойству плотности вероятности равен 1, а второй – по определению дисперсии равен . Окончательно

(2.24)

Таким образом, диффиринциал энтропия гауссовский случайной величины не зависит от её математического ожидания и монотонно возрастает с увеличением дисперсии.

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

 

Тема 2.5. Пропускная способность канала связи

В любой системе связи через канал передаётся информация. Её скорость передачи зависит не только от самого канала, но и от свойств подаваемого на его вход сигнала и поэтому не может характеризовать канал как средство передачи информации. Найдём способ оценки способности канала передавать информацию. Для каждого источника количество информации, переданной по каналу принимает своё значение.

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

бит/ симв.

(где максимизация производится по всем многомерным распределениям вероятностей Р(А))

Можно также определить пропускную способность С канала в расчёте на единицу времени.

(2.25)

Вычислим пропускную способность симметричного канала без памяти

(2.26)

Величина в данном случае легко вычисляется, поскольку условная (переходная) вероятность принимает только два значения: , если и (1-Р), если .

Первое из этих значений возникает с вероятностью Р, а второе – с вероятностью (1-Р). К тому же, поскольку рассматривается канал без памяти, результаты приёма отдельных символов независимы друг от друга.

Поэтому

(2.27)

Следовательно Н(В/А) не зависит от распределения вероятности в ансамбле А, а определяется только переходными вероятностями канала. Это свойство сохраняется для всех моделей с аддитивным шумом.

Подставив (2.27) в (2.26) получим:

(2.28)

Поскольку в правой части только член Н(В) зависит от распределения вероятности Р(А), то максимизировать необходимо именно его.

Максимальное значение Н(В) равно log m и реализуется оно тогда, когда все принятые символы равновероятны и независимы друг от друга. Легко убедиться, что это условие удовлетворяется, если входные символы равновероятны и независимы, поскольку в этом случае

При этом и

(2.29)

Отсюда пропускная способность в расчёте на единицу времени

(2.30)

Для двоичного симметричного канала (m=2) пропускная способность в двоичных единицах в единицу времени

(2.31)

Зависимость от Р согласно формуле (2.31)

При Р=1/2 пропускная способность двоичного канала С=0, поскольку при такой вероятности ошибки последовательность выходных двоичных символов можно получить совсем не передавая сигналы по каналу, а выбирая их наугад (например, по результатам бросания монеты), то есть при Р=1/2 последовательности на выходе и входе канала независимы. Случай С=0 называется обрывом канала. То, что пропускная способность при P=1 в двоичном канале такая же, как при Р=0 (канал без шумов), объясняется тем, что при Р=1 достаточно все выходные символы инвертировать (то есть заменить 0 на 1 и 1 на 0), чтобы правильно восстановить входной сигнал.

Пропускная способность непрерывного канала вычисляется аналогично. Пусть, например, канал имеет ограниченную полосу пропускания шириной F. Тогда сигналы U(t) и Z(t) соответственно на входе и выходе канала по теореме. Котельникова определяются своими отсчётами, взятыми через интервал 1/(2F), и поэтому информация, проходящая по каналу за некоторое время Т, равна, сумме количества информации, переданной за каждый такой отсчёт. Пропускная способность канала на один такой отсчёт:

(2.32)

Здесь U и Z – случайные величины – сечения процессов U(t) и Z(t) на входе и выходе канала соответственно и максимум берётся по всем допустимым входным сигналам, то есть по всем распределениям U.

Пропускная способность С определяется как сумма значений , взятая по всем отсчётам за секунду. При этом разумеется дифференциальные энтропии в (2.35) должны вычисляться с учётом вероятностных связей между отсчётами.

Вычислим пропускную способность непрерывного канала без памяти с аддитивным белым гауссовским шумом, имеющим полосу пропускания шириной F, если средняя мощность сигнала . Мощность (дисперсию) шума в полосе F обозначим . Отсчёты выходного и входного сигналов, а также шума N связаны равенством:

Z=U+N (2.33)

Так как N имеет нормальное распределение с нулевым математическим ожиданием, то и условная плотность вероятности при фиксированном U будет так же нормальной – с математическим ожиданием U и дисперсией .

Пропускная способность на один отсчёт определятся по формуле (2.32):

Согласно (2.24) условная дифференциальная энтропия h(Z/U) нормального распределения не зависит от математического ожидания и равна . Поэтому для нахождения следует найти такую плотность распределения , при которой максимизируется h(Z). Из (2.33) учитывая, что U и N независимые случайные величины имеем для дисперсий

Таким образом, дисперсиия фиксирована, так как и заданы. Как известно, при фиксированной дисперсии максимальная дифференциальная энтропия обеспечивается нормальным распределением. Из (2.33) видно, что при нормальном одномерном распределении U распределение Z будет так же нормальным и, следовательно, обеспечивается максимум дифференциальной энтропии (2.24).

(2.34)

Откуда

(2.35)

Переходя к пропускной способности С в расчёте на секунду, заметим, что информация, переданная за несколько отсчётов, максимальна в том случае, когда отсчёты сигналов независимы. Этого можно достичь, если сигнал U(t) выбрать так, чтобы его спектральная плотность была равномерной в полосе F. Отсчёты разделённые интервалами, кратными 1/(2F), взаимно некоррелированы, а для гауссовских величин некоррелированность означает независимость. Поэтому пропускную способность С (за секунду) можно найти, сложив пропускные способности (2.35) для 2F независимых отсчётов:

(2.36)

Она реализуется, если U(t) – гауссовский процесс с равномерной спектральной плотностью в полосе частот F (квазибелый шум).

Из (2.36) видно, что если бы мощность сигнала не была ограничена, то пропускная способность была бы сколь угодно большой. Пропускная способность равна нулю, если отношение сигнал-шум в канале равно нулю. С ростом этого отношения пропускная способность увеличивается неограниченно, однако медленно, вследствие логарифмической зависимости.

Соотношение (2.36) называется формулой Шеннона. Эта формула имеет важное значение в теории информации, так как определяет зависимость пропускной способности рассматриваемого непрерывного канала от таких его технических характеристик, как ширина полосы пропускания и отношение сигнал шум. Формула Шеннона указывает на возможность обмена полосы пропускания на мощность сигнала и наоборот. Однако поскольку С зависит от F линейно, а от – по логарифмическому закону, компенсировать возможное сокращение полосы пропускания увеличением мощности сигнала, как правило, не выгодно. Более эффективным является обратный обмен мощности сигнала на полосу пропускания.

Максимальный объём информации, которую можно в среднем передать по непрерывному каналу за время ,

Для гауссовского канала

(2.37)

Заметим, что при Выражение (2.37) совпадает с характеристикой названной ёмкостью (объёмом) канала.

 

Тема 2.6. Теорема К. Шеннона

 

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

(A)< C, (12.38)

то существует способ кодирования (преобразования сообщения в сигнал на входе) и декодирования (преобразования сигнала в сообщение на выходе канала), при при котором вероятность ошибочного декодирования и ненадёжность могут быть сколь угодно малы. Если же (A)> C, то таких способов не существует.

Рассмотрим содержание теоремы Шеннона.

Как отмечалось, для восстановления по пришедшему сигналу переданного сообщения необходимо, чтобы сигнал содержал о нём информацию, равную энтропии сообщения. Следовательно, для правильной передачи сообщения необходимо, чтобы скорость передачи информации была не меньше производительности источника. Так как по определению скорость передачи информации не превышает пропускной способности, то неравенство (A)< C является необходимым условием для точной передачи сообщения.

Но является ли это условие достаточным?

Конечно, при C> H’(A) можно передавать такие сигналы, что достигнет значения H’(A). Но – это скорость передачи информации о сигнале В, а не о сообщении А. Поэтому вопрос сводится к тому, можно ли установить такое соответствие (код) между сообщением А и сигналом В чтобы вся информация, полученная на выходе канала о сигнале В, была в то же время информацией о сообщении А? (Чтобы преобразования между А и В были обратимыми)

Положительный ответ на этот вопрос очевиден в тривиальном случае, когда в канале нет помех и сигнал В принимается безошибочно. При этом , и если между А и В установлено взаимно однозначное соответствие, то по принятому сигналу можно однозначно восстановить сообщение. В общем же случае в канале имеются помехи и сигнал В принимается с ошибками, так что . Отсюда следует, что даже если достигнет (A), то всё равно (В)> (А), так как . Это значит, что производительность источника сигнала В должна быть выше производительности источника сообщения А и, следовательно, В содержит, кроме информации об А дополнительную собственную информацию. Часть информации о сигнале В в канале теряется. Вопрос сводится к следующему: можно ли осуществить кодирование так, чтобы терялась только дополнительная (избыточная) часть собственной информации В, а информация об А сохранялась?

Теорема Шеннона даёт на этот вопрос почти положительный ответ, с той лишь поправкой, что скорость «утечки информации» (или ненадёжность) не равна в точности нулю, но может быть сделана сколь угодно малой. соответственно сколь угодно малой может быть сделана вероятность ошибочного декодирования. При этом, чем меньше допустимая вероятность ошибочного декодирования, тем сложнее должен быть код.

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

(2.39)

В этом случае данная теорема свелась бы к теореме о кодировании источника.

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

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

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

 

Тема 2.7. Информация в непрерывных сообщениях. Эпсилон-энтропия

 

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