Дискретных случайных систем

Лабораторная работа № 1

Информационные характеристики дискретных информационных систем

Основные сведения об информационных характеристиках

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

Сведения, являющиеся объектом хранения, передачи и преобразования, называют информацией. Для измерения количества информации о некоторой дискретной случайной системе Х используется энтропия, которая показывает степень неопределенности со­стояния этой системы. К.Шеннон ввел следующую формулу для определения энтропии:

,

где x ₁, x ₂, … x_i,…, x_n – возможные состояния системы X, p (x ₁), (x ₁), …, p(x_i),…, p (x_n) – вероятности состояний, , M – оператор математического ожидания. Примерные значения вероятностей состояний можно получить по формуле

, i = 1, 2, …, n,

где n_i = n (x_i) – число наблюдений системы X в состоянии x_i или частота состояния x_i.

Свойства энтропии:

1. энтропия есть величина вещественная, ограниченная и неотрицатель­ная;

2. энтропия минимальна и равна нулю, если хотя бы одно из состояний сис­темы достоверно известно, т.е. вероятность одного из состояний равна 1;

3. энтропия максимальна и равна логарифму числа состояний, если состоя­ния системы равновероятны, т.е. вероятности всех состояний равны между собой;

4. энтропия бинарных величин изменяется от 0 до 1 – она равна 0, если вероятность одного из состояний равна 0, затем возрастает и достигает максимума при вероятностях 0.5.

Пусть имеется сложная система, состоящая из двух систем X и Y:

X = (x ₁, …, x_i, …, x_n), Y = (y ₁, …, y_j, …, y_m).

Ее поведение определяется матрицей вероятностей совместных событий P (X, Y) = [ p (x_i, y_j)] _{n ´ m} =[ p_ij ] _{n ´ m}:

.

Энтропия сложной системы вычисляется по формуле:

.

В случае независимых систем X и Y энтропия сложной системы рассчитывается следующим образом:

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

В случае зависимых систем X и Y можно определить условную частную энтропию H (Y / x_i) системы Y относительно от­дельного события x_i:

,

где p (x_i / y_j) – условные вероятности, задаваемые матрицей:

.

Аналогично можно определить и условную частную энтропию H (X / y_j) системы X относительно от­дельного события y_j:

,

где p (y_j / x_i) – условные вероятности, задаваемые матрицей:

.

Если частную условную энтропию ус­реднить по всем состояниям x_i с учетом вероятности появления каждого из состояний p (x_i), то можно найти полную условную энтропию системы Y отно­сительно системы X:

,

,

.

Аналогично рассчитывается условная энтропия системы X отно­сительно системы Y:

,

,

.

В случае зависимых систем X и Y энтропию сложной системы можно вычислить с помощью соотношений:

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

Энтропию сложной системы также называют энтропией объединения. Для нее справедливо неравенство:

H (X, Y) ≤ H (Y) + H (X).

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

I (X) = H ₁(X) – H ₂(X),

где H ₁(X) – энтропия системы до наблюдения, H ₂(X) – энтропия в результате наблюдения. Если в результате наблюдения неопределенность исчезает, т.е. H ₂(X) = 0, то количество информации будет равно исходной энтропии системы:

I (X) = H ₁(X),

т.е. количество информации, приобретаемое при полном выясне­нии состояния некоторой системы, равно энтропии этой системы.

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

,

где l – число символов вторичного алфавита, используемых для представления одного символа первичного алфа­вита сообщения, а k - количество передаваемых букв первичного алфавита в сообщении.

На практике часто встречается ситуация, когда интересующая система Х для наблюдения не доступна. Поэтому наблюде­ние ведут за другой системой Y, связанной каким-либо образом с системой Х. Между системой X и Y имеются различия из-за ошибок, которые могут быть двух видов:

1) ошибки наблюдения за системой X;

2) ошибки передачи информации о системе X посредством системы Y.

Для определения того, какое количество информации о системе X дает наблюдение системы Y, используют следующее выражение:

I_{Y ® X} = H (X) – H (X/Y) = H (X) + H (Y) – H (X, Y),

где H (X)- априорная энтропия системы X (энтропия до наблюдения), H (X/Y)- апостериорная (остаточная) эн­тропия системы X (энтропия после наблюдения) с учетом наблюдения системы Y, H (Y) – энтропия системы Y, H (X, Y) – энтропия объединения систем X и Y. Величина I_{Y ® X} есть полная информация о системе X, содержащаяся в системе Y. В общем случае, при наличии двух систем, каждая содержит относи­тельно другой системы одну и ту же полную информацию:

H (X) – H (X/Y) = H (Y) – H (Y/X).

Тогда I_{Y ® X} = I_{X ® Y} = I_{Y « X}. Величину I_{Y « X} называют полной взаимной информацией содержащейся в сис­темах X и Y.

Пример. Пусть даны две системы X и Y:

X = bbcabaabacabbacbbaccbbaccbbddadadad,

Y = ccabacabbacbbaccabcabbaccbbddadadab,

состояния которых определяются символами алфавита A = { a, b, c, d }. Найти:

1. вероятности состояний систем X и Y;

2. энтропии независимых систем X и Y;

3. условные энтропии систем X и Y, считая, что каждому символу одной системы соответствует соответствующий по индексу символ второй системы;

4. энтропию объединения независимых систем X и Y;

5. энтропию объединения зависимых систем X и Y;

6. взаимную информацию систем X и Y;

7. объем информации для систем X и Y, считая, что каждый символ алфавита A кодируется двумя символами вторичного алфавита.

Решение.

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

Состояние	a	b	c	d	Всего
Число наблюдений для системы X
Число наблюдений для системы Y
Вероятность для системы X	0.314	0.343	0.2	0.143
Вероятность для системы Y	0.314	0.314	0.257	0.115

 

2. Энтропии независимых систем находим по формуле К.Шеннона:

, .

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

, , i = 1, 2, …, n, j = 1, 2, …, m,

где n (x_i / y_j) – число состояний x_i системы X, наблюдаемых, когда система Y находилась в состоянии y_j, n (y_j) – число наблюдений состояния y_j системы Y, n (y_j / x_i) – число состояний y_j системы Y, наблюдаемых, когда система X находилась в состоянии x_i, n (x_i) – число наблюдений состояния x_i системы X.

 

	y 1 = a	y 2 = b	y 3 = c	y 4 = d	n (x i)
n (x 1= a / yj)
n (x 2= b / yj)
n (x 3= c / yj)
n (x 4= d / yj)
n (yj)

 

 

	x 1 = a	x 2 = b	x 3 = c	x 4 = d	n (y j)
n (y 1= a / xi)
n (y 2= b / xi)
n (y 3= c / xi)
n (y 4= d / xi)
n (xi)

 

	y 1 = a	y 2 = b	y 3 = c	y 4 = d
p (x 1= a / yj)	0.545	0.273	0.223
p (x 2= b / yj)	0.182	0.636	0.333
p (x 3= c / yj)	0.273		0.444
p (x 4= d / yj)		0.091

 

	x 1 = a	x 2 = b	x 3 = c	x 4 = d
p (y 1= a / xi)	0.545	0.167	0.429
p (y 2= b / xi)	0.273	0.583		0.2
p (y 3= c / xi)	0.182	0.25	0.571
p (y 4= d / xi)				0.8

 

Полученные условные вероятности подставим в формулы

,

и получим H (X / Y) = 1.234, H (Y / X) = 1.226.

 

4. Энтропия объединения независимых систем равна:

H (X, Y) = H (X) + H (Y) = 3.831.

5. Энтропия объединения зависимых систем равна:

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

6. Взаимная информация систем равна:

I_{Y « X} = H (X) – H (X/Y) = H (Y) – H (Y / X) = 0.69.

7. Объемы информации равны:

Q (X) = 35 ´ 2 = 70 бит, Q (Y) = 35 ´ 2 = 70 бит.

 

Поделиться:

Воспользуйтесь поиском по сайту: