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

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

Первую количественную метрику предложил Хартли в 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 бит/символ.

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

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

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

Не претендуя на строгое определение понятия «информация», подчеркнем два необходимых ее атрибута: 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 бит. Отсюда объем фазового пространства, приходящийся на один бит, равен

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

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

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

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

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

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

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

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

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

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

.

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

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

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

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

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

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

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

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

,

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

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

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

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

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

[бит/с],

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

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

Как мы можем измерить информацию в событии? Сколько информации нам доставляет событие? Давайте ответим на эти вопросы с помощью примеров.

Пример F.1

Вообразите человека, сидящего в комнате. Глядя из окна, он может ясно видеть, что сияет солнце. Если в этот момент он получает сообщение (событие) от соседа, который говорит "Хороший день", это сообщение содержит какую-либо информацию? Конечно нет! Человек уже уверен, что это день и погода хорошая. Сообщение не уменьшает неопределенности его знаний.

Пример F.2

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

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

F.2. Энтропия

Предположим, что S - распределение вероятностей конечного числа событий (См. "приложение D"). Энтропия или неопределенность в S может быть определена как:

где - возможный результат одного испытания. Обратите внимание, что, если. P (s) = 0 , то мы будем считать, что P(S) x равно 0 , чтобы избежать деления на 0.

Пример F.3

Предположим, что мы бросаем правильную монету. Результаты - "орел" и "решка", каждый с вероятностью 1/2, и это означает

H (S) = P(орел) x + P (решка) x H (S) = (1/2) x = 1 бит

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

Пример F.4

Предположим, что мы бросаем неправильную (поврежденную) монету. Результаты выпадения "орла" и "решки" следующие P ("орел") = 3/4 и P ("решка") = 1/4 . Это означает, что

H (S) = (3/4) x + (1/4) x = 0,8 бит

Этот пример показывает, что результат бросания неправильной монеты дает нам только 0,8 битов информации (неопределенность). Количество информации здесь меньше, чем количество информации в Примере F.3, потому что мы ожидаем получить "орлов" большее число раз, чем "решек".

Пример F.5

Теперь предположим, что мы бросаем полностью неправильную монету, в которой результат является всегда "орел", P ("орел") = 1 и P ("решка") = 0 . Энтропия в этом случае

H (S) = (1) x + (0) x = (1) x (0) + (0) = 0

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

Максимальная энтропия

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

H max = log 2 n бит

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

Пример F.6

Предположим, что бросается шестигранная игральная кость. Энтропия испытания равна

Минимальная энтропия

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

H min (S) = 0 битов

Другими словами, эта формула определяет нижний предел энтропии для любого набора вероятностей.

Энтропия любого набора вероятностей находится между 0 бит и log 2 n бит, где n - число возможных результатов .

Интерпретация энтропии

Энтропию можно воспринимать как число бит , которым можно представить каждый результат из множества вероятностей, в том случае, когда результаты одинаково вероятны. Например, когда возможное случайное распределение имеет восемь возможных результатов, каждый результат может быть представлен в виде трех бит (от 000 до 111 ). Когда мы получаем результат эксперимента, мы можем сказать, что получили 3 бита информации. Энтропия этого набора вероятностей - также 3 бита (ln 2 8 = 3 ).

Совместная энтропия

Когда мы имеем два набора распределения вероятностей, S 1 и S 2 , мы можем определить совместную энтропию H (S 1 , S 2) как

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

Мы часто должны знать неопределенность распределения вероятностей S 1 , при условии получения результата, который определяется неопределенностью распределения вероятности S 2 . Она называется условной энтропией H (S 1 | S 2) . Может быть доказано, что

H (S 1 | S 2) = H (S 1 , S 2) - H (S 2) бит

Другие соотношения

Приведем здесь без доказательства некоторые другие соотношения для энтропии:

1. H (S 1 , S 2) = H (S2 | S 1) + H (S 1) = H (S 1 | S 2) + H (S2)
2. H (S 1 , S 2) <= H (S 1) + H (S2)
3. H (S 1 | S 2) <= H (S 1)
4. H (S 1 , S2, S3) = H (S 1 | S2, S3) + H (S 1 , S3)

Второе и третье соотношения справедливы, если S 1 и S 2 статистически независимы.

Пример F.7

В криптографии, если P - распределение вероятностей исходного текста, C - распределение вероятностей зашифрованного текста и K - распределение вероятностей ключей, то H (K|C) может интерпретироваться как сложность атаки зашифрованного текста, в которой знание C может привести к знанию K .

Пример F.8

В криптографии, учитывая исходный текст и ключ, детерминированный алгоритм шифрования создает уникальный зашифрованный текст, что означает H (C | K, P) = 0 . Также учитывая зашифрованный текст и ключевой алгоритм дешифрования, создается уникальный исходный текст, что означает H (P | K, C) = 0 . Если дан зашифрованный текст и исходный текст, ключ также определяется уникально: H (K | P, C) = 0 .

Совершенная секретность

В криптографии, если P , K и C - пространства выборки вероятности исходного текста, зашифрованного текста и ключа соответственно, то мы имеем H (P|C) <=H (P) . Это может быть интерпретировано так: неопределенность P данного C меньше или равна неопределенности P . В большинстве криптографических систем, справедливо отношение H (P|C)< H (P) , что означает, что перехват зашифрованного текста уменьшает знание, которое требуется для того, чтобы найти исходный текст. Криптографическая система обеспечивает совершенную секретность , если соблюдается соотношение H (P|C)=H (P) , - это означает, что неопределенность исходного текста и данного зашифрованного текста - одна и та же неопределенность исходного текста. Другими словами, Ева не получает никакой информации, перехватив зашифрованный текст; она по-прежнему должна исследовать все возможные варианты.

Криптографическая система обеспечивает совершенную секретность, если H (P | C) = H (P) .

Пример F.9

В предыдущих лекциях мы утверждали, что одноразовый шифр блокнота обеспечивает совершенную секретность. Докажем этот факт, используя предыдущие соотношения энтропии. Предположим, что алфавит - только 0 и 1 . Если длина сообщения - L , может быть доказано, что ключ и зашифрованный текст состоят из 2 L символов, в которых каждый символ является одинаково вероятным. Следовательно, H (K) = H (C) = log 2 2 L = L . Используя отношения, полученные в примере F.8, и то, что H (P, K) = H (P) + H (K) , потому что P и K независимы, мы имеем

H (P, K, C) = H (C|P, K) + H (P, K) = H (P, K) = H (P) + H (K) H (P, K, C) = H (K|P, C) + H (P, C) = H (P, C) = H (P|C) + H (C)

Это означает, что H (P | C) = H (P)

Пример F.10

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

F.3. Энтропия языка

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

Энтропия произвольного языка

Предположим, что язык использует N букв и все буквы имеют равную вероятность появления. Мы можем сказать, что энтропия этого языка - H L = log 2 N . Например, если мы используем двадцать шесть прописных букв (от A до Z), чтобы передать наше сообщение, то