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.


 

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

43160. Теоретический ремонт РМ при отсутствии отображения информации в режиме «ТХ» 94.5 KB
  На экране индикатора БИВ РМ №1 2 3 4 5 отсутствует отображение информации в режиме ТХ 2. УОП предназначен для организации обмена РМ с СВ хранения и регенерации принятой информации кодирования информации набранной на пультах контроля работоспособности РМ. В состав блока УОП входит: устройство управления обменом УУО; устройство кодирования пультовой информации УКПИ; устройство контроля РМ. Состав УУО: Сдвиговый регистр №1 Рг С1 96 разр осуществляет прием и выдачу информации.
43161. ИСПОЛНИТЕЛЬНЫЙ МЕХАНИЗМ 4.44 MB
  Провести расчет элементов и параметров конструкции исполнительного механизма прибора комплекса ЛА с учетом указанных в задании системных особенностей. Введение 4 Расчет кинематических параметров 5 Выбор двигателя 5 Расчет мощности двигателя 5 Кинематический расчет редуктора 6 Определение передаточного числа 6 Выбор кинематической схемы и типа используемых зп 7 Расчет числа зубьев 7 Ошибка по скорости 8 Расчет КПД...
43162. Проектирование технических расчетов зон ТО, диагностики и ТР на примере подвижного состава автотранспортных предприятий 273.5 KB
  Автомобильный транспорт является наиболее массовым и удобным видом транспорта обладающим большой манёвренностью хорошей проходимостью и приспособленностью для работы в различных климатических и географических условиях. Техническое обслуживание ТО является профилактическим мероприятием проводимым в плановом порядке через определенные длительность пробега или срок работы подвижного состава. ТО1 и ТО2 включают контрольнодиагностические крепёжные...
43163. Водный транспорт леса 2.26 MB
  В данном курсовом проекте рассмотрен пример организации первоначального лесосплава, представляющий собой комплекс производственных и подготовительных работ, связанных с перемещением лесных грузов по водным путям. В проекте рассматриваются наиболее распространенные виды водной транспортировки леса - молевой лесосплав, сплав леса в пучках, плотах и в баржах. Также необходимо оптимальным образом подобрать технику и оборудование на технологических участках, что, в свою очередь, обеспечивало бы беспрерывность работы и снижало простой данного оборудования.
43164. Восстановление детали оси пульта управления автокрана К-64 и разработка технологической планировки кабино-жестяницкого участка завода по ремонту тракторов Т-130 374.5 KB
  Курсовой проект является завершающим этапом изучения дисциплины ремонт машин и оборудования позволяющим в ходе работы над ним углубить и закрепить умение и навыки более детально изучить вопросы восстановления детали в частности оси пульта управления автокрана К64 углубить и закрепить умение и навыки в разработке технологической планировки медницкорадиаторного участка завода по ремонту тракторов Т130. В настоящее время ремонт детали достаточно широко применяется в практике эксплуатации строительных машин что и делает тему...
43165. Тепловой расчет конвективной туннельной сушильной установки для зимнего и летнего режимов 1.72 MB
  Определяем по заданным температурам tол=20.4 Определяем влагосодержание do г кгс.5 Определяем энтальпию ho кДж кгс.6 Определяем плотность природного газа при нормальных условиях.
43166. Тепловой расчет конвективной туннельной сушильной установки для зимнего (январь) и летнего (июль) периода 1.57 MB
  Выполнить тепловой расчет конвективной туннельной сушильной установки, определить длительность сушки, размеры установки, выбрать вентилятор для подачи наружного воздуха, дымосос, циклон и сожигательное устройство, на основании следующих данных.
43167. ОСКОРБЛЕНИЕ КАК ИЛЛОКУТИВНЫЙ ЛИНГВОКУЛЬТУРНЫЙ КОНЦЕПТ 194 KB
  Научная новизна данной работы заключается в применении концептологического подхода к рассмотрению лингвистических проблем права и в историко-этимологическом описании социальных явлений, которые стали основой современного толкования концепта «оскорбление». В работе была исследована дискурсная реализация этого концепта и выделена типовая базовая структура иллокутивных концептов, объясняющая прагматическую природу лингвосоциальных явлений
43168. ОБРАЗ ШЕРЛОКА ХОЛМСА В ПРОИЗВЕДЕНИЯХ СЭРА АРТУРА КОНАН ДОЙЛА 248.5 KB
  При этом мироощущение и fin de siècle и неоромантизма было подчеркнуто инаким особенным что не устраивало консервативное викторианское общество и образ Шерлока Холмса начал меняться под воздействием такого экстралитературного фактора как цензура: образ редактировался и упрощался чтобы умещаться в строгие рамки жанра семейного чтения. Таким образом образ Шерлока Холмса прошел в процессе своего формирование через влияние fin de siècle и неоромантизма чтобы прийти к викторианским традиционным ценностям. В данной работе...