Аналіз моделі джерела дискретних повідомлень та ефективного статистичного кодування
Методичні вказівки до виконання лабораторної роботи №2
з курсу «Теорія інформації та кодування»


Шаблон оформлення звіту можна одержати тут в форматах doc або odt.

Мета роботи:
- закріпити знання про модель джерела дискретних повідомлень;
- закріпити знання принципів ефективного статистичного кодування джерела й опанувати побудову коду Хаффмена;
- оцінити підходи до статистичного стиснення реальних повідомлень.


Короткі теоретичні відомості
Інформаційна модель джерела дискретних повідомлень використовується для аналізу їх інформативності. Така модель описує джерело повідомлень як генератор випадкової послідовності знаків, для яких задані їх незмінні ймовірності. Як показник інформативності (біт/знак) застосовується ентропія, що визначається обсягом використовуваного алфавіту й розподілом імовірностей знаків. Оцінка продуктивності джерела (біт/с) враховує середню швидкість генерації знаків. Найпоширенішим є варіант моделі джерела «без пам'яті», у якому знаки вважаються незалежними. Тут ентропія називається безумовною. Більш повний, але й більш громіздкий варіант моделі «з пам'яттю» враховує залежності знаків на задану глибину. Така модель дозволяє оцінити умовну ентропію. Детальний опис інформаційних моделей дискретного джерела, що містить формули для розрахунку ентропії та аналіз прийнятих припущень, наведено в лекції 3.

Ефективне статистичне кодування знаків базується на врахуванні ймовірнісних закономірностей джерела повідомлень. Зокрема, знакам, які частіше трапляються, присвоюються коротші кодові ланцюжки. При цьому для визначення меж ланцюжків має виконуватися додаткова умова «префіксності». Згідно з теоремою Шеннона про кодування джерела, такий підхід, у принципі, може повністю усувати надмірність вихідного коду (середня довжина кодових ланцюжків знаків наближається до ентропії). На практиці застосовуються відносно прості коди, які забезпечують прийнятний ступінь стиснення. Зокрема, поширення набув код Хаффмена, який будується виходячи з інформаційної моделі джерела без пам'яті й забезпечує наближення середньої довжини коду до величини безумовної ентропії. Процедура побудови коду Хаффмена й характеристика його використання наведені в лекції 4.

Можливості статистичного кодування реальних повідомлень обмежуються тим, що розподіл ймовірностей знаків часто заздалегідь не відомий. Рішенням тут може бути використання адаптивного підходу, коли код формується й коригується в ході обробки знаків повідомлення. Зокрема, застосовується адаптивний варіант коду Хаффмена, який описаний у лекції 4. Для більшості практично важливих типів повідомлень характерна суттєва взаємозалежність між сусідніми знаками (як, наприклад, між літерами в словах тексту). Це проявляється в зменшенні ентропії зі збільшенням глибини пам'яті джерела. На практиці таке зменшення означає можливість додаткового стискання повідомлень, якщо відповідний код враховує взаємозв'язки знаків. Такі коди будуть розглянуті в наступній лабораторній роботі.

Зміст роботи
Ця робота містить три розділи, які передбачають:
- аналіз базової інформаційної моделі дискретного джерела;
- аналіз способу статистичного кодування джерела;
- аналіз підходів до кодування реальних повідомлень.


У розділі 1 аналізується опис інформаційної моделі дискретного джерела повідомлень. За допомогою електронної таблиці з розрахунковими формулами моделі без пам'яті визначаються характеристики джерел за заданим індивідуальним варіантом. Їх аналіз показує погодженість з результатами теорії.

У розділі 2 коротко характеризуються принципи ефективного статистичного кодування, будується таблиця кодування за Хаффменом для заданих згідно з індивідуальним варіантом ймовірностей знаків, а також виконується порівняння надмірності початкового й одержаного кодування. Реалізується приклад кодування для заданої послідовності знаків.

У розділі 3 за допомогою відповідної програми виконується адаптивне кодування за Хаффменом для заданих файлів поширених форматів і оцінюється його ефективність. Також за допомогою програми аналізу інформаційних характеристик повідомлень здійснюється розрахунок безумовної та умовної ентропії для тих самих файлів. Результати підтверджують значущість врахування зв'язків сусідніх знаків при стисканні.

Порядок виконання роботи

Підготовка до виконання роботи:
1. Ознайомитися з теоретичним матеріалом, використовуючи електронний конспект лекцій 3 і 4 на сайті tik-diit.dp.ua.
2. Закріпити знання, використовуючи режим пробного тестування.
3. Завантажити архів матеріалів до лабораторної роботи і розгорнути його на робочому комп'ютері.

Виконання розділу 1:
1. Спираючись на вивчений теоретичний матеріал, заповнити пропуски в тексті пункту 1 та вписати формули на рис. 2.1 звіту.
2*. Проаналізувати припущення моделі, їх переваги та обмеженість.
3. За допомогою електронної таблиці із сайту виконати розрахунок інформаційних характеристик заданих джерел відповідно до варіанта. Внести результати до табл. 2.1 звіту (додаток Б). За результатами їх аналізу заповнити пропуски в тексті п. 2.

Виконання розділу 2:
1. Спираючись на теоретичний матеріал, заповнити пропуски в тексті пункту 1 та поля на рис. 2.2 звіту.
2. Використовуючи приклад на рис. 2.3, детально розібрати методику побудови таблиці кодування за Хаффменом. Заповнити пропуски у відповідному тексті.
3*. Виконати побудову коду Хаффмена за індивідуальним варіантом. Відобразити результати у звіті у вигляді, аналогічному рис. 2.3.
4. Виходячи з отриманих результатів кодування, виконати порівняння надмірності для вихідного й отриманого коду (рис. 2.3). Зробити висновок про ефективність кодування за Хаффменом.
5*. Для заданої індивідуальної послідовності знаків виконати кодування та декодування згідно з побудованою в п. 2 таблицею. При декодуванні звернути увагу на необхідність «префіксності» коду. Внести результати у звіт у вигляді, аналогічному рис. 2.4.

Виконання розділу 3:
1. Спираючись на вивчений теоретичний матеріал, заповнити пропуски в тексті п.1 звіту.
2. За допомогою програми ArchDemo виконати для заданих файлів стискання за адаптивним методом Хаффмена. Відобразити результати в табл. 2.2. Проаналізувати досягнутий ступінь стискання й зробити висновки про можливості використання адаптивного методу Хаффмена. З урахуванням отриманих результатів заповнити пропуски в тексті пункту 2.
3*. Детально розібрати алгоритм адаптивного стискання за Хаффменом.
4. За допомогою програми StatDemo виконати для заданих файлів оцінку максимальної, безумовної та умовної ентропії (при глибині пам'яті 1 і 2). Внести результати до звіту у формі табл. 2.3. Зробити висновки щодо суттєвості врахування зв'язків сусідніх знаків.

Запитання та завдання для самоконтролю

До розділу 1
1. Запишіть основні розрахункові формули інформаційної моделі джерела дискретних повідомлень.
2*. Поясніть основні припущення моделі. Як вони можуть порушуватися в реальних повідомленнях. Чим виправдане прийняття таких припущень?
3. Поясніть результати розрахунків характеристик джерел повідомлень у табл. 2.1.
4. Сформулюйте закономірності, які підтверджуються результатами розрахунків.

До розділу 2
1. Назвіть основні принципи статистичного кодування. У чому полягає умова «префіксності» коду й чому необхідно її дотримання?
2. Запишіть формули для визначення середньої довжини кодового ланцюжка знака й величини надмірності кодування.
3. Сформулюйте теорему Шеннона про кодування джерела. *Чому на практиці задовольняються приблизним виконанням умов теореми?
4. Назвіть етапи побудови таблиці кодування за Шенноном, ілюструючи прикладом рис. 2.3.
5. Прокоментуйте спосіб і результати оцінки надмірності для початкового й одержаного коду. Як Ви оцінюєте ефективність побудованого коду?
6*. Запишіть довільну послідовність двійкових розрядів і декодуйте її за допомогою побудованої таблиці Хаффмена. Як при цьому використовується правило «префіксності»?

До розділу 3
1. У чому полягають переваги адаптивного статистичного стискання?
2*. Охарактеризуйте алгоритм адаптивного стискання за Хаффменом.
3. Чому адаптивний алгоритм Хаффмена не використовується в сучасних архіваторах?
4. Поясніть результати аналізу ентропії в табл. 2.3. Чому вони дають підставу вважати, що стискання з урахуванням зв'язку між знаками може бути більш ефективним?
5*. Чому умовна ентропія може зменшуватися зі збільшенням глибини пам'яті джерела? За яких умов вона буде залишатися незмінною?
О дисциплине ТИК
Почему «Теория информации и кодирования» - одна из самых интересных дисциплин, которые изучают будущие системщики и защитники информации?

В ней сочетаются золотая классика и самая актуальная современность computer-science.

продолжение
О сайте
Здесь вы найдете материалы, которые помогут в изучении дисциплины “Теория информации и кодирования” (ТИК) в том виде, как она преподается на кафедре ЭВМ ДИИТа.

На сайте размещены методические материалы:
  • электронный конспект лекций;
  • методическое обеспечение к лабораторным работам;
  • полезные ссылки.

продолжение
© 2008-2013 • Теория информации и кодирования
UP