5.1.3. Аддитивная мера

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

I = l log h, (5.4)

где I – количество информации, содержащейся в сообщении;

l – длина сообщения;

h – мощность исходного алфавита.

При исходном алфавите {0,1}; l = 1; h = 2 и основании логарифма, равном 2, имеем

I = 1*log₂2 = 1.

Данная формула даёт аналитическое определение бита (BIT - BInary digiT) по Хартли: это количество информации, которое содержится в двоичной цифре.

Единицей измерения информации в аддитивной мере является бит.

Пример 5.3. Рассчитать количество информации, которое содержится в шестнадцатеричном и двоичном представлении ASCII-кода для числа 1.

В соответствии с таблицей ASCII-кодов (рис. 4.1) имеем:

шестнадцатеричное представление числа 1 – 31, (5.5)

двоичное представление числа 1 – 00110001. (5.6)

В соответствии с (5.4) получаем:

для (5.5) I = 2log₂16 = 8 бит;

для (5.6) I = 8 log₂2 = 8 бит.

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

5.2. Статистический подход к измерению информации

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

Вероятность p – количественная априорная (т.е. известная до проведения опыта) характеристика одного из исходов (событий) некоторого опыта. Измеряется в пределах от 0 до 1. Если заранее известны все исходы опыта, сумма их вероятностей равна 1, а сами исходы составляют полную группу событий. Если все исходы могут свершиться с одинаковой долей вероятности, они называются равновероятными.

Например, пусть опыт состоит в сдаче студентом экзамена по информатике. Очевидно, у этого опыта всего 4 исхода (по количеству возможных оценок, которые студент может получить на экзамене). Тогда эти исходы составляют полную группу событий, т.е. сумма их вероятностей равна 1. Если студент учился хорошо в течение семестра, значения вероятностей всех исходов могут быть такими:

p(5) = 0,5; p(4) = 0,3; p(3) = 0,1; p(2) = 0,1. (5.7)

Здесь запись p(j) означает вероятность исхода, когда получена оценка j (j = {2, 3, 4, 5}).

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

p (5) = 0,1; p(4) = 0,2; p(3) = 0,4; p(2) = 0,3. (5.8)

В обоих случаях выполняется условие:

где n – число исходов опыта,

i – номер одного из исходов.

Пусть можно получить n сообщений по результатам некоторого опыта (т.е. у опыта есть n исходов), причем известны вероятности получения каждого сообщения (исхода) - p_i. Тогда в соответствии с идеей Шеннона, количество информации I в сообщении i определяется по формуле (5.9):

I = -log₂ p_i, (5.9)

где p_i – вероятность i-го сообщения (исхода).

Пример 5.4. Определить количество информации, содержащейся в сообщении о результате сдачи экзамена для студента из (5.7).

Пусть I(j) – количество информации в сообщении о получении оценки j. В соответствии с (5.9) имеем:

I(5) = -log₂ 0,5 = 1,

I(4) = -log₂ 0,3 = 1,74,

I(3) = -log₂ 0,1 = 3,32,

I(2) = -log₂ 0,1 = 3,32.

Пример 5.5. Определить количество информации, содержащейся в сообщении о результате сдачи экзамена для студента из (5.8):

I(5) = -log₂ 0,1 = 3,32,

I(4) = -log₂ 0,2 = 2,32,

I(3) = -log₂ 0,4 = 1,32,

I(2) = -log₂ 0,3 = 1,74.

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

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

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

Пример 5.6. Есть 4 сообщения: a, b, c, d с вероятностями, соответственно, р(a) = 0,5; р(b) = 0,25; р(c) = 0,125; р(d) = 0,125. Определить число двоичных разрядов, требуемых для кодирования каждого их четырех сообщений.

В соответствии с (5.9) имеем:

I(a) = -log₂0,5 = 2,

I(b) = -log₂0,25 = 2,

I(c) = -log₂0,125 = 3,

I(d) = -log₂0,125 = 3.

Судя по примеру 4.7, эффективное кодирование методом Шеннона-Фано сформировало для заданных сообщений (символов) коды полученной длины.

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

Для вещественных значений объемов информации (что произошло в примере 5.4) в целях определения требуемого числа двоичных разрядов полученные значения округляются по традиционным правилам арифметики. Тогда имеем требуемое число двоичных разрядов:

для сообщения об оценке 5 – 1,

для сообщения об оценке 4 – 2,

для сообщения об оценке 3 – 3,

для сообщения об оценке 2 – 3.

Проверим результат, построив эффективный код для сообщений об исходах экзамена методом Шеннона-Фано. Исходные данные – из примера 5.4.

Имеем:

Исходные символы	Вероятности	Коды
сообщение об оценке 5	0,5	1
сообщение об оценке 4	0,25	01
сообщение об оценке 3	0,125	001
сообщение об оценке 2	0,125	000

Таким образом, задача решена верно.

П

(5.10)

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

где p_i – вероятность i-го сообщения.

Пример 5.8. Определить среднее количество информации, получаемое студентом из (5.7), по всем результатам сдачи экзамена.

В соответствии с (5.10) имеем:

I_ср = - (0,5*log₂0,5 + 0,3*log₂0,3 + 0,1*log₂0,1 + 0,1*log₂0,1) = 1,67.

Пример 5.9. Определить среднее количество информации, получаемое студентом из (5.8), по всем результатам сдачи экзамена.

В соответствии с (5.10) имеем:

I_ср = - (0,1*log₂0,1 + 0,2*log₂0,2 + 0,4*log₂0,4 + 0,3*log₂0,3) = 1,73.

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

Пусть у опыта два равновероятных исхода, составляющих полную группу событий, т.е. p_{1 =} p₂ = 0,5. Тогда имеем в соответствии с (5.10):

I _ср = -(0,5*log₂0,5 + 0,5*log₂0,5) = 1. (5.11)

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

Единица измерения информации при статистическом подходе – бит.

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

Пример 5.10. Пусть имеются 14 определений информатики из прил. 1 и других определений не существует (это значит, что определения из прил. 1 составляют полную группу событий, т.е. сумма их вероятностей равна 1). Все определения – равновероятны, т.е. предпочтения не отдается никакому из них (это означает, что вероятности всех определений равны между собой и равны 1/14). Рассчитать количество информации, содержащейся в определении 13, и среднее количество информации, получаемое по всем определениям.

Количество информации, содержащейся в определении 13, рассчитаем по формуле (5.9). Имеем:

I = -log₂ p_i = I = -log₂1/14 = 3,8 бит.

При расчете среднего количества информации в соответствии с (5.10) имеем:

I _ср = -(1/14*log₂(1/14))*14 = 3,8 бит.

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

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

У

(5.12)

сложним задачу. Пусть сообщение – набор длиной N символов русского алфавита. Пусть опыт состоит в появлении той или иной буквы исходного алфавита в j-той позиции сообщения. Вероятности (или частоты) исходов известны (см. табл. 4.6): p_i – вероятность появления символа i. Тогда вероятность p самого сообщения является функцией от вероятностей появления конкретных символов в сообщении и рассчитывается по формуле:

где p_ij – вероятность появления символа в j-той позиции (численно равна вероятности p_i).

Тогда количество информации в сообщении с учетом составляющих его символов можно рассчитать по формуле (5.9), если вероятность сообщения рассчитана по формуле (5.12).

Пример 5.11. Рассчитать количество информации в определении информатики под номером 13 из прил. 1, если вероятности составляющих его символов приведены в табл. 4.6.

Имеем N = 48 – количество символов в сообщении, число символов с их вероятностями (выборка из табл. 4.6) - в табл. 5.1.

Таблица 5.1

символы	число символов в сообщении	вероятность одного символа (из табл. 4.6)
а	3	0,062
в	1	0,038
е	3	0,072
з	2	0,016
и	4	0,062
к	1	0,028
м	2	0,026
н	5	0,053
о	7	0,09
п	1	0,023
р	3	0,04
с	3	0,045
т	2	0,053
у	1	0,021
ф	1	0,001
х	1	0,009
ц	2	0,004
ч	1	0,012
ы	1	0,016
точка и пробелы	4	0,175

В соответствии с (5.12) вероятность p сообщения – определения информатики 13 из прил. 1 – имеет значение:

p = (0,062*3)*(0,038*1)*(0,072*3)*(0,016*2)*(0,062*4)*(0,028*1)*(0,026*2)*

(0,053*5)*(0,09*7)*(0,023*1)*(0,04*3)*(0,045*3)*(0,053*2)*(0,021*1)*(0,001*1)*

(0,009*1)*(0,004*2)*(0,012*1)*(0,016*1)*(0,175*4) = 24*10^-27.

Тогда в соответствии с (5.9) количество информации в данном сообщении:

I = -log₂(24*10^-27) = 85 бит.