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