ВИЗНАЧЕННЯ ЕНТРОПІЙНИХ ХАРАКТЕРИСТИК ОБ’ЄКТІВ КОМП’ЮТЕРНИХ МЕРЕЖ. Звіт до лабораторної роботи з Методи та засоби комп’ютерних інформаційних технологій. Робота № 525563

ВИЗНАЧЕННЯ ЕНТРОПІЙНИХ ХАРАКТЕРИСТИК ОБ’ЄКТІВ КОМП’ЮТЕРНИХ МЕРЕЖ

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

КН

Кафедра:

Не вказано

Інформація про роботу

Рік:

2014

Тип роботи:

Звіт до лабораторної роботи

Предмет:

Методи та засоби комп’ютерних інформаційних технологій

Завантажити

Частина тексту файла (без зображень, графіків і формул):

МІНІСТЕРСТВО ОСВІТИ І НАУКИ МОЛОДІ ТА СПОРТУ УКРАІНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА» КАФЕДРА АСУ ЗВІТ до лабораторної роботи № 1 з дисципліни: «Методи і засоби комп’ютерних інформаційних технологій» на тему «ВИЗНАЧЕННЯ ЕНТРОПІЙНИХ ХАРАКТЕРИСТИК ОБ’ЄКТІВ КОМП’ЮТЕРНИХ МЕРЕЖ» Мета роботи: навчитися визначати ентропії джерела інформації, приймача, каналу зв’язку, системи взаємозв’язаних об’єктів. Теоретичні відомості Ентропія джерела інформації Х, що генерує незалежні повідомлення xi, обчислюється за формулою: , (1) де p(xi)- ймовірність появи повідомлення xi; N - кількість можливих повідомлень (символів, станів об’єкту) Властивості ентропії Ентропія завжди невід’ємна: . Ентропія максимальна, коли значення xi випадкової величини X рівноймовірні: . (2) Максимальне значення ентропії . (3) Для полегшення обчислень ентропії використовують наведену у додатку 1 таблицю значень добутків Розглянемо систему, що є об’єднанням двох статистично взаємозв’язаних об’єктів, наприклад, джерела Х з можливими станами x1, xi, xn та приймача Y з можливими станами y1, yj, ym... Сумісна ентропія системи: , (4) де ( ймовірність сумісної появи i-го стану в об’єкті X та j-го стану в об’єкті Y. Якщо об’єкти X та Y незалежні, то сумісна ентропія дорівнює сумі ентропій окремих об’єктів: . (5) Ентропія об’єкту Y (приймача), знайдена за умови, що об’єкт Х згенерував повідомлення хi, називається частковою умовною ентропією об’єкту Y. Її визначають за формулою: (6) де p(yj/xi) ( ймовірність події yj за умови, що в об’єкті X відбулася подія xi або ймовірність того, що приймач прийме символ yj за умови, що джерело передало символ xi. Середню або повну умовну ентропію об’єкту Y відносно об’єкту X називають просто умовною ентропією, позначають H(Y/X) і визначають за формулою: . (7) Для незалежних об’єктів , (8) . (9) Формули (10) та (11) показують взаємозв’язок ентропії об’єкту, сумісної та умовної ентропій. (10) , (11) де H(X) ( ентропія (безумовна) об’єкту Х; H(Y) ( ентропія (безумовна) об’єкту Y; H(X,Y) – сумісна ентропія; H(Y/X) ( умовна ентропія об’єкту Y відносно об’єкту Х; H(X/Y) ( умовна ентропія об’єкту X відносно об’єкту Y. Через часткову і повну умовну ентропії описують інформаційні втрати при передачі даних в каналі зв'язку з завадами. Для цього застосовують так звані канальні матриці. В якості елементів канальної матриці звичайно використовують умовні ймовірності p(yj/xi) отримання приймачем Y символу yj за умови, що джерелом Х був відправлений символ xi. При цьому канальна матриця P(Y/X)має наступний вигляд: . (12) Ймовірності, що є елементами головної діагоналі матриці, описують ймовірність правильного прийому. Втрати, які мали місце при передачі сигналу xi, описуються через часткову умовну ентропію: (13) Для обчислення всіх втрат при передачі всіх сигналів використовується умовна (повна) ентропія: (14) Для визначення ентропії приймача H(Y) за умови, що відома ентропія джерела H(X) і канальна матриця P(Y/X), необхідно знайти ймовірності появи символів на вході приймача p(yj): . (15) Взаємозв'язок переданих і отриманих символів може бути описаний також матрицею сумісних ймовірностей P(X,Y): . (16) Сума всіх елементів стовпчика з номером j дає p(yj), сума рядка з номером i дорівнює p(xi), а сума всіх елементів матриці рівна 1. Сумісна ймовірність p(xi, yj) обчислюється таким чином: . (17) На практиці джерело Х найчастіше буває недоступне безпосередньому спостереженню, і його стан з’ясовується за допомогою деякого об’єкту Y, певним чином пов’язаного з об’єктом X. Для визначення кількості інформації IY->X, що міститься в об’єкті Y (приймачі) про об’єкт X (джерело) використовують взаємну ентропію H(Y->X). Взаємна кількість інформації IY->X IY->X = IX->Y = IY<->X = IX<->Y = H(Y->X) = H(X->Y) = H(X<->Y). (18) Взаємна ентропія . (19) Формули (20) та (21) показують взаємозв’язок взаємної ентропії з іншими видами ентропій: H(X<->Y) = H(Y) – H(Y/X) = H(X) – H(X/Y), (20) H(X<->Y) = Н(Х) + Н(Y) – Н(Х, Y) = IX->Y. (21) Для ілюстрації формули (21) наведено рисунок, що дозволяє краще зрозуміти суть взаємної ентропії та взаємної кількості інформації. Рис.1 До визначення взаємної інформації. Хід роботи Завдання N=5, р(yi /xi) = 0,3 для всіх j<>i, одна з ймовірностей р(yj/xi) = 0,6 р(yi /xi) = У1 У2 У3 У4 У5 Х1 0.3 0.7 0 0 0 Х2 0 0.3 0.7 0 0 Х3 0 0 0.3 0.7 0 Х4 0 0 0 0.3 0.7 Х5 0.7 0 0 0 0.3 р(xi , yi) = У1 У2 У3 У4 У5 Х1 0.06 0.14 0 0 0 Х2 0 0.06 0.14 0 0 Х3 0 0 0.06 0.14 0 Х4 0 0 0 0.06 0.14 Х5 0.14 0 0 0 0.06 Х А Б 0.2 0.2 В Д Г 0.2 0.2 0.2 У А Б 0.2 0.2 В Д Г 0.2 0.2 0.2 Схема ймовірнісних переходів. А 0,3 А Б 0,3 Б В 0,3 В Г 0,3 Г Д 0,3 Д Ентропія системи Х: H(X)=- 1

Звіт до лабораторної роботи Методи та засоби комп’ютерних інформаційних технологій

sashasem

25.01.2014 19:15

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись