3. Запрограмувати процедуру кодування методом довжин серій.
4. Створити файл (не менше 1 Кб), що містить послідовність з нулів і одиниць, причому P (0) >> P (1). Порівняти ступеня стиснення цього файлу методом довжин серій при використанні трьох кодів цілих чисел (Fixed + Variable, # 947; -код Еліаса, # 969; -код Еліаса).
5. Коефіцієнт стиснення визначати як процентне відношення довжини закодованого файлу до довжини вихідного файлу.
6. Результати оформити у вигляді таблиці
Коефіцієнт стиснення файлу
1. У чому полягає основна ідея кодування цілих чисел?
2. Чим відрізняються коди Fixed + Variable і Variable + Variable?
3. Як формуються кодові слова гамма-коду Еліаса?
4. Як будується омега-код Еліаса?
5. У чому полягає кодування довжин серій?
Лабораторна робота №2
Оптимальний код Хаффмана
Порядок виконання роботи
1. Вивчити теоретичний матеріал гл. 3 і гл.4.
2. Реалізувати процедуру побудови оптимального коду Хаффмана.
3. Побудувати код Хаффмана для тексту англійською мовою. використовувати файл не менше 1 Кб. Роздрукувати отриману кодову таблицю у вигляді:
4. Перевірити виконання нерівності Крафта-Макміллана для отриманого коду
5. Обчислити ентропію вихідного файлу і порівняти з середньою довжиною кодового слова.
1. Які символи ви бачите називається разделімого? Префіксним?
2. У чому полягає теорема Крафта? Теорема Макміллана?
3. Що таке ентропія дискретного імовірнісного джерела?
4. Яка основна характеристика нерівномірного коду?
5. Що таке надмірність коду?
6. Чому код Хаффмана називається оптимальним?
Лабораторна робота №3
Майже оптимальне алфавітний кодування
Порядок виконання роботи
1. Вивчити теоретичний матеріал гл. 5
2. Реалізувати процедури побудови кодів Шеннона, Фано і Гілберта-Мура.
3. Побудувати коди Шеннона, Фано і Гілберта-Мура для тексту англійською мовою (використовувати файл не менше 1 Кб). Роздрукувати отримані кодові таблиці у вигляді:
1. Чому коди Шеннона, Фано і Гілберта-Мура вважаються майже оптимальними?
2. На скільки середня довжина кодового слова перевершує ентропію джерела для коду Шеннона? Для коду Фано?
3. Які символи ви бачите називається алфавітним?
4. Чи є алфавітними коди Шеннона, Фано і Гілберта-Мура?
5. Чому код Гілберта-Мура має найбільшу надмірність серед розглянутих майже оптимальних кодів?
Лабораторна робота №4
Порядок виконання роботи
1. Вивчити теоретичний матеріал гл. 6
2. Закодувати арифметичним кодом текст англійською мовою, використовувати файл не менше 1 Кб.
3. Обчислити коефіцієнт стиснення даних як процентне відношення довжини закодованого файлу до довжини вихідного файлу.
4. Визначити залежність коефіцієнта стиснення даних від довжини блоку при арифметичному кодуванні.
5. Декодувати файл, закодований арифметичним кодом, і порівняти отриманий файл з вихідним текстом англійською мовою.
1. Як залежить середня довжина кодового слова від довжини блоку при арифметичному кодуванні?
2. Як формується кодове слово для послідовності символів при арифметичному кодуванні?
3. Скільки двійкових розрядів необхідно взяти для арифметичного кодування k вихідних символів, щоб декодування було можливим?
4. Як здійснюється арифметичне декодування?
5. Які проблеми виникають при реалізації арифметичного кодування?
Лабораторна робота №5
Порядок виконання роботи
1. Вивчити теоретичний матеріал гл. 7
2. Закодувати текст англійською мовою (використовувати файл не менше 1 Кб) за допомогою адаптивного коду Хаффмана, коду «Стопка книг», інтервального і частотного кодів.
3. Обчислити коефіцієнти стиснення даних як процентне відношення довжини закодованого файлу до довжини вихідного файлу.
4. Порівняти отримані коефіцієнти стиснення даних, побудувати таблицю виду:
4. Декодувати файли, закодовані словниковим кодом, і порівняти отримані файли з вихідними текстами.
1. Яка загальна схема кодування, яка використовується в LZ-методах?
2. Чим відрізняються один від одного алгоритми класу LZ?
3. У чому полягає метод кодування на безперервній основі вікна?
4. Як використовується в LZ-кодах адаптивний словник?
5. Як здійснюється декодування в методах з адаптивним словником?
1. Ахо А. Хопкрофта Дж. Ульман Дж. Структури даних і алгоритми. - М. Видавничий дім "Вільямс", 20с.
4. Галлагер Р. Теорія інформації та надійний зв'язок. - М. Радянське радіо, 19с.
5. Кричевський і пошук інформації. - М. Радіо і зв'язок, 19с.
Псевдокод для запису алгоритмів
: = Операція присвоювання значень.
Операція обміну значеннями.
1. IF (умова) Якщо виконується умова,
<действие> то виконати дію
FI FI вказує на кінець цих дій.
ELSE <действия 2> Дії 2 виконуються,
FI якщо невірно умова.
ELSEIF (условіе2) Дії 2 виконуються,
<действия2> якщо невірно условіе1 і вірно умова 2
1.Цікл з передумовою.
DO (умова) Дії повторюються
<действия> поки умова істинна.
OD OD вказує на кінець циклу.
2.Цікл з умовою поста.
OD (умова виконання)
3.Цікл з параметром.
DO (i = 1, 2. n) Дії виконуються для значень
<действия> параметра зі списку
4.Бесконечний цикл.
5.Прінудітельний вихід з циклу.
IF (умова) OD Якщо умова істинно, то вийти з циклу.
Олена Вікторівна Курапова
Олена Павлівна Мачікіна
ОСНОВНІ МЕТОДИ КОДУВАННЯ ДАНИХ
Методичні вказівки
Підписано до друку.
Формат паперу 62 x 84/16, видрукувано на різографі, шрифт № 10,
изд. л. замовлення №. тираж - прим. СібГУТІ.
З через великий обсяг цей матеріал розміщений на декількох сторінках:
1 2 3 4 5 6