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

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

где суммирование, как видно, производится во всем возможным последовательностям длины с элементами, взятыми из алфавита объёма К. Для того, чтобы получить исчерпывающую информационную характеристику источника сообщений, который, вообще говоря, может выдавать последовательности неограниченной длины, нужно вычислить предел среднего количества информации отнесённый к одному символу последовательности. Полученная величина, которую мы, следуя ещё установленной Шенноном традиции [29], обозначим через называется энтропией источника сообщений, т.е.

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

где — вероятности выдачи источником символов причём они не зависят от номера элемента последовательности, так как

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

1. , причём тогда и только тогда, когда одна из последовательностей имеет единичную вероятность, а все остальные - нулевую. (Это свойство очевидно из определения энтропии.)

2. Для любого стационарного источника сообщений

Поскольку выражение в правой части (6.12) - это энтропия источника без памяти, то данное свойство означает, что память уменьшает энтропию источника. Данное свойство, хотя очевидное, требует специального доказательства [16], которое здесь не приводим.

3. Для любого стационарного источника сообщений

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

Из свойства 2 следует, что при доказательстве неравенств (6.13) мы сразу можем ограничиться источниками без памяти. Для доказательства свойства 3 рассмотрим разность

Далее воспользуемся известным неравенством

Тогда

Равенство в (6.15) будет иметь место только при что и доказывает данное свойство.

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

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

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

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

Известно, что избыточность естественных языков является весьма важным свойством, позволяющим воспринимать рукописный или искажённый текст, слышать речь в больших акустических помехах и т. д. Теория информации, как мы убедимся в дальнейшем, позволяет количественно оценить эти возможности. Для экспериментального вычисления энтропии или избыточности естественных языков используются статистические данные о частости, с которой встречаются буквы текста и их сочетания (биграммы, триграммы и т.д.). Так, если воспользоваться так называемой статистикой английского языка порядка (т.е. частостью отдельных букв), то энтропия оказывается равной 4,03 бит/букву, а если статистикой порядка, то 3.32 бит/букву. В то же время более точную оценку энтропии можно получить, воспользовавшись, например, предложенным ещё К. Шенноном "методом случайного угадывания" [29]. Такой подход даёт верхнюю оценку энтропии английского языка 2 бит/букву и нижнюю 1 бит/букву. Это позволяет сделать вывод, что основная избыточность естественного языка определяется многомерными зависимостями между буквами (корреляцией текста), и для её использования необходимо знать эти зависимости Аналогичные выводы можно сделать и относительно русского и других языков, хотя их энтропии и несколько отличаются друг от друга. (Известно, например, что одна и та же пьеса В. Шекспира идёт в Берлине дольше, чем в Лондоне.)

Рис. 6.1. Энтропия двоичного источника без памяти

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

Вид этой функции показан на рис. 6.1 для основания логарифма, равного двум.

Если источник сообщений имеет фиксированную скорость симв/с, то определим производительность источника как энтропию в единицу времени, (секунду)

Максимум обычно называют информационной скоростью источника.