МАТЕМАТИЧНА ТЕОРІЯ ІНФОРМАЦІЇ
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.
При цьому вираз для ентропії рівноймовірно, незалежних елементів одно:
Знайдемо ентропію системи двох альтернативних подій з ймовірностями 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 НЕ рівноймовірно його елементів дорівнює (цей захід запропонована в 1948 р. К. Шенноном):
Для випадку незалежних рівноймовірно подій кількість інформації визначається (ця міра запропонована в 1928 р. Р. Хартлі):
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.
При цьому вираз для ентропії рівноймовірно, незалежних елементів одно:
Знайдемо ентропію системи двох альтернативних подій з ймовірностями 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 стор