Курс: "
Теорія інформації та кодування"
Тема: "МАТЕМАТИЧНА
ТЕОРІЯ ІНФОРМАЦІЇ"
1.
КІЛЬКІСТЬ ІНФОРМАЦІЇ, ТА ЇЇ МІРА
На вхід системи передачі
інформації (СПІ) від джерела інформації подається сукупність повідомлень, вибраних з ансамблю повідомлень (рис.1).
Перешкоди
x
1 y
1 x
2 y
2 x
n y
n Рис. 1. Система передачі інформації
Ансамбль повідомлень - безліч можливих повідомлень з їх імовірнісними характеристиками -
{Х, р (х)}. При цьому:
Х = {х 1, х 2, ..., х m} - безліч можливих повідомлень джерела;
i = 1, 2 ,..., m, де
m - обсяг алфавіту;
p (x i) - ймовірності появи повідомлень , причому
p (x i) ³ 0 і оскільки ймовірності повідомлень представляють собою повну групу подій, то їх сумарна ймовірність дорівнює одиниці
.
Кожне повідомлення несе в собі певну
кількість інформації. Визначимо
кількість інформації, що міститься в повідомленні
x i, вибраному з ансамблю повідомлень джерела
{Х, р (х)}. Одним з параметрів, що характеризують дане повідомлення, є ймовірність його появи -
p (x i), тому
природно припустити, що кількість інформації
I (x i) в повідомленні
x i є
функцією p (x i). Імовірність появи двох незалежних повідомлень
x 1 і
x 2 дорівнює добутку ймовірностей
p (x 1, x 2) = p (x 1). p (x 2), а у них
інформація повинна
мати властивість адитивності, тобто:
I (x 1, x 2) = I (x 1) + I (x 2). (1)
Тому для оцінки кількості інформації запропонована логарифмічна міра:
. (2)
При цьому, найбільшу кількість інформації містять найменш вірогідні повідомлення, а кількість інформації в повідомленні про достовірне подію дорівнює нулю. Т. до все логарифми пропорційні, то
вибір підстави визначає одиницю інформації:
log a x = log b x / log b a. Залежно від основи логарифма використовують такі одиниці інформації:
2 - [біт]
(bynary digit - двійкова одиниця), використовується при аналізі ін-формаційних
процесів в ЕОМ і ін пристроях, що функціонують на основі двійкової системи числення;
e - [ніт]
(natural digit - натуральна одиниця), використовується в
математичних методах теорії зв'язку;
10 - [дит]
(decimal digit - десяткова одиниця), використовується при аналізі процесів у приладах працюють з десятковою системою числення.
Бітом (двійковій одиницею інформації) - називається кількість інформації, яка знімає невизначеність відносно настання одного з двох рівноймовірно, незалежних подій.
Середня кількість інформації для всієї сукупності повідомлень можна отримати шляхом усереднення по всіх подій:
. (3)
Кількість інформації, в повідомленні, що складається з
n НЕ рівноймовірно його елементів дорівнює (цей захід запропонована в
1948 р . К. Шенноном):
. (4)
Для випадку незалежних рівноймовірно подій кількість інфор-мації визначається (цей захід запропонована в
1928 р . Р. Хартлі):
. (5)
2. ВЛАСТИВОСТІ КІЛЬКОСТІ ІНФОРМАЦІЇ 1. Кількість інформації в повідомленні назад - пропорційно ймовірності появи даного повідомлення.
2. Властивість адитивності - сумарна кількість інформації двох джерел дорівнює сумі
інформацією джерел.
3. Для події з одним результатом кількість інформації дорівнює нулю.
4. Кількість інформації в дискретному повідомленні зростає в залежності від збільшення обсягу алфавіту -
m. Приклад 1. Визначити кількість інформації в повідомленні з 8 двійкових
символів (n =
8, m = 2), якщо ймовірності рівні:
p i0 = p i1 = 1 / 2.
Кількість інформації дорівнює:
I = n log m = 8 log 2 лютого = 8 біт. Приклад 2. Визначити кількість інформації в повідомленні з 8 двійкових символів
(n =
8, m = 2), якщо ймовірності рівні:
p i0 = 3 / 4;
p i1 = 1 / 4.
Кількість інформації дорівнює:
3. ЕНТРОПІЯ ІНФОРМАЦІЇ Е нтропія - Змістовність, міра невизначеності інформації.
Е нтропія -
математичне сподівання
H (x) випадкової величини
I (x) визначеної на ансамблі
{Х, р (х)}, тобто вона
характеризує середнє значення кількості інформації, що припадає на один символ.
. (6)
Визначимо максимальне значення ентропії
H max (x). Скористаємося методом невизначеного множника Лагранжа - l для відшукання умовного екстремуму
функції [6]. Знаходимо допоміжну функцію:
(7)
Уявімо допоміжну функцію
F у вигляді:
. (8)
Знайдемо максимум цієї функції
т. к.
.
Як видно з виразу, величина ймовірності
p i не залежить від
i, а це може бути у випадку, якщо все
p i рівні, тобто
p 1 = p 2 = ...= p m = 1 / m. При
m = 2 для рівноймовірно подій
p i = 1 / 2
ентропія дорівнює 1. Зміна ентропії в залежність від імовірності події наведено на рис. 2.
Як видно, максимум ентропії
відповідає різновірогідні подіям.
При цьому, вираз для ентропії рівноймовірно, незалежних елементів одно:
H (x i) H max 1 0 0,5 1,0 P (x i)
|
Рис. 2. Графік ентропії для двох альтернативних подій
. (9)
Знайдемо ентропію системи двох альтернативних подій з ймовірностями
p 1 і
p 2. Ентропія дорівнює
4. ВЛАСТИВОСТІ ЕНТРОПІЯ ПОВІДОМЛЕНЬ 1.
Ентропія є величина речова, обмежена, не негативна, неперервна на інтервалі
0 £ p £ 1. 2.
Ентропія максимальна для рівноймовірно подій.
3.
Ентропія для детермінованих подій дорівнює нулю.
4. Ентропія системи двох альтернативних подій змінюється від 0 до 1.
Ентропія чисельно збігається із середньою кількістю інформації але
принципово різні, так як:
H (x) - виражає середню невизначеність
стану джерела і є його об'єктивною характеристикою, вона може бути обчислена апріорно, тобто до отримання повідомлення при наявності статистики повідомлень.
I (x) - визначається апостеріорного, тобто після отримання повідомлення. З отриманням інформації про стан системи ентропія знижується.
5. НАДЛИШКОВОЇ ПОВІДОМЛЕНЬ Однією з
інформаційних характеристик джерела дискретних повідомлень є надмірність, яка визначає, яка частка максимально-можливого ентропії не використовується джерелом
, (10)
де? - коефіцієнт стиснення.
Надмірність призводить до збільшення часу передачі повідомлень, зменшенню швидкості передачі інформації, зайвої завантаження каналу, разом з тим, надмірність необхідна для забезпечення достовірності даних, що передаються, тобто надійності СПД, підвищення завадостійкості. При цьому, застосовуючи спеціальні коди, що використовують надмірність у повідомленнях, можна виявити і виправити помилки.
Приклад 1. Обчислити ентропію джерела, що видає два
символи 0 і 1 з ймовірностями
p (0) = p (1) = 1 / m і визначити його надмірність.
Рішення: Ентропія для випадку незалежних, рівноймовірно елементів дорівнює:
H (x) = log 2 m = log 2 лютого = 1 [дв.ед / симв.] При цьому
H (x) = H max (x) і надмірність дорівнює
R = 0. Приклад 2. Обчислити ентропію джерела незалежних повідомлень, що видає два символи 0 і 1 з ймовірностями
p (0) = 3 / 4, p (1) = 1 / 4. Рішення: Ентропія для випадку незалежних, не рівноймовірно елементів дорівнює:
При цьому надмірність дорівнює
R = 1-0,815 = 0,18 Приклад 3. Визначити кількість інформації та ентропію повідомлення з п'яти букв, якщо кількість літер в алфавіті одно 32 і всі повідомлення рівноімовірні.
Рішення: Загальне число пятібуквенних повідомлень одно:
N = m n = 32
Ентропія для рівноймовірно повідомлень дорівнює:
H = I =-log 2 1 / N = log лютого 1932 5 = 5 log лютого 1932 = 25 біт. / Симв.
ЛІТЕРАТУРА 1 Грінченка А.Г.
Теорія інформації та
кодування: Навч. посібник. -
Харків: ХПУ, 2000.
2 Цимбал В.П.
Теорія інформації та кодування. -М.: Вищ. шк., 1986.
3 Кловський Д. Д.
Теорія передачі сигналів. -М.: Зв'язок, 1984.
4 Кудряшов Б. Д. Теорія інформації.
Підручник для вузів Вид-во ПИТЕР, 2008. - 320с.
5 Цимбал В.П. Теорія інформації та кодування. -М.: Вищ. шк., 1986.
6 Асанов М.О., Баранський В.А., Расін В.В.
Дискретна математика: графи матроіди, алгоритми. - К.: НДЦ "РХД", 2001, 288 стор