Бит, информационная энтропия Шеннона и код Хэмминга. Как измерить любую информацию и передать ее без потерь. Информационная энтропия Определение энтропии с точки зрения теории информации

1.4 Энтропия источника. Свойства количества информации и энтропии

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

, i =1…k , (1.3)

где k – объём алфавита сообщений.

Таким образом, энтропия – это среднестатистическая мера неопределенности знаний получателя информации относительно состояния наблюдаемого объекта.

В выражении (1.3) статистическое усреднение (т.е. определение математического ожидания дискретной случайной величины I (X i )) выполняется по всему ансамблю сообщений источника. При этом необходимо учитывать все вероятностные связи между сообщениями. Чем выше энтропия источника, тем большее количество информации в среднем закладывается в каждое сообщение, тем труднее запомнить (записать) или передать такое сообщение по каналу связи. Таким образом, суть энтропии Шеннона заключается в следующем: энтропия дискретной случайной величин – это минимум среднего количества битов, которое нужно передавать по каналу связи о текущем значении данной случайной величины.

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

I (N )=NH (X ) .

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

1) энтропия равна нулю, если хотя бы одно из сообщений достоверно (т.е. имеет вероятность p i = 1);

2) величина энтропии всегда больше или равна нулю, действительна и ограничена;

3) энтропия источника с двумя альтернативными событиями может изменяться от 0 до 1;

4) энтропия – величина аддитивная: энтропия источника, сообщения которого состоят из сообщений нескольких статистически независимых источников, равна сумме энтропий этих источников;

5) энтропия будет максимальной, если все сообщения равновероятны

. (1.4)

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

, (1.5)

где H (X ) – энтропия реального источника; H (X ) max = log 2 k – максимально достижимая энтропия источника.

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

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

Рассмотрим дискретные случайные величины (д.с.в.) Х и Y , заданные законами распределения P (X = X i )= p i , P (Y = Y j )= q j и совместным распределением P (X = X i , Y = Y j )= p ij . Тогда количество информации, содержащееся в д. с. в. Х относительно д. с. в. Y , определяется по формуле

. (1.6)

Для непрерывных случайных величин (сл. в.) X и Y , заданных плотностями распределения вероятностей r X (t 1 ) , r Y (t 2 ) и r XY (t 1 , t 2 ) , аналогичная формула имеет вид

Очевидно, что

следовательно

т.е. приходим к выражению (1.3) для расчета энтропии H (X ) .

Свойства количества информации и энтропии:

1) I (X , Y ) ≥ 0 ; I (X , Y ) =0 Û X и Y независимые (одна случайная величина ничем не описывает другую);

2) I (X, Y ) =I (Y, X ) ;

3) НХ =0 Û X=const ;

4) I (X, Y ) =HX+HY-H (X, Y ) , где ;

5) I (X, Y ) ≤ I(X, X); I(X, Y)= I(X, X) Þ X= f(Y) .

КОНТРОЛЬНЫЕ ВОПРОСЫ

1 Какие существуют виды информации?

2 Как перевести непрерывную информацию в дискретный (цифровой) вид?

3 Что такое частота дискретизации непрерывной информации?

4 Как формулируется теорема дискретизации?

5 Что такое информация, кодирование, канал связи, шум?

6 В чем заключаются основные положения вероятностного подхода Шеннона к определению количества информации?

7 Как определяется количество информации, содержащееся в одном сообщении дискретного источника?

8 Как определяется количество информации на одно сообщение источника взаимозависимых сообщений?

9 Что такое энтропия источника? Какие ее свойства?

10 При каких условиях энтропия источника максимальна?

11 Как определяется количество информации? Какие свойства количества информации?

12 Чем обусловлена статистическая избыточность источника информации?

«Информация есть форма жизни», - писал американский поэт и эссеист Джон Перри Барлоу. Действительно, мы постоянно сталкиваемся со словом «информация» - ее получают, передают и сохраняют. Узнать прогноз погоды или результат футбольного матча, содержание фильма или книги, поговорить по телефону - всегда ясно, с каким видом информации мы имеем дело. Но что такое сама информация, а главное - как ее можно измерить, никто обычно не задумывается. А между тем, информация и способы ее передачи - важная вещь, которая во многом определяет нашу жизнь, неотъемлемой частью которой стали информационные технологии. Научный редактор издания «Лаба.Медиа» Владимир Губайловский объясняет, что такое информация, как ее измерять, и почему самое сложное - это передача информации без искажений.

Пространство случайных событий

В 1946 году американский ученый-статистик Джон Тьюки предложил название БИТ (BIT, BInary digiT - «двоичное число» - «Хайтек») - одно из главных понятий XX века. Тьюки избрал бит для обозначения одного двоичного разряда, способного принимать значение 0 или 1. Клод Шеннон в своей программной статье «Математическая теория связи» предложил измерять в битах количество информации. Но это не единственное понятие, введенное и исследованное Шенноном в его статье.

Представим себе пространство случайных событий, которое состоит из бросания одной фальшивой монеты, на обеих сторонах которой орел. Когда выпадает орел? Ясно, что всегда. Это мы знаем заранее, поскольку так устроено наше пространство. Выпадение орла - достоверное событие, то есть его вероятность равна 1. Много ли информации мы сообщим, если скажем о выпавшем орле? Нет. Количество информации в таком сообщении мы будем считать равным 0.

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

Что изменилось? В нашем пространстве событий появилась неопределенность. Нам есть, что о нем рассказать тому, кто сам монету не бросает и исхода бросания не видит. Но чтобы правильно понять наше сообщение, он должен точно знать, чем мы занимаемся, что означают 0 и 1. Наши пространства событий должны совпадать, и процесс декодирования - однозначно восстанавливать результат бросания. Если пространство событий у передающего и принимающего не совпадает или нет возможности однозначного декодирования сообщения, информация останется только шумом в канале связи.

Если независимо и одновременно бросать две монеты, то разных равновероятных результатов будет уже четыре: орел-орел, орел-решка, решка-орел и решка-решка. Чтобы передать информацию, нам понадобится уже 2 бита, и наши сообщения будут такими: 00, 01, 10 и 11. Информации стало в два раза больше. Это произошло, потому что выросла неопределенность. Если мы попытаемся угадать исход такого парного бросания, то имеем в два раза больше шансов ошибиться.

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

Немного усложним наше пространство событий. Пока все события, которые случались, были равновероятными. Но в реальных пространствах далеко не все события имеют равную вероятность. Скажем, вероятность того, что увиденная нами ворона будет черной, близка к 1. Вероятность того, что первый встреченный на улице прохожий окажется мужчиной, - примерно 0,5. Но встретить на улице Москвы крокодила почти невероятно. Интуитивно мы понимаем, что сообщение о встрече с крокодилом имеет гораздо большую информационную ценность, чем о черной вороне. Чем ниже вероятность события, тем больше информации в сообщении о таком событии.

Пусть пространство событий не такое экзотическое. Мы просто стоим у окна и смотрим на проезжающие машины. Мимо проезжают автомобили четырех цветов, о которых нам необходимо сообщить. Для этого мы закодируем цвета: черный - 00, белый - 01, красный - 10, синий - 11. Чтобы сообщить о том, какой именно автомобиль проехал, нам достаточно передать 2 бита информации.

Но довольно долго наблюдая за автомобилями, замечаем, что цвет автомобилей распределен неравномерно: черных - 50% (каждый второй), белых - 25% (каждый четвертый), красных и синих - по 12,5% (каждый восьмой). Тогда можно оптимизировать передаваемую информацию.

Больше всего черных автомобилей, поэтому обозначим черный - 0 - самый короткий код, а код всех остальных пусть начинается на 1. Из оставшихся половина белые - 10, а оставшиеся цвета начинаются на 11. В заключение обозначим красный - 110, а синий - 111.

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

Энтропия по Шеннону

Пусть наше пространство событий состоит из n разных событий. При бросании монеты с двумя орлами такое событие ровно одно, при бросании одной правильной монеты - 2, при бросании двух монет или наблюдении за автомобилями - 4. Каждому событию соответствует вероятность его наступления. При бросании монеты с двумя орлами событие (выпадение орла) одно и его вероятность p1 = 1. При бросании правильной монеты событий два, они равновероятны и вероятность каждого - 0,5: p1 = 0,5, p2 = 0,5. При бросании двух правильных монет событий четыре, все они равновероятны и вероятность каждого - 0,25: p1 = 0,25, p2 = 0,25, p3 = 0,25, p4 = 0,25. При наблюдении за автомобилями событий четыре, и они имеют разные вероятности: черный - 0,5, белый - 0,25, красный - 0,125, синий - 0,125: p1 = 0,5, p2 = 0,25, p3 = 0,125, p4 = 0,125.

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

• 1Энтропия достоверного события, вероятность которого 1, равна 0.

• Энтропия двух независимых событий равна сумме энтропий этих событий.

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

Все эти требования вполне соответствуют нашим представлениям о неопределенности пространства событий. Если событие одно (первый пример) - никакой неопределенности нет. Если события независимы - неопределенность суммы равна сумме неопределенностей - они просто складываются (пример с бросанием двух монет). И, наконец, если все события равновероятны, то степень неопределенности системы максимальна. Как в случае с бросанием двух монет, все четыре события равновероятны и энтропия равна 2, она больше, чем в случае с автомобилями, когда событий тоже четыре, но они имеют разную вероятность - в этом случае энтропия 1,75.

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

Клод Шеннон

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

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

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

Шеннон внес ключевой вклад в теорию вероятностных схем, теорию игр, теорию автоматов и теорию систем управления - области наук, входящие в понятие «кибернетика».

Кодирование

И бросаемые монеты, и проезжающие автомобили не похожи на цифры 0 и 1. Чтобы сообщить о событиях, происходящих в пространствах, нужно придумать способ описать эти события. Это описание называется кодированием.

Кодировать сообщения можно бесконечным числом разных способов. Но Шеннон показал, что самый короткий код не может быть меньше в битах, чем энтропия.

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

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

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

Сообщения на естественном языке

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

Самым частотным символом (то есть таким, который чаще всего встречается во всех текстах, написанных на русском языке) является пробел: из тысячи символов в среднем пробел встречается 175 раз. Вторым по частоте является символ «о» - 90, далее следуют другие гласные: «е» (или «ё» - мы их различать не будем) - 72, «а» - 62, «и» - 62, и только дальше встречается первый согласный «т» - 53. А самый редкий «ф» - этот символ встречается всего два раза на тысячу знаков.

Будем использовать 31-буквенный алфавит русского языка (в нем не отличаются «е» и «ё», а также «ъ» и «ь»). Если бы все буквы встречались в языке с одинаковой вероятностью, то энтропия на символ была бы Н = 5 бит, но если мы учтем реальные частоты символов, то энтропия окажется меньше: Н = 4,35 бит. (Это почти в два раза меньше, чем при традиционном кодировании, когда символ передается как байт - 8 бит).

Но энтропия символа в языке еще ниже. Вероятность появления следующего символа не полностью предопределена средней частотой символа во всех текстах. То, какой символ последует, зависит от символов уже переданных. Например, в современном русском языке после символа «ъ» не может следовать символ согласного звука. После двух подряд гласных «е» третий гласный «е» следует крайне редко, разве только в слове «длинношеее». То есть следующий символ в некоторой степени предопределен. Если мы учтем такую предопределенность следующего символа, неопределенность (то есть информация) следующего символа будет еще меньше, чем 4,35. По некоторым оценкам, следующий символ в русском языке предопределен структурой языка более чем на 50%, то есть при оптимальном кодировании всю информацию можно передать, вычеркнув половину букв из сообщения.

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

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

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

Избыточность естественного языка

В статье «О том, как мы ворпсиманием теcкт» (название звучит именно так!) был взят фрагмент романа Ивана Тургенева «Дворянское гнездо» и подвергнут некоторому преобразованию: из фрагмента было вычеркнуто 34% букв, но не случайных. Были оставлены первые и последние буквы в словах, вычеркивались только гласные, причем не все. Целью было не просто получить возможность восстановить всю информацию по преобразованному тексту, но и добиться того, чтобы человек, читающий этот текст, не испытывал особых трудностей из-за пропусков букв.

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

Оцифровка сигнала

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

При цифровой связи по каналу мы можем передать только конечное количество значений. Значит ли это, что звук нельзя передать точно? Оказывается, нет.

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

Теорема Котельникова (в англоязычной литературе - теорема Найквиста - Шеннона, теорема отсчетов) - фундаментальное утверждение в области цифровой обработки сигналов, связывающее непрерывные и дискретные сигналы и гласящее, что «любую функцию F(t), состоящую из частот от 0 до f1, можно непрерывно передавать с любой точностью при помощи чисел, следующих друг за другом через 1/(2*f1) секунд.

Помехоустойчивое кодирование. Коды Хэмминга

Если по ненадежному каналу передать закодированный текст Ивана Тургенева, пусть и с некоторым количеством ошибок, то получится вполне осмысленный текст. Но вот если нам нужно передать все с точностью до бита, задача окажется нерешенной: мы не знаем, какие биты ошибочны, потому что ошибка случайна. Даже контрольная сумма не всегда спасает.

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

Существуют специальные помехоустойчивые коды, которые позволяют восстанавливать информацию после сбоя. Один из них - код Хэмминга. Допустим, весь наш язык состоит из трех слов: 111000, 001110, 100011. Эти слова знают и источник сообщения, и приемник. И мы знаем, что в канале связи случаются ошибки, но при передаче одного слова искажается не более одного бита информации.

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

1) 111000, 0 11000, 10 1000, 110 000, 1111 00, 11101 0, 111001 .

При передаче слова 001110 может получиться любое из слов:

2) 001110, 1 01110, 01 1110, 000 110, 0010 10, 00110 0, 001111 .

Наконец, для 100011 у нас может получиться на приеме:

3) 100011, 0 00011, 11 0011, 101 011, 1001 11, 10000 1, 100010 .

Заметим, что все три списка попарно не пересекаются. Иными словами, если на другом конце канала связи появляется любое слово из списка 1, получатель точно знает, что ему передавали именно слово 111000, а если появляется любое слово из списка 2 - слово 001110, а из списка 3 - слово 100011. В этом случае говорят, что наш код исправил одну ошибку.

Исправление произошло за счет двух факторов. Во-первых, получатель знает весь «словарь» , то есть пространство событий получателя сообщения совпадает с пространством того, кто сообщение передал. Когда код передавался всего с одной ошибкой, выходило слово, которого в словаре не было.

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

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

Сенсация

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

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

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

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

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

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

Клод Элвуд Шеннон (1916-2001) -
американский инженер и математик,
основатель теории информации,
т.е. теории обработки, передачи
и хранения информации

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

Одной из самых известных научных работ Клода Шеннона является его статья «Математическая теория связи» , опубликованная в 1948 году.

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

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

H (p) .

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

На практике значения вероятностей p i в приведённой формуле заменяют их статистическими оценками: p i - относительная частота i -го символа в сообщении, где N - число всех символов в сообщении, N i - абсолютная частота i -го символа в сообщении, т.е. число встречаемости i -го символа в сообщении.

Во введении к своей статье «Математическая теория связи» Шеннон отмечает, что в этой статье он расширяет теорию связи, основные положения которой содержатся в важных работах Найквиста и Хартли .

Гарри Найквист (1889-1976) -
американский инженер шведского
происхождения, один из пионеров
теории информации

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

В 1928 году Хартли ввёл логарифмическую меру информации H = K · log 2 N , которую часто называют хартлиевским количеством информации.

Хартли принадлежит следующая важная теорема о необходимом количестве информации: если в заданном множестве M , состоящем из N элементов, содержится элемент x , о котором известно только то, что он принадлежит этому множеству M , то, чтобы найти x , необходимо получить об этом множестве количество информации, равное log 2 N бит.

Кстати, отметим, что название БИТ произошло от английской аббревиатуры BIT - BInary digiT . Этот термин впервые был предложен американским математиком Джоном Тьюки в 1946 году. Хартли и Шеннон использовали бит как единицу измерения информации.

Вообще, энтропия Шеннона - это энтропия множества вероятностей p 1 , p 2 ,…, p n .

Ральф Винтон Лайон Хартли (1888-1970)
- американский учёный-электронщик

Строго говоря, если X p 1 , p 2 ,…, p n - вероятности всех её возможных значений, то функция H (X ) задаёт энтропию этой случайной величины, при этом, хотя X и не является аргументом энтропии, можно записывать H (X ).

Аналогично, если Y - конечная дискретная случайная величина, а q 1 , q 2 ,…, q m - вероятности всех её возможных значений, то для этой случайной величины можно записывать H (Y ).

Джон Уайлдер Тьюки (1915-2000) -
американский математик. Тьюки избрал
бит для обозначения одного разряда
в двоичной системе счисления

Шеннон назвал функцию H (X )энтропией по совету Джона фон Неймана .

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

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

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

7. Энтропия Колмогорова

Андрей Николаевич
Колмогоров (1903-1987) -
советский учёный, один из крупнейших
математиков XX века

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

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

В своих работах по теории информации и в области теории динамических систем А.Н. Колмогоров обобщил понятие энтропии на эргодические случайные процессы через предельное распределение вероятностей. Чтобы понять смысл этого обобщения, необходимо знать основные определения и понятия теории случайных процессов.

Значение энтропии Колмогорова (еще называемой K-энтропией ) задает оценку скорости потери информации и может интерпретироваться как мера «памяти» системы, или мера скорости «забывания» начальных условий. Её можно также рассматривать как меру хаотичности системы.

8. Энтропия Реньи

Альфред Реньи (1921-1970) -
венгерский математик, создатель
Математического института в Будапеште,
ныне носящего его имя

Ввёл однопараметрический спектр энтропий Реньи.

С одной стороны, энтропия Реньи представляет собой обобщение энтропии Шеннона. А с другой стороны, одновременно с этим она представляет собой обобщение расстояния (расхождения) Кульбака-Лейблера . Отметим также, что именно Реньи принадлежит полное доказательство теоремы Хартли о необходимом количестве информации.

Расстояние Кульбака-Лейблера (информационная дивергенция, относительная энтропия) - это несимметричная мера удалённости друг от друга двух вероятностных распределений .

Обычно одно из сравниваемых распределений является «истинным» распределением, а второе распределение - предполагаемым (проверяемым) распределением, являющимся приближением первого.

Пусть X , Y - это конечные дискретные случайные величины, для которых области возможных значений принадлежат заданному множеству и известны функции вероятности: P (X = a i ) = p i и P (Y = a i ) = q i .

Тогда значение DKL расстояния Кульбака-Лейблера вычисляется по формулам

D KL (X , Y ) =, D KL (Y , X ) = .

В случае абсолютно непрерывных случайных величин X , Y , заданных своими плотностями распределения, в формулах для вычисления значения расстояния Кульбака-Лейблера суммы заменяются соответствующими интегралами.

Расстояние Кульбака-Лейблера всегда является неотрицательным числом, при этом оно равно нулю D KL (X , Y ) = 0 тогда и только тогда, когда для заданных случайных величин почти всюду справедливо равенство X = Y .

В 1960 году Альфред Реньи предлагает своё обобщение энтропии.

Энтропия Реньи представляет собой семейство функционалов для количественного разнообразия случайности системы. Реньи определил свою энтропию как момент порядка α меры ε-разбиения (покрытия).

Пусть α - заданное действительное число, удовлетворяющее требованиям α ≥ 0, α ≠ 1. Тогда энтропия Реньи порядка α определяется формулой H α = H α (X ), где p i = P (X = x i ) - вероятность события, состоящего в том, что дискретная случайная величина X окажется равна своему соответствующему возможному значению, n - общее число различных возможных значений случайной величины X .

Для равномерного распределения, когда p 1 = p 2 =…= p n =1/n , все энтропии Реньи равны H α (X ) = ln n .

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

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

Рассмотрим некоторые частные случаи энтропии Реньи для конкретных значений порядка α:

1. Энтропия Хартли : H 0 = H 0 (X ) = ln n , где n - мощность области возможных значений конечной случайной величины X , т.е. количество различных элементов, принадлежащих множеству возможных значений;

2. Информационная энтропия Шеннона : H 1 = H 1 (X ) = H 1 (p ) (определяется как предел при α → 1, который несложно найти, например, с помощью правила Лопиталя);

3. Корреляционная энтропия или столкновение энтропии : H 2 = H 2 (X )= - ln (X = Y );

4. Min-энтропия : H ∞ = H ∞ (X ).

Отметим, что для любого неотрицательного значения порядка (α ≥ 0) всегда выполняются неравенства H ∞ (X ) ≤ H α (X ). Кроме того, H 2 (X ) ≤ H 1 (X ) и H ∞ (X ) ≤ H 2 (X ) ≤ 2·H ∞ (X ).

Альфред Реньи ввёл не только свои абсолютные энтропии (1.15), он определил также спектр мер расхождений, обобщающих расхождения Кульбака-Лейбнера.

Пусть α - заданное действительное число, удовлетворяющее требованиям α > 0, α ≠ 1. Тогда в обозначениях, использованных при определении значения D KL расстояния Кульбака-Лейблера, значение расхождения Реньи порядка α определяется формулами

D α (X , Y ), D α (X , Y ).

Расхождение Реньи также называют alpha -расхождением или α-дивергенцией. Сам Реньи использовал логарифм по основанию 2, но, как всегда, значение основания логарифма абсолютно неважно.

9. Энтропия Тсаллиса

Константино Тсаллис (род. 1943) -
бразильский физик
греческого происхождения

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

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

Энтропия Тсаллиса Sq , часто называемая неэкстенсивной (неаддитивной) энтропией, определяется для n микросостояний согласно следующей формуле:

S q = S q (X ) = S q (p ) = K · , .

Здесь K - размерная константа, если размерность играет важную роль для понимания задачи.

Тсаллис и его сторонники предлагают развивать «неэкстенсивную статистическую механику и термодинамику» в качестве обобщения этих классических дисциплин на случай систем с длинной памятью и/или дальнодействующими силами.

От всех других разновидностей энтропии, в т.ч. и от энтропии Реньи, энтропия Тсаллиса отличается тем, что не является аддитивной. Это принципиальное и важное отличие .

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

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

Начиная с 1988 года, когда Константино Тсаллис предложил свою энтропию, появилось значительное число приложений термодинамики аномальных систем (с длиной памятью и/или с дальнодействующими силами), в том числе и в области термодинамики гравитирующих систем.

10. Квантовая энтропия фон Неймана

Джон (Янош) фон Нейман (1903-1957) -
американский математик и физик
венгерского происхождения

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

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

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

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

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

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

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

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

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

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

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

Кстати, именно Рудольфу Клаузиусу принадлежит одна из формулировок второго начала термодинамики: «Невозможен процесс, единственным результатом которого являлась бы передача тепла от более холодного тела к более горячему» .

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

Со времени открытия второго начала термодинамики необратимые процессы играли уникальную роль в физической картине мира. Так, знаменитая статья 1849 года Уильяма Томпсона , в которой приведена одна из первых формулировок второго начала термодинамики, называлась «Об универсальной тенденции в природе к диссипации механической энергии».

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

Илья Романович Пригожин (1917-2003) -
бельгийско-американский физик и
химик российского происхождения,
лауреат Нобелевской премии
по химии 1977 года

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

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

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

Второй вопрос : можно ли признать сферу применения энтропийного подхода обширной или все приложения энтропии и второго начала термодинамики ограничиваются самой термодинамикой и смежными направлениями физической науки?

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

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

Говоря о прикладной математике, нельзя не упомянуть приложения принципа максимума энтропии.

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

Упомянем лишь один оригинальный результат термодинамики чёрных дыр: энтропия чёрной дыры равна четверти площади её поверхности (площади горизонта событий) .

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

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

А.В. Сигал , доктор экономических наук, Крымский университет имени В.И. Вернадского

Информация и энтропия

Обсуждая понятие информация, невозможно не затронуть другое смежное понятие – энтропия. Впервые понятия энтропия и информация связал К.Шеннон.

Клод Элвуд Шеннон (Claude Elwood Shannon ), 1916-2001 - дальний родственник Томаса Эдисона, американский инженер и математик, был сотрудником Bell Laboratories с 1941 дo 1972 г. В его работе "Математическая теория связи" (http://cm.bell-labs.com/cm/ms/what/shannonday/), опубликованной в 1948 г., впервые определялась мера информационного содержания любого сообщения и понятие кванта информации - бита. Эти идеи легли в основу теории современной цифровой связи. Другая работа Шеннона "Communication Theory of Secrecy Systems", опубликованная в 1949 г., способствовала превращению криптографии в научную дисциплину. Он является основателем теории информации , нашедшей применение в современных высокотехнологических системах связи. Шеннон внес огромный вклад в теорию вероятностных схем, теорию автоматов и теорию систем управления - науки, объединяемые понятием «кибернетика».

Физическое определение энтропии

Впервые понятие энтропии ввел Клаузиус в 1865 г. как функцию термодинамического состояния системы

где Q – теплота, T - температура.

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

Л.Больцман (1872г.) методами статистической физики вывел теоретическое выражение энтропии

где К – константа; W – термодинамическая вероятность (количество перестановок молекул идеального газа, не влияющее на макросостояние системы).

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

Сам Больцман в 1886г. попытался с помощью энтропии объяснить, что такое жизнь. По мнению Больцмана, жизнь это явление, способное уменьшать свою энтропию. Согласно Больцману и его последователям, все процессы во Вселенной изменяются в направлении хаоса. Вселенная идет к тепловой смерти. Этот мрачный прогноз долго господствовал в науке. Однако углубление знаний об окружающем Мире постепенно расшатали эту догму.

Классики не связывали энтропию с информацией .

Энтропия как мера информации

Заметим, что понятие "информация" часто трактуется как "сведения", а передача информации осуществляется с помощью связи. К. Шеннон рассматривал энтропию как меру полезной информации в процессах передачи сигналов по проводам.

Для расчета энтропии Шеннон предложил уравнение, напоминающее классическое выражение энтропии, найденное Больцманом. Рассматривается независимое случайное событие x с N возможными состояниями и p i -вероятность i-го состояния. Тогда энтропия события x

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

Величина

H i = P i log 2 1/P i = ‑P i log 2 P i ,

называется частной энтропией, характеризующей только i-e состояние.

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

Для монеты число равновероятных возможностей N = 2. Вероятность выпадения орла (решки) равна 1/2.

При бросании кости получаем информацию о выпадении определенного количества очков (например, трех). В каком случае мы получаем больше информации?

Для кости число равновероятных возможностей N = 6. Вероятность выпадения трех очков кости равна 1/6. Энтропия равна 2.58. Реализация менее вероятного события дает больше информации. Чем больше неопределенность до получения сообщения о событии (бросание монеты, кости), тем большее количество информации поступает при получении сообщения.

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

Измерение информации

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

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