Информационная энтропия. Формула Шеннона

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

Первую количественную метрику предложил Хартли в 1928 году и назвал её информационной емкостью.

Рассмотрим некоторую ячейку из n реле. Считая, что каждое реле может хранить два состояния m = 2, вся ячейка может содержать N = 2 n состояний. Хартли ввел двоичную логарифмическую меру, позволяющую измерять информацию в двоичных единицах – битах. Один бит – это количество информации, которое может храниться в элементарной ячейке на два состояния: . В ячейке на состояний хранится . Основание логарифма определяет размерность единиц измерения информации. Поскольку используют двоичные единицы – биты, основание логарифма опускают. Двоичная единица информации «бит» произошла от «сжатия» английских слов binary digit – двоичная единица.

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

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

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

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

2) количество информации в сообщении о достоверном событии равно 0;

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

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

,

где – вероятности формирования сообщения а 1 и а 2 соответственно.

Общее количество информации I (a 1 , а 2), содержащейся в этих двух сообщениях, согласно условию аддитивности определяется как сумма количеств информации в каждом из них:

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

,

где k – произвольный коэффициент.

Логарифм, вообще говоря, может быть взят по любому основанию. Эта формула может быть использована для определения количества информации, содержащейся в сообщении а i . Эта формула удовлетворяет и требованию 2): в случае достоверного события вероятность сообщения = 1. Тогда количество информации согласно полученной формуле:

Поскольку < 1, и следовательно, log ≤ 0, то, чтобы измерять количество информации неотрицательными числами, выбираем значение коэффициента k = –1:

.

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

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

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

.

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

И количество информации I в сообщении и энтропия источника H измеряются в одних единицах – в битах, но эти величины различны. Энтропия H источника определяет способность источника производить информацию; при наличии достаточной статистики она может быть вычислена априори, до получения сообщений. Получение информации I снимает часть неопределенности источника, уменьшает его энтропию. Это уменьшение энтропии происходит после (апостериори) получения сообщения, т.е. I определяется апостериорно. Таким образом, количество информации может рассматриваться как противоположность энтропии , в этом проявляется диалектический закон единства и борьбы противоположностей.

Энтропия источника дискретных сообщений обладает следующими свойствами:

1. Энтропия положительна.

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

3. Энтропия максимальна, если сообщения источника равновероятны.

.

4. В случае равновероятных сообщений энтропия возрастает с увеличением числа сообщений.

5. Энтропия источника бинарных (двоичных) сообщений изменяется от нуля до единицы в зависимости от вероятности сообщений и имеет максимум при . В этом случае мера Шеннона совпадает с мерой Хартли. Источник с энтропией в 1 бит полностью согласован с каналом, например, реле, имеющим информационную емкость в 1 бит. При неравновероятности сообщений канал будет недогружен. Зависимость энтропии от вероятности для бинарного источника иногда называют функцией Шеннона (рис. 40). При большом числе сообщений источника и при равновероятности сообщений они могут быть переданы с помощью равномерного двоичного кода. Так, восемь сообщений кодируются: 000, 001, 010, 011, 100, 101, 110, 111. Энтропия источника равна трем: это совпадает со средним числом символов на сообщение. Иногда используется понятие удельной энтропии , это – энтропия, приходящаяся на один символ. Данный источник имеет энтропию 3 бита на сообщение, можно также сказать, что его энтропия 1 бит/символ. Такая оценка удобна при сравнении различных источников.

Рассмотрим, как можно использовать введенные понятия при вскрытии неопределенности источника.

Пример 1. Пусть, надо отгадать задуманное число от 1 до 32, задавая источнику двоичные вопросы. Так как задуманное число с равной вероятностью может быть любым, энтропия источника Н = log 32 = 5 бит/число. Задаем первый вопрос: Число в нижней половине? Ответ: да. Количество полученной от источника информации I = 1 бит. Энтропия источника уменьшилась и стала Н = 4 бит/число. Задавая подобный вопрос еще раз и получая любой ответ, мы сужаем диапазон поиска вдвое и уменьшаем неопределенность источника на один бит. Таких вопросов и ответов будет ровно пять, после чего энтропия источника будет равна нулю.

Пример 2. Предположим, среди 25 монет одна фальшивая, более легкая. Какое минимальное число взвешиваний на рычажных весах необходимо сделать для нахождения фальшивой монеты?

Прежде всего определяем энтропию источника. Так как весы могут быть в трех состояниях, каждое взвешивание уменьшает энтропию источника на одну троичную единицу информации. Поэтому монеты следует разделить на три примерно равные кучки: 8, 8 и 9 монет. Положив на чашки весов одинаковое число монет 8 и 8, определяем, есть ли среди них фальшивая и, если есть, то в какой чашке. Предположим, что первая кучка легче второй. Значит, монета здесь. Эту кучку делим на три части 3, 3 и 2. Взвешиваем одинаковые части. Допустим, они равны. Значит, искомая монета находится среди двух оставшихся. При третьем взвешивании монета найдена.

Число характеризует число кодовых признаков, используемых при передаче сообщений. Это число определяет алфавит источника. При удельная энтропия источника возрастает. В принципе, такой источник более эффективен, он позволяет передавать больше информации в единицу времени. Так, если алфавит источника равен 32 буквам, то энтропия источника – 5 бит/букву; если в китайском языке используется около 2000 иероглифов, то энтропия такого источника – 11 бит/иероглиф, т.е. 11 бит/символ. Ясно, что использование большого алфавита приводит к техническим сложностям, отсюда, наибольшее распространение в технике получил двоичный алфавит с буквами или символами 0 и 1. Источник, работающий на таком алфавите, не может иметь энтропию больше 1 бит/символ.

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

Л Е К Ц И Я № 29

Тема:

Текст лекции по дисциплине: «Теория электрической связи»

Г. Калининград 2012 г.

Текст лекции № 30

по дисциплине: «Теория электрической связи»

«Основные понятия теории информации»

Введение

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

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

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

Информация – это сведения, являющиеся объектом передачи, распределения, преобразования, хранения или непосредственного использования.

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

Сообщение является формой представления информации.

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

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

Сигнал (от латинского signum – знак) представляет собой любой процесс, несущий информацию.

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

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

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

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

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

Рис.1. Тракт передачи дискретных сообщений

Вид передаваемого сигнала определяет тип канала связи.

Понятие информации, постановка задачи её определения.

Какое количество информации содержится, к примеру, в тексте романа «Война и мир», во фресках Рафаэля или в генетическом коде человека? Возможно ли, объективно измерить количество информации?

Определить понятие «количество информации» довольно сложно. В решении этой проблемы существуют два основных подхода. Исторически они возникли почти одновременно. В конце 40-х годов XX века один из основоположников кибернетики американский математик Клод Шеннон развил вероятностный подход к измерению количества информации, а работы по созданию ЭВМ привели к «объемному» подходу .

Вероятностный подход

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

При этом понятие «информация » связывается с вероятностью осуществления того или иного события.

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

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

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

;

(1.2)

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

Приведем примеры равновероятных сообщений: при бросании монеты: «выпала решка», «выпал орел»; на странице книги: «количество букв четное», «количество букв нечетное».

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

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

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

Если вероятности равны, то каждая из них равна , и формула Шеннона превращается в формулу Хартли.

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

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

Это – единица измерения информации. Она получила наименование бит.

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

В качестве примера определим количество информации, связанное с появлением каждого символа в сообщениях, записанных на русском языке. Будем считать, что русский алфавит состоит из букв и знака «пробел» для разделения слов. По формуле Хартли:

;

(1.4)

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

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

Таблица . Частотность букв русского языка

i	Символ	P(i)	i	Символ	P(i)	i	Символ	P(i)
	Пробел	0,175		К	0,028		Г	0.012
		0,090		М	0,026		Ч	0,012
	Е	0,072		Д	0,025		И	0,010
	Ё	0,072		П	0,023		X	0,009
	А	0,062		У	0,021		Ж	0,007
	И	0,062		Я	0,018		Ю	0,006
	Т	0,053		Ы	0,016		Ш	0.006
	Н	0,053		З	0.016		Ц	0,004
	С	0,045		Ь	0,014		Щ	0,003
	Р	0,040		Ъ	0,014		Э	0,003
	В	0,038		Б	0,014		Ф	0,002
	Л	0,035

Запомните комбинацию из наиболее повторяющихся букв русского алфавита СЕНОВАЛИТР. Эти знания использовали дешифровальщики при вскрытии тайных переписок в различные исторические периоды.

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

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

;

(1.5)

Таким образом бит можно также определить как количество информации, которое содержит один разряд двоичного числа (отсюда название «бит»: b inary digit - двоичный разряд). Другими словами количество информации (в битах), заключенное в двоичном слове, равно числу двоичных знаков в нем.

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

Количество информации, равное битам, называется байтом.

В восьми разрядах можно записать различных целых двоичных чисел от до . Этого вполне достаточно для представления в двоичной форме информации об алфавитах Русском и Латинском, всех знаках препинания, цифрах от до , арифметических и алгебраических действиях, а так же специальных символов (например § @ $).

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

Энтропия источника сообщений

Для большинства реальных источников сообщения имеют разные вероятности. Например, в тексте буквы А, О, Е встречаются сравнительно часто, а Щ, Ы – редко. Согласно экспериментальным данным, для букв русского алфавита характерны безусловные вероятности, сведенные в табл. 4.1.

Таблица 4.1 Безусловные вероятности букв русского алфавита

	вероятность		вероятность		вероятность

При разных вероятностях сообщения несут различное количество информации . При решении большинства практических задач необходимо знать среднее количество информации, приходящееся на один элемент сообщения. Это среднее количество информации при общем числе элементов сообщения источника n и числе символов алфавита m равно:

(бит/сообщение).

Величину называют энтропией источника сообщений. Термин «энтропия» заимствован из термодинамики, где она характеризует среднюю неопределенность состояния системы молекул вещества. В теории информации этот термин введен в 1948 г. американским ученым К. Шенноном и далее более строго определен советскими математиками А.Я. Хинчиным и А.Н. Колмогоровым . Физически энтропия выражает среднюю неопределенность состояния источника сообщений и является объективной информационной характеристикой источника. Энтропия всегда положительна и принимает максимальное значение при равновероятных сообщениях :

.

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

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

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

Определим энтропию двоичного источника. Из формулы (4.2) получим:

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

Избыточность источника сообщений

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

Количественно избыточность оценивается коэффициентом избыточности:

,

где – энтропия источника; – максимальная энтропия источника с алфавитом из сообщений.

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

Однако при увеличении избыточности появляется возможность повышения помехоустойчивости передачи сообщений. Так, избыточность текста позволяет исправлять отдельные ошибки или восстанавливать пропущенные буквы или даже слова в телеграмме. У русского и всех европейских языков избыточность с учетом всех статистических зависимостей букв примерно одинакова . Она сформировалась в результате длительной, общественной практики на основе требований исправления искажения слов и фраз под воздействием различных мешающих факторов. Для систем связи устанавливается компромиссное значение избыточности, которое обеспечивает заданную скорость и надежность передачи сообщений.

Производительность источника сообщений

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

[бит/с],

где – интервал времени для передачи элементарного сообщения.

Физический смысл производительности – количество информации, выдаваемое источником в среднем за единицу времени (одну секунду) его непрерывной работы.

4.ЭНТРОПИЯ И ИНФОРМАЦИЯ

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

Неопределенность может иметь разное происхождение. Один из ее видов – неизвестность – рассматривается теорией познания и философией; такого типа неопределенность возникает, когда мы, например, задаем вопрос «Есть ли жизнь на других планетах?» или «Существуют ли другие цивилизации?» и т.п.

Другой вид неопределенности – расплывчатость, размытость, – например, «Сколько надо взять песчинок, чтобы образовать небольшую кучу»? С неопределенностью этого типа мы встречаемся в квантовой механике. На её основе построена нелокальная версия термодинамики, которая способна ответить на сходный вопрос: «сколько надо иметь частиц, чтобы образовать макроуровень и каково квантовое рассеяние этого числа»?. Эта неопределенность объективна, для нее характерно, что она неустранима в процессе измерений. В математике такой неопределенностью занимается теория размытых множеств. Следует попутно отметить, что размытость – характерное свойство языка: «в комнату (какую?) вошел высокий (какого роста?) молодой (какого конкретно возраста?) человек (кто он?) и т.п.

Третий вид неопределенности – случайность . В ее основе лежат статистические закономерности, устанавливаемые теорией вероятности. Этот вид неопределенности используется статистической физикой и совместно с неопределённостью второго типа в квантовой механике. Отличительная особенность статистической неопределенности заключается в том, что для нее можно установить количественную меру, о которой пойдет речь далее.

Оставим пока в стороне вопрос о практической значимос888ти статистической меры неопределенности, сосредоточив внимание на её сущности. Рассмотрим несколько простейших ситуаций, которые будем именовать опытами А,BиC. Предполагается, что читателю знакомы элементы теории вероятности.

О п ы т А будет заключаться в бросании монеты. В этом опыте возможны два исхода (k =2): “орел или решка”. Очевидно, вероятность каждого исхода(i =1,2).

О п ы т B– бросание игральной шестигранной кости. В этом опыте возможны уже шесть исходов (k =6). Вероятность каждого исхода.

О п ы т C предполагает одновременное бросание двух костей. Для этого опыта k =36 и.

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

Чтобы перейти к количественной оценке неопределённости сформулируем основные требования к функции, которая должна играть роль меры неопределённости. Будем обозначать эту функцию буквой H .

П е р в о е требование. Функция Н должна монотонно возрастать с увеличением числа исходов опыта.

В т о р о е требование. Функция Н должна быть равна нулю, если имеется единственный исход (k =1). Это означает, что если возможен лишь один исход, то никакой неопределённости не возникает и результат опыта можно предвидеть безошибочно.

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

или в общем случае не для двух, а n простых опытов

Если бы третье требование не соблюдалось, то оценка неопределённости опыта С оказалась бы противоречивой и зависела бы от субъективной трактовки самого опыта – считать ли, что имел место опыт С, или всё же кости упали не одновременно и имели место два опыта В. Принятие этого требования равносильно введению свойств аддитивности для будущей оценки неопределённости. По умолчанию принимается, что рассматриваемые элементы (кости) не взаимодействуют между собой. В термодинамической трактовке это равносильно принятию идеальной системы.

Решим функциональное уравнение (4.1) относительно функции . Для этого дифференцируем обе части выражения (4.1-1) поk , используя требование монотонности функции:

Теперь дифференцируем (4.1) по n

Разделим уравнение (4.2) на (4.3)

что равносильно

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

где – постоянная интегрирования.

Из последнего выражения

Так как с увеличением k энтропия растёт (первое требование), тоC >0, и это выражение можно переписать в следующем окончательном виде:

,a >1.

Из него следует, что оно удовлетворяет также второму требованию. Выбор основания логарифмов при a >1не имеет значения и определяет лишь выбор единицы измерения неопределённости. Чаще всего применяют двоичные или натуральные логарифмы. Если используют двоичные логарифмы, то за единицу измерения неопределённости принимают неопределённость опыта, который имеет два равновероятных исхода (опыт А). Такая ситуация отвечает энтропии одной элементарной компьютерной ячейки, в которой хранится либо 0 либо 1. Для этой ячейки

Такая единица измерения называется битом (от англ.binarydiget– двоичная единица).

Итак, при k равновероятных исходах неопределённость опыта составляет

где p – вероятность исхода опыта.

Если учесть, что для равновероятных исходов

то, умножая (4.4) на единицу в виде суммы вероятностей , получаем

Каждый член правой части этого выражения можно рассматривать как вклад отдельного исхода в общую неопределённость опыта. В случае равновероятных исходов вклад каждого из них в общую неопределенность опыта одинаков и формула (4.5) сворачивается в (4.4).

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

Выражение (4.5) можно записать в компактной форме

Если число опытов N , то с учётом аддитивности энтропии

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

Рис. 4.1. Зависимость энтропии для двух исходов опыта

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

Так как только приp =0 илиp =1, то энтропия опыта равна нулю только в случае, когда одна из вероятностей равна единице и, следовательно, все остальные равны нулю. Это обстоятельство хорошо согласуется со смыслом величиныH как меры неопределенности: в этом случае опыт вообще не содержит никакой неопределенности, так как результат опыта можно предвидеть заранее.

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

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

Тот факт, что максимум энтропии отвечает равновероятным событиям, согласуется со смыслом энтропии. Действительно, в случае равновероятных событий нельзя отдать предпочтение ни одному исходу и таким образо8м предвидеть результат труднее всего.

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

Если неопределенность до опыта составляла Н (априорная неопределенность ), а после опыта –(апостериорная неопределенность ), то очевидно, неопределенность, устраненная в ходе опыта, составит:

Эта разность носит название количества информации .

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

Количество информации, как и энтропия, измеряется в битах. Один бит информации – это количество информации, сообщающее о том, какое из двух равновероятных событий имело место. Например, количество информации, заключающееся в одной элементарной ячейке ЭВМ, содержащей либо 0, либо 1, составляет один бит.

Рассмотрим пример, в котором бы фигурировала апостериорная неопределенность. Пусть методом перебора вариантов ведется поиск корня некоторого уравнения с точностью до полуцелого числа. Предварительно известно, что значение корня находится в интервале от 1 до 100, так что следует перебрать 200 вариантов. Тогда неопределенность значения корня в равновероятном варианте (4.4) составит H = log 2 200 = 13,3 бит.

Пусть проведена проверка 150 вариантов возможных значений корня, но корень не найден. Однако получена ли некоторая информация о значении корня? Несомненно, и чтобы ее определить, необходимо сначала найти остаточную (апостериорную) неопределенность: Н 1 =log 2 (200 – 150) = 5,6. Тогда искомое количество информации составит= 13,3 – 5,6 = 7,7 бит.

Условная энтропия. Рассмотрим понятие количества информации на примере передачи сигналов. Пусть передается группа сигналов азбукой Морзе:

        

До получения очередного символа на приемном конце существует неопределенность «какой сигнал будет отправлен?» Эту неопределенность можно характеризовать энтропией «на один символ» (4.6) при числе исходов k= 3 (точка, тире, пробел) с вероятностями р i (i= 1, 2, 3). Вероятности появления на приемном конце точки, тире или пробела, т.е. вероятности (частоты) употребления символов конкретного языка специалистам известны из статистического анализа большого объема текстов на этом языке. Подсчитав энтропию на один символ, по формуле (4.6) легко определить общую энтропию сообщения (4.7). В данном примере 10 символов, включая пробел и, следовательно, N = 10.

Итак, на приемном конце до получения сообщения существовала априорная неопределенность (4.7) или на один знак (4.6). После получения сообщения неопределенность была устранена и получена информация I=H– 0.

Однако такая простая ситуация возникает, если сообщение передается без помех (канал без шума ). Если имеется шум, то его действие приводит к тому, что переданный символ может либо остаться прежним (i-м), либо быть случайно подмененным любым другим (n-м) символом. Вероятность такой подмены по обозначению р(y n  x i), где х относится к переданному сигналу, а y к принимаемому сигналу в приемнике. В канале без помех y n = x i . Вероятность р(y n  x i) носит название условной вероятности x i) -–вероятность того, что отправленный i-й сигнал соответствует n-му сигналу на приемном конце. Конечно, эту ситуацию можно рассматривать и со стороны передатчика, используя условные вероятности вида р(x i y n). В этом случае р(x i y n) – вероятность того, что принятый на приемном конце n-й сигнал соответствует i-му сигналу на передающей стороне. Понятие условной вероятности вводит условную энтропию как функцию условной вероятности. В общем виде это записывается в следующих обозначениях:

I(X,Y) = H(X) – H(XY)

I(X,Y) = H(Y) – H(YX)

В этих идентичных выражениях условная энтропия играет роль апостериорной энтропии, а количество информации есть мера соответствия двух случайных объектов Х и Y.

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

Здесь полезно обратиться к п.3.6, где уже касались ограничений классического, причинно-следственного механизма при описании взаимодействий в открытой системе.

4.3.Энтропия непрерывного множества. Ранее была рассмотренаэнтропия дискретного множества. Это означает, что подразумевались системы, где число возможных исходов (элементов множества) конечно. Однако приходится часто сталкиваться с ситуациями, когда число элементов может быть сколь угодно велико. Из теории вероятностей известно, что в этом случае следует иметь дело не с вероятностью отдельного исхода, которая равна нулю, а с плотностью распределения вероятности. Эта функция обладает таким свойством, что величинаесть вероятность того, что интересующая нас переменнаяx (значение корня в примере п.4.2.) примет значения, заключенные в интервале отx доx+dx .

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

. (4.9)

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

Повышая требования к точности ответа, можно ожидать сколь угодно большого числа возможных исходов опыта. При этом вероятность каждого исхода стремится к нулю, а искомый корень может принимать все возможные (бесчисленные) значения в заданном числовом интервале от 0 до 200. Попробуем использовать для этой же задачи энтропию непрерывного множества. Введем отрезок длиной l =x 1 –x 0 относительных единиц. Вероятность обнаружить значение корня на участке dx составляет dx/1 . С другой стороны, эта же вероятность по определению. Следовательно, для равновероятного случая=dx /l и= 1/l. Подставляя это значение в (4.), несложно получить H = log 2 l= 5,6 бит.

Сравним полученный результат с примером в п.4.2. В случае дискретного множества в энтропии используется число дискретных интервалов на выделенном отрезке, а в случае непрерывного множества – относительная длина самого отрезка . Заметим, что длина должна быть выражена в относительной форме, в противном случае под логарифмом появилась бы размерная величина. Масштаб приведения к относительной форме не имеет для информационной энтропии принципиального значения, поскольку с самого начала энтропия введена с точностью до множителя (до постоянной интегрирования, см процедуру интегрирования в п.4.1).

Энтропия непрерывного множества или дифференциальная энтропия (4.9) обладает большинством свойств энтропии дискретного множества.

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

4.4.Энтропия как мера разнообразия, неупорядоченности, хаоса. До сих пор понятие энтропии связывалось с неопределенностью. Энтропия допускает и другое толкование. Представим себе систему, состоящую из камеры, в которой находятсяN шаровmтипов, отличающихся, например, цветом. Предполагается, чтоNдостаточно большое число. Обозначим долю шаровi -го типа (цвета) –. Если произвести опыт над системой, заключающийся в извлечении наугад одного шара, то энтропия одного опыта согласно (4.6) составит:

При этом принято, что размеры шаров одинаковы, в противном случае вероятность извлечения шаров i -того типа не будет точно соответствовать их доле в камере. Энтропия всех опытов над системой

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

Первая из двух функций характеризует степень неупорядоченности системы или степень разнообразия в ней с учётом выбранного признака для различения элементов системы (цвета шаров). Если бы в камере находились шары одного типа, тогда одно из значений вероятностиp =z равнялось бы единице, а все остальные – нулю, и энтропия приняла бы нулевое значение. Это означало бы, что система полностью упорядочена, или, что то же самое – в системе отсутствует разнообразие по оцениваемому признаку (цвету).

Вторая функция (4.11) измеряет неупорядоченность (разнообразие) в системе несколько иначе. Отличие этих двух функций можно иллюстрировать следующим примером. Если камеру разделить на две части, то при достаточно большом количестве шаров в ней доля шаров i -го типа в каждой из двух частей останется прежней, но число шаров уменьшится вдвое, также вдвое уменьшится неупорядоченность, оцениваемая формулой (4.11). Однако степень неупорядоченности для каждой из двух частей, оцениваемая функцией (4.10) останется прежней.

По аналогии с только что рассмотренным примером формулой (4.11) можно оценивать неупорядоченность потока смеси каких-либо веществ. В этом случае – концентрацияi -го компонента в мольных долях;N – расход потока или число молекул, проходящее через некоторое сечение в единицу времени. Поскольку числоN в практических задачах всегда очень велико, можно перейти к иному масштабу для энтропии. Например, поделив левую и правую части на число Авогадро, получим

где F – расход потока, кмоль/ед. времени. Обозначение энтропии в новом масштабе оставлено прежним.

Таким образом, энтропия оценивает разнообразие элементов в системе по некоторому определенному признаку, который может нас интересовать в той или иной задаче; см п. 4.6 и 4.7.

Обратим внимание, что выражение (4.10) с точностью до множителя совпадает с термодинамическим выражением для мольной энтропии смешения идеального газа

S= –R, (4.13)

где R– газовая постоянная.

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

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

4.5.Связь информационной энтропии с физикой. Понятие энтропии впервые было введено в термодинамику Клаузисом как соотношение, связывающее элементарное приращение энтропииdS с элементарным количеством теплотыdQ при температуреТ

dS = dQ/T (4.14)

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

Энтропия Больцмана. Рассмотрим основанное на статистическом подходе известное уравнение Больцмана

где k B – постоянная Больцмана,k B =1,3810Дж/К;W– число микросостояний.

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

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

Проследим на весьма упрощённой модели, как появляются эти новые свойства, связанные с понятием энтропии Больцмана.

Для наглядности возьмем систему всего из десяти частиц (N =10), распределённых на четырёх энергетических уровнях, имеющих относительные величины энергии 1, 2, 3 и 4. Общая энергия системы равна 20 относительным единицам. Задача заключается в том, чтобы высказать некоторые соображения относительно того состояния, которое примет система, предоставленная самой себе, т.е. относительно того, как распределятся частицы по уровням энергии.

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

Так, одно из возможных макросостояний в рассматриваемой системе из десяти частиц таково: на первом энергетическом уровне находится одна частица (N 1 =1), на втором располагаются восемь частиц (N 2 =8) и одна занимает третий уровень (N 3 =1). Четвертый уровень не занят. Общая энергия равна 11+82+13+ 40=20. Предположим, что частицы пронумерованы. Тогда данное макросостояние можно было бы осуществлять различным способом (через различные микросостояния), помещая, например, на уровеньcэнергией 1 поочерёдно частицы с номером 1, 2, 3, 4, 5 и т.д., т.е. осуществляя разные перестановки частиц, не нарушая макросостояния системы.

. (4.16)

Здесь r – число энергетических уровней; в данном примереr = 4.

Если теперь перейти к другому макросостоянию, т.е. взять иное распределение частиц по энергетическим уровням, например, N 1 =2,N 2 =7,N 3 =0 иN4=1 (общая энергия 21+72+14 = 20), то число способов осуществления данного макросостоянияWоказывается равным 360.

Аннотация: Вводится понятие энтропии. На нескольких примерах показывается, как вычисляется энтропия дискретной случайной величины. Вводится понятие префиксного кодирования. Задачи на самостоятельную работу улучшают восприятие материала. Также много различных математических исследований

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

Рассмотрим пример (скачки). В заезде участвуют 4 лошади с равными шансами на победу, т.е. вероятность победы каждой лошади равна 1/4. Введем д.с.в. , равную номеру победившей лошади. Здесь . После каждого заезда по каналам связи достаточно будет передавать два бита информации о номере победившей лошади. Кодируем номер лошади следующим образом: 1-00, 2-01, 3-10, 4-11. Если ввести функцию , которая возвращает длину сообщения, кодирующего заданное значение , то м. о. - это средняя длина сообщения, кодирующего . Можно формально определить через две функции , где каждому значению ставит в соответствие некоторый битовый код, причем, взаимно однозначно, а возвращает длину в битах для любого конкретного кода. В этом примере .

Пусть теперь д.с.в. имеет следующее распределение

Т.е. лошадь с номером 1 - это фаворит. Тогда

Закодируем номера лошадей: 1-0, 2-10, 3-110, 4-111, - т.е. так, чтобы каждый код не был префиксом другого кода (подобное кодирование называют префиксным ). В среднем в 16 заездах 1-я лошадь должна победить в 12 из них, 2-я - в 2-х, 3-я - в 1-м и 4-я - в 1-м. Таким образом, средняя длина сообщения о победителе равна бит /сим или м. о. . Действительно, сейчас задается следующим распределением вероятностей: , , . Следовательно,

Итак, .

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

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

Упражнение 13 Найти энтропию д.с.в. и среднюю длину каждого из приведенных кодов для этой д.с.в.

Упражнение 14 д.с.в. равна количеству "гербов", выпавших на двух идеальных монетках. Найти энтропию . Придумать минимальный код для , вычислить его среднюю длину и обосновать его минимальность.

Упражнение 15 д.с.в. задана распределением , Найти энтропию этой д.с.в. Придумать минимальный код для , вычислить его среднюю длину и обосновать его минимальность.

Упражнение 16 Про д.с.в. известно, что ее значениями являются буквы кириллицы. Произведен ряд последовательных измерений , результат которых - "ТЕОРИЯИНФОРМАЦИИ". Составить на основании этого результата приблизительный закон распределения вероятностей этой д.с.в. и оценить минимальную среднюю длину кодов для .

Семантическая информация

В 50-х годах XX века появились первые попытки определения абсолютного информационного содержания предложений естественного языка. Стоит отметить, что сам Шеннон однажды заметил, что смысл сообщений не имеет никакого отношения к его теории информации, целиком построенной на положениях теории вероятностей. Но его способ точного измерения информации наводил на мысль о возможности существования способов точного измерения информации более общего вида, например, информации из предложений естественного языка. Примером одной из таких мер является функция , где - это предложение, смысловое содержание которого измеряется, -