ПЗ№5

1

ЭНТРОПИЯ

Задание 1. Рассчитать энтропию события – бросание игральной кости с шестью гранями при равновероятных исходах.

Решение. Если все варианты равновероятны, то

H(X) = log2 (6) = 2,585 (бит).

Задание 2. Рассчитать энтропию при разных вероятностях выпадения сторон игральной кости:

Р(1) = 0,5; Р(6) = 0,06; Р(2) = Р(3) = Р(4) = Р(5) = 0,11.

Решение. Средняя энтропия всех исходов равна:

H(X) = – [0,5 * log2 0,5 + 4 * (0,11 * log2 0,11) + 0,06 * log2 0,06]. H(X) = 2,344 (бит).

Задание 3. Определить энтропию сообщения из 5 букв, если общее число букв в алфавите равно 32 и все сообщения равновероятны.

Решение. Общее число пятибуквенных сообщений : n = 325. Энтропия равновероятных событий:

Н(Х) = log2 (n) = 5 log2 (32) = 25 (бит).

Задание 4: Определить минимальное количество взвешиваний, которое необходимо произвести на уравновешивающих весах (аптечных), чтобы среди 27 внешне неотличимых монет найти одну фальшивую, более легкую.

Решение. При случайном поиске монеты общая неопределенность одного опыта:

H(X) = log 27 = log 33 = 3 * log 3.

Одно взвешивание имеет 3 исхода: левая чаша легче, правая чаша легче, весы находятся в равновесии. Поэтому после одного взвешивания равномерного количества монет неопределенность уменьшится на величину:

H(X1) = log 3.

Из этих равенств следует, что для снятия полной неопределенности потребуется 3 взвешивания.

Задание 5 : для двух событий X и Y приведены вероятности совместных событий P(X,Y):

	X1	X2	X3
Y1	0.1	0.2	0.3
Y2	0.25	0	0.15

Определить: энтропию сообщений H(X) и H(Y);

2

энтропию совместного события H(X,Y); условные энтропии H(X/Y), H(Y/X).

Решение: P(X1) = 0,1 + 0,25 = 0,35;

P(X2) = 0,2;

P(X3) = 0,3 + 0,15 =0,45;

P(Y1) = 0,1 + 0,2 + 0,3 = 0,6;

P(Y2) = 0,25 + 0,15 = 0,4.

Энтропии отдельных событий:

3

H(X) P(Xi) logP(Xi ) 1,512 (бит);

i 1

2

H(Y) P(Yi ) logP(Yi) 0,917 (бит).

i 1

Энтропия совместного события:

3 2

H(X,Y) P(Xi,Yj ) logP(Xi,Yj ) 2,228 (бит).

i 1 j 1

Условные энтропии:

H(Y/X) H(X,Y) H(X) 2.228 1.512 0.716 (бит);

H(X/Y) H(X,Y) H(Y) 2.228 0.971 1.257 (бит).

Задание 6. Измеряемая величина имеет равновероятное распределение в пределах от х0 до х0 + а. Найти дифференциальную энтропию данной величины.

Решение. Закон равновероятного распределения:

1

(X) a при хo Х хo а,0 приостальных Х.

Формула дифференциальной энтропии:

h(X) (X) log (X)dX .

2

h(X)	1	xo a	log	1	dX log a(бит).
				2 a
	a	x			2
		o

Задание 7. Сигнал формируется в виде двоичного кода с вероятностями появления символов: р(х0) = 0,6; р(х1) = 0,4. Появление любого из символов взаимосвязаны условными вероятностями:

3

р(х0/х0) = 0,1 – вероятность того, что после 0 будет 0; р(х1/х0) = 0,9 – вероятность того, что после 0 будет 1; р(х1/х1) = 0,1 – вероятность того, что после 1 будет 1; р(х0/х1) = 0,9 – вероятность того, что после 1 будет 0. Найти энтропию сигналов.

Решение.

1	1	p(xi/xj) log2 p(xj/xi)
H(X) p(xi)
i 0	j 0

= – (0,1 log2 0,1 + 0,9 log2 0,9) (0,6 + 0,4) = 0,467 (бит).

Задание 8. Вероятности появления четырех событий равны:

Р(х1) = 0,5; Р(х2) = 0,25; Р(х3) = Р(х4) = 0,125.

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

xi, xj

P(xi, xj)

P(xi/xj)

xi, xj

P(xi, xj)

P(xi/xj)

x1,x1

13/32

13/16

x3,x1

0

0

x1,x2

3/64

3/16

x3,x2

0

0

x1,x3

0

0

x3,x3

0

0

x1,x4

0

0

x3,x4

1/8

1

x2,x1

1/16

1/8

x4,x1

1/4

1/2

x2,x2

1/8

1/2

x4,x2

1/16

1/4

x2,x3

3/64

3/8

x4,x3

1/32

1/4

x2,x4

0

0

x4,x3

0

0

Решение. Для зависимых событий (между которыми имеются

корреляционные связи) энтропия рассчитывается по формуле:

4

4

H(X)

p(xi,xj) log2 p(xi/xj) = –13/32 log2 13/16 – 3/64 log2 3/16 –

i 1j 1

1/64 log2 3/16 – 1/16 log2 1/8 – 1/8 log2 1/2 – 3/64 log2 3/8 – 1/4 log2 1/2 –

1/16 log2 1/4 – 2/32 log2 1/4 = 0,886 (бит)

Задание

9.

Передаваемые сигналы

р(y0/x0)

могут иметь два значения с равными

х0

y0

вероятностями: р(х0) = р(х1) = 0,5.

р(y0/x1)=0,01

Вследствие наличия шумов принятые сигналы

могут

быть

зарегистрированы,

как

р(y1/x0)=0,01

противоположные с вероятностью р(y1/х0) =

х1

y1

р(y0/х1) = 0,01. Определить количество

р(y1/x1)

информации после приема одного сигнала.

4

Решение. Количество получаемой информации при неполной достоверности переданных сигналов будет равно разности начальной и остаточной энтропии:

I(Y,X) = H(X) – H(X/Y) =

1

p(x ) log

p(x )

1

p(y

1

p(x /y

) log

p(x /y

).

)

i 0

i

2

i

j 0

j

i 0

i

j

2

i

j

Начальная энтропия:

H(X) = – p(x0) log2 p(x0) – p(x1) log2 p(x1) = 2 * 0,5 * log2 0,5 = 1 (бит)

Для определения условной энтропии H(X/Y) необходимо знать вероятности

p(yj), p(xi/yj).

Вероятности p(yj) вычисляем по формуле полной вероятности:

p(yj) i p(xi) p(yj /xi).

p(y0) = p(x0) p(y0/x0) + p(x1) p(y0/x1)= 0,5 * 0,99 + 0,5 * 0,01 = 0,5; p(y1) = p(x0) p(y1/x0) + p(x1) p(y1/x1) = 0,5 *0,01 + 0,5 * 0,99 = 0,5.

Условные вероятности p(xi/yj) вычисляем по теореме Байеса:

p(x /y			)		p(xi) p(yj /xi)			.
i		j			p(yj)
p(x0	/ y1)			p(x0) p(y1 /x0)				0,5 0,01	0,01;
					p(y1)			0,5
p(x1	/ y0)			p(x1) p(y0 /x1)				0,5 0,01	0,01.
					p(y0)			0,5

Тогда: p(x0/y0) = 1 – p(x1/y0) = 1 – 0,01 = 0,99; p(x1/y1) = 1 – p(x0/y1) = 1 – 0,01 = 0,99.

Таким образом, условная энтропия равна:

H(X/Y) = – 0,5 (0,99 * log2 0,99 + 0,01 * log2 0,01) – 0,5 (0,01 * log2 0,01 + +0,99 * log2 0,99) = 0,081 (бит).

Окончательно получаем:

I(Y,X) = 1 – 0,081 = 0,919 (бит).