1.4. Энтропия и производительность источника сообщений

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

(1.7)

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

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

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

, (1.7а)

где — объем алфавита источника; — вероятность выбора -гo элемента (-й буквы).

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

. (1.8)

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

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

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

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

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

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

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

Цепью Маркова -гo порядка называется последовательность зависимых испытаний, при которой условная вероятность некоторого исхода в -м испытании, когда известны исходы в предыдущих испытаниях, не зависит от более ранних исходов. Другими словами, при

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

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

(1.9)

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

(1.10)

Выражение (1.7а) является частным случаем (1.10) при , т. е. при единственном состоянии источника. Если бы мы не учитывали вероятностных связей между элементами сообщения и исходили из безусловных вероятностей , определяемых по (1.9), то за энтропию источника на один элемент следовало бы принять

. (1.11)

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

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

. (1.12)

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

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

В таком источнике избыточность алфавита равна 0,12.

Пусть теперь вероятности выбора зависят от одного предшествующего элемента, а именно: и . Здесь обозначает вероятность выбора элемента при условии, что предыдущим был элемент и т.д. Легко убедиться, что безусловные вероятности обоих элементов в таком источнике одинаковы и равны 0,5. Этот источник имеет два состояния, определяемые последним выбранным элементом, причем оба состояния имеют вероятности, равные 0,5. Тогда из (1.10) получим дв. ед.; избыточность алфавита, вызванная вероятностными связями в таком источнике .

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

и .

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

дв. ед.

и избыточность алфавита .

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

Если учесть неравные вероятности появления букв в тексте и зависимость этих вероятностен от ранее предшествовавших букв, то по данным различных авторов энтропия, приходящаяся на одну букву, находится в пределах от 1 до 2,5 дв. ед. Такой значительный разброс результатов вызван трудностью учета всех вероятностных связей, простирающихся на значительное число последовательных букв. К тому же величина энтропии в некоторой степени зависит от характера текста. Исходя из этих данных, избыточность русского алфавита лежит в пределах от 0,5 до 0,8. По-видимому, вторая цифра ближе к действительности. Близкие к этим данные получены и для алфавитов многих других языков.

Определенная выше энтропия источника на элемент сообщения зависит от того, каким образом сообщения расчленяются на элементы, т. е. от выбора алфавита. Однако энтропия обладает важным свойством аддитивности. Пусть источник сообщения с объемом алфавита имеет энтропию на элемент сообщения (с учетом всех вероятностных характеристик), равную . Произведем укрупнение алфавита, считая каждую последовательность из любых букв первичного алфавита одним элементом нового, вторичного, алфавита. Очевидно, что объем вторичного алфавита . Покажем, что энтропия на один элемент вторичного алфавита равна . Из определения количества информации следует, что в некотором конкретном элементе вторичного алфавита содержится ровно столько же информации, сколько ее содержится в элементах первичного алфавита, входящих в его состав. Количество информации в одном конкретном элементе первичного алфавита является случайной величиной, принимающей различные значения для различных элементов. Количество информации в элементе вторичного алфавита является суммой случайных величин . Математическое ожидание величины , равное по определению , как известно [11], равно сумме математических ожиданий слагаемых (), а так как каждое из последних равно , то

. (1.13)

Определим избыточность вторичного алфавита . Максимальная энтропия для алфавита объемом равна

откуда, учитывая (1.13),

. (1.14)

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

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

. (1.15)

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

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