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


Шаблон оформлення звіту можна одержати тут.
Комплект матеріалів до виконання роботи (демо-програми, приклади повідомлень для дослідження) можна скачати звідсіля.
При необхідності портовану версію архіватора "7-Zip" можна одержати тут.

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


Короткі теоретичні відомості
Для оцінювання інформативності дискретних повідомлень використовується інформаційна модель, яка розглядає Джерело таких повідомлень як генератор знаків із незмінним в часі розподілом їх імовірностей. Виділяються варіанти моделі «без пам'яті», де знаки розглядаються як незалежні, а також «із пам'яттю», де враховуються такі статистичні залежності на задану глибину k. В першому випадку показником інформативності джерела є так звана безумовна ентропія H(0), яка визначається безумовними імовірностями p1..pN появи всіх знаків алфавіту: H(0)=- ∑pi log2 pi. В другому випадку інформативність характеризується умовною ентропією H(k), яка визначається умовними імовірностями знаків. Зокрема, якщо враховується тільки один попередній знак (k=1), то H(1), =- ∑pj ∑pi/j log2 pi/j. Вочевидь врахування передісторії дозволяє точніше прогнозувати появу наступних знаків, отже H(0)>=H(1)>=… На практиці значення ентропії можуть суттєво різнитись для різних типів повідомлень (зокрема, тексту, електронних таблиць, растрових зображень тощо).

Детальна характеристика властивостей ентропії наведена в лекції 4. Тут же охарактеризоване оцінювання інформативності неперервних повідомлень.

Для стискання повідомлень на основі моделей дискретного джерела розроблені класичні методи кодування. Принцип такого кодування полягає в тому, що знакам, які частіше зустрічаються в повідомленнях, а отже і несуть менше інформації, виділяються коротші коди. Згідно теореми Шеннона такий спосіб може дозволити практично повіністю усунути вихідну збитковість кодування. Метод кодування Шеннона з позицій практики має певні недоліки, отже більше розповсюдження одержав удосконалений метод Хаффмана, який гарантує одержання оптимального за збитковістю кода при заданому розподілі імовірностей знаків. Класичне кодування за Хаффманом нині використвується як складовий елемент комплексних методів стискання повідомлень без втрат інформації.

Опис методів класичного статистичного кодування, а також аналіз теореми Шеннона наведені в лекції 5.

За сучасних умов реальні повідомлення характеризуються різноманітністю типів та їх сполучень. Це обмежує можливість статистичного кодування на базі відомир розподілів імовірностей знаків. Рішення проблеми втілюють так звані динамічні методи статистичного кодування, які формують код по ходу обробки повідомлень. Зокрема, використовується динамічне кодування за Хаффменом, яке не враховує передісторію появи знаків, а також більш складний і водночас ефективний метод PPM (Prediction by Partial Matching — передбачення по частковому співпадінню), який таку передісторію враховує. Останній метод одержав поширення в складі сучаних програм архіваторів.

Характеристика методів динамічного стискання, зокрема, динамічного стискання по Хаффману, а також стискання за методом PPM наведені в лекції 5.

Зміст роботи
Робота включає три розділи, що присвячені відповідно аналізу інформаційних моделей джерела повідомлень, виконання та аналіз класичного статистичного кодування та дослідженню сучасних рішень із динамічного статистичного кодування.
Не обов'язкові розділи надалі помічаються *.

1) Аналіз інформаційних моделей джерела повідомлень включає:
- аналіз моделі дискретного джерела повідомлень, включаючи основні формули для визначення інформативності джерела через безумовну та умовну ентропію;
- дослідження інформативності типових повідомлень (зокрема тексту, растрового зображення та даних електронної таблиці) за допомогою демо-програми StatDemo;
* - аналіз моделі безперервного джерела повідомлень, включаючи основні формули для різностної ентропії, зокрема для типових розподілів імовірностей.

2) Виконання та аналіз класичного статистичного кодування передбачають:
- аналіз принципів статистичного стискання повідомлень та відповідної теореми Шеннона;
- побудування за індивідуальним завданням статистичного коду Шеннона *та коду Хаффмана;
- оцінювання ефективності кодування за показником збитковості *та аналіз можливості подальшого збільшення такої ефективності.

* 3) Дослідження динамічного підходу до статистичного кодування включає:
- детальне ознайомлення із алгоритмом динамічного кодування за Хаффманом (без урахуння передісторії появи знаків);
- детальне ознайомлення із алгоритмом динамічного кодування методом PPM (із урахунням передісторії знаків);
- дослідження щільності стискання типових повідомлень з використанням динамічного методу Хаффмана та методу PPM.

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

Для підготовки до роботи необхідно:
- ознайомитись із необхідними теоретичними відомостями, зокрема, змістом лекцій 4 та 5 в електронному конспекті на сайті tik-diit.dp.ua;
- скачати архів з методичними матеріалами та файл з шаблоном звіту із сайту та разгорнути його на робочому комп'ютері (подібно до попередньої роботи).

1) Аналіз інформаційних моделей джерела повідомлень
а) Виконати аналіз інформаційної моделі дискретного джерела:
- вписати формули для максимальної, безумовної та умовної ентропій на рис.2.1 в звіті;
- розібратись із основними властивостями моделі, зокрема в варіантах «без пам'яті» та «із пам'яттю».

б) Дослідити інформаційні характеристики типових повідомлень із допомогої демо-програми StatDemo:
- запустити програму StatDemo в папці «Програми» та в режимі «Налаштування» задати додаткову можливість розрахунку умовної ентропії другого порядку. Знайти вихідні дані в папці «Файли» згідно індивідуальному варіанту (якщо його номер перевищує 8, то взяти його саме за модулем 8. Додати в папку файл із растровим зображенням в форматі bmp із глибиной кодування 1 байт із попередньої лабораторної роботи;
- послідовно обирати файли трьох типів (текст, електронна таблиця та растрове зображення) і виконувати для нього обробку в режимі «Статистика — Загальна». Зберігати необхідні результати в табл.2.1 звіту;
- розібратись із результатами дослідження в плані різниці значень ентропії в залежності від глибини пам'яті та типів файлів.

* в) Виконати аналіз інформаційної моделі безперервного джерела
- вписати формули для різностної ентропії на рис.2.2 в звіті;
- розібратись із основними властивостями моделі, зокрема для випадків рівномірного та нормального розподілів імовірностей.

2) Побудування та аналіз класичних статистичних кодів
а) Виконати аналіз принципів статистичного стискання повідомлень та відповідної теореми Шеннона:
- записати необхідні формули та визначення на рис.2.3;
- розібратись із формулюваннями основних принципів та положень класичного статистичного кодування.

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

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

* 3) Дослідження динамічного підходу до статистичного кодування
а) Проаналізувати динамічний алгоритм кодування за Хаффманом (стискання без врахування передісторії знаків) да дослідити його ефективність:
- розібратись із динамічним кодуванням за Хаффманом по матеріалах лекції 4;
- дослідити щільність такого кодування за допомогою демо-програми ArhDemo для трьох рані досліджених файлів і відобразити результати в табл. 2.2 звіту.

б) Проаналізувати метод динамічного кодування PPM (стискання із врахуванням передісторії знаків) да дослідити його ефективність:
- розібратись із динамічним кодуванням за Хаффманом по матеріалах лекції 4;
- дослідити щільність такого кодування за допомогої архіватора 7zip для трьох рані досліджених файлів і відобразити результати в табл. 2.2 звіту.

в) Детально розібратись в одержаних результатах, звернувши увагу на різницю практичного рівню стискання і передбаченнях, що витікають із теоретичних моделей.

Вимоги до виконання роботи, оформлення та захисту звіту
Ті самі, що і для попередньої роботи

Питання для самоконтролю при підготовці до захисту звіту

До розділу 1. Аналіз інформаційних моделей джерела повідомлень
1) Поясніть формули для визначення ентропій на рис.2.1
2) В чому полягає різниця моделей джерела «без пам'яті» та «із пам'яттю»
3) Поясніть різницю энтропій для різних в типів повідомлень та різної глибини пам'яті за даними табл.2.1.
*4) Поясніть природу різностної ентропії та особливості випадків рівномірного та нормального розподілів імовірностей.

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

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

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

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

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

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