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.


 

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

82909. Ділення і множення багатоцифрових чисел на двоцифрове. Свято Великодня. Робота з геометричним матеріалом 367 KB
  Мета: слайд № 2 навчальна: удосконалювати з учнями алгоритм письмового множення та ділення багатоцифрових чисел на двоцифрове; ознайомити учнів із народними звичаями традиціями що повязані з початком весняного календарного обрядового циклу; розвиваюча: розвивати мовлення мислення увагу память...
82910. Множення у випадку кількох нулів у множнику 210 KB
  Спробуємо знайти другий спосіб розв’язування задачі. Чому катер за той самий час пройшов більшу відстань? (Тому, що в нього була більша швидкість). Знаючи, що катер має більшу швидкість, про що ми можемо дізнатися? (На скільки швидкість катера більша, ніж швидкість буксира?) Що для цього потрібно зробити?
82911. Чи може музика передавати рух? 102 KB
  Мета: формувати в учнів уявлення про зображальні можливості музики в передачі руху. Повторення понять темп, ритм. Розвивати уявлення учнів. Виховувати любов до української народної пісні, етикетне поводження в школі. Обладнання: фортепіано, аудіозаписи, малюнки, презентація.
82912. Співучі труби. Мідні духові 33 KB
  Мета: поглибити знання про духові інструменти познайомити із мідною духовою групою особливостями звучання інструментів що входять до її складу; підвести учнів до усвідомлення значимості мідних духових інструментів для; розвивати музичну пам’ять спостережливість...
82913. Причини виникнення пожежі – порушення правил протипожежної безпеки. Правила поведінки під час виникнення пожежі 46.5 KB
  Вогонь Правильно а звідки береться вогонь Відгадайте ще одну загадку. І мають душу щедру Хоч дерева сини Згоряючи до щенту Вогонь дають вони. Бесіда Отже сьогодні ми поговоримо про вогонь. Вогонь як ви знаєте може бути добрим другом для людини але може бути і страшним ворогом який забирає життя.
82914. Вода та її властивості 180 KB
  Давайте пригадаємо що таке природа На які групи вона поділяється Повітряземля і водаце природа Природа це я і ти це природа.вода Гостею нашого сьогоднішнього уроку буде вода а наша краплинка просто відірвалась від неї. Хто пригадає: який колір має вода смак запах Сьогодні краплинка хоче розповісти нам про властивості води.
82915. Лісові зони світу 33.5 KB
  Що побачили куди потрапили Чому це ліс Які ознаки лісу знаєте це великі ділянки землі на яких ростуть дерева розташовані близько одне від одного. Проте ліс це не тільки дерева але й інші рослини і тварини які живуть серед дерев. Кожна група рослин утворює свій поверх ярус...
82916. Зелене диво Землі — рослини. Різноманітність живих організмів. Значення рослин у природі та житті людей 52.5 KB
  Мета: продовжити формувати поняття природа нежива і жива, уявлення про царства живої природи, значення рослин, різноманітність рослин на землі, про види рослин; продовжити виробляти навички дослідницької роботи та спостереження; розвивати логічне мислення, виховувати естетичні почуття.
82917. Як розмножуються тварини 265.5 KB
  Мета: ознайомити учнів з особливостями розмноження комах, риб, плазунів, земноводних, птахів, звірів; розвивати вміння спостерігати, аналізувати, порівнювати, робити висновки; виховувати пізнавальний інтерес до природи, бажання досліджувати, берегти і вивчати природу.