Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

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

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

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

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

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

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

,

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

, i = 1, 2, …, n,

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

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

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

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

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

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

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

X = (x 1, …, xi, …, xn), Y = (y 1, …, yj, …, ym).

Ее поведение определяется матрицей вероятностей совместных событий P (X, Y) = [ p (xi, yj)] n ´ m =[ pij ] n ´ m:

.

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

.

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

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

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

,

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

.

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

,

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

.

Если частную условную энтропию ус­реднить по всем состояниям xi с учетом вероятности появления каждого из состояний p (xi), то можно найти полную условную энтропию системы 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 1(X) – H 2(X),

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

I (X) = H 1(X),

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

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

,

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

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

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

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

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

IY ® 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. Величина IY ® X есть полная информация о системе X, содержащаяся в системе Y. В общем случае, при наличии двух систем, каждая содержит относи­тельно другой системы одну и ту же полную информацию:

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

Тогда IY ® X = IX ® Y = IY « X. Величину IY « 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 (xi / yj) – число состояний xi системы X, наблюдаемых, когда система Y находилась в состоянии yj, n (yj) – число наблюдений состояния yj системы Y, n (yj / xi) – число состояний yj системы Y, наблюдаемых, когда система X находилась в состоянии xi, n (xi) – число наблюдений состояния xi системы 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. Взаимная информация систем равна:

IY « X = H (X) – H (X/Y) = H (Y) – H (Y / X) = 0.69.

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

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

 

Поделиться:





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



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...