Ім'я файлу: Циган О.Ю. МЗІТП Лабораторна робота №1.docx
Розширення: docx
Розмір: 238кб.
Дата: 09.12.2022
скачати
Розширення: docx
Розмір: 238кб.
Дата: 09.12.2022
скачати
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра CAПР
Лабораторна робота №1
на тему: «Методи оптимального кодування»
з дисципліни
“Методи і засоби інформаційних технологій проектування ”
Виконав:
студент групи КН-31з
Циган О.Ю.
Прийняв:
Ханас Ю.Ю.
Львів – 2022
Мета: дізнатись про оптимальні методи кодування та навчитись їх застосовувати.
Індивідуальне завдання:
Варіант 26.
| A | 90 |
| B | 50 |
| C | 45 |
| D | 40 |
| E | 30 |
| F | 10 |
| G | 10 |
Хід роботи:
Почнемо з побудови оптимального коду методом Шеннона-Фано.
| A | 90 |
| B | 50 |
| C | 45 |
| D | 40 |
| E | 30 |
| F | 10 |
| G | 10 |
Різниця між 2-ма верхніми і 5-ма нижніми буде мінімальна (140 та 135 відповідно).
Потім проводим наступні поділи.
| A | 90 | 1 |
| B | 50 | 1 |
| C | 45 | 0 |
| D | 40 | 0 |
| E | 30 | 0 |
| F | 10 | 0 |
| G | 10 | 0 |
| A | 90 | 1 | 1 |
| B | 50 | 1 | 0 |
| C | 45 | 0 | |
| D | 40 | 0 | |
| E | 30 | 0 | |
| F | 10 | 0 | |
| G | 10 | 0 | |
| A | 90 | 1 | 1 |
| B | 50 | 1 | 0 |
| C | 45 | 0 | 1 |
| D | 40 | 0 | 1 |
| E | 30 | 0 | 0 |
| F | 10 | 0 | 0 |
| G | 10 | 0 | 0 |
| A | 90 | 1 | 1 | |
| B | 50 | 1 | 0 | |
| C | 45 | 0 | 1 |  1 |
| D | 40 | 0 | 1 | 0 |
| E | 30 | 0 |  0 | |
| F | 10 | 0 | 0 | |
| G | 10 | 0 | 0 | |
Останній поділ:| A | 90 | 1 | 1 | | |
| B | 50 | 1 | 0 | | |
| C | 45 | 0 | 1 | 1 | |
| D | 40 | 0 | 1 | 0 |  |
| E | 30 | 0 | 0 | 1 | |
| F | 10 | 0 | 0 | 0 |  1 |
| G | 10 | 0 | 0 | 0 |  0 |
Отже, такий вигляд має результат кодування методом Шеннона-Фано заданих символів.
Наступним ми побудуємо оптимальний код методом Хаффмана. Символи та їх частоти залишаються такими самими, як і в попередньому прикладі.
Формуєм схему частот:
| A | 90 | 90 | 90 | 90 | 100 | 175 | 275 |
| B | 50 | 50 | 50 | 85 | 90 | 100 | |
| C | 45 | 45 | 50 | 50 | 85 | | |
| D | 40 | 40 | 45 | 50 | | | |
| E | 30 | 30 | 40 | | | | |
| F | 10 | 20 | | | | | |
| G | 10 | | | | | | |
Тепер на основі даної схеми ми намалюємо кодове бінарне дерево, котре необхідне для отримання коду Хаффмана. Для того щоб побудувати код нам потрібно позначити усі гілки дерева одиницями та нулями за принципом – усі гілки що направлені у ліву сторону (до більшого числа) позначаються одиницею, а усі що у праву сторону (до меншого числа) позначаються нулем.
Отримуєм результат кодування методом Хаффмана.
Отже маєм результати кодування обома заданими методами.
| A | 90 | 1 | 1 | | |
| B | 50 | 1 | 0 | | |
| C | 45 | 0 | 1 | 1 | |
| D | 40 | 0 | 1 | 0 | |
| E | 30 | 0 | 0 | 1 | |
| F | 10 | 0 | 0 | 0 | 1 |
| G | 10 | 0 | 0 | 0 | 0 |
| A | 90 | 1 | 1 | | |
| B | 50 | 1 | 0 | | |
| C | 45 | 0 | 1 | 1 | |
| D | 40 | 0 | 1 | 0 | |
| E | 30 | 0 | 0 | 1 | |
| F | 10 | 0 | 0 | 0 | 1 |
| G | 10 | 0 | 0 | 0 | 0 |
Кст=(8біт*суму частот усіх символів)/(довжина коду симоволу А * на його частоту + довжина коду симоволу B * на його частоту +) довжина коду симоволу C * на його частоту + довжина коду симоволу D * на його частоту + довжина коду симоволу E * на його частоту + довжина коду симоволу F * на його частоту + довжина коду симоволу G * на його частоту ) = 2200/705 = 3,121
Висновок: в даній лабораторній роботі я навчився кодувати дані методами Шеннона-Фано та Хаффмана.