Мои Конспекты
Главная | Обратная связь


Автомобили
Астрономия
Биология
География
Дом и сад
Другие языки
Другое
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Металлургия
Механика
Образование
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Туризм
Физика
Философия
Финансы
Химия
Черчение
Экология
Экономика
Электроника

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

Лабораторная работа №10

 

Цель работы: изучить метод оптимального кодирования Хаффмана. Сравнить коды, построенные по методу Хаффмана и Шеннона-Фано (л.р.9)

Задание на лабораторную работу:

1. Проанализировать первичный алфавит: количество символов алфавита, значение энтропии. Определить длину равномерного двоичного кода

2. Сформировать коды Хаффмана для символов алфавита

3. Оценить эффективность кода Хаффмана

4. Сравнить построенные коды Хаффмана с кодами Шеннона-Фано

Методические указания:

Исходные данные для работы – упорядоченные по не возрастанию частоты встречаемости (вероятности появления) символы первичного алфавита.

Результат – кодовое дерево

Алгоритм формирования кодовых комбинаций:

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

2. Выбираются два свободных узла дерева с наименьшими весами.

3. Создается их родитель с весом, равным их суммарному весу.

4. Родитель добавляется в список свободных узлов, а двое его детей удаляются из этого списка.

5. Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой — бит 0.

6. Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.

Анализ алфавитов:

Эффективность кода определяется средним числом двоичных разрядов для кодирования одного символа:

, где k - число двоичных разрядов для кодирования символа, f - частота символа.


 

Содержание отчета:

1. Титульный лист с названием лабораторной работы, фамилией студента и группы

2. Упорядоченные по невозрастанию частоты встречаемости символы первичного алфавита.

3. Дерево кодов Хаффмана

4. Длина кодового слова при эффективном кодировании

5. Выводы по работе – оценка эффективности кода Хаффмана, сравнение кодов Хаффмана с кодами Шеннона-Фано

 

Варианты:

1. p(z1) = 0,09; p(z2) = 0,15; p(z3) = 0,24; p(z4) = 0,01; p(z5) = 0,26; p(z6) = 0,07; p(z7) = 0,16; p(z8) = 0,02

2. p(z1) = 0,12; p(z2) = 0,01; p(z3) = 0,08; p(z4) = 0,19; p(z5) = 0,23; p(z6) = 0,02; p(z7) = 0,31; p(z8) = 0,04

3. p(z1) = 0,05; p(z2) = 0,13; p(z3) = 0,20; p(z4) = 0,15; p(z5) = 0,22; p(z6) = 0,07; p(z7) = 0,08; p(z8) = 0,10

4. p(z1) = 0,15; p(z2) = 0,13; p(z3) = 0,20; p(z4) = 0,14; p(z5) = 0,12; p(z6) = 0,07; p(z7) = 0,08; p(z8) = 0,11

5. p(z1) = 0,08; p(z2) = 0,14; p(z3) = 0,24; p(z4) = 0,03; p(z5) = 0,16; p(z6) = 0,12; p(z7) = 0,16; p(z8) = 0,07

6. p(z1) = 0,03; p(z2) = 0,12; p(z3) = 0,23; p(z4) = 0,2; p(z5) = 0,03; p(z6) = 0,11; p(z7) = 0,1; p(z8) = 0,18

7. p(z1) = 0,03; p(z2) = 0,05; p(z3) = 0,31; p(z4) = 0,08; p(z5) = 0,02; p(z6) = 0,3; p(z7) = 0,1; p(z8) = 0,11

8. p(z1) = 0,15; p(z2) = 0,14; p(z3) = 0,6; p(z4) = 0,04; p(z5) = 0,16; p(z6) = 0,12; p(z7) = 0,1; p(z8) = 0,07

9. p(z1) = 0,07; p(z2) = 0,09; p(z3) = 0,12; p(z4) = 0,31; p(z5) = 0,04; p(z6) = 0,08; p(z7) = 0,11; p(z8) = 0,18

10. p(z1) = 0,14; p(z2) = 0,05; p(z3) = 0,01; p(z4) = 0,2; p(z5) = 0,19; p(z6) = 0,1; p(z7) = 0,12; p(z8) = 0,19