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

Розділ 1. Інформаційна модель джерела дискретних повідомлень
Розділ 2. Статистичне кодування джерела повідомлень
Розділ 3. Інформаційна модель дискретного каналу із шумом
Розділ 4. Підходи до усунення помилок передачі каналом

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

Загальна характеристика роботи
Ця робота включає чотири розділи, що присвячени аналізу інформаційних моделей джерела і каналу передачі дискретних повідомлень, а також дослідженню відповідних базових методів кодування. Для кожного розділу наводиться окремий опис стислих теоретичних відомостей та порядку виконання роботи. Більш повні теоретичні відомості наведені зокрема в електронному конспекті лекції №4 та лекції №5
на сайті tik-diit.dp.ua за поточний рік.

Для виконання роботи студент має обрати його рівень: повний або базовий. Останній варіант суттєво менший за обсягом, але відповідний бал не перевищує 75% від повного. Далі в тексті завдання, які належать тільки повному варіанту, помічені *.

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

Розділ 1. Інформаційна модель джерела дискретних повідомлень

Короткі теоретичні дані до розділу 1

Основою підходу дисципліни ТІК є оцінювання кількості інформації в повідомленнях. Теорія пов'язує інформативність з імовірностями появи знаків: якщо така імовірність вища, то поява знака більш прогнозована і він несе менше інформації. Відповідні математичні формули одержуються для інформаційної моделі джерела дискретних повідомлень.

Рисунок 1 Основні формули інформаційної моделі дискретного джерела

Основні властивості моделі:
- модель розглядає джерело повідомлень як генератор знаків, які належать до алфавіту обсягом N. При цьому розподіл імовірностей появи знаків вважається незмінним в часі. Розглядаються варіанти моделі «без пам'яті», де наступні знаки не залежать від передісторії, а також «із пам'яттю», де така залежність присутня. В першому випадку враховуються безумовні імовірності знаків, а в другому — умовні із заданою глибиною k;
- варіант моделі «без пам'яті» дозволяє оцінити інформативність джерела через безумовну ентропію H(0) (біт/знак). При цьому мінімальному значенню Hmin=0 відповідає випадок, коли появляється тільки один вид знаків, а максимальне значення інформативності Hmax=log2N досягається при рівномірному розподілу імовірностей знаків. Такий варіант моделі дає орієнтовну оцінку інформативності джерела;
- варіант моделі «з пам'яттю» дозволяє уточнити оцінку інформативності через умовну ентропію H(1)...H(k). Така ентропія зазвичай зменшується зі зростанням глибини пам'яті k, оскільки урахування передісторії означає зростання прогнозованості наступних знаків. Варіант моделі «з пам'яттю» дозволяє більш повно оцінити інформативність джерела із врахуванням кореляції сусідніх знаків в повідомленнях.

Порядок виконання роботи в розділі 1

1.1 Дослідити властивості функції безумовної ентропії, яка характеризує питому інформативність джерела дискретних повідомлень (біт/знак). Для цього виконати розрахунки за для трьох варіантів імовірностей знаків, що відмінні за нерівномірністю їх розподілу, скориставшись електронною таблицею Вивчення ентропії та статистичне кодування.xls. Результати відобразити в табл.1.1 звіту.
Спираючись на виконані розрахунки, сформулювати висновки щодо впливу нерівномірності розподілу імовірностей знаків на питому інформативність повідомлень.

* 1.2 Дослідити інформаційних характеристик реальних джерел даних (на прикладі файлів у відповідності до індивідуального варіанту). Використати демо-програму StatDemo, яка розраховує оцінки безумовної та умовної ентропії. Результати дослідження відобразити в табл.1.2 звіту.
Спираючись на результати експериментів, сформулювати висновки щодо безумовної ентропії файлів різних типів та впливу глибини передісторії знаків на ентропію повідомлень, а отже й на рівнень їх стискання.

Розділ 2. Статистичне кодування джерела повідомлень

Короткі теоретичні дані до розділу 2

Цілі та підходи статистичного кодування джерела повідомлень пояснює рис.2.
Рисунок 2. Підходи статистичного кодування джерела повідомлень

Завданням кодування джерела є стискання вихідного коду, який зазвичай містить збитковість. Теорема Шеннона про кодування джерела дискретних повідомлень твердить, що таке стискання можливо до межі, де середня довжина коду знака Lk прагне до ентропії джерела Н. Зокрема зіставлення формул середньої довжини кода та безумовної ентропії Н(0) показує, що це можливо, коли довжина кодових ланцюжків всіх знаків прагне до їх інформативності.

Виходячи з цього статистичне стискання виконується таким чином, щоб більш імовірні (а отже і менш інформативні) знаки одержували коротші коди. В практиці найбільше поширена процедура кодування за Хаффманом, яку ми і вивчемо. Показником ефективності статистичного стискання може бути зменшення збитковості кода.

Оскільки в практиці імовірності всіх типів знаків зазвичай невідомі, застосовується два підходи: або побудування статистичних кодів безпосередньо в ході обробки конкретних повідомлень (так зване динамічне або адаптивне кодування), або попереднє перетворення знаків повідомлень, щоб виявити стійкі статистичні закономірності (так зване моделювання джерела). Тут ми дослідимо перший підхід, зокрема на прикладах адаптивного коду Хаффмена (без врахування кореляції знаків), а також метода PPM (із таким врахуванням).

Порядок виконання роботи в розділі 2

2.1 Побудувати для заданих характеристик джерела повідомлень статистичний код за процедурою Хаффмена. Порівняти збитковість вихідного (однобайтного) кодування і кодування за Хаффманом. Використати електронну таблицю Вивчення ентропії та статистичне кодування.xls.
Результати представити на рис.2.1 звіту.
Спираючись на виконані дії, сформулювати висновки щодо впливу процедури побудування, властивостей і ефективності кодування за Хаффманом.

* 2.2 Виконати експерименти із оцінювання ефективності динамічного (адаптивного) стискання за методами Хаффмана та PPM. Зокрема:
- за допомогою демо-програми ArhDemo виконати адаптивне кодування за Хаффманом для тих файлів, які досліджувались із програмою StatDemo в розділі 1. Порівняти рівень стискання із межею, яка визначається безумовною ентропією;
- за допомогою архіватора 7-Zip виконати стискання тих самих файлів, обравши при налаштуванні параметрів стискання метод PPMd. Порівняти рівень стискання із межею, яка визначається умовною ентропією з глибиною два.
Результати експериментів представити в табл.2.1.
Спираючись на одержані результати, сформулювати висновки щодо ефективності динамічного статистичного кодування.

Розділ 3. Інформаційна модель дискретного каналу із шумом

Короткі теоретичні дані до розділу 3

Характеристики та результати використання інформаційної моделі дискретного каналу із шумом відображені на рис.3.

Рисунок 3. Інформаційна модель дискретного каналу із шумом

Модель відображує вплив випадкових помилок, що можуть ставатись в каналі з фізичними завадами (як наприклад в каналі електрозв'язку або в ефірі). Такі помилки створюють невизначенісь при прийомі: насправді невідомо, чи прийнятий розряд коду Y співпадає з переданим Х, чи він був викривлений при передачі. В моделі це відображається умовною ентропією Н(X/Y). В практиці для оцінювання пропускної спроможності С (біт/c) використовують робочу формулу, яка включає два параметри: швидкість передачі Vх (розряд/c) та імовірність помилки po.

Викривлення при передачі в каналі з шумом компенсуються за рахунок використання збиткових кодів, які виявляють та усувають помилки, а також за рахунок повторної передачі помилкових фрагментів повідомлень. В обох випадках підсумковий час передачі зростає, що і відображує зниження пропускної спроможності каналу. Зокрема мінімальний час передачі обсягу інформації Q(MБ) каналом із пропускною спроможністю С(Мбіт/c) з урахуванням розмірностей може розраховуватись за формулою T= (Q*8*1024^2) /(C*1000^2) (тут в чисельнику та знаменнику використані розмірності відповідно біт та біт/c).

Порядок виконання роботи в розділі 3

3.1 Виконати розрахунок пропускної спроможності каналу та відповідного мінімального часу передачі повідомлення заданого обсягу. Результати розрахунку відобразити в таблиці 3.1. Проаналізувати використані розрахункові формули, які враховують погодження розмірностей обсягу даних (МБ) та швидкості передачі (Мбіт/с).
Спираючись на результати аналізу та розрахунків, сформулювати висновки щодо впливу імовірності помилок на пропускну спроможність каналу та потрібний час передачі повідомлень.

* 3.2 Детально проаналізувати припущення інформаційної моделі дискретного каналу при одержанні робочої формули проускної спроможності каналу.
Спираючись на результати аналізу, сформулювати висновки щодо припущень інформаційної моделі дискретного каналу.

Розділ 4. Підходи до усунення помилок передачі каналом

Короткі теоретичні дані до розділу 4

Характеристика підходів до корекції помилок передачі каналом із шумом відображена на рис.4.

Рисунок 4. Підходи щодо корекції помилок передачі

Якщо завданням кодування джерела повідомлень є усунення збитковості, то при кодуванні для передачі каналом із шумом метою є виявлення та усунення можливих помилок. Для її досягення використовуються додаткові контрольні розряди коду, які створюють умовну «захисну оболонку», потребуючи для цього певної збитковості. Теорема Шеннона про кодування каналу з шумом твердить, що за рахунок такого кодування можна впритул наблизити потік інформації до пропускної спроможності каналу.

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

Оскільки виявлення помилок кодом є значно простішим за їх усування, широко використовується спосіб корекції за рахунок повторної передачі фрагментів повідомлення, де такі помилки знайдені. Такий спосіб потребує додаткового «зворотнього» каналу передачі.

Порядок виконання роботи в розділі 4

3.1 Виконати дослідження кода з контролем парності в його варіантах з контролем по рядках та в матриці. Використати для цього демо-програму CorrectCode. Упевнитись, що кратність помилок, які гарантовано виявляє та усуває код, відповідає відповідним рівнянням (рис.4). Відобразити результати експериментів на скриншотах (рис.4.1 у звіті).
Спираючись на результати досліджень, сформулювати висновки щодо властивостей коду з перевіркою парності.

* 3.2 Проаналізувати дію схеми усунення помилок із зворотнім каналом.
Спираючись на результати аналізу, сформулювати висновки щодо механізму, переваг та обмежень такого способу корекції.

О дисциплине ТИК
Почему «Теория информации и кодирования» - одна из самых интересных дисциплин, которые изучают будущие системщики и защитники информации?

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

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

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

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