В основе нашего мира лежат три составляющие: вещество, энергия и информация. Как много в мире вещества, энергии и информации? Можно ли их измерить и как именно? Нам известны способы измерения количества вещества и энергии. Но как быть с информацией? Можно ли ее измерить?
Ранее уже отмечалось, что существует несколько подходов к оценке количества информации. Сейчас мы более подробно остановимся на одном из них.
Любое сообщение будет являться информативным, если оно пополняет знания человека, т.е. уменьшает неопределенность его знаний.
Равновероятные события
Пример 1
Например, при подбрасывании монеты мы пытаемся угадать, какой стороной она упадет. Возможен один из вариантов исхода: монета окажется в положении «орел» или «решка». Каждое из этих двух событий окажется равновероятным, т. е. ни одно из них не имеет преимущества перед другим. Перед подбрасыванием монеты никто не может знать, как она упадет, т.е. существует неопределенность знания. После же наступления события, наоборот, присутствует полная определенность, так как бросающий получает зрительное сообщение о положении монеты, которое, в свою очередь, уменьшает неопределенность его знания в два раза, поскольку из двух равновероятных событий произошло одно.
Пример 2
Другим примером является ситуация с шестигранным кубиком, т.е. перед броском никто не может знать, какой стороной он упадет. В данном случае присутствует возможность получить один результат из шести равновероятных. Таким образом, до броска неопределенность знаний бросающего будет равна 6, после же броска, она уменьшится ровно в 6 раз, поскольку именно 6 равновероятных событий может произойти.
Пример 3
Рассмотрим пример, где для экзамена приготовили 40 билетов. Вероятность событий, которые произойдут при вытягивании билета, будет равна 40. Причем эти события будут равновероятны. При этом неопределенность знаний студента перед выбором билета, будет равна 40. Соответственно неопределенность знания после того как студент взял билет уменьшится в 40 раз. Зададимся вопросом, зависит ли этот показатель от номера вытянутого билета. Нет, поскольку события равновероятны.
Проанализировав все рассмотренные выше примеры, можно прийти к выводу, что чем больше исходное число возможных равновероятных событий, тем в большее количество раз уменьшается неопределенность знаний, и тем большее количество информации будет содержаться в сообщении о результатах опыта.
Неравновероятные события
Рассмотрим в качестве примера разговорные языки. Обратимся к фактам доказанных исследований, которые показывают, что во всех разговорных языках одни буквы встречаются гораздо чаще, чем другие. Результаты исследований подтверждают, что на $1000$ букв в разных разговорных языках приходится различное число повторений. В качестве примеров в таблице приведены некоторые буквы в русском и английском языках:
Рисунок 1.
Помимо этого, вероятность появления отдельных букв будет зависеть от того, какие буквы используются перед ними. Так, в русском языке после гласной никогда не может стоять мягкий знак, а также в словах не используются четыре гласные подряд и т.д. Разговорные языки имеют, как правило, свои особенности и закономерности. Именно поэтому количество информации, содержащееся в сообщениях любого разговорного языка, неприемлемо оценивать с помощью формулы Хартли, которая используется в алфавитном подходе к оценке информации и характерна для примеров с равновероятными событиями (примеры с монетой и кубиком).
Как определить, какое количество информации содержит, например, текст романа "Война и мир", или фрески и полотна великих итальянских художников, или генетический код человека? Ответы на эти вопросы и подобные им науке пока не известны и, по всей вероятности, еще не скоро будут известны. Однако всех интересует, возможно ли объективно оценить количество информации? К задаче подобного рода можно отнести следующий пример.
Как выяснить, являются ли равновероятными сообщения "первой выйдет из здания женщина" и "первым выйдет из здания мужчина"? Однозначного ответа на этот вопрос нет. Все будет зависеть от того, о каком именно здании идет речь. Если это, например, здание гинекологической клиники, то вероятность выйти первой у женщины очень высока, если это военная казарма, то вероятность выйти первым для мужчины будет выше, чем для женщины, а вот если это здание кинотеатра, то вероятности выйти первыми для мужчины и женщины будут одинаковыми.
Оценка количества информации. Формула Шеннона
Для решения задач подобного рода используется общая оценка количества информации, предложенная американским учёным Клодом Шенноном в 1948г. Созданная им формула определения количества информации способна учитывать возможную неодинаковую вероятность сообщений, содержащихся в наборе. Шеннон при создании формулы использовал применяемую в математике и гидродинамике вероятностную меру неопределенности (называемую энтропией) для того, чтобы в полной мере оценить состояние изучаемой системы и получить максимально возможную информацию о протекающих в этой системе процессах. Эта оценка количества информации, по существу, является вероятностной мерой , и, как оценка неопределенности, она отражает способность какого-либо источника проявлять все новые и новые состояния и таким образом отдавать информацию.
Определение 1
Шеннон определил энтропию как среднюю логарифмическую функцию множества вероятностей возможных состояний системы (возможных исходов опыта). Для расчета энтропии Шеннон предложил следующее уравнение:
$H= -(p_1log_2p_1+p_2log_2p_2+. . .+p_Nlog_2p_N)$,
где $p_i$ - вероятность появления $i$-того события в наборе из $N$ событий.
Тогда количество информации, полученное в результате опыта, будет не что иное, как разность между энтропией системы до ($H_0$) и после ($H_1$) опыта:
причем если неопределенность в результате опыта полностью исключается, то имеем:
$I=\Sigma (p_ilog_2p_i), i=1,\dots ,N$.
Рассмотрим пример, подтверждающий использование данной теории Шеннона на практике.
Пример 4
В озере обитают пескари и окуни. Подсчитано количество особей в каждой популяции (пескарей - $1500$, а окуней - $500$). Необходимо определить, сколько информации содержится в сообщениях о том, что рыбак выловил пескаря, окуня, вообще рыбу?
Решение. События улова пескаря или окуня не являются равновероятными, поскольку окуней в озере обитает намного меньше, чем пескарей.
Общее количество пескарей и окуней, обитающих в озере:
$1500 + 500 = 2000$.
Определим вероятность улова пескаря:
$p_1= \frac{1500}{2000} = 0,75$,
Определим вероятность улова окуня:
$p_2 - \frac{500}{2000} = 0,25$.
$I_1=log_2(\frac{1}{p_1}), I_1=log_2(\frac{1}{p_2})$,
где $I_1$ и $I_2$ - вероятности улова пескаря и окуня соответственно.
Количество информации, содержащейся в сообщении об улове пескаря:
$I_1 = log_2(\frac{1}{0,75}) » 0,43$ бит,
Количество информации, содержащейся в сообщении об улове окуня:
$I_2=log_2(\frac{1}{0,25}) » 2$ бит.
Количество информации, содержащейся в сообщении об улове рыбы (карася или окуня) рассчитывается по формуле Шеннона:
$I = - p_1log_2p_1 - p_2log_2p_2$
$I = -0,75 \cdot log_20,75- 0,25 \cdot log_20,25=-0,75 \cdot (\frac{log0,75}{log2})-0,25 \cdot(\frac{log0,25}{log2}) =0,604 бит » 0.6$ бит.
Ответ: в сообщении содержится $0,6$ бит информации
(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», используемых для внутримашинного представления данных и команд.
Наиболее широкое распространение при определении среднего количества информации, которое содержится в сообщениях от источников самой разной природы, получил подход. К Шеннона. Рассмотрим следующую ситуацию.
Источник передает элементарные сигналы k
различных типов. Проследим за достаточно длинным отрезком сообщения. Пусть в нем имеется N
1 сигналов первого типа, N
2 сигналов второго типа, ..., N
k
сигналов k
-го типа, причем N
1 + N
2 + ... + N
k
= N
– общее число сигналов в наблюдаемом отрезке, f
1, f
2, ..., f
k
– частоты соответствующих сигналов. При возрастании длины отрезка сообщения каждая из частот стремится к фиксированному пределу, т.е.
lim f
i
= p
i
, (i
= 1, 2, ..., k
),
где р
i
можно считать вероятностью сигнала. Предположим, получен сигнал i
-го типа с вероятностью р
i
, содержащий – log p
i
единиц информации. В рассматриваемом отрезке i
-й сигнал встретится примерно Np
i
раз (будем считать, что N
достаточно велико), и общая информация, доставленная сигналами этого типа, будет равна произведению Np
i
log р
i
. То же относится к сигналам любого другого типа, поэтому полное количество информации, доставленное отрезком из N
сигналов, будет примерно равно
Чтобы определить среднее количество информации, приходящееся на один сигнал, т.е. удельную информативность источника, нужно это число разделить на N
. При неограниченном росте приблизительное равенство перейдет в точное. В результате будет получено асимптотическое соотношение – формула Шеннона
В последнее время она стала не менее распространенной, чем знаменитая формула Эйнштейна Е
= mc
2 . Оказалось, что формула, предложенная Хартли, представляет собой частный случай более общей формулы Шеннона. Если в формуле Шеннона принять, что
р
1 = p
2 = ... = р
i
= ... =p
N
= 1/N
, то
Знак минус в формуле Шеннона не означает, что количество информации в сообщении – отрицательная величина. Объясняется это тем, что вероятность р
, согласно определению, меньше единицы, но больше нуля. Так как логарифм числа, меньшего единицы, т.е. log p
i
– величина отрицательная, то произведение вероятности на логарифм числа будет положительным.
Кроме этой формулы, Шенноном была предложена абстрактная схема связи, состоящая из пяти элементов (источника информации, передатчика, линии связи, приемника и адресата), и сформулированы теоремы о пропускной способности, помехоустойчивости, кодировании и т.д.
В результате развития теории информации и ее приложений идеи Шеннона быстро распространяли свое влияние на самые различные области знаний. Было замечено, что формула Шеннона очень похожа на используемую в физике формулу энтропии, выведенную Больцманом. Энтропия обозначает степень неупорядоченности статистических форм движения молекул. Энтропия максимальна при равновероятном распределении параметров движения молекул (направлении, скорости и пространственном положении). Значение энтропии уменьшается, если движение молекул упорядочить. По мере увеличения упорядоченности движения энтропия стремится к нулю (например, когда возможно только одно значение и направление скорости). При составлении какого-либо сообщения (текста) с помощью энтропии можно характеризовать степень неупорядоченности движения (чередования) символов. Текст с максимальной энтропией – это текст с равновероятным распределением всех букв алфавита, т.е. с бессмысленным чередованием букв, например: ЙХЗЦЗЦЩУЩУШК ШГЕНЕЭФЖЫЫДВЛВЛОАРАПАЯЕЯЮЧБ СБСЬМ. Если при составлении текста учтена реальная вероятность букв, то в получаемых таким образом «фразах» будет наблюдаться определенная упорядоченность движения букв, регламентируемая частотой их появления: ЕЫТ ЦИЯЬА ОКРВ ОДНТ ЬЧЕ МЛОЦК ЗЬЯ ЕНВ ТША.
При учете вероятностей четырехбуквенных сочетаний текст становится настолько упорядоченным, что по некоторым формальным признакам приближается к осмысленному: ВЕСЕЛ ВРАТЬСЯ НЕ СУХОМ И НЕПО И КОРКО. Причиной такой упорядоченности в данном случае является информация о статистических закономерностях текстов. В осмысленных текстах упорядоченность, естественно, еще выше. Так, в фразе ПРИШЛ... ВЕСНА мы имеем еще больше информации о движении (чередовании) букв. Таким образом, от текста к тексту увеличиваются упорядоченность и информация, которой мы располагаем о тексте, а энтропия (мера неупорядоченности) уменьшается.
Используя различие формул количества информации Шеннона и энтропии Больцмана (разные знаки), Л. Бриллюэн охарактеризовал информацию как отрицательную энтропию, или негэнтропию
.
Так как энтропия является мерой неупорядоченности, то информация может быть определена как мера упорядоченности материальных систем
.
В связи с тем, что внешний вид формул совпадает, можно предположить, что понятие информация ничего не добавляет к понятию энтропии. Однако это не так. Если понятие энтропии применялось ранее только для систем, стремящихся к термодинамическому равновесию, т.е. к максимальному беспорядку в движении ее составляющих, к увеличению энтропии, то понятие информации обратило внимание и на те системы, которые не увеличивают энтропию, а наоборот, находясь в состоянии с небольшими значениями энтропии, стремятся к ее дальнейшему уменьшению.
Трудно переоценить значение идей теории информации в развитии самых разнообразных научных областей.
Однако, по мнению К. Шеннона, все нерешенные проблемы не могут быть решены при помощи таких магических слов, как «информация», «энтропия», «избыточность».
Теория информации основана на вероятностных, статистических закономерностях явлений. Она дает полезный, но не универсальный аппарат. Поэтому множество ситуаций не укладываются в информационную модель Шеннона. Не всегда представляется возможным заранее установить перечень всех состояний системы и вычислить их вероятности. Кроме того, в теории информации рассматривается только формальная сторона сообщения, в то время как смысл его остается в стороне. Например, система радиолокационных станций ведет наблюдение за воздушным пространством с целью обнаружения самолета противника Система S
, за которой ведется наблюдение, может быть в одном из двух состояний x
1 – противник есть, x
2 – противника нет. Важность первого сообщения нельзя оценить с помощью вероятностного подхода. Этот подход и основанная на нем мера количества информации выражают, прежде всего, «структурно-синтаксическую» сторону ее передачи, т.е. выражают отношения сигналов. Однако понятия «вероятность», «неопределенность», с которыми связано понятие информации, предполагают процесс выбора. Этот процесс может быть осуществлен только при наличии множества возможностей. Без этого условия, как можно предположить, передача информации невозможна.
Своё дальнейшее развитие теория информации получила в работах Клода Шеннона, американского инженера и математика (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 – число событий.
Вероятность события определяется как отношение числа благоприятных событию исходов опыта к общему числу исходов.
Частота события – эмпирическое приближение его вероятности. Она вычисляется в результате проведения серии опытов как отношение числа опытов, в которых событие наступило к общему числу опытов. При большом числе опытов (испытаний) частота события стремится к его вероятности.
К. Шеннон, используя подход Р. Хартли, обратил внимание на то, что при передаче словесных сообщений частота (вероятность) использования различных букв алфавита не одинакова: некоторые буквы используются очень часто, другие - редко.
Рассмотрим алфавит A m состоящий из m символов. Обозначим через p i вероятность (частоту) появления i -ого символа в любой позиции передаваемого сообщения, состоящего из n символов.
Один i
– ый символ алфавита несёт количество информации равное -Log 2 (p i)
. Перед логарифмом стоит «минус» потому, что количество информации величина неотрицательная, а Log 2 (x) <0
при 0
На месте каждого символа в сообщении может стоять любой символ алфавита A m ; количество информации, приходящееся на один символ сообщения, равно среднему значению информации по всем символам алфавита A m :
Общее количество информации, содержащееся в сообщении из n символов равно:
Если все символы алфавита A m появляются с равной вероятностью, то все p i = p . Так как ∑р i = 1 , то p = 1/m.
Формула в случае, когда все символы алфавита равновероятны, принимает вид
I = n *Log 2 (m ).
Вывод : формула Шеннона в случае, когда все символы алфавита равновероятны, переходит в формулу Хартли.
В общем случае количество энтропии H произвольной системы X (случайной величины), которая может находиться в m различных состояниях x 1 , x 2 , … x m c вероятностями p 1 , p 2 , … p m , вычисленное по формуле Шеннона, равно
Напомним, что p 1 + p 2 + … +p m = 1. Если все p i одинаковы, то все состояния системы X равновероятны; в этом случае p i = 1/m , и формула переходит в формулу Хартли: 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) достигается в том случае, когда все состояния системы равновероятны. Это означает, что
Если система 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) + (l-x)*log 2 (l-x))
Область её определения - интервал (0 ;1) , Lim h(x) = 0 при х -> 0или х -> 1.
График этой функции представлен на рисунке:
График функции h(x) = -(x*log 2 (x) + (l-x)*log 2 (l-x))
Если обозначить 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, каждая из которых принимает по два значения с вероятностями:
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 равна 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 = 1 bit.
На примере разобранной задачи можно пояснить одно из распространённых определений единицы измерения – 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) < 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).
В общем случае , энтропия H и количество получаемой в результате снятия неопределенности информации I зависят от исходного количества рассматриваемых вариантов N и априорных вероятностей реализации каждого из них P : {p 0 , p 1 , …p N -1 } , т.е. H =F (N , P ) . Расчет энтропии в этом случае производится по формуле Шеннона , предложенной им в 1948 году в статье "Математическая теория связи".
В частном случае , когда все варианты равновероятны , остается зависимость только от количества рассматриваемых вариантов, т.е. H =F (N ) . В этом случае формула Шеннона значительно упрощается и совпадает с формулой Хартли , которая впервые была предложена американским инженером Ральфом Хартли в 1928 году, т.е. не 20 лет раньше.
Формула Шеннона имеет следующий вид:
Знак минус в формуле (1) не означает, что энтропия – отрицательная величина. Объясняется это тем, что p i £ 1 по определению, а логарифм числа меньшего единицы - величина отрицательная. По свойству логарифма , поэтому эту формулу можно записать и во втором варианте, без минуса перед знаком суммы.
Интерпретируется как частное количество информации , получаемое в случае реализации i -ого варианта. Энтропия в формуле Шеннона является средней характеристикой – математическим ожиданием распределения случайной величины {I 0 , I 1, … I N -1 } .
Приведем пример расчета энтропии по формуле Шеннона. Пусть в некотором учреждении состав работников распределяется так: ¾ - женщины, ¼ - мужчины. Тогда неопределенность, например, относительно того, кого вы встретите первым, зайдя в учреждение, будет рассчитана рядом действий, показанных в таблице 1.
Таблица 1.
|
p i |
1/p i |
I i = log 2 (1/p i ), бит |
p i *log 2 (1/p i ), бит |
|
|
log 2 (4/3)=0,42 |
||||
|
å |
H=0,81 бит |
Если же априори известно, что мужчин и женщин в учреждении поровну (два равновероятных варианта), то при расчете по той же формуле мы должны получить неопределенность в 1 бит. Проверка этого предположения проведена в таблице 2.
Таблица 2.
|
p i |
1/p i |
I i = log 2 (1/p i ), бит |
p i *log 2 (1/p i ), бит |
|
|
1 /2 |
log 2 (2 )=1 |
1/2 * 1 =1/2 |
||
|
log 2 (2 )=1 |
1/2 * 1 =1/2 |
|||
|
å |
H=1 бит |
Формула Шеннона (1) совпала по форме с формулой Больцмана, полученной на 70 лет ранее для измерения термодинамической энтропии идеального газа. Эта связь между количеством информации и термодинамической энтропией послужила сначала причиной горячих дискуссий, а затем – ключом к решению ряда научных проблем. В самом общем случае энтропия понимается как мера неупорядоченности, неорганизованности материальных систем .
В соответствии со вторым законом термодинамики закрытые системы, т.е. системы лишенные возможности вещественно-энергетически-информационного обмена с внешней средой, стремятся, и с течением времени неизбежно приходят к естественному устойчивому равновесному внутреннему состоянию, что соответствует состоянию с максимальной энтропией. Закрытая система стремится к однородности своих элементов и к равномерности распределения энергии связей между ними. Т.е. в отсутствии информационного процесса материя самопроизвольно забывает накопленную информацию.
