69429

Код Хаффмена

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

Информатика, кибернетика и программирование

Все кодируемые сообщения источника располагаются в столбец по убывающим вероятностям. Затем два наименее вероятных сообщения расположенных в последних строках столбца объединяются в одно которому приписывается суммарная вероятность.

Русский

2014-10-04

74.5 KB

2 чел.

Министерство науки и образования Украины

Университет развития человека „Украина

Отчет по лабораторной работе
Дисциплина "Теория информации и кодирования"
Тема: " Код Хаффмена "

Принял: Вишталь 

Выполнил:
студент 3  курса гр.КС-31
Жабко К.В..

Киев 2005

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

Цель:  Изучить Код Хаффмена, выяснить особенности его построения и применения

Краткие теоретические сведения.

Все кодируемые сообщения источника располагаются в столбец по убывающим вероятностям. Затем два наименее вероятных сообщения (расположенных в последних строках столбца) объединяются в одно, которому приписывается суммарная вероятность. Затем составляется первая вспомогательная группа элементов, отличающаяся от исходной тем, что объединенный элемент занимает в колонке положение, соответствующее его вероятности. Далее процес объединения пары наимение вероятных элементов и создания второй и последующих вспомогательных групп повторяется до получения единственного элемента с вероятностью 1.
    На первом этапе работы Вам предлагается построить таблицу из дополнительных групп. 

    Второй этап тестирования заключается в отыскании кодовых комбинаций для данного сообщения по таблице дополнительных групп. Для образования кодовых сообщений необходимо построить кодовое дерево. Отмечают вершину кодового дерева и приписывают ей вероятность 1.0. Из вершины проводят две ветви, оканчивающиеся узлами. Узлам приписывают вероятности, которые при суммировении дают единицу. Вертикальной ветви (с меньшей вероятностью) приписывают символ "0", а горизонтальной (с большей) – символ "1". Если вероятность при некотором узле равна вероятности какого-либо сообщения, узлу приписывают символ этого сообщения и переходят к анализу следующего узла. Если вероятность при некотором узле образована суммированием двух меньших вероятностей, то из него опять проводят две разнонаправленные ветви, оканчивающиеся узлами. Узлам приписывают вероятности с учетом принятой ориентации. Ветвям приписывают символы: вертикальной – "0", горизонтальной – "1". Процесс построения кодового дерева продолжается, пока все символы сообщений источника не будут приписаны корневым узлам.
    Кодовые комбинации, соответствующие сообщений источника, записываются следующим образом. На полученном кодовом дереве необходимо проследить по ветвям путь от корневого узла (узла с вероятностью 1.000), до узла, соответствующего заданному сообщению, записывая последовательно слева направо символы 1 или 0, соответствующие прослеживаемым ветвям. Полученные кодовые комбинации и представляют собой оптимальный код Хаффмена.

Сообщения

Вспомогательные группы

1

2

3

4

5

6

7

8

9

P1

0.319

0.319

0.319

0.319

0.319

0.319

0.319

0.398

0.602

1.000

P2

0.138

0.138

0.138

0.145

0.169

0.229

0.283

0.319

0.398

P3

0.120

0.120

0.120

0.138

0.145

0.169

0.229

0.283

P4

0.085

0.085

0.109

0.120

0.138

0.145

0.169

P5

0.084

0.084

0.085

0.109

0.120

0.138

P6

0.083

0.083

0.084

0.085

0.109

P7

0.062

0.062

0.083

0.084

P8

0.050

0.059

0.062

P9

0.033

0.050

P10

0.026

В данном примере ветви с большей вероятностью присваювается значение "1". Очевидно, что реализация кода принципиально не поменяется, если значение "1" присваивать ветви с меньшей вероятностью.

Кодирование сообщения

Закодировать сообщение P10.

Для кодирования сообщения необходимо проследить путь по построенному дереву от корня (элемента с вероятностью 1.000 до искомого сообщения и записать по порядку значения на всех ветвях этого пути.

Для сообщения P10 этот путь будет выглядеть как 1.000 - 0.398 - 0.229 - 0.109 - 0.059 - 0.026. Записывая значения пройденных ветвей, получаем код сообщения P10 - 01010.

Закодировать сообщение      P3 – 011.

     Р9 – 01011.

     Р7 – 1010.


 

А также другие работы, которые могут Вас заинтересовать

69621. Управление временем выполнения проекта 374 KB
  Процедура сокращения времени. Косвенные издержки проекта. Прямые издержки проекта. Сокращение времени выполнения проекта. Построение графика стоимости времени выполнения проекта. Определение операций для сокращения времени их выполнения. Сценарии управления отклонениями.
69622. Формування матриці альтернатив, використання похідних критеріїв вибору 143 KB
  Мета: набути навиків у проведенні аналізів варіантів рішень та формуванні матриці альтернатив. Завдання Сформувати матрицю рішень відповідно до поставленої задачі. Задача №1 Завод випускає тонізуючий напій у 40-літрових бочках. Витрати на виробництво одного літра напою складають...
69624. Вирішення ЗПР за схемою «дерева рішень» 136.5 KB
  Мета: навчитись складати дерево цілей визначати найбільшу ефективність правильно вибирати рішення відносно дерева цілей. При виконанні індивідуального завдання необхідно: скласти дерево яке охоплює усі можливі варіанти подій; визначити найбільш ефективну послідовність дій...
69625. Визначення вартості достовірної інформації, графік корисності 102 KB
  Мета: набути навиків у проведенні аналізів варіантів рішень та формуванні матриці альтернатив. Задача №1 Завод випускає тонізуючий напій у 40-літрових бочках. Витрати на виробництво одного літра напою складають 70 коп., а продають за 1,3 грн.
69626. Організаційна структура підприємства «Foot-service» 84 KB
  Foot-Service - динамічно розвивається компанія на взуттєвому ринку України, заснована в 2010 році. Основними напрямками компанії є виробництво та оптові продажі взуття. Мета компанії це: виведення на ринок сучасної, комфортної та якісної продукції.
69627. Теорія прийняття рішень в задачах управління та контролю 32 KB
  Торгівельна фірма що продає взуття оптовим покупцям на вітчизняному ринку повинна вирішити яку кількість пар потрібно виготовити щоб задовольнити попит покупців і отримати максимальний прибуток. Закупівельна ціна однієї пари взуття становить 95 якщо партія менша 1000 штук та 90 якщо...
69628. Формування матриці альтернатив, використання класичних критеріїв вибору 48.91 KB
  Мета: набути навиків у проведенні аналізів варіантів рішень та формуванні матриці альтернатив. Завдання Сформувати матрицю рішень відповідно до поставленої задачі. Задача №1 Завод випускає тонізуючий напій у 40-літрових бочках. Витрати на виробництво одного літра напою складають...
69629. МАІ – метод аналізу ієрархій. Метод Сааті 111 KB
  Побудувати дерево ієрархії відповідно до своєї теми, на якому вказати мету, критерії та альтернативи. Визначити експертів, які будуть оцінювати альтернативи за даними критеріями за 9 – ти бальною шкалою. Визначити пріоритети критеріїв, в які входять : компоненти власного вектору...