Определение количества информации по К. Шеннону

 

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

Допустим, некоторое устройство вырабатывает (генерирует) число как независимую последовательность из единиц и нулей, которые появляются соответственно с вероятностями, равными р и q= 1— р. В этом случае при неограниченном возрастании длины последовательности п с вероятностью, равной единице, появляются последовательности, количество единиц в которых незначительно отличается от среднего значения, равного пр. Такие последовательности называются типичными. Они различаются между собой в основном только размещением единиц, а не их количеством. Поскольку количество типичных последовательностей Q меньше общего количества последовательностей, то имеется возможность уменьшить количество информации, необходимое для определения числа.

Последовательность назовем типичной для заданного источника, если количество единиц n в ней удовлетворяет неравенству

или (4.1)

и нетипичной в противном случае, то есть когда

(4.2)

Вероятность появления нетипичной последовательности равна вероятности, с которой n₁ удовлетворяет неравенству (4.2). Для оценки этой вероятности воспользуемся нера­венством Чебышева, которое для произвольной случайной величины ξ, имеющей конечную дисперсию, при каждом b>0 записывается в виде

,

где и — соответственно математическое ожидание и дисперсия случайной величины . Полагая =n_1, = =пр, b= n, = =npq (q=( 1—p)), получим аналогичное неравенство для случайного числа единиц n₁

Следовательно, вероятность появления нетипичной последовательности

,

а вероятность появления типичной последовательности

.

Вероятность Р_нт стремится к нулю, а вероятность Р_т стремится к единице при любом сколь угодно малом значении ε и неограниченном возрастании длины последовательности п. Интервал [- п , п ], которому принадлежит количество единиц в типичной последовательности, неограниченно увеличива­ется (п → ), хотя относительная величина интервала всегда меньше значения ε. Докажем, что одновременно с неограниченным увеличением длины последовательности п можно уменьшать значение = (n) с такой скоростью, при которой относительная величина интервала будет стремиться к нулю, а вероятность появления типичной последовательности — к единице. При этом абсолютная величина интервала по-прежнему неограниченно возрастает. Вероятность Р_Т стремится к единице, если величина ²(п)п неограниченно увеличивается с ростом п. Пусть ²(п)п= , где >0 — некоторый параметр, определяющий скорость роста величины ²(п)п. Отсюда , (0< <0,5).

Величина (п) стремится к нулю с ростом п при <0,5. При этом абсолютная величина интервала п (п) не может быть постоянной или стремиться к нулю одновременно с неограни­ченным увеличением величины ²(п)п, стремлением (п) к нулю.

Определим количество типичных последовательностей Q.

Вероятность появления произвольной последовательности B_k равна .

В результате тождественных преобразований .

Прологарифмировав последнее равенство, получим

 

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

Покажем, что в случае типичных последовательностей остаточным членом О(п) по сравнению с величиной Н(Х) можно пренебречь.

Поскольку для типичных последовательностей справедливо неравенство ,то

Следовательно,

Таким образом, при достаточно большом п справедливо приближенное равенство .

Отсюда вероятность появления отдельной типичной последовательности

P(B_k) m^-nH(X)

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

Рт= ,

где суммирование ведется по всему множеству типичных последовательностей. Отсюда:

Q₌m^nH(X)

причем единица измерения энтропии Н(Х) совпадает с основанием степени т. Поскольку количество информации, необходимое для определения состояния регистра, равно log Q, то энтропия

Н(Х) = равна количеству информации, которое необходимо для определения состояния одного разряда.

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

 

Свойства энтропии

Энтропия поскольку p_i удовлетворяет неравенству 0 1. Энтропия H(X)=0, когда система находится в одном из состояний с вероятностью, равной единице, и во всех остальных — с вероятностью, равной нулю. При этом имеется в виду, что

p_ilog p_i=0.

При равномерном распределении (p_i= ) энтропия H(X)=logm_x

Докажем, что это максимальное значение энтропии. Используя равенство =1, можно выполнить следующие тождественные преобразования:

Н(Х)-logm_X=

Для оценки выражения log воспользуемся неравенством

lnz z—1, положив z= .

 

0 0,2 0,4 0,6 0,8 1 р

0,2

0,4

0,6

0,8

H 1

 

 

Рис. 4.1. Энтропия системы с двумя состояниями: р – вероятность одного из состояний

 

 

Заменяя на , получим

где log e —модуль перехода. Отсюда

Пусть множество состоит из двух элементов, которые обозначим через единицу и ноль, причем единица появляется с вероятностью, равной р, а ноль — с вероятностью, равной q=1 — р. Тогда

.

Указанная зависимость изображена на рис. 1. Максимум достигается при p=q= 0,5.

 

Ценность информации

 

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

Один из способов измерения ценности информации, сформулированный в рамках статистической теории информации, был предложен А.А.Харкевичем [3]. Ценность информации может быть выражена через приращение вероятности достижения цели. Если значение априорной вероятности достижения цели обозначить через р₁, а апостериорной — через p₂, то ценность полученной информации можно определить как log .

В системах передачи информации цель сводится к правильной передаче сообщений независимо от их конкретного содержания и формулируется относительно каждого символа множества X. Пусть целью является принятие решения в пользу x_i. Тогда относительно этой цели ценность сведений,содержащихся в принятом y_j равна log , где P(x_i) — априорная вероятность передачи х_i; p(x_i|y_j) — вероятность того, что было передано x_i после принятия y_j. При такой формулировке цели ценность информации совпадает с обычным количеством информации, которое определено выше.

Таким образом, количество информации, которое у_i несет об x_i, равно

.

Умножая числитель и знаменатель под логарифмом на р{у_j) и учитывая равенства

p(x_i|y_j)p(y_j)= p(x_i, y_j)= p(y_j |x_i)р(х_i),

получим

(4.3)

 

Отсюда следует, что y_j несет об такое же количество информации, какое х_i несет об y_j (свойство симметрии). Поэтому I(х_i, y_j) называется взаимным количеством информации между i-м символом множества X и j-м символом множества У. Взаимное количество информации I(х_i, y_j), может быть положительным , отрицательным и равным нулю . Отрицательная информация называется дезинформацией.