Файл: Изучение методов эффективного кодирования.pdf

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
«Нижегородский государственный архитектурно-строительный университет»
(ННГАСУ)
Факультет инженерно-экологических систем и сооружений
Кафедра информационных систем и технологий
Отчет по лабораторной работе
По дисциплине: Теории информации, данные, знания
Тема:
Изучение методов эффективного кодирования
Вариант 4
Выполнил студент группы ИС-29:
Гордеев Н. С.
(подпись)
Проверил кандидат технических наук, доцент:
Родькина О.Я.
(подпись)
Нижний Новгород
2023 г.

Цель работы и задание
Изучение принципа эффективного кодирования источника дискретных сообщений на примере нескольких методов и сравнение их с равномерным кодированием.
Задание:
1. Изучить принцип эффективного кодирования источника дискретных сообщений методами Шеннона - Фано и Хаффмена.
2. Осуществить кодирование каждого сообщения алфавита (см. таблицу 1) последовательно тремя различными способами, используя двоичный код: o равномерный; o код Шеннона – Фано; o код Хаффмена, в соответствии с заданным вариантом.
3. Определить значения и
–длину кода при равномерном кодировании;
4. Для каждого из эффективных методов кодирования рассчитать значения - среднюю длину кода элементарного сообщения.
5. Для каждого из эффективных методов кодирования рассчитать значения и

Основная идея методов эффективного кодирования
Равномерный код – такой код, когда все символы какого-либо алфавита кодируются кодами одинаковой длины.
Код Шеннона – Фано.
Прежде всего, буквы (или любые сообщения, подлежащие кодированию) исходного алфавита записывают в порядке убывающей вероятности. Упорядоченное таким образом множество букв разбивают так, чтобы суммарные вероятности этих подмножеств были примерно равны. Всем знакам (буквам) верхней половины в качестве первого символа присваивают кодовый элемент 1, а всем нижним 0. Затем каждое подмножество снова разбивается на два подмножества с соблюдением того же условия равенства вероятностей и с тем же условием присваивания кодовых элементов в качестве второго символа. Такое разбиение продолжается до тех пор, пока в подмножестве не окажется только по одной букве кодируемого алфавита
Код Хаффмана.
Буквы алфавита сообщений выписывают в основной столбец таблицы в порядке убывания вероятностей. Две последние буквы объединяют в одну вспомогательную букву, которой приписывают суммарную вероятность. Вероятности букв, не участвующих в объединении и полученная суммарная вероятность снова располагаются в порядке убывания вероятностей в дополнительном столбце, а две последние объединяются. Процесс продолжается до тех пор, пока не получат единственную вспомогательную букву с вероятностью, равной единице.

Двоичное кодирование равномерным методом.

Двоичное кодирование методом Шеннона-Фано. Расчет
показателей эффективности.

Двоичное кодирование методом Хаффмана. Расчет показателей
эффективности.

Выводы об эффективности использования выбранных кодов
для данного источника.
Вычисления по данной лабораторной работе показали, что для кодирования данного источника нужно использовать коды
Хаффмана или Шеннона-Фано.