3 Ключевые вопросы
3.1 Что такое информация и как определяется ее количество?
3.2 Что такое энтропия источника? Когда она максимальна?
3.3 Что такое избыточность источника и каковы ее причины?
3.4 Сформулировать теорему кодирования Шеннона для канала без помех.
3.5 В чем заключается основной принцип эффективного кодирования?
3.6 Что такое префиксность?
3.7 Описать алгоритм кодирования методом Хаффмана.
3.8 Описать алгоритм кодирования методом Шеннона-Фано.
3.9 Перечислить недостатки методов эффективного кодирования Хаффмана и Шеннона-Фано.
4 Домашнее задание
4.1. Выучить раздел “Эффективное кодирование дискретных источников” по конспекту лекций и ключевым положениям. Также можно воспользоваться литературой [1, с. 295-298; 2, с. 307-310; 3, с. 876-885].
4.2. Задан источник дискретных сообщений с объемом алфавита MA = 5. Количество появлений знаков задано в таблице 2. Построить дерево Хаффмана (таблицу разбиений на подгруппы методом Шеннона-Фано), записать кодовые комбинации, определить H(A), Kизб, , μ и η.
Таблица 2 – Количество появлений знаков алфавита дискретного источника
№ варианта |
Количество появлений знаков алфавита дискретного источника |
||||
А |
Б |
В |
Г |
Д |
|
1 |
30 |
25 |
20 |
15 |
10 |
2 |
40 |
20 |
18 |
12 |
10 |
3 |
48 |
25 |
12 |
10 |
5 |
4 |
33 |
30 |
17 |
16 |
2 |
5 |
43 |
18 |
14 |
13 |
12 |
6 |
37 |
29 |
16 |
10 |
8 |
4.3. Подготовиться к обсуждению по ключевым вопросам.
5 Лабораторное задание
5.1. Запустить программу “Кодирование Хаффмана”/“Кодирование Шеннона-Фано”, используя иконку “Лабораторные работы” на рабочем столе, а затем папку ОТПИ (ТИ). Изучить схему макета.
5.2. Исследовать источник дискретных равновероятных сообщений. Установить объем алфавита равным 5, затем создать поля, и оставить знаки равновероятными. Запустить алгоритм. Пошагово пронаблюдать процесс кодирования на макете. Записать кодовые комбинации, значение энтропии и рассчитать среднюю длину кодовых комбинаций. Сравнить с равномерным кодом.
Нажать кнопку “Очистить”.
Провести аналогичные исследования для равновероятных сообщений объема алфавита равного 8. Сделать выводы.
5.3. Исследовать источник дискретных не равновероятных сообщений. Установить объем алфавита равным 5, затем создать поля, в которые записать количество появлений знаков как в домашнем задании. Пошагово пронаблюдать процесс кодирования на макете. Сравнить результаты с выполненным домашним заданием. Сделать выводы.
Установить объем алфавита любым от 10 до 16. Создать поля со случайным количеством появлений знаков нажав кнопку “случайные”. Запустить алгоритм. Зарисовать процесс кодирования и записать значение энтропии. Записать кодовые комбинации, рассчитать среднюю длину кодовых комбинаций, эффективность кодирования и коэффициент сжатия. Сделать выводы о возможности декодирования сообщений.
5.4. Исследовать источник дискретных сообщений с максимальной эффективностью кодирования. Установить объем алфавита равным 6. Установить вероятности знаков равных отрицательным степеням двойки (для этого можно установить количество появлений: 16; 8; 4; 2; 1; 1). Запустить алгоритм. Записать кодовые комбинации и рассчитать среднюю длину кодовых комбинаций. Сравнить ее с энтропией. Сделать выводы.