6. Эффективное кодирование. Код Хаффмана

МИНОБРНАУКИ РОССИИ

Санкт-Петербургский государственный

электротехнический университет

«ЛЭТИ» им. В.И. Ульянова (Ленина)

Кафедра информационных систем

отчЁт

по практической работе №6

по дисциплине «Теория информации, данные, знания»

Тема: Эффективное кодирование. Код Хаффмана.

Студент гр. 93—		—
Преподаватель		Писарев И. А.

Санкт-Петербург

2020

Цель работы

Сформулировать ответы на вопросы с указанием источников информации.

Вопросы по теме:

1. Опишите метод Хаффмана.

2. Какие существуют другие методы кодирования? Дайте их сравнительную характеристику.

3. Укажите правильный вариант ответа. Если взять два наименее вероятных символа в алфавите, эти два символа получат кодовые слова с максимальной длиной, отличающиеся:

   1. последним символом

   2. первым символом

Решить задачи:

1. Закодировать сообщение методом Хаффмана.

Сообщение	1	2	3	4	5	6	7
Вероятность	0,3	0,2	0,2	0,1	0,1	0,05	0,05

2. Алфавит содержит 7 букв, которые встречаются с вероятностями 0,4; 0,2; 0,1; 0,1; 0,1; 0,05; 0,05. Осуществить кодирование по методу Хаффмана.

Выполнение работы

Вопрос 1.

1. Взять два наименее вероятных символа в алфавите. Эти два символа получат кодовые слова с максимальной длиной, отличающиеся последним символом.

2. Объединить два символа в один, повторить 1.

(1, С. 58)

Вопрос 2.

Другие методы кодирования:

1. Оптимальное кодирование Шеннона;

   1. обеспечивает ;

2. Оптимальное кодирование Шеннона—Фано;

3. Блочное кодирование;

   1. устраняет избыточность кода;

4. Арифметическое кодирование;

   1. энтропийный, как алгоритм Хаффмана;

   2. более высокие результаты сжатия, чем у алгоритма Хаффмана;

   3. кодирует символ нецелым числом бит.

(1, С. 57—60)

Вопрос 3.

Взять два наименее вероятных символа в алфавите. Эти два символа получат кодовые слова с максимальной длиной, отличающиеся последним символом. (1, С. 58)

Задача 1.

Сообщение	Вероятность	Процесс кодирования						Код
1	0,3	0,3	0,3	0,3	0,4	0,6	1,0	11
2	0,2	0,2	0,2	0,3	0,3	0,4		00
3	0,2	0,2	0,2	0,2	0,3			01
4	0,1	0,1	0,2	0,2				101
5	0,1	0,1	0,1					1000
6	0,05	0,1						10010
7	0,05							10011

1,0
0,4 (0)				0,6 (1)
0,2 (0)		0,2 (1)		0,3 (0)						0,3 (1)
					0,2 (0)			0,1 (1)
					0,1 (0)	0,1 (1)
						0,05 (0)	0,05 (1)

Задача 2.

		Процесс кодирования						Код
	0,4	0,4	0,4	0,4	0,4	0,6	1,0	0
	0,2	0,2	0,2	0,2	0,4	0,4		10
	0,1	0,1	0,2	0,2	0,2			1100
	0,1	0,1	0,1	0,2				1101
	0,1	0,1	0,1					1110
	0,05	0,1						11110
	0,05							11111

1,0
0,4 (0)	0,6 (1)
	0,2 (0)	0,4 (1)
		0,2 (0)		0,2 (1)
		0,1 (0)	0,1 (1)		0,1 (0)	0,1 (1)
						0,05 (0)	0,05 (1)

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Гошин Е.В. Теория информации и кодирования. Самара: Самарский университет. 2018. 124 с.