Закон аддитивности информации

Пусть задано множество X, содержащее N₁ элементов x_i Є X,а также множество Y,содержащее N₂ элементов y_j Є Y. Составим пары элементов (x_i y_j). Очевидно, что множество пар будет содержать N₁·N₂ элементов.

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

log₂(N₁·N₂)= log₂ N₁+ log₂ N₂

Последнее выражение носит название закона аддитивности информации.

Формула Хартли получена при ограничениях.

1. Отсутствие смысловой ценности информации.

2. N возможных состояний равновероятны:

log N = -log 1/N = -log p

p = 1/N— вероятность появления одного сообщения.

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

log N = - log 1/N= - log p

р=1/N— вероятность появления любого значения из N возможных.

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

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

x_1, x_2,… x_i… x_n Σ P_i = 1

{X,P(x)} =

P₁, P₂,…P_i…P_n

Верхняя строка содержит сообщение (значение дискретной случайной величины), нижняя — вероятности их появления.

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

Жизненный опыт подсказывает, что информация о событии тем значительнее, чем меньше вероятность появления такого события. Однако, мера количества информации в виде 1/P(x_i)не удобна по двум причинам: она не обладает свойством аддитивности и не обслуживает случай достоверного события.

В теории информации в качестве меры количества информации принята логарифмическая мера.

Определение 1. Количеством собственной информации в сообщении x_i Є Xназывается число I(x_i),определяемое соотношением:

I(x_i)= log 1/P(x_i)=-log P(x_i) (1)

Единица измерения количества информации и её названия зависит от основания логарифма. Если основанием логарифма является:

· Число 2, т.е. log₂P(x_i)[бит]

· Число e, т.е. log_eP(x_i)=lnP(x_i)[нат] «natural digit»

· Число 10, т.е. . lg₁₀P(x_i)[дит]

Собственная информация неотрицательно и сообщение, имеющее меньшую вероятность несет большую информацию.

Количество информации, определяемое соотношением (1) является действительной функцией на ансамбле {X,P(x)}и следовательно, представляет собой случайную функцию со значениями I(x₁), I(x₂),…, I(x_n).

Среднее количество информации, содержащееся в одном сообщении можно выразить:

M [I(x_i)]=Σ P_i I(x_i)=-Σ P _ilogP_i (2)

Выражение (2) является формулой Шеннона и решает одну из основных задач теории информации, задачу количественной меры информации. Для двоичных сообщений формула имеет вид:

I[X] = -Σ P_i log₂P_i [бит]

Формула Шеннона отображает общий случай, для произвольного закона распределения, когда вероятности отдельных сообщений не равны. Легко показать, что формула Хартли является частным случаем формула Шеннона, когда вероятности сообщений равны между собой. Если в формуле Шеннона принять одинаковую вероятность всех сообщений равную P_i(x_i)=1/N=1/2ⁿ, если N=2ⁿ, то после преобразований получим:

-Σ P_i log₂P_i = N·1/N·log₂ 1/(1/N) = log₂N = n

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

Энтропия

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

Определение. Математическое ожидание H(X) случайной величины I(x_i),определенной на ансамбле {X,P(x)}называется энтропией этого ансамбля:

H(X) = Σ I(x_i) P(x_i) = -Σ P(x_i) log₂P(x_i)бит/выход источника

Энтропия источника – среднее количество информации в одном сообщении. Не следует путать энтропию источника с количеством информации в одном конкретном сообщении I(x_i).

Свойства энтропии источника дискретных сообщений:

1. Энтропия ограничена, неотрицательна, вещественна. Это вытекает из свойства вероятности:

0 ≤ P(x_i) ≤ 1

2. Энтропия детерминированного сообщения равна нулю.

Запишем формулу энтропии в виде:

H(X) = -P₁ log₂P_i - Σ P_i log₂P_i = 0 , где P₁log₂P_i=0 (2)

Если P₁=1, то сумма всех остальных вероятностей равна 0. Первый член в выражении (2) равен нулю. Рассмотрим одно слагаемое в сумме, устремив P_i→0.

lim(-P_i log₂P_i)=lim P log₂1/P_i= lim log₂ß/ ß_i

P_i→0 P_i→0 ß → ∞

Раскрыв неопределённость по Лопиталю, получим:

lim (1/ ß) ·ln2 = 0

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

3. Энтропия альтернативного сообщения.

Альтернативный источник имеет только два выходных значения с вероятностями p и q, где q=(1-p), выражение для энтропии имеет вид:

H=-p log₂₍p-q) log₂q

Это функция двух переменных p и q. Учитывая, что q=(1-p), получим:

H=-p log₂₍p-(1-p)) log₂(1-p)

Изменяя p от 0 до 1 можно построить график рис. 2.

ХХХХХХХХХХХХХХХХХХХХХХХХХХХХХХХХ

4. Энтропия дискретного источника со многими состояния максимальна, если состояния равновероятны.

Термин «энтропия» имеет несколько неопределённый смысл, что вызвано использованием его в термодинамике и статистической механике для выражения несколько иных понятий.

Результатом рассмотрения информационных моделей сигналов являлась оценка информации для каждого символа:

I(x_i) = -log₂P(x_i)

И формула энтропии источника дискретных сообщений:

H(x) = M[I(x_i)] = -Σ P_i log₂P_i

Из свойств энтропии следует, что количество информации в битах на символ лежит в пределах:

0 ≤ H(X) ≤ log₂N

Нижний предел соответствует отсутствию неопределённости, а верхний максимальной неопределённости или равновероятности исходов наблюдений. Если распределение алфавита неравномерно информационное содержание алфавита меньше максимального и может быть найдено по формуле Шеннона:

H(x) = - Σ P_i log₂P_i

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

P(x_j,x_k) = P(x_j/x_k) P(x_k) = P(x_j) P(x_k)

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

Между максимальной энтропией H_max(x)и безусловной H_без(x)должно соблюдаться очевидное условие:

H_без(x) ≤ H_max(x)

Уменьшение безусловной энтропии обусловлено различием вероятностей сообщений.

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

H_усл(x) = Σ P(x_i) H_усл(x/x_i), бит/сообщение.

Где H_усл(x/x_i) = - Σ P(x_j/x_i) log2P(x_j/x_i)

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

Hусл (x) ≤ H_без(x)

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

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

Зависимость символов означает, что для последовательности Ксимволов неопределённость относительно К-го символа уменьшается, если известны (K-1) предыдущие. В слове СТУДЕН_неопределённость относительно последней буквы уменьшается, если известны предшествующие.

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

или , (1.4)

где H(X) - безусловная энтропия величины Х;

H(Y) - безусловная энтропия величины Y;

H(Y/X) - условная энтропиявеличины Y относительно величины Х;

H(X/Y) - условная энтропия величины X относительно Y.

Для независимых величин и .

Условная энтропия X относительно Y

, (1.5)

где P(x_i/y_j) - вероятность значения x_i величины X при условии, что величина Y приняла значение y_j (условная вероятность).

Условная энтропия величины X относительно значения y_j величины Y

. (1.6)