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

Рассмотрим ансамбли X = {x i } и Y ={y j } и их произведение XY ={(x i ,y j ), P (x i ,y j )}. Для любого фиксированного y j ÎY можно построить условное распределение вероятностей P (x i /y j )на множестве X и для каждого x i ÎX подсчитать собственную информацию

которую называют условной собственной информацией сообщения x i при фиксированном y j .

Ранее мы назвали энтропией ансамбля X среднюю информацию сообщений x i ÎX . Аналогично, усреднив условную информацию I (x i /y j )по x i ÎX , получим величину

,

называемую условной энтропией X при фиксированном y j ÎY . Заметим, что в данном определении имеет место неопределенность в случае, когда P (x i /y j )=0. Следует отмечалось, что выражение вида z log z стремится к нулю при z® 0 и на этом основании мы считаем слагаемые энтропии, соответствующие буквам x i с вероятностью P (x i /y j )=0, равными нулю.

Вновь введенная энтропия H (X /y j ) – случайная величина, поскольку она зависит от случайной переменной y j . Чтобы получить неслучайную информационную характеристику пары вероятностных ансамблей, нужно выполнить усреднение по всем значениям y j . Величина

называется условной энтропией ансамбля X при фиксированном ансамбле Y . Отметим ряд свойств условной энтропии.

2. , причем равенство имеет место в том и только в том случае, когда ансамбли X и Y независимы.

5. причем равенство имеет место в том и только в том случае, когда ансамбли X и Y условно независимы при всех zÎ Z .

Обсудим «физический смысл» сформулированных свойств условной энтропии. Свойство 2 устанавливает, что условная энтропия ансамбля не превышает его безусловной энтропии. Свойство 5 усиливает это утверждение. Из него следует, что условная энтропия не увеличивается с увеличением числа условий. Оба эти факта неудивительны, они отражают тот факт, что дополнительная информация об ансамбле X , содержащаяся в сообщениях других ансамблей, в среднем, уменьшает информативность (неопределенность) ансамбля X . Замечание «в среднем» здесь очень важно, поскольку неравенство H(X /y j ) ≤ H(X ), вообще говоря, не верно.

Из свойств 1 – 5 следует неравенство

, (11.4)

в котором равенство возможно только в случае совместной независимости ансамблей X 1 , …, X n .

Напомним, что вычисление энтропии – это вычисление затрат на передачу или хранение букв источника. Свойства условной энтропии подсказывают, что при передаче буквы X n + 1 следует использовать то обстоятельство, что предыдущие буквы X 1 , …, X n уже известны на приемной стороне. Это позволит вместо H (X n +1)бит потратить меньшее количество H (X n +1 /X 1 ,…,X n ) бит. В то же время неравенство (11.4) указывает другой подход к экономному кодированию. Из этого неравенства следует, что буквы перед кодированием нужно объединять в блоки и эти блоки рассматривать как буквы нового «расширенного» источника. Затраты будут меньше, чем при независимом кодировании букв. Какой из двух подходов эффективнее?

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

Условная энтропия

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

Например, в последовательности букв, составляющих какое-либо предложение на русском языке, разные буквы появляются с разной частотой, поэтому неопределённость появления для некоторых букв меньше, чем для других. Если же учесть, что некоторые сочетания букв (в этом случае говорят об энтропии n -ого порядка, см. ) встречаются очень редко, то неопределённость ещё более уменьшается.

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

Формальные определения

Информационная энтропия для независимых случайных событий x с n возможными состояниями (от 1 до n ) рассчитывается по формуле:

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

Таким образом, энтропия события x является суммой с противоположным знаком всех произведений относительных частот появления события i , умноженных на их же двоичные логарифмы (основание 2 выбрано только для удобства работы с информацией, представленной в двоичной форме). Это определение для дискретных случайных событий можно расширить для функции распределения вероятностей .

В общем случае b -арная энтропия (где b равно 2, 3, …) источника с исходным алфавитом и дискретным распределением вероятности где p i является вероятностью a i (p i = p (a i ) ) определяется формулой:

Определение энтропии Шеннона связано с понятием термодинамической энтропии . Больцман и Гиббс проделали большую работу по статистической термодинамике, которая способствовала принятию слова «энтропия» в информационную теорию. Существует связь между термодинамической и информационной энтропией. Например, демон Максвелла также противопоставляет термодинамическую энтропию информации, и получение какого-либо количества информации равно потерянной энтропии.

Альтернативное определение

Другим способом определения функции энтропии H является доказательство, что H однозначно определена (как указано ранее), если и только если H удовлетворяет условиям:

Свойства

Важно помнить, что энтропия является количеством, определённым в контексте вероятностной модели для источника данных. Например, кидание монеты имеет энтропию − 2(0,5log 2 0,5) = 1 бит на одно кидание (при условии его независимости). У источника, который генерирует строку, состоящую только из букв «А», энтропия равна нулю: . Так, например, опытным путём можно установить, что энтропия английского текста равна 1,5 бит на символ, что конечно будет варьироваться для разных текстов. Степень энтропии источника данных означает среднее число битов на элемент данных, требуемых для её зашифровки без потери информации, при оптимальном кодировании.

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

Математические свойства

Эффективность

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

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

Энтропия ограничивает максимально возможное сжатие без потерь (или почти без потерь), которое может быть реализовано при использовании теоретически - типичного набора или, на практике, - кодирования Хаффмана , кодирования Лемпеля - Зива - Велча или арифметического кодирования .

Вариации и обобщения

Условная энтропия

Если следование символов алфавита не независимо (например, во французском языке после буквы «q» почти всегда следует «u», а после слова «передовик» в советских газетах обычно следовало слово «производства» или «труда»), количество информации, которую несёт последовательность таких символов (а следовательно и энтропия) очевидно меньше. Для учёта таких фактов используется условная энтропия.

Условной энтропией первого порядка (аналогично для Марковской модели первого порядка) называется энтропия для алфавита, где известны вероятности появления одной буквы после другой (то есть вероятности двухбуквенных сочетаний):

где i - это состояние, зависящее от предшествующего символа, и p i (j ) - это вероятность j , при условии, что i был предыдущим символом.

Так, для русского языка без буквы « » .

Через частную и общую условные энтропии полностью описываются информационные потери при передаче данных в канале с помехами. Для этого применяются так называемые канальные матрицы . Так, для описания потерь со стороны источника (то есть известен посланный сигнал), рассматривают условную вероятность получения приёмником символа b j при условии, что был отправлен символ a i . При этом канальная матрица имеет следующий вид:

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

Для вычисления потерь при передаче всех сигналов используется общая условная энтропия:

Означает энтропию со стороны источника, аналогично рассматривается - энтропия со стороны приёмника: вместо всюду указывается (суммируя элементы строки можно получить p (a i ) , а элементы диагонали означают вероятность того, что был отправлен именно тот символ, который получен, то есть вероятность правильной передачи).

Взаимная энтропия

Взаимная энтропия, или энтропия объединения , предназначена для расчёта энтропии взаимосвязанных систем (энтропии совместного появления статистически зависимых сообщений) и обозначается H (A B ) , где A , как всегда, характеризует передатчик, а B - приёмник.

Взаимосвязь переданных и полученных сигналов описывается вероятностями совместных событий p (a i b j ) , и для полного описания характеристик канала требуется только одна матрица:

Для более общего случая, когда описывается не канал, а просто взаимодействующие системы, матрица необязательно должна быть квадратной. Очевидно, сумма всех элементов столбца с номером j даст p (b j ) , сумма строки с номером i есть p (a i ) , а сумма всех элементов матрицы равна 1. Совместная вероятность p (a i b j ) событий a i и b j вычисляется как произведение исходной и условной вероятности,

Условные вероятности производятся по формуле Байеса . Таким образом имеются все данные для вычисления энтропий источника и приёмника:

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

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

Взаимная энтропия обладает свойством информационной полноты - из неё можно получить все рассматриваемые величины.

Рассматривая формулу Шеннона (3.3) для вычисления энтропии случайной величины и количества информации, мы предполагали, что информация о случайной величине (X) поступает непосредственно к наблюдателю. Однако, как правило, мы получаем информацию не о той случайной величине (X), которая нас интересует, а о некоторой другой (Y), которая связана с X стохастическим образом. Такая связь случайных величин отличается от функциональной связи, при которой каждому значению одной величины соответствует единственное, вполне определённое значение другой величины. Стохастическая (вероятностная) связь двух случайных величин X и Y означает, что изменение одной из них влияет на значение другой, но таким образом, что зная значение X нельзя точно указать значение, которое примет величина Y. Можно лишь указать тенденцию изменения величины Y.

Пусть B – случайное событие; p(B) – вероятность его наступления; обозначим через X случайную величину, которая принимает N различных значений {x 1 , x 2 , … x N }, а через A k событие, состоящее в том, что случайная величина X примет значение x k:

A k = { X = x k }, k=1,2, …N ;

Вероятность события A k обозначим через p(A k). Вероятность наступления некоторых событий может меняться в зависимости от того, наступило или нет некоторое другое событие. Вероятность p B (A k) события A k , вычисленная в предположении, что наступило событие B, называется условной вероятностью события A k , при этом:

События А k и B называются независимыми, если вероятность наступления события А k не зависит от того, наступило или нет событие B. Это означает, что условная вероятность события p B (A k) равна «обычной» вероятности p(A k).

Определение. Условной энтропией случайной величины X при условии B называется величина

(4.2)

Отличие от формулы Шеннона (3.3) заключается в том, что вместо вероятностей p(A k) используются условные вероятности p B (A k).

Пусть теперь Y – другая случайная величина, принимающая значения {y 1 , y 2 , … y M }. Обозначим через B j событие, состоящее в том, что случайная величина Y примет значение y j:

B j = { Y = y j }, j=1, 2,… M.

Вероятность события B j обозначим через p(B j).

Определение. Условной энтропией случайной величины X при заданном значении случайной величины Y называется величина H Y (X)

(4.3)

Выполним преобразование формулы (4.3):

Формула (4.3) принимает вид:

(4.4)

Вычислим количество информации о случайной величине X, полученное при наблюдении за случайной величиной Y. Это количество информации I(X,Y) равно убыли энтропии случайной величины X при наблюдении за случайной величиной Y:

Подставим в (15) выражения для H(X) и H Y (X):

Заменим в первой сумме p(A k)=p(A k B 1)+ p(A k B 2)+ p(A k B 3)…+ p(A k B M). Это равенство действительно имеет место, т.к. события A k B 1 , A k B 2 , … A k B M – попарно несовместные, при этом одно из них наступит, если наступит A k . Наоборот, если наступит одно из B j , то наступит и A k . Продолжая преобразования, получим:

Итак, мы получили формулу для вычисления количества информации о случайной величине X при наблюдении за другой случайной величиной Y:

(4.6)

Если случайные величины (или события) независимы, то для них выполняется соотношение p(A k B j) = p(A k)p(B j) – вероятность совместного наступления двух событий равна произведению вероятностей этих событий.

Относительно величины I(X,Y) справедливы следующие утверждения.

Для независимых случайных величин получим

Это означает, что наблюдение за случайной величиной Y не даст никакого преимущества в получении информации о случайной величине Х.

В других случаях I(X,Y) >0, при этом выполняется неравенство:

Равенство достигается в случае наличия функциональной связи Y=F(X). В этом случае наблюдение за Y даёт полную информацию о X. Если Y=X, то I(X,X) = H(X).

Величина I(X,Y) симметрична: I(X,Y) = I(Y,X). Это означает, что наблюдение случайной величины Y даёт такое же количество информации о случайной величине Х, какое наблюдение случайной величины Х даёт относительно случайной величины Y. Если мы рассматриваем две случайные величины, которые находятся в стохастической зависимости, то средствами теории информации нельзя установить какая из них является причиной, а какая следствием.

Условная энтропия

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

Например, сообщение о матче футбольных команд Комета и Ракета «Комета выиграла» полностью снимает неопределенность о том, как сыграла Ракета.

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

Пусть источник А порождает ансамбль Ма сообщений (а а, а 2 ,..., а Ма), источнике порождает ансамбль Mb сообщений (Ь 2 , Ь 2 ,..., Ьдд,) и источники зависимы. Общий алфавит источников представляет собой множество пар вида (а, Ь;), общая мощность алфавита: Ма х Mb.

Энтропия сложной информационной системы (из двух источников) равна

Поскольку А и В зависимы, то а

Подставив это в выражение для энтропии сложной системы, получаем:

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

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

Во втором слагаемом члены вида

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

или подробнее

где Н(В |А) есть общая условная энтропия источника В относительно источника А. Окончательно получаем для энтропии сложной системы:

Полученное выражение представляет собой общее правило нахождения энтропии сложной системы. Совершенно очевидно, что выражение (2.9) является частным случаем (2.11) при условии независимости источников А и В.

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

1. Условная энтропия является величиной неотрицательной. Причем Н(В |А) = 0 только в том случае, если любое сообщение А полностью определяет сообщение В, т.е.

В этом случае Н(А, В) = Н(А).

2. Если источники А и В независимы, то Н(В |А) = Н(В), причем это оказывается наибольшим значением условной энтропии. Другими словами, сообщение источника А не может повысить неопределенность сообщения источника В; оно может либо не оказать никакого влияния (если источники независимы), либо понизить энтропию В.

Приведенные утверждения можно объединить одним неравенством:

т.е. условная энтропия не превосходит безусловную.

3. Из соотношений (2.11) и (2.12) следует, что

причем равенство реализуется только в том случае, если источники А и В независимы.

Энтропия источника непрерывных сообщений

Рассмотрим систему, где качественные признаки состояния изменяются непрерывно (непрерывный сигнал). Вероятность нахождения системы в состоянии х (т.е. сигнал принимает значение х) характеризуется плотностью вероятности/(х). Чтобы найти энтропию такого сообщения, разбиваем диапазон возможного изменения сигнала на дискреты размером Дх. Вероятность нахождения системы в i-й дискрете равна