- •Теорія інформації та кодування
- •Загальні положення, які необхідно знати для успішного вирішення задач теорії інформації та кодування
- •Тема 1 Кількісна оцінка інформації
- •Математичні основи теорії інформації. Міра Хартлі. Ентропія.
- •Оскільки основа логарифма дорівнює основі системи числення, для перевірки правильності розрахунків можна визначити всі можливі комбінації двійкового коду довжиною 4 біта:
- •Як видно, обидва варіанти рішення дали однаковий результат. Завдання для закріплення матеріалу заняття 1
- •Кількісна оцінка інформації в системах з нерівномірним розподілом імовірностей
- •Завдання для закріплення матеріалу заняття 2
- •Тема 2 Надлишковість повідомлень та оптимальне кодування
- •Оцінка недовантаження та надлишковості повідомлень
- •Згідно з формулою (3.1) визначаємо абсолютне недовантаження двійкового шестирозрядного повідомлення:
- •Завдання для закріплення матеріалу заняття 3
- •Оптимальне кодування повідомлень (стиск інформації)
- •Завдання для закріплення матеріалу заняття 4
- •Тема 3 Перешкодостійке кодування
- •Основи перешкодостійкого кодування. Оцінка перевіряючої та корегуючої здатності кодів
- •Завдання для закріплення матеріалу заняття 5
- •Паритетні коди. Кодування за парністю та непарністю повідомлень і блоків даних
- •Завдання для закріплення матеріалу заняття 6
- •Код Хеммінга
- •Завдання для закріплення матеріалу заняття 7
- •Циклічні коди
- •Завдання для закріплення матеріалу заняття 8
- •Значення двійкових логарифмів цілих та дробових чисел
- •Значення десяткових логарифмів цілих та дробових чисел
- •Приклади мінімальних неприводимих в полі двійкових чисел многочленів
- •Перелік використаних джерел
- •Додаткова література
Оскільки основа логарифма дорівнює основі системи числення, для перевірки правильності розрахунків можна визначити всі можливі комбінації двійкового коду довжиною 4 біта:
0000 0001 0010 0011
0100 0101 0110 0111
1000 1001 1010 1011
1100 1101 1110 1111 .
Як видно, нами отримано 16 двійкових кодових комбінацій довжиною 4 біта, які можуть бути співставлені інформаційним повідомленням даної обчислювальної системи. Таким чином, для передачі будь якого з 16 повідомлень системи достатньо передати 4 біта відповідного двійкового коду, тобто кількість інформації в такому повідомлені дорівнює 4 біта.
Примітка 1.3. Звісно, при визначенні кількості інформації в повідомленні може виникнути ситуація, коли кількість інформації не є ціле число (наприклад, кількість інформації в одному з 15 можливих повідомлень дорівнює 3.92 біта), а повідомлення, як відомо, може передаватися лише цілим числом бітів (в прикладі 1.4 – 4 біта). В таких випадках говориться про інформаційне недовантаження повідомлення, до аналізу якого ми повернемось пізніше.
Як відомо, інформацією з точки зору теорії інформації є лише те повідомлення, яке здатне знімати невизначеність, що існувала до моменту надходження цього повідомлення. З цього твердження постає питання визначення ступеня невизначеності, яка існує в кожному конкретному випадку.
Для вирішення цієї задачі в теорії інформації введено поняття ентропії як чисельної міри середньої невизначеності, що приходиться на один з можливих варіантів, який може приймати предмет дослідження (літера алфавіту, повідомлення, стан системи, результат випробування і т.д.).
У випадку, якщо різні варіанти є взаємно не пов’язаними і мають однакову імовірність виникнення, ентропія Н на один варіант визначається за формулою:
Н = logl N , (1.6)
де N – кількість різних варіантів представлення предмету дослідження; l - основа системи числення, в якій вимірюється ентропія.
Кидається в око схожість між формулами (1.2) та (1.6). Ця схожість пояснюється однаковою природою досліджуваного явища обох формул, але слід пам’ятати, що при його дослідженні в обох випадках вживаються різні підходи. Ентропія може інтерпретуватись як кількість інформації, яку необхідно передати для зняття невизначеності, що в середньому приходиться на один варіант представлення предмету дослідження. Предметом дослідження при визначені ентропії можуть бути, як вже зазначалося, літера алфавіту, повідомлення, стан досліджуваної системи, результат випробування та інші предмети, які можуть мати декілька варіантів представлення. Кількість інформації ж є характеристикою інформаційних повідомлень.
Ентропія та кількість інформації в повідомленні “об’єднуються” в момент зняття цим повідомленням невизначеності. Так, якщо k повідомлень знімають невизначеність про, відповідно, k можливих варіантів представлення предмету дослідження, то кількість інформації, що передається зазначеними повідомленнями, можна визначити за формулою:
І = k Н = k logl N . (1.7)
Приклад 1.5. Визначити ентропію на символ шістнадцяткового коду. Скільки інформації міститься в повідомленні, яке складається з 5 таких символів?
Розв’язок.
Предметом дослідження в нашому випадку є символи шістнадцяткового коду, тобто N=16. Обчислення виконаємо в двійковій системі числення, тобто l=2. За формулою (1.6) визначаємо ентропію на 1 символ:
Н = log2 16 = 4 біта/символ .
Для визначення кількості інформації в повідомленні з 5 символів (k=5) скористаємось формулою (1.7). Отримуємо:
І = 5*4 (символ*біт/символ) = 20 біт .
Примітка 1.4. На практиці досить часто виникають ситуації, коли необхідно визначити ентропію певного предмета дослідження при відомих характеристиках його складових частин. В таких випадках ентропію предмета дослідження можна визначити як суму ентропій його складових частин.
Приклад 1.6. Визначити ентропію системи з п’яти елементів, кожен з яких може знаходитись в чотирьох станах з однаковою імовірністю.
Розв’язок.
Для визначення ентропії системи в цілому згідно з приміткою 1.4 визначаємо ентропію її елементів за формулою (1.6):
Нел. =log2 4 = 2 біта/стан .
Ентропію системи визначаємо як суму ентропій її елементів:
Нсист. = Нел.1+Нел.2+Нел.3+Нел.4+Нел.5 = 5 Нел. ;
Нсист.= 5*2 = 10 біт/стан .
Для перевірки скористаємось іншим підходом. За формулою (1.1) визначимо кількість можливих станів системи:
Nсист.= 45= 1024 стани .
Згідно з формулою (1.6) визначимо ентропію системи:
Нсист.= log2 1024 = 10 біт/стан .