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

Л Е К Ц И Я № 29

Тема:

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

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

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

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

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

;

(1.4)

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

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

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

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

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

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

;

(1.5)

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

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

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

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

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

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

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

Рассмотрим пример (скачки). В заезде участвуют 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 века появились первые попытки определения абсолютного информационного содержания предложений естественного языка. Стоит отметить, что сам Шеннон однажды заметил, что смысл сообщений не имеет никакого отношения к его теории информации, целиком построенной на положениях теории вероятностей. Но его способ точного измерения информации наводил на мысль о возможности существования способов точного измерения информации более общего вида, например, информации из предложений естественного языка. Примером одной из таких мер является функция , где - это предложение, смысловое содержание которого измеряется, -

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

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

Не претендуя на строгое определение понятия «информация», подчеркнем два необходимых ее атрибута: 1) информация предполагает выбор одного (или нескольких) вариантов из многих возможных, 2) сделанный выбор должен быть запомнен. Подчеркнем: второе условие - запоминание информации - является очень важным. Впервые на это обратил внимание Кастлер [П26] в 1960. г. В процессах передачи информации «запоминаемость» играет меньшую роль, чем при рецепции, обработке и хранении информации. Действительно, передающая система обязана запомнить информацию лишь на время передачи, которое в принципе может быть коротким. В биологии условие запоминания на длительный срок, напротив, играет важную роль.

Количеством информации называют величину

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

Ничего не известно. Основание логарифма (т. е. двоичная система) выбрано для удобства; единицей информации в этой системе является один бит; он соответствует выбору одного варианта из двух возможных.

Выражение (12.8) легко обобщается на случай, когда a priori N вариантов могут реализоваться с вероятностями а реализуются a posteriori с вероятностями тогда

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

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

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

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

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

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

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

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

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

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

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

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

Совпадение (12.11) и (12.12) по форме послужило основанием для утверждения о тождественности понятий информации и энтропии. Точнее, утверждается, что энтропия есть недостающая информация о состоянии системы и (или) информация есть недостающая энтропия, т. е. разность между максимальной энтропией, которой

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

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

Обсудим вопрос более детально.

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

Блюменфельд (см. [П61) на ряде биологических примеров (клетка, организм и т. д.) показал, что содержащаяся в объекте энтропия во много раз (на несколько порядков) превышает имеющуюся нем информацию. Разница еще больше в современных неживых информационных системах (например, в печатном тексте энтропия превышает информацию примерно в 1010 раз).

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

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

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

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

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

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

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

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

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

При достаточно большой (макроскопической) величине с барьер составляет

Таким образом, в этом случае увеличение энтропии, приходящееся на один бит информации, равно

или в информационных единицах:

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

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

Прирост энтропии на один бит информации при этом равен

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

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

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

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

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

Если известно, что в данный момент система находится в одной (любой) из ячеек то

и между микроинформацией и энтропией имеет место простое соотношение:

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

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

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

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

где число стационарных устойчивых макросостояний, о которых известно, что система находится в одном из них (но неизвестно, в каком именно).

Согласно определению, информационная энтропия связана с информацией соотношением

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

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

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

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

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

Энтропи́я (информационная) - мера хаотичности информации , неопределённость появления какого-либо символа первичного алфавита . При отсутствии информационных потерь численно равна количеству информации на символ передаваемого сообщения.

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

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

Формальные определения

Информационная энтропия для независимых случайных событий x с n возможными состояниями (от 1 до n ) рассчитывается по формуле:

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

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

В общем случае b -арная энтропия (где b равно 2, 3, …) источника с исходным алфавитом и дискретным распределением вероятности где p i является вероятностью a i (p i = p (a i ) ) определяется формулой:

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

Альтернативное определение

Другим способом определения функции энтропии H является доказательство, что H однозначно определена (как указано ранее), если и только если H удовлетворяет условиям:

Свойства

Важно помнить, что энтропия является количеством, определённым в контексте вероятностной модели для источника данных. Например, кидание монеты имеет энтропию − 2(0,5log 2 0,5) = 1 бит на одно кидание (при условии его независимости). У источника, который генерирует строку, состоящую только из букв «А», энтропия равна нулю: . Так, например, опытным путём можно установить, что энтропия английского текста равна 1,5 бит на символ, что конечно будет варьироваться для разных текстов. Степень энтропии источника данных означает среднее число битов на элемент данных, требуемых для её зашифровки без потери информации, при оптимальном кодировании.

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

Математические свойства

Эффективность

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

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

Энтропия ограничивает максимально возможное сжатие без потерь (или почти без потерь), которое может быть реализовано при использовании теоретически - типичного набора или, на практике, - кодирования Хаффмана , кодирования Лемпеля - Зива - Велча или арифметического кодирования .

Вариации и обобщения

Условная энтропия

Если следование символов алфавита не независимо (например, во французском языке после буквы «q» почти всегда следует «u», а после слова «передовик» в советских газетах обычно следовало слово «производства» или «труда»), количество информации, которую несёт последовательность таких символов (а следовательно и энтропия) очевидно меньше. Для учёта таких фактов используется условная энтропия.

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

где i - это состояние, зависящее от предшествующего символа, и p i (j ) - это вероятность j , при условии, что i был предыдущим символом.

Так, для русского языка без буквы « » .

Через частную и общую условные энтропии полностью описываются информационные потери при передаче данных в канале с помехами. Для этого применяются так называемые канальные матрицы . Так, для описания потерь со стороны источника (то есть известен посланный сигнал), рассматривают условную вероятность получения приёмником символа b j при условии, что был отправлен символ a i . При этом канальная матрица имеет следующий вид:

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

Для вычисления потерь при передаче всех сигналов используется общая условная энтропия:

Означает энтропию со стороны источника, аналогично рассматривается - энтропия со стороны приёмника: вместо всюду указывается (суммируя элементы строки можно получить p (a i ) , а элементы диагонали означают вероятность того, что был отправлен именно тот символ, который получен, то есть вероятность правильной передачи).

Взаимная энтропия

Взаимная энтропия, или энтропия объединения , предназначена для расчёта энтропии взаимосвязанных систем (энтропии совместного появления статистически зависимых сообщений) и обозначается H (A B ) , где A , как всегда, характеризует передатчик, а B - приёмник.

Взаимосвязь переданных и полученных сигналов описывается вероятностями совместных событий p (a i b j ) , и для полного описания характеристик канала требуется только одна матрица:

Для более общего случая, когда описывается не канал, а просто взаимодействующие системы, матрица необязательно должна быть квадратной. Очевидно, сумма всех элементов столбца с номером j даст p (b j ) , сумма строки с номером i есть p (a i ) , а сумма всех элементов матрицы равна 1. Совместная вероятность p (a i b j ) событий a i и b j вычисляется как произведение исходной и условной вероятности,

Условные вероятности производятся по формуле Байеса . Таким образом имеются все данные для вычисления энтропий источника и приёмника:

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

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

Взаимная энтропия обладает свойством информационной полноты - из неё можно получить все рассматриваемые величины.

История

Примечания

См. также

Ссылки

• Claude E. Shannon. A Mathematical Theory of Communication (англ.)
• С. М. Коротаев.