Сборник примеров и задач по Теории информации

Добавил:

Yuppie_ModeratorNGMU Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Новосибирский государственный медицинский университет

Предмет:

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

Файл:

Pyi. ln Pyi

3. q. ln ( q) и составит H Y = 1.585 bit;

.pdf

Скачиваний:

283

Добавлен:

30.03.2015

Размер:

624.7 Кб

Скачать

☆

1 / 71 2 3 4 5 6 7 > Следующая >>>

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

___.___

ТАГАНРОГСКИЙ ГОСУДАРСТВЕННЫЙ РАДИОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

С.В. Кавчук

СБОРНИК ПРИМЕРОВ И ЗАДАЧ ПО ТЕОРИИ ИНФОРМАЦИИ

Руководство для практических занятий на базе Mathcad 6.0 Plus

Таганрог 2002

УДК 681.3 ×5(076.1) + 681.3.06(076.1)

С.В. Кавчук. Сборник примеров и задач по теории информации. Руководство для практических занятий на базе Mathcad 6.0 Plus. Таганрог: Изд-во ТРТУ, 2002. 64 с.

Рассмотрены основные понятия и расчетные соотношения теории информации для практических занятий по темам: оценка энтропийных характеристик, оценка количества информации, оценка информационных характеристик систем и эффективное кодирование. Приводятся примеры решения типовых задач с использованием программного обеспечения Matchad 6.0 Plus. Дается набор типовых задач с ответами.

Руководство предназначено для улучшения качества изучения курса “Теоретические основы информационно-измерительной техники” и других дисциплин, содержащих разделы теории информации.

Табл. 1. Ил. 13. Библиогр.: 13 назв.

Рецензент С.В. Николаев, канд. техн. наук, доцент кафедры АСНИиЭ ТРТУ.

1.ОЦЕНКА ЭНТРОПИЙНЫХ ХАРАКТЕРИСТИК

1.1.Основные сведения

1.1.1. Дискретные случайные величины

Вероятностная мера неопределенности Шеннона или энтропия дис-

кретной случайной величины имеет вид

			N				N
			H(X) = ∑P(xi ) loga	1			= −∑P(xi ) loga P(xi ) ,	(1.1)
			H(X) = ∑P(xi ) loga	P(x	i	)	= −∑P(xi ) loga P(xi ) ,	(1.1)
			i=1		i		i=1
где	P(xi )		− вероятность появления i-го значения xi случайной величины X;
loga	1		= Hi − мера неопределенности i-го значения; знак минус понимает-
loga		P(xi )
		P(xi )

ся как наличие "беспорядка" для величины X. Формулу (1.1) можно записать в компактном виде

H(X)=M[-log2P(x)],

где log2P(x) − дискретная случайная величина, для которой i-е значение log2P(xi) имеет вероятность P(xi).

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

ятны

P(x1) = P(x2 ) =K= P(xN ) = P =					1	.
P(x1) = P(x2 ) =K= P(xN ) = P =						.
Тогда					N
Тогда
N	1		1
H(X) = −∑	1	log2	1	= log2 N ,			(1.2)
H(X) = −∑	N	log2	N	= log2 N ,			(1.2)
i=1	N		N
i=1

где log2 N − мера Хартли.

В этом случае статистическая мера Шеннона совпадает с комбинаторной мерой Хартли.

Энтропия системы дискретных случайных величин X и Y

n	m
H(X, Y) = −∑∑P(xi , y j ) log2 P(xi , y j ) ,		(1.3)
i=1	j=1

где P(xi , y j ) − вероятность совместного появления i-го и j-го значений слу-

чайных величин X и Y, или в форме математического ожидания

H(X, Y) = Μ[−log2 P(X, Y)] ,

где log2P(X,Y) − случайная величина, принимающая значения согласно матрице совместного распределения, и для которой значение log2P(xi,yj) имеет вероятность P(xi,yj).

Энтропия системы зависимых величин

H(X, Y) = H(X) +H(Y / X) или H(X, Y) = H(Y) +H(X / Y) ,	(1.4)
где H(X) − безусловная энтропия величины Х;
H(Y) − безусловная энтропия величины Y;
H(Y/X) − условная энтропия величины Y относительно величины Х;
H(X/Y) − условная энтропия величины X относительно Y.
Для независимых величин H(X / Y) = H(X) и H(Y / X) = H(Y) .
Условная энтропия X относительно Y
H(X / Y) = −∑∑P(xi , y j ) log2 P(xi / y j ) = M[−log2 P(X / Y)],	(1.5)
i j

где P(xi/yj) − вероятность значения xi величины X при условии, что величина Y приняла значение yj (условная вероятность).

Условная энтропия величины X относительно значения yj величины Y
H(X / y j ) = −∑∑P(xi / y j ) log2 P(xi / y j ) .	(1.6)
i j
Условная энтропия Y относительно X
H(Y / X) = −∑∑P(xi , y j ) log2 P(y j / xi ) .	(1.7)

1.1.2.Непрерывные случайные величины

Энтропия непрерывной случайной величины

H(X) = − ∞∫p(x) log2 p(x)dx −log2 x ,	(1.8)
−∞
где p(x) − плотность вероятности случайной величины X;	x − шаг ее кванто-

вания, определяющий точность перехода от непрерывной величины к дискретной.

При x=1 имеем дифференциальную или относительную энтропию

Hд(X) = − ∞∫p(x) log2 p(x)dx .	(1.9)
−∞
Энтропия системы непрерывных случайных величин X и Y
H(X, Y) = − ∞∫ ∞∫p(x, y) log2 p(x, y)dxdy −log2 x y ,	(1.10)
−∞ −∞

где p(x,y) − совместная (безусловная) плотность вероятности двух случайных величин X и Y.

Дифференциальная энтропия системы двух случайных величин

Hд(X, Y) = − ∞∫ ∞∫p(x, y) log2 p(x, y)dxdy ,	(1.11)
−∞ −∞
Условная дифференциальная энтропия X относительно Y
Hд(X / Y) = − ∞∫ ∞∫p(x, y) log2 p(x / y) ,	(1.12)
−∞ −∞

где p(x/y) − условная плотность вероятности.

Условная дифференциальная энтропия величины X относительно значения y величины Y

Hд(X / y) = − ∞∫ ∞∫p(x / y) log2 p(x / y) .	(1.13)
−∞ −∞

1.2. Типовые примеры

Пример 1.2.1. Имеются три дискретных источника информации

X(x1,x2), Y(y1,y2,y3) и Z(z1,z2). Вероятности появления сообщений P(xi),

P(y ) и P(z ) каждого источника заданы при p					1	, q		1	и ORIGIN	1 (за-
					1			1


i	i			2			3
дание начальных значений индексов) векторами				2			3
дание начальных значений индексов) векторами
	Px	( p p ) T , Py	( q q q ) T и Pz				( p 2. q ) T.

Требуется определить, какой источник обладает большей неопределенностью.

Решение. Сначала определим единицы измерения количества энтропии: а) при натуральном логарифме (нит) − nit ln ( e );

б) при двоичном логарифме (бит) − bit nit. ln ( 2 ). На основании (1.1) энтропии источников:

•первого − assume p

		2
H	X		Px . ln	Px	i	2. p. ln ( p )и составит H	X	= 1 bit;


			i

i = 1

•второго − assume q

• третьего − assume p , q

				6
		2
H Z			Pz i. ln Pz i		p. ln ( p )	2. q. ln ( 2. q)




	i = 1
и составит H Z = 0.89		bit.

Таким образом, в случае равновероятных сообщений большей неопределенностью обладает троичный источник Y. При этом неопределенность может быть подсчитана так же как мера Хартли, равная logN, где N − число равновероятных сообщений. Сравнение двоичных источников X и Z показывает, что большей неопределенностью обладает источник с равновероятными сообщениями.

Пример 1.2.2. Число символов алфавита источника N 4 (i 1 .. N или j 1 .. N ). Вероятности появления символов источника

Px1 0.5 , Px2 0.25 , Px3 0.125 и Px4 0.125 .

Между соседними символами имеются корреляционные связи, которые опи-

сываются при ORIGIN			1 матрицей условных вероятностей P(xi/xj)=Px xi , j



следующего вида		5		3
		5		3	0		0
	8		8		0		0
	8		8
		1		1		3	0
Px x	8		2		8		0	, например Px x	= 0.5.



	0		0		0		1		2, 2
	0		0		0		1
		1		1		1	0
	2		4		4		0
	2		4		4

Требуется определить энтропию источника.

б) при двоичном логарифме (бит) − bit nit. ln ( 2 ).

Ввиду зависимости между символами неопределенность источника характеризуется условной энтропией H(X/X). С учетом корреляционной связи и соотношения

P(xi , y j ) = P(y j )P(xi / y j )

на основании (1.5) условная энтропия

Px .

. ln Px

, HX

= 1.016 bit.

i , j

i = 1

j = 1

Пример 1.2.3. Ансамбли событий X и Y объединены, причем вероятности совместных событий определяются матрицей PXY совместных вероятностей P(X,Y) при ORIGIN 1:

0.1		0.25
P XY	0.2	0 ; P XY1, 2	= 0.25.


0.3		0.15

Требуется определить:

а) энтропии ансамблей X и Y;

б) энтропию объединенного ансамбля; в) условные энтропии ансамблей.

Решение. Предварительно определим единицы измерения количества энтропии:

а) при натуральном логарифме (нит) − nit ln ( e ); б) при двоичном логарифме (бит) − bit nit. ln ( 2 ).

Найдем безусловные вероятности P(xi) и P(yj) при i 1 .. 3 и j 1 .. 2:

0.35

Pxi

P XY

i , j

;

Px =

0.2

;

j = 1

0.45

0.6

Pyj

P XY

;

Py =

i , j

0.4

i = 1

На основании (1.1) вычислим энтропии ансамблей:

Px . ln

;

= 1.513

bit;

Px . ln

;

= 0.994

bit.

На основании (1.3) энтропия объединенного ансамбля

. ln P

; H

= 2.228 bit.

i , j

Так как согласно (1.4), энтропия объединения

H(X,Y)=H(X)+H(Y/X)=H(Y)+H(X/Y),

то условные энтропии будут

HY X	H XY	H X	;	HY X = 0.715	bit.



HX Y	H XY	H Y	;	HX Y = 1.234	bit.

Пример 1.2.4. По линии связи передаются непрерывные амплитудномодулированные сигналы x(t), распределенные по нормальному закону с ну-

левым

средним значением и

среднеквадратичными

отклонениями

8. volt.

Определить

энтропию

сигнала

при

точности

его

измерения

0.2 . volt.

Решение. Предварительно определим единицы измерения количества эн-

тропии:

а) при натуральном логарифме (нит) − nit

ln ( e );

б) при двоичном логарифме (бит) − bit

nit. ln ( 2 ).

По условию задачи плотность вероятности сигнала

p( x )

. exp

2. σ x2

σ x. 2. π

На основании (1.8) энтропия непрерывного сигнала

∞

2.σx2

. e

. ln

. e

ln ( x ) ;

. 2

. π

2. π

∞

. ln ( 2 )

ln σ

. ln ( π )

ln ( x ).

Итак, энтропия сигнала H

σ x

; H

= 7.369

bit.

Пример 1.2.5. В системе регулирования скорости вращения вала двига-

теля

задающее

воздействие

X в

виде электрического

напряжения имеет

16 независимых дискретных значений с шагом квантования δ

0.2 . volt,

вероятности появления которых распределены по двухстороннему экспоненциальному закону с параметром α 0.5 . volt и функцией плотности вероятности

p( x )

. exp

;

p( 0.5 . volt ) = 0.368

volt 1.

2. α

1.6 . volt. Сигнал

Максимальное значение воздействия составляет

0.3 . sec

дискретизирован по

времени

шагом

и имеет

длительность

30. sec.Определить энтропию сигнала.

Решение. Предварительно определим единицы измерения количества

информации:

а) при натуральном логарифме (нит) − nit

ln ( e );

б) при двоичном логарифме (бит) − bit

nit. ln ( 2 ).

График плотности вероятности в виде ступенчатой функции, соответст-

вующей

шагу квантования

δ,

приведен

на

рис.1.2.1

при

0 .. N и

i. δ.

Ступенчатый график плотности вероятности

2.δ

volt

p xi

1 /

volt

Рис.1.2.1

Определим вероятности появления уровней сигнала

Pxi

p( x ) dx

; Px9 = 0.11.

. δ;

Px9 = 0.134.

по приближенной формуле Pxi

p xi

Согласно (1.1), энтропия или средняя неопределенность одного дискрет-

ного значения задающего воздействия

Px . ln

; H1

= 3.488

bit.

i = 0

nit. ln ( 2 ).

Сигнал состоит из n T отсчетов задающего воздействия. На основа- t

нии свойства аддитивности энтропии окончательно имеем энтропию сигнала в целом

H	X	n. H1	X	; H	X	= 348.836 bit.

Пример 1.2.6. Случайная погрешность Σ измерительной системы, состоящей из двух устройств, является суммой двух независимых случайных

погрешностей

1 и

2 отдельных ее устройств. Погрешности имеют с пара-

метрами a

4. volt

и b

2. volt

равномерные

законы

распределения

(рис.1.2.2 при

8. volt,

.. q и

.. q) с

500

плотностями вероятности соответственно

p 1

1 a и p 2

2 b.

2. a

2. b

otherwise

0 otherwise

График плотностей вероятности

1/вольт

p	1	1	b	a	1
						2.b
p	2	2				2.b
p	2	2			1
						2.a

	10	5	0	5	10
	10	5	0	5	10
			1, 2
			вольт
			Рис.1.2.2
Найти дифференциальную			энтропию	суммарной	погрешности

Σ= 1+ 2.

Решение. Предварительно определим единицу измерения энтропии как nit ln ( e ). При этом один bit

1 / 71 2 3 4 5 6 7 > Следующая >>>

Соседние файлы в предмете Медицинская информатика

#
07.05.2019868.35 Кб6задачник.doc
#
13.03.201610.92 Mб52Информационные технологии.docx
#
30.03.20155.46 Mб17Мед. информатика. Кобринский.pdf
#
30.03.20151.05 Mб18Методическое пособие Основные понятия и методы теории информатики и кодирования.pdf
#
15.08.2019102.4 Кб5Работа с Windows.doc
#
30.03.2015624.7 Кб283Сборник примеров и задач по Теории информации.pdf
#
30.03.2015458.9 Кб11СИСТЕМЫ СЧИСЛЕНИЯ В ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКЕ, Борисенко А.А..pdf
#
30.03.2015489.58 Кб13Системы счисления2..pdf