Формулы Хартли, Шеннона.

В 1928 г. американский инженер Р. Хартли предложил научный подход к оценке сообщений. Предложенная им формула имела следующий вид:

I = log₂ K

где К - количество равновероятных событий; I - количество бит в сообщении, такое, что любое из К событий произошло. Тогда K=2^I.

Иногда формулу Хартли записывают так:

I = log₂ K = log₂ (1 / р) = - log₂ р

т. к. каждое из К событий имеет равновероятный исход р = 1 / К, то К = 1 / р.

   Задача.

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

   Решение.

   Такое сообщение содержит I = log₂ 3 = 1,585 бита информации.

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

   "Однажды в детстве я уронил бутерброд. Глядя, как я виновато вытираю масляное пятно, оставшееся на полу, старший брат успокоил меня:

   -    не горюй, это сработал закон бутерброда.

   -    Что еще за закон такой? - спросил я.

   -    Закон, который гласит: "Бутерброд всегда падает маслом вниз". Впрочем, это шутка, - продолжал брат. - Никакого закона нет. Просто бутерброд действительно ведет себя довольно странно: большей частью масло оказывается внизу.

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

   Проверили. Из десяти раз восемь бутерброд упал маслом вниз.

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

   Наши опыты прервала мать…"

   ( Отрывок из книги "Секрет великих полководцев", В.Абчук).

   В 1948 г. американский инженер и математик К. Шеннон предложил формулу для вычисления количества информации для событий с различными вероятностями.

Если I - количество информации,

         К - количество возможных событий,

         р_i - вероятности отдельных событий,

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

I = - Sum р_i log₂ р_i,

где i принимает значения от 1 до К.

   Формулу Хартли теперь можно рассматривать как частный случай формулы Шеннона:

I = - Sum 1 / К log₂ (1 / К) = I = log₂ К.

   При равновероятных событиях получаемое количество информации максимально.

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

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

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

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

            4 = 2^I, т.е. I = 2 бит.

   Каждая буква русского алфавита (если считать, что е=ё) несет информацию 5 бит (32 = 2^I).

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

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

Пример 1. Использование формулы  Хартли  для вычисления количества информации.  Сколько бит информации несет сообщение о том, что

         поезд прибывает на один из 8 путей?                                

Формула Хартли:  I = log₂N,

где N – число равновероятностных исходов события, о    котором речь идет в сообщении,

 I  – количество информации в сообщении.

   I = log₂8 =  3(бит) Ответ: 3 бита.

Модифицированная формула Хартли для неравновероятностных событий. Так как наступление каждого из N возможных событий имеет одинаковую вероятность

 p = 1 / N, то N = 1 / p и формула имеет вид

I = log₂N= log₂ (1/p) = - log₂ p

Количественная зависимость между вероятностью события (p) и количеством информации в сообщении о нем (I) выражается формулой:

I = log₂(1/p)

Вероятность события вычисляется по формуле  p=K/N, K – величина, показывающая, сколько раз произошло интересующее нас событие; N – общее число возможных исходов, событий. Если вероятность уменьшается, то количество информации увеличивается.

Пример 2. В классе 30 человек. За контрольную работу по математике получено 6 пятерок, 15 четверок, 8 троек и 1 двойка. Сколько бит информации несет сообщение о том, что Иванов получил четверку?

Ответ:1 бит.

Использование формулы  Шеннона. Общий случай вычисления количества информации в сообщении об одном из N, но уже неравновероятных событий. Этот подход был предложен К.Шенноном в 1948 году.

Основные информационные единицы:

I_ср = -   
 

Значение  I_ср достигает максимума при равновероятных событиях, то есть при равенстве всех p_i                             p_i = 1 / N.

В этом случае формула Шеннона превращается в формулу Хартли.

Пример 3. Сколько бит информации несет случайно сгенерированное сообщение «фара», если в среднем на каждую тысячу букв в русских текстах буква «а» встречается 200 раз, буква «ф» - 2 раза, буква «р» - 40 раз.

Будем считать, что вероятность появления символа в сообщении совпадает с  частотой  его появления в текстах. Поэтому буква «а» встречается со средней  частотой 200/1000=0,2; Вероятность появления буквы “а” в тексте (p_a)можем считать приблизительно равной 0,2;

 буква «ф» встречается с частотой 2/1000=0,002; буква «р» - с частотой 40/1000=0,04;  

Аналогично, p_р = 0,04, p_ф = 0,002. Далее поступаем согласно К.Шеннону. Берем двоичный логарифм от величины 0,2 и называем то, что получилось количеством информации, которую переносит одна-единственная буква “а” в рассматриваемом тексте. Точно такую же операцию проделаем для каждой буквы. Тогда количество собственной информации, переносимой одной буквой равно log₂ 1/p_i = - log₂ p_i, Удобнее в качестве меры количества информации пользоваться средним значением количества информации, приходящейся на один символ алфавита

I_ср = -   

Значение  I_ср достигает максимума при равновероятных событиях, то есть при равенстве всех p_i

p_i = 1 / N.

В этом случае формула Шеннона превращается в формулу Хартли.

I = M*I_ср=4*(-(0,002*log₂0,002+0,2* log₂0,2+0,04* log₂0,04+0,2* log₂0,2))=4*(-(0,002*(-8,967)+0,2*(-2,322)+0,04*(-4,644)+0,2*(-2,322)))=4*(-(-0,018-0,46-0,19-0,46))=4*1,1325=4,53

Ответ: 4,53 бита

При составлении таблицы мы должны учитывать:

1.     Ввод данных (что дано в условии).

2.     Подсчет общего количества числа возможных исходов (формула N=K₁+K₂+…+K_i).

3.     Подсчет вероятности каждого события (формула p_i= К_i/N).

4.     Подсчет количества информации о каждом происходящем событии (формула I_i= log₂(1/p_i)).

5.     Подсчет количества информации для событий с различными вероятностями (формула Шеннона).

Ход работы:

1. Сделать табличную модель для вычисления количества информации.

2. Используя табличную модель, сделать вычисления к задаче №2 (рис.3), результат вычисления занести в тетрадь.

Рис. 3

3. Используя таблицу-шаблон, решить задачи №3,4 (рис.4, рис.5), решение оформить в тетради.

Рис. 4

Рис. 5

Задача №2

В классе 30 человек. За контрольную работу по информатике получено 15 пятерок, 6 четверок, 8 троек и 1 двойка. Какое количество информации несет сообщение о том, что Андреев получил пятерку?

Задача№3

В коробке лежат кубики: 10 красных, 8 зеленых, 5 желтых, 12 синих. Вычислите вероятность доставания кубика каждого цвета и количество информации, которое при этом будет получено.

Задача№4

В непрозрачном мешочке хранятся 10 белых, 20 красных, 30 синих и 40 зеленых шариков. Какое количество информации будет содержать зрительное сообщение о цвете вынутого шарика?