Формула шеннона для вычисления количества информации. Формулы хартли и шеннона

Своё дальнейшее развитие теория информации получила в работах Клода Шеннона, американского инженера и математика (1916 – 2001). Шеннон является одним из создателей математической теории информации. Его основные труды посвящены теории релейно-контактных схем, математической теории связи, кибернетике. К. Шеннон изучал вопросы передачи информации в телеграфии, телефонии или радиовещании в виде сигналов электромагнитных колебаний. Одна из задач, которую ставил перед собой К. Шеннон, заключалась в том, чтобы определить систему кодирования, позволяющую оптимизировать скорость и достоверность передачи информации. Так как в годы войны он служил в шифровальном отделе, где занимался разработкой криптографических систем, то это позже помогло ему открыть методы кодирования с коррекцией ошибок. В своих работах 1948-1949 годов К. Шеннон определил количество информации через энтропию - величину, известную в термодинамике и статистической физике как мера разупорядоченности системы, а за единицу количества информации принял то, что впоследствии назвали битом (bit).

Для дальнейшего изложения необходимо использовать некоторые понятия теории вероятности: случайное событие, опыт, вероятность события, случайная величина. В окружающем нас мире происходят различные события, причём мы можем интуитивно, основываясь на опыте, оценивать одни из них как более возможные, чем другие. Случайным называют событие, которое может наступить или не наступить в результате некоторого испытания, опыта или эксперимента. Будем обозначать события заглавными буквами A, B,Cи т.д. Количественная мера возможности наступления некоторого событияAназывается его вероятностью и обозначается какp(A),p– от английского probability. Чем более возможно наступление случайного события, тем больше его вероятность: еслиAболее возможно чемB, то p(A) > p(B). Вводится понятие достоверного события – событие, которое обязательно наступит. Это событие обозначаюти полагают, что его вероятностьp() = 1. Невозможным называют событие, которое никогда не произойдёт. Его обозначаюти полагают, что его вероятностьp() = 0. Для вероятностей всех остальных событий A выполняется неравенствоp() < p(A)

Для событий вводится понятие суммы и произведения. Сумма событий A+B – это событие, которое состоит в наступлении события A или В. Произведение событий A*B состоит в одновременном наступлении события A и B. События AиBнесовместны , если они не могут наступить вместе в результате одного испытания. Вероятность суммы несовместных событий равна сумме их вероятностей. Если А и В несовместные события, то p(A+B) = p(A) + p(B).

События A1, A2, A3, …Anобразуютполную группу , если в результате опыта обязательно наступит хотя бы одно из них. Если события A1, A2, A3, …Anпопарно несовместны и образуют полную группу, то сумма их вероятностей p1+p2+p3+ ….pn=1. Если они при этом ещё и равновероятны, то вероятность каждого равнаp= 1/n, гдеn– число событий.Вероятность события определяется как отношение числа благоприятных событию исходов опыта к общему числу исходов.Частота события – эмпирическое приближение его вероятности. Она вычисляется в результате проведения серии опытов как отношение числа опытов, в которых событие наступило к общему числу опытов. При большом числе опытов (испытаний) частота события стремится к его вероятности.

К. Шеннон, используя подход Р. Хартли, обратил внимание на то, что при передаче словесных сообщений частота (вероятность) использования различных букв алфавита не одинакова: некоторые буквы используются очень часто, другие - редко.

Рассмотрим алфавит A m состоящий изmсимволов. Обозначим черезp i вероятность (частоту) появления i-ого символа в любой позиции передаваемого сообщения, состоящего из n символов. Один i – ый символ алфавита несёт количество информации равное -Log 2 (p i). Перед логарифмом стоит «минус» потому, что количество информации величина неотрицательная, а Log 2 (x) <0 при 0

На месте каждого символа в сообщении может стоять любой символ алфавита A m ; количество информации, приходящееся на один символ сообщения, равно среднему значению информации по всем символам алфавита A m:

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

(3.2)

Если все символы алфавита A m появляются с равной вероятностью, то все p i = p. Так какр i = 1, то p = 1/m.

Формула (3.2) в случае, когда все символы алфавита равновероятны, принимает вид

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

В общем случае количество энтропии Hпроизвольной системы X (случайной величины), которая может находиться в m различных состояниях x 1 ,x 2 , …x m cвероятностями p 1 ,p 2 , …p m , вычисленное по формуле Шеннона, равно

(3.3)

Напомним, что p 1 +p 2 + … +p m = 1. Если все p i одинаковы, то все состояния системы X равновероятны; в этом случае p i = 1/m, и формула (3.3) переходит в формулу Хартли (2.5):H(X) =Log 2 (m).

Замечание. Количество энтропии системы (случайной величины) Х не зависит от того, в каких конкретно состояниях x 1 ,x 2 , …x m может находиться система, но зависит от числаmэтих состояний и от вероятностей p 1 ,p 2 , …p m , с которыми система может находиться в этих состояниях. Это означает, что две системы, у которых число состояний одинаково, а вероятности этих состояний p 1 ,p 2 , …p m равны (с точностью до порядка перечисления), имеют равные энтропии.

Теорема. Максимум энтропии H(X) достигается в том случае, когда все состояния системы равновероятны. Это означает, что

(3.4)

Если система X может находиться только в одном состоянии (m=1), то её энтропия равна нулю. Рассмотрим систему, которая может принимать только два состояния x1 и x2 с вероятностями p1 иp2:

Количество энтропии такой системы равно

H(X) = - (1/2*Log 2 (1/2)+ 1/2*Log 2 (1/2)) = -Log 2 (1/2) = Log 2 (2) = 1

Это количество принимается за единицу измерения энтропии (информации) и называется 1 бит (1 bit).

Рассмотрим функцию

h(x) = -(x*log 2 (x) + (1-x)*log 2 (1-x)). (3.5)

Область её определения – интервал (0 ;1), Limh(x) = 0 приx0 или 1. График этой функции представлен на рисунке:

Рис. 4. График функции (3.5)

Если обозначить x через p 1 , а (1-x) через p 2 , тоp 1 +p 2 =1;p 1 ,p 2 (0;1), h(x) = H(p 1 ,p 2) = - (p 1 *log 2 (p 1) + (p 2)*log 2 (p 2)) – энтропия системы с двумя состояниями; максимум H достигается приp 1 =p 2 = 0.5.

График h(x) можно использовать при решении следующих задач:

Задача 1. Заданы три случайных величины X, Y, Z, каждая из которых принимает по два значения с вероятностями:

P(X=x1) = 0.5; P(X=x2) = 0.5;

P(Y=y1) = 0.2;P(Y=y2) = 0.8;

P(Z=z1) = 0.3; P(Z=z2) = 0.7 .

Запись P(X=x1) = 0.5 означает, что случайная величина X принимает значение x1 с вероятностью 0.5. Требуется расположить энтропии этих систем в порядке возрастания.

Решение. Энтропия H(X) равна 1 и будет наибольшей; энтропия H(Y) равна значению функции h(x), см. (3.5), приx= 0.2, т.е.H(Y)=h(0.2); энтропияH(Z) =h(0.3). По графику h(x) можно определить, что h(0.2) < h(0.3). Следовательно, H(Y) < H(Z) < H(X).

Замечание 1. Энтропия системы тем больше, чем менее отличаются вероятности её состояний друг от друга. На основании этого можно сделать вывод, что H(Y) < H(Z). Например, если для систем X и Y с тремя состояниями заданы вероятности: дляX{0.4; 0.3; 0.3}, дляY{0.1; 0.1; 0.8}, то очевидно, что неопределённость системыXбольше, чем неопределённость системыY: у последней, скорее всего, будет реализовано состояние, вероятность которого равна 0.8 .

Энтропия H(X) характеризует степень неопределённости системы. Чем больше объём полученных о системе сведений, тем больше будет информации о системе, и тем менее неопределённым будет её состояние для получателя информации.

Если энтропия системы после получения информации становится равной нулю, это означает, что неопределённость исчезла, вся энтропия «перешла» в информацию. В этом случае говорят, что была получена полная информацию о системе X.Количество информации, приобретаемое при полном выяснении состояния физической системы, равно энтропии этой системы.

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

I = H1(X) - H2(X), (3.6)

где H1(X) и H2(X) - энтропия системы до и после сообщения, соответственно. Если H2(X) = 0, то мера неопределённости системы равна нулю и была получена полная информация о системе.

Пример. Вы хотите угадать количество очков, которое выпадет на игральном кубике. Вы получили сообщение, что выпало чётное число очков. Какое количество информации содержит это сообщение?

Решение. Энтропия системы «игральный кубик» H1 равна Log 2 6, т.к. кубик может случайным образом принять шестьравновозможных состояний {1, 2, 3, 4, 5, 6}. Полученное сообщение уменьшает число возможных состояний до трёх: {2, 4, 6}, т.е. энтропия системы теперь равна H2= Log 2 3. Приращение энтропии равно количеству полученной информации I = H1 – H2 = Log 2 6 - Log 2 3 = Log 2 2 = 1bit.

На примере разобранной задачи можно пояснить одно из распространённых определений единицы измерения – 1 бит: 1 бит - количество информации, которое уменьшает неопределённость состояния системы в два раза. Неопределённость дискретной системы зависит от числа её состоянийN. Энтропия до получения информацииH1= Log 2 N. Если после получения информации неопределённость уменьшилась в два раза, то это означает, что число состояний стало равнымN/2, а энтропияH2 =Log 2 N/2. Количество полученной информацииI= H1 -H2 =Log 2 N-Log 2 N/2 =Log 2 2 = 1 бит.

Рассмотрим несколько задач на применение формулы Шеннона и Хартли.

Задача 2. Может ли энтропия системы, которая принимает случайным образом одно из 4-х состояний, равняться: а) 3; б) 2.1 в) 1.9 г) 1; д) 0.3? Ответ объяснить.

Решение. Максимально возможное значение энтропия системы с 4-мя состояниями достигает в случае, когда все состояния равновероятны. Это значение по формуле Хартли равноLog 2 4 = 2 бита. Во всех других случаях энтропия системы с 4-мя состояниями будет меньше 2. Следовательно, возможными значениями энтропии из перечисленных выше, могут быть значения 1.9, 1, 0.3.

Задача 3. Задана функцияH(x)= -x*Log 2 (x) - (1-x)*Log 2 (1-x). Расположите в порядке возрастания следующие значения:H(0.9),H(0.85),H(0.45),H(0.2),H(0.15).

Решение. Используем график функции (3.5). Наибольшим значением будет H(0.45), наименьшим значением – H(0.9), затем по возрастанию идут значенияH(0.15) иH(0.85) = H(0.15); H(0.2). Ответ:H(0.9)

Задача 4. По линии связи переданы сообщения:a) «начало_в_10»;b) «лоанча_1_в0». Сравните количество информации в первом и втором сообщении.

Решение. Первое и второе сообщение состоят из одних и тех же символов: второе получено из первого в результате перестановки этих символов. В соответствии с формулой Шеннона эти сообщения содержат одинаковое количество информации. При этом первое сообщение несёт содержательную информацию, а второе – простой набор символов. Однако, в этом случае можно сказать, что второе сообщение является «зашифрованным» вариантом первого, и поэтому количество информации в обоих сообщениях одинаковое.

Задача 5. Получены три различных сообщенияA,B,C:

A= «прибытие в десять часов»;B= «прибытие в десять часов ноль минут»;C= «прибытие ровно в десять часов». Используя энтропийный подход Шеннона, сравните количество информации, содержащееся в этих сообщениях.

Решение. Обозначим количество информации в сообщениях A, B, C черезI(A),I(B),I(C) соответственно. В смысле «содержания» эти сообщения совершенно одинаковы, но одинаковое содержание выражено с помощью разного количества символов. При этом все символы сообщения А содержатся в сообщении B и С, сообщение С = A + «ровно», В = A + «ноль минут»; в соответствии с подходом Шеннона получаем: I(A) < I(C) < I(B).

(Claude Elwood Shannon, 30 апреля 1916 - 24 февраля 2001) - американский математик и электротехник, один из создателей математической теории информации, в значительной мере предопределил своими результатами развитие общей теории дискретных автоматов, которые являются важными составляющими кибернетики. В 1936 году закончил Мичиганский университет. После защиты диссертации (1940) в 1941 году поступил на работу в знаменитые Лаборатории Белла.

С 1956 года преподавал в МТИ.

Большую ценность представляет другая работа - Communication Theory of Secrecy Systems (1949), в которой сформулированы математические основы криптографии.

С 1956 - член Национальной академии наук США и Американской академии искусств и наук

Процесс передачи информации

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

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

Примеры

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

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

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

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

Так, американский инженер Р. Хартли в 1928 году, процесс получения информации рассматривает как выбор одного сообщения из конечного наперед заданного множества из N равновероятных сообщений, а количество информации I, содержащееся в выбранном сообщении, определяет как двоичный логарифм N.

Формула Шеннона

I=- (p1 log2 p1 + p2 log2 p2 + … + pN log2 pN)

где pi - вероятность того, что именно i-е сообщение выделено в наборе из N сообщений.

Легко заметить, что если вероятности p1, …, pN равны, то каждая из них равна 1/N, и формула Шеннона превращается в формулу Хартли.

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

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

В качестве единицы информации условились принять один бит (английский bit - binary, digit - двоичная цифра).

Бит в теории информации - количество информации, необходимое для различения двух равновероятных сообщений.

А в вычислительной технике битом называют наименьшую;порцию; памяти, необходимую для хранения одного из двух знаков «0» и «1», используемых для внутримашинного представления данных и команд.

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

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

где I - количество информации;

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

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

Для частного, но широко распространенного и рассмотренного выше случая, когда события равновероятны (р; = 1 / N), величину количества информации I можно рассчитать по формуле:

Задание «Бросание пирамидки». Определить количество информации, которое мы получаем в результате бросания несимметричной и симметричной пирамидок.

При бросании несимметричной четырехгранной пирамидки вероятности отдельных событий равны:

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

При бросании симметричной четырехгранной пирамидки вероятности отдельных событий равны между собой:

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

Таким образом, при бросании симметричной пирамидки, когда события равновероятны, мы получим большее количество информации (2 бита), чем при бросании несимметричной пирамидки, когда события неравновероятны (1,75 бита).

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

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

Количество информации, которое несет знак, зависит от вероятности его получения. Если получатель заранее точно знает, какой знак придет, то полученное количество информации будет равно 0. Наоборот, чем менее вероятно получение знака, тем больше его информационная емкость.

В русской письменной речи частота использования букв в тексте различна, так, в среднем на 1000 знаков осмысленного текста приходится 200 букв «а» и в сто раз меньшее количество буквы «ф» (всего 2). Таким образом, с точки зрения теории информации информационная емкость знаков русского алфавита различна (у буквы «а» она наименьшая, а у буквы «ф» - наибольшая).

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

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

Выбор правильной стратегии в игре «Угадай число». На получении максимального количества информации строится выбор правильной стратегии в игре «Угадай число», в которой первый участник загадывает целое число (например, 3) из заданного интервала (например, от 1 до 16), а второй должен «угадать» задуманное число.

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

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

Как видно из табл. 2.4, угадывание числа 3 произошло за четыре шага, на каждом из которых неопределенность знаний второго участника уменьшалась в два раза за счет получения сообщений от первого участника, содержащих 1 бит информации. Таким образом, количество информации, необходимое для отгадывания одного из 16 чисел, составило 4 бита.

Таблица 2.4

Информационная модель игры «Угадай число»

Практическое задание «Определение количества информации».

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

Так как количество шариков различных цветов неодинаково, то вероятности зрительных сообщений о цвете вынутого из мешочка шарика также различаются и равны количеству шариков данного цвета, деленному на общее количество шариков:

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

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

Контрольные вопросы

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

Задания для самостоятельного выполнения

• 2.12. Какое количество вопросов достаточно задать вашему собеседнику, чтобы наверняка определить:
  • ? день недели, в котором он родился?
  • ? месяц, в котором он родился?
  • ? число, в которое он родился?

Практикум к главе 2

Практическая работа 2.1. Перевод единиц измерения количества информации с помощью калькулятора

Практическая работа 2.2. Определение количества информации по формуле Шеннона с помощью калькулятора

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

Формула Хартли:

где К - количество информации, N -число равновероятных событий.

Формула Хартли может быть записана и так: N=2k

Так как наступление каждого из N событий имеет одинаковую вероятность P, то:

где P- вероятность наступления события.

Тогда, формулу можно записать иначе:

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

Формула Шеннона:

K = - (p1 *log2 p1+ p2 *log 2p 2 + p 3 *log 2p 3 +…+ pi * log2 pi),

где pi вероятность того, что именно i-е сообщение выделено в наборе из N сообщений.

Также эту формулу записывают:

Современная наука о свойствах информации и закономерностях информационных процессов называется теорией информации. Содержание понятия "информация" можно раскрыть на примере двух исторически первых подходов к измерению количества информации: подходов Хартли и Шеннона: первый из них основан на теории множеств и комбинаторике, а второй - на теории вероятностей.

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

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

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

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

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

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

Объемный подход.

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

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

Для удобства использования введены и более крупные, чем бит, единицы количества информации. Так, двоичное слово из восьми знаков содержит один байт информации, 1024 байта образуют килобайт (кбайт), 1024 килобайта - мегабайт (Мбайт), а 1024 мегабайта - гигабайт (Гбайт).

Энтропийный (вероятностный) подход.

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

Количество информации в сообщении определяется тем, насколько уменьшилась эта мера после получения сообщения: чем больше энтропия системы, тем больше степень её неопределённости. Поступающее сообщение полностью или частично снимает эту неопределённость, следовательно, количество информации можно измерять тем, насколько понизилась энтропия системы после получения сообщения. За меру количества информации принимается та же энтропия, но с обратным знаком.

Подход Р. Хартли основан на фундаментальных теоретико-множественных, по существу комбинаторных основаниях, а также нескольких интуитивно ясных и вполне очевидных предположениях.

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

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

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

Чем больше элементов в множестве, тем больше неопределенность выбора, тем больше информации.

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

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

Клод Шеннон предположил, что прирост информации равен утраченной неопределённости, и задал требования к её измерению:

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

Поэтому функция энтропии должна удовлетворять условиям:

определена и непрерывна для всех,

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

Для целых положительных, должно выполняться следующее неравенство:

Для целых положительных, где, должно выполняться равенство:

информационный пропускной энтропийный

Шеннон определил, что измерение энтропии, применяемое к источнику информации, может определить требования к минимальной пропускной способности канала, требуемой для надёжной передачи информации в виде закодированных двоичных чисел. Для вывода формулы Шеннона необходимо вычислить математическое ожидание «количества информации», содержащегося в цифре из источника информации. Мера энтропии Шеннона выражает неуверенность реализации случайной переменной. Таким образом, энтропия является разницей между информацией, содержащейся в сообщении, и той частью информации, которая точно известна (или хорошо предсказуема) в сообщении. Примером этого является избыточность языка -- имеются явные статистические закономерности в появлении букв, пар последовательных букв, троек и т.д.

Американский инженер Р. Хартли в 1928 г. процесс получения информации рассматривал как выбор одного сообщения из конечного наперёд заданного множества из N равновероятных сообщений, а количество информации I, содержащееся в выбранном сообщении, определял как двоичный логарифм N.

Формула Хартли: I = log 2 N или N = 2 i

Допустим, нужно угадать одно число из набора чисел от единицы до ста. По формуле Хартли можно вычислить, какое количество информации для этого требуется: I = log 2 100 > 6,644. Таким образом, сообщение о верно угаданном числе содержит количество информации, приблизительно равное 6,644 единицы информации.

Приведем другие примеры равновероятных сообщений :

1. при бросании монеты: «выпала решка», «выпал орел»;

2. на странице книги: «количество букв чётное», «количество букв нечётное».

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

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

Формула Шеннона: I = - (p 1 log 2 p 1 + p 2 log 2 p 2 + . . . + p N log 2 p N),

где p i - вероятность того, что именно i-е сообщение выделено в наборе из N сообщений.

Легко заметить, что если вероятности p 1 , ..., p N равны, то каждая из них равна 1 / N, и формула Шеннона превращается в формулу Хартли.

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

В качестве единицы информации Клод Шеннон предложил принять один бит (англ. bit - binary digit - двоичная цифра).

Бит в теории информации - количество информации, необходимое для различения двух равновероятных сообщений (типа «орел»-«решка», «чет»-«нечет» и т.п.).

В вычислительной технике битом называют наименьшую «порцию» памяти компьютера, необходимую для хранения одного из двух знаков «0» и «1», используемых для внутримашинного представления данных и команд.

Бит - слишком мелкая единица измерения. На практике чаще применяется более крупная единица - байт , равная восьми битам. Именно восемь битов требуется для того, чтобы закодировать любой из 256 символов алфавита клавиатуры компьютера (256=2 8).

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

1 Килобайт (Кбайт) = 1024 байт = 210 байт,

1 Мегабайт (Мбайт) = 1024 Кбайт = 220 байт,

1 Гигабайт (Гбайт) = 1024 Мбайт = 230 байт.

В последнее время в связи с увеличением объёмов обрабатываемой информации входят в употребление такие производные единицы, как:

1 Терабайт (Тбайт) = 1024 Гбайт = 240 байт,

1 Петабайт (Пбайт) = 1024 Тбайт = 250 байт.

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

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

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

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

В компьютере информация представлена в двоичном коде или на машинном языке, алфавит которого состоит из двух цифр (0 и 1). Эти цифры можно рассматривать как два равновероятных состояния. При записи одного двоичного разряда реализуется выбор одного из двух возможных состояний (одной из двух цифр) и, следовательно, один двоичный разряд несет количество информации в 1 бит. Два двоичных разряда несут информацию 2 бита, три разряда – 3 бита и т.д.

Поставим теперь обратную задачу и определим: «Какое количество различных двоичных чисел N можно записать с помощью I двоичных разрядов?» С помощью одного двоичного разряда можно записать 2 различных числа (N=2=2 1), с помощью двух двоичных разрядов можно записать четыре двоичных числа (N=4=2 2), с помощью трех двоичных разрядов можно записать восемь двоичных чисел (N=8=2 3) и т.д.

В общем случае количество различных двоичных чисел можно определить по формуле

N – количество возможных событий (равновероятных)!!!;

В математике существует функция, с помощью которой решается показательное уравнение, эта функция называется логарифмом. Решение такого уравнения имеет вид:

Если события равновероятны , то количество информации определяется по данной формуле.

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

,

где I – количество информации;

N – количество возможных событий;

P i – вероятность отдельных событий.

Пример 3.4

В барабане для розыгрыша лотереи находится 32 шара. Сколько информации содержит сообщение о первом выпавшем номере (например, выпал номер 15)?

Решение:

Поскольку вытаскивание любого из 32 шаров равновероятно, то количество информации об одном выпавшем номере находится из уравнения: 2 I =32.

Но 32=2 5 . Следовательно, I=5 бит. Очевидно, ответ не зависит от того, какой именно выпал номер.

Пример 3.5

Какое количество вопросов достаточно задать вашему собеседнику, чтобы наверняка определить месяц, в котором он родился?

Решение:

Будем рассматривать 12 месяцев как 12 возможных событий. Если спрашивать о конкретном месяце рождения, то, возможно, придется задать 11 вопросов (если на 11 первых вопросов был получен отрицательный ответ, то 12-й задавать не обязательно, так как он и будет правильным).

Правильнее задавать «двоичные» вопросы, то есть вопросы, на которые можно ответить только «да» или «нет». Например, «Вы родились во второй половине года?». Каждый такой вопрос разбивает множество вариантов на два подмножества: одно соответствует ответу «да», а другое – ответу «нет».

Правильная стратегия состоит в том, что вопросы нужно задавать так, чтобы количество возможных вариантов каждый раз уменьшалось вдвое. Тогда количество возможных событий в каждом из полученных подмножеств будет одинаково и их отгадывание равновероятно. В этом случае на каждом шаге ответ («да» или «нет») будет нести максимальное количество информации (1 бит).

По формуле 2 и с помощью калькулятора получаем:

бита.

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

Пример 3.6

После экзамена по информатике, который сдавали ваши друзья, объявляются оценки («2», «3», «4» или «5»). Какое количество информации будет нести сообщение об оценке учащегося А, который выучил лишь половину билетов, и сообщение об оценке учащегося В, который выучил все билеты.

Решение:

Опыт показывает, что для учащегося А все четыре оценки (события) равновероятны и тогда количество информации, которое несет сообщение об оценке, можно вычислить по формуле (1):

На основании опыта можно также предположить, что для учащегося В наиболее вероятной оценкой является «5» (p 1 =1/2), вероятность оценки «4» в два раза меньше (p 2 =1/4), а вероятности оценок «2» и «3» еще в два раза меньше (p 3 =p 4 =1/8). Так как события неравновероятны, воспользуемся для подсчета количества информации в сообщении формулой 2:

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

Пример 3.7

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

Решение:

Так как количество шариков разного цвета неодинаково, то вероятности зрительных сообщений о цвете вынутого из мешочка шарика также различаются и равны количеству шариков данного цвета деленному на общее количество шариков:

P б =0,1; P к =0,2; P с =0,3; P з =0,4.

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

Для вычисления этого выражения, содержащего логарифмы можно воспользоваться калькулятором. I»1,85 бита.

Пример 3.8

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

I=log 2 256=8 бит=1 байт

Следовательно, для двоичного кодирования 1 символа необходим 1 байт информации или 8 двоичных разрядов.

Какое количество информации содержится, к примеру, в тексте романа «Война и мир», во фресках Рафаэля или в генетическом коде человека? Ответа на эти вопросы наука не даёт и, по всей вероятности, даст не скоро. А возможно ли объективно измерить количество информации? Важнейшим результатом теории информации является следующий вывод:«В определенных, весьма широких условиях можно пренебречь качественными особенностями информации, выразить её количество числом, а также сравнить количество информации, содержащейся в различных группах данных».

В настоящее время получили распространение подходы к определению понятия «количество информации», основанные на том, что информацию, содержащуюся в сообщении, можно нестрого трактовать в смысле её новизны или, иначе, уменьшения неопределённости наших знаний об объекте. Эти подходы используют математические понятия вероятности и логарифма.