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.


 

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

36069. Философия. Основы философии 1.2 MB
  В своих сочинениях Платон не просто ставит и решает те или иные философские проблемы он дает нам чистый образец того что есть философское рассуждение само по себе что за мир открывается философу и каково значение обращения души человека к миру умопостигаемого. Душа видевшая всего больше попадает в плод будущего поклонника мудрости и красоты или человека преданного Музам и любви; вторая за ней в плод царя соблюдающего законы в человека воинственного или способного управлять; третья в плод государственного деятеля хозяина...
36070. Философия жизни 130.5 KB
  Ницше: он подверг критике рационалистические концепции мира человека истории которые господствовали в философии на протяжении XVII XVIII первой половины XIX вв. НИЦШЕ гениальный немецкий философ главным мучением всей жизни которого был вопрос: Можно ли надеяться когданибудь облагородить человечество Наделенный ясновиденьем нервов С. Цвейг Ницше пережил смерть Бога в личном трагическом опыте и вместе с тем провозвещая XX век постиг как судьбу современного человека. Обозначив кризис европейского гуманизма философия Ницше...
36071. Конспект лекцій з курсу Філософія 1.63 MB
  Філософія як форма світогляду її роль в житті суспільства і людини. Буття людини. У цій ситуації проблеми світоглядної орієнтації людини усвідомлення нею свого місця і ролі в суспільстві мети і сенсу соціальної і особистої активності відповідальності за свої вчинки і вибір форм і напрямів своєї діяльності стають головними життєвими цінностями. У становленні і формуванні світоглядної культури людини філософія завжди грала особливу роль повязану з її багатовіковим досвідом критичнорефлексивного осмислення глибинних...
36072. Потенціал підприємства: сутність і механізм функціонування 73.5 KB
  Предмет мета завдання курсу управління потенціалом підприємства УПП . Елементи підприємницького потенціалу підприємства ППП Джерела потенціалу підприємства і шляхи його збільшення. Управління потенціалом підприємства УПП є сферою економічного дослідження і створення методів аналізу і оцінювання можливостей підприємств з урахуванням практики діагностики внутрішнього і зовнішнього середовища підприємств.
36073. Структурний аналіз ресурсного потенціалу в системі управління витратами і інвестиціями 92 KB
  Структурний аналіз ресурсного потенціалу в системі управління витратами і інвестиціями. Обєкти субєкти цілі в системі управління витратами. Аналіз витрат і прийняття управлінського рішення. Резерви підприємства можуть бути повязані з витратами.
36074. Виробничий потенціал: структура, вимірювання величини, оцінювання ефективності використання 89 KB
  План Характеристика виробничого потенціалу. Оцінювання виробничого потенціалу на підставі аналізу рівня ефективності використання структури робочих місць. Оцінювання ефективності використання основних елементів потенціалу підприємства основних фондів виробничого персоналу технологічного та інформаційного потенціалу. Але поряд з цим існує ще ряд практичних завдань при вирішенні цієї проблеми: вибір найбільш ефективного показника для оцінювання виробничого потенціалу підприємства; обгрунтування збалансованості виробничого...
36075. Управління потенціалом підприємства на основі маркетингової діяльності (діагностика) 205 KB
  Розробка стратегії маркетингу починається з визначення ринку або його окремого сегменту на якому здійснюється діяльність підприємства. Мета аналізу СЗГ оцінювання перспектив розвитку з погляду масштабів зростання стабільності місткості ринку перспектив технологій норми прибутку. Стан зовнішнього оточення СЗГ слід оцінювати з використанням змінних параметрів : перспектив зростання перспектив рентабельності очікуваного рівня нестабільності успішної конкурентності на ринку. Очікуваний рівень нестабільності характеризується...
36076. Управління формуванням і розвитком потенціалу підприємства 64 KB
  Оцінка організаційного потенціалу підприємства. Методів управління при формуванні потенціалу підприємства. Це досягається формуванням організаційного потенціалу шляхом: проектуванням і створенням цілеспрямованої виробничої і соціотехнічної системи; організації підприємства з встановленням цілей діяльності і корпоративних норм; організацією управління діяльністю підприємства; забезпеченням інформацією; реорганізацією реструктуризацією підприємства відповідно до зміни цілей стану внутрішнього середовища потреб споживачів продукції;...
36077. Управління трудовими ресурсами підприємства 56.5 KB
  Ринок праці функціонування ринку праці. Регулювання ринку праці. Роль підприємства в регулюванні ринку праці управління трудовими ресурсами підприємства с. Завдання першої підсистеми управління трудовими ресурсами полягає в управлінні формуванням робочої сили відтворення підготовка відшкодування управління процесом розподілу трудових ресурсів управління створення робочих місць управління перерозподілом робочої сили; управління використанням робочої сили управління...