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.


 

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

72045. РОЗВИТОК НАУКОВИХ ОСНОВ ФОРМУВАННЯ СТРУКТУРИ ТА ВЛАСТИВОСТЕЙ ЗНОСОСТІЙКИХ НИЗЬКОХРОМИСТИХ ЧАВУНІВ ДЛЯ ДЕТАЛЕЙ ТЕХНОЛОГІЧНОГО ОБЛАДНАННЯ 377 KB
  Важливе місце в переробці сировинних і будівельних матеріалів належить операціям дроблення, подрібнювання та розмелу, що споживають більше половини всіх енергетичних і матеріальних витрат переробних підприємств у гірничо-металургійній, сировинній, будівельній і енергетичній галузях промисловості України.
72046. ДОІНДОЄВРОПЕЙСЬКИЙ СУБСТРАТ У ЛЕКСИЦІ СЛОВ’ЯНСЬКИХ, ГЕРМАНСЬКИХ І РОМАНСЬКИХ МОВ 195 KB
  Актуальність дисертаційної роботи продиктовано сучасною тенденцією компаративістики до вивчення мовних явищ у тісному зв’язку з історією та культурою народу загалом та необхідністю комплексного дослідження міжетнічних і міжкультурних контактів, на тлі яких зростає інтерес до етногенетичних процесів...
72047. ФОРМУВАННЯ ЛОГІСТИЧНОЇ МОДЕЛІ УПРАВЛІННЯ ДІЯЛЬНІСТЮ КОМУНАЛЬНИХ ФАРМАЦЕВТИЧНИХ ПІДПРИЄМСТВ В УМОВАХ МЕНЕДЖМЕНТУ ЯКОСТІ 920 KB
  Головною метою діяльності комунальних фармацевтичних підприємств КФП є виконання соціальної функції щодо максимально повного і ефективного забезпечення населення регіону доступними за ціною та якісними лікарськими засобами ЛЗ і виробами медичного призначення ВМП.
72048. ЕМБРІОНАЛЬНИЙ ГІСТОГЕНЕЗ НИРКИ У РАННІХ ЗАРОДКІВ ЛЮДИНИ 197 KB
  В тепершній час відсутня концепція механізмів регуляції розвитку людини оскільки більшість наведених у літературі даних грунтується на вивченні ембріогенезу експериментальних тварин або на культивуванні ембріональних клітин.
72049. СТРАТЕГІЧНИЙ АНАЛІЗ КОНКУРЕНТОСПРОМОЖНОСТІ ПІДПРИЄМСТВ 234.5 KB
  За відсутності комплексної методики аналізу конкурентоспроможності підприємства виникає низка важливих питань які потребують вирішення. Для досягнення належної конкурентоспроможності підприємства необхідні тривалий час і значні зусилля.
72050. СОЦІАЛЬНЕ ПРОЕКТУВАННЯ: ПРОБЛЕМА ВЗАЄМОЗВ’ЯЗКУ СУСПІЛЬНИХ ПОТРЕБ І ДЕРЖАВНИХ ІНТЕРЕСІВ 287 KB
  На підґрунті діалектичного підходу сутність соціального проектування розкривається як суперечливий процес відтворення рефлексивної єдності соціального суб’єкта та об’єктивної реальності. Згідно з цим реалізується принцип відповідності, за яким встановлюються логіко-гносеологічні засоби відновлення...
72051. ФОРМУВАННЯ КУЛЬТУРИ ЕКОНОМІЧНОГО МИСЛЕННЯ МАЙБУТНІХ ГЕОГРАФІВ У ПРОЦЕСІ ПРОФЕСІЙНОЇ ПІДГОТОВКИ 192.5 KB
  Стрімкий розвиток сучасних економічних відносин і вплив господарської діяльності людини на всю поверхню Землі як інтегрованого утворення вимагає переосмислення не тільки місця людини в географічному світі але й її ставлення до навколишнього середовища.
72052. ПОРІВНЯЛЬНИЙ АНАЛІЗ ОКРЕМИХ ПАТОБІОХІМІЧНИХ ТА ПАТОМОРФОЛОГІЧНИХ ЕКВІВАЛЕНТІВ ІШЕМІЧНО-РЕПЕРФУЗІЙНОГО ПОШКОДЖЕННЯ ГОЛОВНОГО МОЗКУ В ДОРОСЛИХ ТА СТАРИХ ЩУРІВ 469.5 KB
  З’’ясувати особливості деяких ланок патогенезу ішемічно-реперфузійного пошкодження структур нової кори та гіпокампа в старих самцівщурів за окремими гістохімічними патобіохімічними і патоморфологічними параметрами на...
72053. МЕДИКО-СОЦІАЛЬНЕ ОБГРУНТУВАННЯ ОПТИМІЗАЦІЇ ФУНКЦІОНАЛЬНО-ОРГАНІЗАЦІЙНОЇ МОДЕЛІ ЗБЕРЕЖЕННЯ ТА ПОЛІПШЕННЯ ЗДОРОВ’Я ШКОЛЯРІВ ВЕЛИКОГО ПРОМИСЛОВОГО МІСТА 306 KB
  Актуальність оптимізації діяльності зі збереження та поліпшення здоров’я дитячого населення посилюється необхідністю виконання Програми економічних реформ на 2011–2014 роки «Заможне суспільство, конкурентоспроможна економіка, ефективна держава» в частині реформування системи надання медичної допомоги.