Курс: "Теорія інформації та кодування"
Тема: "МАТЕМАТИЧНА ТЕОРІЯ ІНФОРМАЦІЇ"
Перешкоди
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. Властивість адитивності - сумарна кількість інформації двох джерел дорівнює сумі інформацією джерел.
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.
Кількість інформації дорівнює:
Е нтропія - математичне сподівання 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.
При цьому, вираз для ентропії рівноймовірно, незалежних елементів одно:
. (9)
Рис.2. Графік ентропії для двох альтернативних подій
Знайдемо ентропію системи двох альтернативних подій з ймовірностями p 1 і p 2. Ентропія дорівнює
При m = 2 для рівноймовірно подій p i = 1 / 2 ентропія дорівнює 1. Зміна ентропії в залежність від імовірності події наведено на рис. 2. Як видно, максимум ентропії відповідає різновірогідні подіям.
2. Ентропія максимальна для рівноймовірно подій.
3. Ентропія для детермінованих подій дорівнює нулю.
4. Ентропія системи двох альтернативних подій змінюється від 0 до 1.
Ентропія чисельно збігається із середньою кількістю інформації але принципово різні, так як:
H (x) - виражає середню невизначеність стану джерела і є його об'єктивною характеристикою, вона може бути обчислена апріорно, тобто до отримання повідомлення при наявності статистики повідомлень.
I (x) - визначається апостеріорного, тобто після отримання повідомлення. З по-лучанин інформації про стан системи ентропія знижується.
, (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 біт. / Симв.
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 НЕ рівноймовірно його елементів дорівнює (цей захід запропонована в 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.
При цьому, вираз для ентропії рівноймовірно, незалежних елементів одно:
Рис.2. Графік ентропії для двох альтернативних подій
H (x i) H max 1 0 0,5 1,0 P (x i) |
Знайдемо ентропію системи двох альтернативних подій з ймовірностями p 1 і p 2. Ентропія дорівнює
При m = 2 для рівноймовірно подій p i = 1 / 2 ентропія дорівнює 1. Зміна ентропії в залежність від імовірності події наведено на рис. 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 стор