Загрузил alertion

Практическая работа: Эффективное кодирование (Теория информации)

Министерство науки и высшего образования Российской Федерации
Федеральное государственное бюджетное образовательное учреждение
высшего образования
«Иркутский Национальный Исследовательский Технический Университет»
(ИрНИТУ)
Институт информационных технологий и анализа данных
Практическая работа №8
по дисциплине «Теория информации»
Вариант №1
Тема: Методы эффективного кодирования
Выполнил:
Студент гр. ИБб-23-1
Н.А.Кудрявцев
Принял:
Преподаватель:
Ю.И. Огородников
Иркутск, 2025
Дано текстовое сообщение:
ВООБРАЖЕНИЕ ВАЖНЕЕ, ЧЕМ ЗНАНИЕ
1) Определить, сколько бит занимает исходное текстовое сообщение;
2) Построить эффективный код сообщения методом Шеннона-Фано,
определить объем закодированного сообщения и эффективность
кода;
3) Построить эффективный код сообщения методом Хаффмана и
определить объем закодированного сообщения.
Задание 1.
ВООБРАЖЕНИЕ ВАЖНЕЕ, ЧЕМ ЗНАНИЕ
В — 2, О — 2, Б — 1, Р — 1, А — 3 ,Ж — 2, Е — 6, Н — 4, И — 2,
«Пробел» — 3, З — 1, М — 1; , — 1, Ч — 1
Всего символов: 30
Всего различных символов – 14; для кодирования 14 символов, 4 бита будет
достаточно. Тогда объем сообщения = 4*30 = 120 бит
Ответ: объем сообщения = 120 бит
Задание 2.
ВООБРАЖЕНИЕ ВАЖНЕЕ, ЧЕМ ЗНАНИЕ
Расположим символы в порядке убывания:
Символы по убыванию частот:
Е (6), Н (4), А (3), Пробел (3), В (2), О (2), Ж (2), И (2), Б (1), Р (1), З (1), М
(1); , (1), Ч (1).
Теперь нужно разделить символы на две группы, так, чтобы сумма «частот»
была примерна одна и та же (разделяем «сверху вниз», т. е. в первую группу
попадут символы с максимальной частотой появления. Символы первой
группы получают первый бит равный 1, вторая группа бит равный 0):
1 группа: Е (6), Н (4), А (3), Пробел (3). Сумма = 16.
2 группа: В (2), О (2), Ж (2), И (2), Б (1), Р (1), З (1), М (1), , (1), Ч (1). Сумма
= 1.
Теперь работаем отдельно с 1-ой и 2-ой группой, разбивая каждую из них
снова на две группы:
Разобьем 1 группу на две группы:


Подгруппа 1: Е (6), Н (4) → Код: 11
o
Е: 111
o
Н: 110
Подгруппа 2: А (3), Пробел (3) → Код: 10
o
А: 101
o
Пробел: 100
Код для символов из 1 группы сформирован. Тот же алгоритм для 2 группы:


Подгруппа 1: В (2), О (2), Ж (2), И (2) → Код: 01
o
В: 0111
o
О: 0110
o
Ж: 0101
o
И: 0100
Подгруппа 2: Б (1), Р (1), З (1), М (1), , (1), Ч (1) → Код: 00
o
Б: 00111
o
Р: 00110
o
З: 00101
o
М: 00100
o
, : 00011
o
Ч: 00010
Итак, мы закодировали все символы, выпишем символы и их код в таблицу:
Символ
Е
Н
А
Пробел
В
О
Ж
И
Б
Р
Код
111
110
101
100
0111
0110
0101
0100
00111
00110
З
М
,
Ч
00101
00100
00011
00010
Для расчета этого значения построил таблицу в Excel, затем с помощью
формулы «=СУММПРОИЗВ()» рассчитал требуемое значение:
Исходные
символы
Количество
символов
Частоты
символов
Кол-во двоичных разрядов
Е
Н
6
4
0,2
0,1333
3
3
А
3
0,1
3
Пробел
3
0,1
3
В
2
0,0667
4
О
2
0,0667
4
Ж
2
0,0667
4
И
2
0,0667
4
Б
1
0,0333
5
Р
1
0,0333
5
З
1
0,0333
5
М
1
0,0333
5
,
Ч
1
1
0,0333
0,0333
5
5
Сумма символов
30
Эффективность
кода
3,67
Объем
закодированного
сообщения
110
Эффективность кода = 3,67 бит/символ
Теперь рассчитаем объем закодированного сообщения, с помощью того же
СУММПРОИЗВ(): 110 (поэлементно умножали столбец «количество
символов» и столбец «кол-во двоичных разрядов», а затем все сложили)
Объем закодированного сообщения = 110 бит
Ответ:
1) Коды символов:
Символ
Код
Е
111
Н
110
А
101
Пробел
100
В
0111
О
0110
Ж
0101
И
0100
Б
00111
Р
00110
З
00101
М
00100
,
00011
Ч
00010
2) Объем закодированного сообщения = 110 бит
3) Эффективность кода = 4 бит/символ
Задание 3.
ВООБРАЖЕНИЕ ВАЖНЕЕ, ЧЕМ ЗНАНИЕ
Подсчитаем вхождение каждого из символов в сообщении и сразу
отсортируем по убыванию:
Е (6), Н (4), А (3), Пробел (3), В (2), О (2), Ж (2), И (2), Б (1), Р (1), З (1), М
(1); , (1), Ч (1).
Затем строим дерево, следующим образом:
Берем два узла, сумма которых минимальна, объединяем их в один узел.
Продолжаем до тех пор, пока не останется один «главный» узел.
Теперь, когда наше дерево создано можно кодировать сообщение. Мы
должны всегда начинать из корня. Кодируя первый символ (лист дерева
«Пробел») мы прослеживаем вверх по дереву все повороты ветвей и если
делаем левый поворот, то запоминаем 0, а если правый поворот, то
запоминаем 1.
Выполняем для всех символов:
Символ
Код
Е
00
Н
01
А
100
Пробел
101
В
1100
О
1101
Ж
1110
И
1111
Б
10000
Р
10001
З
10010
М
10011
,
10100
Ч
10101
Для вычисления объема текстового сообщения необходимы два столбца из
таблицы:
Исходные
символы
Количество
символов
Е
Н
А
Пробел
В
О
Ж
И
Б
Р
З
М
,
Кол-во двоичных
разрядов
6
4
3
3
2
2
2
2
1
1
1
1
1
3
3
3
3
4
4
4
4
5
5
5
5
5
Таблица полностью совпала с предыдущей для метода Шеннона-Фано,
следовательно, объем закодированного сообщения = 100 бит.
Ответ:
1)
Символ
Код
Е
00
Н
01
А
100
Пробел
101
В
1100
О
1101
Ж
1110
И
1111
Б
10000
Р
10001
З
10010
М
10011
,
10100
Ч
10101
2) Объем закодированного сообщения = 100 бит