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

Рассмотрим ансамбли 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) указывает другой подход к экономному кодированию. Из этого неравенства следует, что буквы перед кодированием нужно объединять в блоки и эти блоки рассматривать как буквы нового «расширенного» источника. Затраты будут меньше, чем при независимом кодировании букв. Какой из двух подходов эффективнее?

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

Для дальнейшего изложения нам понадобятся некоторые известные сведения из теории вероятности.

1) Свойства вероятностей для ансамбля случайных событий А и В :

P(A,B)=P(A)*P(B/A); -> P(B/A)=P(A,B)/P(B);

P(A,B)=P(B)*P(B/A); -> P(A/B)=P(A,B)/P(A);

P(A/B)=P(A)*P(B/A)/P(B); P(B/A)=P(B)*P(A/B)/P(A);

Если А и В независимы, то

P(A/B)=P(A); P(B/A)=P(B):

P(A,B)=P(A)*P(B);

Еще раз определение энтропии по Шеннону для источника дискретных сообщений:

Ее свойства:

Н > 0 ;

Н m ах = log N ;

При независимых источниках H(A,B)=H(A)+H(B) ;

УСЛОВНАЯ ЭНТРОПИЯ

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

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

Рассмотрим передачу сообщений источника случайных символов А через канал передачи информации. При это полагается, что при достоверной передаче при при передаче символа a 1 получаем b 1 , a 2 - b 2 и т.д. При этом для канала с помехами передача искажается, и при получении сивола b 1 можно лишь сговорить о вероятности перередачи символа a 1 . Вполне может быть, что были переданы символы a 2 , a 3 и т.д.

Искажения описываются матрицей условных вероятностей канала P (A / B )={ p (a i / b i }.

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

Если источник сообщений выдает символы

a l , а 2 , ..., a i ..., а n

с вероятностями соответственно

р (а 1 ), р (а 2 ) ... ..., р (а i ), ..., р (а n ),

а на выходе канала передачи мы получаем символы

b 1 ,b 2 , ..., b i ..., b n

с вероятностями соотетственно

р (b 1 ), р (b 2 ), ..., р (b i , ..., р (b n ),

то понятие условной энтропии Н (B/ a i ) выражает неопределенность того, что, отправив a i , мы получим b i ., понятие H (A/b i ) неуверенность, которая остается после получения b i в том, что было отправлено именно a i . Графически это представлено на вышеприведеном рисунке. Если в канале связи присутствуют помехи, то с различной степенью вероятности может быть принят любой из сигналов b j и, наоборот, принятый сигнал b j может появиться и результате отправления любого из сигналов a i . Если в канале связи помехи отсутствуют, то всегда посланному символу а 1 соответствует принятый символ b 1 , а 2 - b 2 , ..., а n - b n .

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

Информационные потери полностью описываются через частную и общую условную энтропию. Вычисление частных и общей условной энтропии удобно производить при помощи канальных матриц. Термин «канальная матрица», означающий: матрица, статистически описывающая данный канал связи, применяется для краткости. Если канал связи описывается со стороны источника сообщений (т. е. известен посланный сигнал), то вероятность того, что при передаче сигнала a i по каналу связи с помехами мы получим сигнал b j обозначается как условная вероятность р (b j /ai). а канальная матрица имеет вид

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

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

Потери информации, приходящиеся на долю сигнала a i описываются при помощи частной условной энтропии. Например, для сигнала a 1

Суммирование производится по j, так как i -е состояние (в данном случае первое) остается постоянным.

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

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

Если иследовать ситуацию со стороны приемника сообщений (то есть когда известен принятый сигнал ) , то то с получением символа b j предполагается, что был послан какойто из символов a 1 , a 2 , …, a i ,…, a m . В этом случае канальная матрица имеет вид:

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

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

А общая условная энтропия

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

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

Если в канале связи помехи отсутствуют, то все элементы канальной матрицы, кроме расположенных на главной диагонали, равны нулю. Это говорит о том, что при передаче сигнала а 1 мы наверняка получим b 1 при передаче а 2 - b 2 , ..., а m - b m . Вероятность получения правильного сигнала станет безусловной , а условная энтропия будет равна нулю .

Своего максимума условная энтропия достигает в случае, когда при передаче символа а i может быть с равной вероятностью получен любой из сигналов b 1 , b 2 , ..., b m .

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

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

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