Методическое пособие Теория информации-2

1.4. Энтропия дискретной информации

Получение информации всегда приводит к уменьшению неопределённости. В соответствии с работами американского математика Шеннона меру неопределённости или энтропию дискретного источника информации можно описать следующим образом:

O = − K <I log <I

(1.18)

где O – энтропия дискретного источникаI информации, представляющая собой

среднюю языковую информацию, приходящуюся на символ или на сообщение;

<I – вероятность появления -го символа или сообщения.

Формальная структура выражения (1.18) совпадает с энтропией

физической системы, определенной ранее Больцманом. Согласно второму
закону термодинамики энтропия	O	замкнутой	системы	определяется
выражением:	ln EI
O = − 1 K EI				(1.19)
F IQ	F
где F – число молекул в пространстве; EI – число молекул,				обладающих
скоростью RI + ∆R; H – номер молекулы; 5		– количество молекул.
Так как отношение US-T – это вероятность того,			что молекула обладает

скоростью RI + ∆R, то выражение (1.19) преобразуется к уравнению (1.18).

Таким образом, величина O характеризует степень разнообразия состояний системы.

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

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

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

O = − K <I log <I = − log <I K <I = − log <I = log 5 ,		(1.20)
I	I
	21

поскольку	− log <I	= − log =	= log 5.
∑I <I = 1; <I = =
O = log 32 = 5		дв. ед.
Энтропия, приходящаяся	на букву алфавита русского языка,

характеризуемого частотами повторения, представленным в табл. 1.5, в

соответствии с выражением (1.18) составит O 4.36 дв. ед. Таким образом,

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

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

удельная	величина	– энтропия	на	символ,	которая	равняется средней
информации, приходящейся на символ сообщения.
Рассмотрим основные свойства энтропии:
1. Энтропия является вещественной и неотрицательной величиной, так
как для любого H, лежащего в интервале от 1 до					5, вероятность <I изменяется в
интервале от 0 до 1, следовательно, величина log <I отрицательна, а величина
−<I log <I положительна.
2.	Энтропия – величина ограниченная.
	limT	−<I log <I = limT		log @<IA		(1.21)
	\ →#		\ →#	1
Обозначив величину \T = ^				<I		правилом Лопиталя,
			и воспользовавшись

получим выражение (1.22).

22

			I	∞ log ^	∞ @^A log `			(1.22)
T		I		= _lim→ ^	= _lim→		= 0
						1
\lim→#		−< log <

3. Энтропия принимает нулевое значение только в том случае, когда вероятность одного из состояний равна 1 (все остальные вероятности равны 0;

неопределённость отсутствует).

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

что видно из выражения (1.20).

5. Энтропия системы, принимающей два состояния, изменяется от 0 до

1, достигая максимума при равенстве их вероятностей < (рис. 1.3).

Рис. 1.3. Энтропия системы, принимающей два состояния

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

O = −a< log < + 1 − < log 1 − <b (1.23)

Принимая во внимание, что для двух равновероятных состояний системы вероятности < = 1 − < = , получим:

O = − c2 log 2	+ 2 log 2d = log 2 = 1 дв. ед.	(1.24)

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

23

Рассмотрим данное положение на примере двух статистически независимых источников информации e и f. Под объединением двух источников e и f понимают обобщённый источник информации (ef),

характеризующийся вероятностями < gI I всех возможных комбинаций

υ

состояний gI источника e и υI источника f. Тогда энтропия объединения двух статистически независимых источников информации будет записываться следующим образом:

O ef = − K K <hgIRij log <hgIRij,							(1.25)
		IQ iQ
где <hgIRij – вероятность совместной реализации состояний, которая в случае
независимых источников информации				e и f равна произведению вероятности
состояний каждого из источников.
I	i	I	i				(1.26)
Подставив	выражение		(1.26)	в уравнение	(1.25) и	учитывая, что
∑IQ= < gI = 1 и	∑iQk	<hRij = 1, получим равенство (1.27).
O ef = − K K < gI <hRij log < gI <hRij =
=		IQ iQ	k		=
		k				=	(1.27)
= − K <(gI) log <(gI) K <hRij − K <hRij log <hRij K <(gI)
IQ		iQ	iQ		IQ
= − K <(gI) log <(gI) − K <hRij log <hRij = O(e) + O(f)
IQ		iQ

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

(1.28)

7. Энтропия объединения нескольких статистически связанных источников информации рассчитывается по формуле (1.29).

24

p	pq	pqr	(1.29)
где Op f и последующие переменные характеризуют условную энтропию.
Рассмотрим вывод уравнения (1.29) на примере объединения двух
статистически связанных источников информации e		и f. Объединение данных
источников информации характеризуется матрицей вероятностей < gIυI всех
возможных комбинаций состояний gI источника		e	и υI источника f.
Вероятности < gIυI совместной реализации взаимозависимых состояний gI и
υI могут быть выражены через	условные вероятности		< ctsuTd или < @tsuTA, в

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

<hgIRij = < gI < cgiId = <hRij< vRiIw						(1.30)
Энтропия вероятности объединения двух статистически связанных
источников примет вид:
O ef = − K K < gI < cRi d log < gI < cRi d =
	IQ iQ	gI		gI		(1.31)
= − K < gI log < gI − K < gI K < cRi d log < cRi d
=		=	k	gI	gI
IQ		IQ	iQ
Величина	− ∑iQk < @tsuTA log < @tsuTA,		взятая	для	реализованного	состояния
H-го источника e, где H a1, 5b, в уравнении (1.31) представляет собой частную
условную энтропию источника f, обозначаемую					OpI f . При усреднении
данной величины по всем состояниям H			системы e получаем полную условную
энтропию системы f :

Op f = K < gI ∙ OpI f	(1.32)
IQ
Учитывая выражения(1.18) и (1.32), преобразуем уравнение (1.31) к
следующему виду:
p	(1.33)
25

Таким образом, энтропия объединения двухe связанных источников e и f

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

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

(1.34)

Ещё раз стоит подчеркнуть, что энтропия в теории информации является мерой свободы выбора в сообщениях, а также мерой средней информации в длинных сообщениях, передаваемых по каналам связи. Выражение для энтропии (1.18) совпадает с введённым Больцманом и Гиббсом выражением для энтропии в статистической механике (1.19). Такое совпадение позволяет применять тот же математический аппарат: в теории информации энтропия максимальна, когда отсутствуют ограничения в свободе выбора сообщений, а в статистической механике – когда имеет место полная беспорядочность.

1.5. Избыточность информации. Шум и отрицательная информация

Отношение энтропии на символ, найденное для определённого языка, к

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

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

которые служат для проверки и корректировки прогноза.

26

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

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

Полученная информация определяется уравнением (1.3). В отсутствии шумов вероятность у приёмника данного события после приёма сообщения всегда равна единице. При наличии шумов, вероятности, входящие в выражение (1.3), будут равны вероятностям фактически происходящих событий независимо от тогоH , правильны ли сообщенияm о них. Например, если передано было сообщение , а принято сообщение , то полученная информация будет определяться выражением:

			полученная информация
		вероятность у приёмника того что					m
			,
			было передано сообщение ,					~
	{при условии что принято сообщениеH								< H i	(1.35)
	y					H		|
= log		априорная вероятность у приёмника						= log
			факта передачи сообщения						< H
Рассмотрим данный случай более′подробно. Пусть I – вероятность того,
что переданное сообщение было				H; i	–	вероятность			того, что принятое в
присутствии			шумов сообщение	было	m	независимо			от того, каково было

переданное сообщение; <Ii – вероятность того, что принятое в присутствии шумов сообщение было m при условии, что было передано сообщение H. Данные

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

27

I	I	Ii	i′	(1.36)
		I		(1.37)
i
		i′
I				(1.38)
i I		I	Ii	(1.39)

В отсутствии шумов справедливо следующее условие:

	Ii	при	совпадающем с	(1.40)
		0 при H, не совпадающем с m
				H не должно быть равно
	В общем случае количество сообщений
	количеству сообщений m вследствие шумов. Определим вероятность того, что
	передавалось сообщение H при условии, что принято сообщение m, и обозначим
	её переменной < H i. Для		этого воспользуемся	теоремой Байеса, которая

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

	!|‚ =	‚|! ∙ !				,			(1.41)
где !|‚ –			‚
	вероятность	гипотезы			A при			наступлении	события	В
(апостприорная вероятность);		! –		априорная вероятность гипотезы А; ‚
– вероятность	наступления события В;				‚|!		–	вероятность	наступления
события В при истинности гипотезы А.
Тогда, в соответствии с (1.41) можно записать:
	< H i =		I	∙ <′ Ii					(1.42)
				i				H → m, в соответствии
Информация, содержащаяся				в сообщении						с

выражением (1.35) будет равна:

28

в сообщении H → m

= log

i

= log

Ii′

IiI

=

(1.43)

= log <Ii − log i′

H

∙

информация содержащаяся

Поскольку

вероятность

появления

сообщения

H → m

составляет

I ∙ <Ii, то среднюю информацию, приходящуюся на сообщение, при наличии

шумов можно определить следующим образом:

сообщение

= K K I ∙ <Ii ∙ ƒlog <Ii − log i′„ =

средняя информация

i

I

=

= K K I ∙ <Ii log <Ii − K K I ∙ <Ii log i′

(1.44)

i

I

i

I

= O m − OI m ,

= K I K <Ii log <Ii − K i′ log i′

где O m

I

i

i

– энтропия,

приходящаяся

на

сообщение

для

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

принятых сообщений при неизвестных сообщениях на входе, а OI m – условная

энтропия на сообщение для последовательности принятых сообщений при известных сообщениях на входе (в отсутствии шумов OI m = 0 ).

Пример. Пусть дана система, через которую передаются два символа 0 и 1, которые и являются сообщениями. Предположим, что появление любого

сообщения – события равновероятные:
1 = 0.5 =		(1.45)
	#	(1.46)

Присутствующие в канале шумы вносят ошибки таким образом, что в среднем 1 символ из 100 принимается неверно (0 вместо 1 и наоборот), причём

ошибкам одинаково подвержены как 0, так и 1. Тогда:

< = 0.99; <## = 0.99; < # = 0.01; <# = 0.01.

Для принятых сообщений согласно формуле (1.36) имеем:

	′				#	(1.47)

29

#		##		#	(1.48)
′
Согласно выражению (1.4 получаем:					= 0.99,
				< (1) = #.†∙##.†.‡‡
				< (1)# = #.†∙##.†.#	= 0.01,
				< (0) = #.†∙##.†.#	= 0.01,
				< (0)# = #.†∙##.†.‡‡ = 0.99.

Определим количество информации при правильном и ошибочном приёме 1 в соответствии с выражением (1.43):

log ˆ		< (1)		‰ = log		0.5	= 0.985 дв. ед.⁄символ	(1.49)
log ˆ	< 1 #		‰ = log		0.5		= −5.64 дв. ед.⁄символ	(1.50)

Аналогичная ситуация имеет место при правильном и ошибочном приёме

0. Обратим внимание на то, что информация, содержащаяся в ложном сообщении, отрицательна. Средняя информация, приходящаяся на символ,

будет равна:

средняя информация = = 2 ∙ 0.5 ∙ 0.99 ∙ 0.985 − 2 ∙ 0символ.5 ∙ 0.01 ∙ 5.64 = 0.919 дв. ед.⁄символ

Определим среднюю информацию, приходящуюся на символ через

энтропию.

O m

= − ∑i i′ log i′

= −h ′

log ′

+ #′

log #′ j =

= − 0.5 log 0.5 + 0.5 log 0.5

= 1.0

дв. ед.⁄символ.

+

€

O m = − ∑ ∑

<

log <

= −a

< log <

+ <

log <

+

I

log <

I I i Ii

Ii

#

#

<

+ <

log <

b = −a0.5 0.99 log 0.99 + 0.01 log 0.01 +

€ #

##

##

#

#

.

.⁄

€

+0.5 0.99 log 0.99 + 0.01 log 0.01 b = 0.081

символ.

€

дв ед

30