3 Ключові питання
3.1 Що таке інформація і як визначається її кількість?
3.2 Що таке ентропія джерела? За яких умов вона максимальна?
3.3 Що таке надмірність джерела і які її причини?
3.4 Сформулювати теорему кодування Шеннона для каналу без завад.
3.5 У чому полягає основний принцип ефективного кодування?
3.6 Що таке префіксний код?
3.7 Описати алгоритм кодування Хаффмана.
3.8 Описати алгоритм кодування Шеннона-Фано.
3.9 Перелічити недоліки алгоритмів ефективного кодування Хаффмана й Шеннона-Фано.
4 Домашнє завдання
4.1. Вивчити розділ “Ефективне кодування дискретних повідомлень” по конспекті лекцій і ключових положеннях. Доцільно скористатися літературою [2, с. 16…26; 3]. Вивчити опис лабораторного макета в розд. 6.
4.2. Задане джерело незалежних дискретних повідомлень із обсягом алфавіту MA = 5. Кількість появ знаків дано в табл. 2. Побудувати дерево Хаффмана й таблицю розбивок на підгрупи алгоритмом Шеннона-Фано, записати кодові комбінації, визначити:
ентропію джерела повідомлень H(A);
коефіцієнт надмірності джерела Kнад;
середню довжину кодових комбінацій ;
коефіцієнт ефективність кодування μ;
коефіцієнт стиснення повідомлення .
4.3. Підготуватися до обговорення по ключових питаннях.
Таблиця 2 – Кількість появ знаків алфавіту дискретного джерела
Номер бригади |
Кількість появ знаків |
||||
А |
Б |
В |
Г |
Д |
|
1, 7 |
30 |
25 |
20 |
15 |
10 |
2, 8 |
40 |
20 |
18 |
12 |
10 |
3, 9 |
48 |
25 |
12 |
10 |
5 |
4, 10 |
33 |
30 |
17 |
16 |
2 |
5, 11 |
43 |
18 |
14 |
13 |
12 |
6, 12 |
37 |
29 |
16 |
10 |
8 |
5 Лабораторне завдання
5.1 Ознайомитися з віртуальним макетом на робочому місці. Для цього запустити програму 2.1 Дослідження алгоритмів ефективного кодування джерел дискретних повідомлень, використовуючи іконку Лабораторні роботи на робочому столі, а потім папки ТЕЗ та Модуль 2. Вивчити схему макета на дисплеї комп’ютера, користуючись розд. 6. Уточнити з викладачем план виконання лабораторного завдання.
5.2 Дослідити джерело дискретних рівноймовірних повідомлень. Установити обсяг алфавіту рівним 5, потім створити поля, і залишити знаки рівноймовірними. Запустити програму на виконання. Спостерігати покроковий процес кодування. Записати кодові комбінації, значення ентропії й розрахувати середню довжину кодових комбінацій. Порівняти середню довжину з довжиною рівномірного коду.
Провести аналогічні дослідження для джерела рівноймовірних повідомлень обсягу алфавіту МА = 8. Зробити висновки.
5.3 Дослідити джерело дискретних нерівноймовірних повідомлень. Установити обсяг алфавіту рівним 5, потім створити поля, у які записати кількість появ знаків з домашнього завдання. Спостерігати покроковий процес кодування. Порівняти з результатами виконання домашнього завдання. Зробити висновки.
Установити обсяг алфавіту будь-яким від 10 до 16. Створити поля з випадковою кількістю появ знаків, натиснувши кнопку “Випадкові”. Запустити програму на виконання. Зафіксувати у зошиті процес кодування та значення ентропії. Записати кодові комбінації, розрахувати середню довжину кодових комбінацій, ефективність кодування й коефіцієнт стиснення. Зробити висновки про можливість декодування повідомлень.
5.4 Дослідити джерело дискретних повідомлень із максимальною ефективністю кодування. Установити обсяг алфавіту рівним 6. Установити ймовірності знаків рівні від’ємним степеням двійки (для цього можна встановити кількість появ: 16; 8; 4; 2; 1; 1). Запустити програму на виконання. Записати кодові комбінації й розрахувати їх середню довжину. Порівняти її з ентропією. Зробити висновки.