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

Своё дальнейшее развитие теория информации получила в работах Клода Шеннона, американского инженера и математика (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) < p(Ω), или 0 < p(A) < 1.

Для событий вводится понятие суммы и произведения.

Сумма событий 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 – число событий.

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

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

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

Рассмотрим алфавит Am состоящий из m символов. Обозначим через pi вероятность (частоту) появления i-ого символа в любой позиции передаваемого сообщения, состоящего из n символов.

Один i – ый символ алфавита несёт количество информации равное -Log2(pi). Перед логарифмом стоит «минус» потому, что количество информации величина неотрицательная, а Log2(x) <0 при 0<x<1.

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

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

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

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

I = n*Log2 (m).

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

В общем случае количество энтропии H произвольной системы X (случайной величины), которая может находиться в m различных состояниях x1, x2, … xm c вероятностями p1, p2, … pm , вычисленное по формуле Шеннона, равно

Напомним, что p1+ p2+ … +pm = 1. Если все pi одинаковы, то все состояния системы X равновероятны; в этом случае pi = 1/m, и формула переходит в формулу Хартли: H(X) = Log2(m).

Замечание.Количество энтропии системы (случайной величины) Х не зависит от того, в каких конкретно состояниях x1, x2, … xm может находиться система, но зависит от числа m этих состояний и от вероятностей p1, p2, … pm , с которыми система может находиться в этих состояниях. Это означает, что две системы, у которых число состояний одинаково, а вероятности этих состояний p1, p2, … pm равны (с точностью до порядка перечисления), имеют равные энтропии.

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

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

Рассмотрим систему, которая может принимать только два состояния x1 и x2 с вероятностями p1 и p2:

X1 X2
P1 P2

Среди всех таких систем с двумя состояниями наибольшая энтропия будет у системы с равновероятными состояниями, т.е. когда p1=p2 =1/2.

 

X1 X2
1/2 1/2

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

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

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

 

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

 

h(x) = -(x*log2(x) + (l-x)*log2(l-x))

 

Область её определения - интервал (0 ;1), Lim h(x) = 0 при х-> 0или х-> 1.

График этой функции представлен на рисунке:

График функции h(x) = -(x*log2(x) + (l-x)*log2(l-x))

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

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

 

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

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

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

3. 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), ()при 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),

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

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

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

На примере разобранной задачи можно пояснить одно из распространённых определений единицы измерения – 1 бит: 1 бит -количество информации, которое уменьшает неопределённость состояния системы в два раза.

Неопределённость дискретной системы зависит от числа её состояний N.

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

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

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

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

Задача 3.Задана функция H(x)= -x*Log2(x) - (1-x)*Log2(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) < H(0.15)=H(0.85)< H(0.2) < H(0.45). É

Задача 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).