Порядок выполнения лабораторной работы

Лабораторная работа № 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	11	12	7	5	35
Число наблюдений для системы Y	11	11	9	4	35
Вероятность для системы X	0.314	0.343	0.2	0.143	1
Вероятность для системы Y	0.314	0.314	0.257	0.115	1

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₁ = a	y₂ = b	y₃ = c	y₄ = d	n(x_i)
n(x₁=a/y_j)	6	3	2	0	11
n(x₂=b/y_j)	2	7	3	0	12
n(x₃=c/y_j)	3	0	4	0	7
n(x₄=d/y_j)	0	1	0	4	5
n(y_j)	11	11	9	4

	x₁ = a	x₂ = b	x₃ = c	x₄ = d	n(y_j)
n(y₁=a/x_i)	6	2	3	0	11
n(y₂=b/x_i)	3	7	0	1	11
n(y₃=c/x_i)	2	3	4	0	9
n(y₄=d/x_i)	0	0	0	4	4
n(x_i)	11	12	7	5

	y₁ = a	y₂ = b	y₃ = c	y₄ = d
p(x₁=a/y_j)	0.545	0.273	0.223	0
p(x₂=b/y_j)	0.182	0.636	0.333	0
p(x₃=c/y_j)	0.273	0	0.444	0
p(x₄=d/y_j)	0	0.091	0	1
	1	1	1	1

	x₁ = a	x₂ = b	x₃ = c	x₄ = d
p(y₁=a/x_i)	0.545	0.167	0.429	0
p(y₂=b/x_i)	0.273	0.583	0	0.2
p(y₃=c/x_i)	0.182	0.25	0.571	0
p(y₄=d/x_i)	0	0	0	0.8
	1	1	1	1

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

и получим 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 бит.

Порядок выполнения лабораторной работы

1. Ознакомиться с основными сведениями об информационных характеристиках дискретных случайных систем.

2. Получить задание на выполнение лабораторной работы.

3. Выполнить расчеты информационных характеристик дискретных случайных систем.

4. Сделать выводы о свойствах информационных характеристик дискретных случайных систем.

5. Оформить отчет о выполнении лабораторной работы.

6. Ответить на контрольные вопросы.

Контрольные вопросы

1. Что такое энтропия дискретной случайной системы?

2. Каковы основные свойства энтропии?

3. Когда энтропия приобретает максимальное (минимальное) значение?

4. Как выражается энтропия объединения двух независимых систем?

5. Как выражается энтропия объединения двух зависимых систем?

6. Как выражается количество информации?

6. В чем разница между объемом информации и количеством информации?

7. Как зависит количество информации от сообщения об отдельном событии от вероятности этого события?

8. Как определить взаимную информацию двух систем?

9. Как определяется полная взаимная информация в случаях полной независимости и полной зависимости систем?

10. Как определить взаимную информацию двух систем через энтропию объединения?

Дата добавления: 2020-04-25; просмотров: 452; Мы поможем в написании вашей работы!

Поделиться с друзьями:

12 Следующая ⇒

Мы поможем в написании ваших работ!