Лабораторная работа №2 Оптимальный код Хаффмана

Порядок выполнения работы

1. Изучить теоретический материал гл. 3 и гл.4.

2. Реализовать процедуру построения оптимального кода Хаффмана.

3. Построить код Хаффмана для текста на английском языке, использовать файл не менее 1 Кб. Распечатать полученную кодовую таблицу в виде:

Символ	Вероятность	Кодовое слово	Длина кодового слова

4. Проверить выполнение неравенства Крафта-МакМиллана для полученного кода

5. Вычислить энтропию исходного файла и сравнить со средней длиной кодового слова.

Контрольные вопросы

1. Какой код называется разделимым? Префиксным?

2. В чем заключается теорема Крафта? Теорема МакМиллана?

3. Что такое энтропия дискретного вероятностного источника?

4. Какова основная характеристика неравномерного кода?

5. Что такое избыточность кода?

6. Почему код Хаффмана называется оптимальным?

Лабораторная работа №3 Почти оптимальное алфавитное кодирование

Порядок выполнения работы

1. Изучить теоретический материал гл. 5

2. Реализовать процедуры построения кодов Шеннона, Фано и Гилберта-Мура.

3. Построить коды Шеннона, Фано и Гилберта-Мура для текста на английском языке (использовать файл не менее 1 Кб). Распечатать полученные кодовые таблицы в виде:

Символ	Вероятность	Кодовое слово	Длина кодового слова

4. Сравнить средние длины кодового слова с энтропией исходного файла для всех построенных статических кодов. Полученные результаты оформить в виде таблицы:

Энтропия исходного текста	Средняя длина кодового слова
	Код Хаффмена	Код Шеннона	Код Фано	Код Гилберта-Мура

Контрольные вопросы

1. Почему коды Шеннона, Фано и Гилберта-Мура считаются почти оптимальными?

2. На сколько средняя длина кодового слова превосходит энтропию источника для кода Шеннона? Для кода Фано?

3. Какой код называется алфавитным?

4. Являются ли алфавитными коды Шеннона, Фано и Гилберта-Мура?

5. Почему код Гилберта-Мура имеет наибольшую избыточность среди рассмотренных почти оптимальных кодов?

Лабораторная работа №4 Арифметическое кодирование

Порядок выполнения работы

1. Изучить теоретический материал гл. 6

2. Закодировать арифметическим кодом текст на английском языке, использовать файл не менее 1 Кб.

3. Вычислить коэффициент сжатия данных как процентное отношение длины закодированного файла к длине исходного файла.

4. Определить зависимость коэффициента сжатия данных от длины блока при арифметическом кодировании.

5. Декодировать файл, закодированный арифметическим кодом, и сравнить полученный файл с исходным текстом на английском языке.

Контрольные вопросы

1. Как зависит средняя длина кодового слова от длины блока при арифметическом кодировании?

2. Как формируется кодовое слово для последовательности символов при арифметическом кодировании?

3. Сколько двоичных разрядов необходимо взять для арифметического кодирования k исходных символов, чтобы декодирование было возможным?

4. Как осуществляется арифметическое декодирование?

5. Какие проблемы возникают при реализации арифметического кодирования?