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.


 

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

54244. Винесення множника з-під знаку кореня. Перетворення виразів, які містять квадратні корні 147.5 KB
  Мета уроку: Повторити навчальний матеріал із теми Квадратні корені; Узагальнити і систематизувати знання учнів по використанню різних підходів до перебудови вираження яке містить квадратні корені; Формувати вміння логічно думати аналізувати й порівнювати одержані результати; Розвивати креатині та алгоритмічні здібності учнів; Виховувати вміння самостійно виконувати перебудову виразів із радикалами.192 №505 Творче креативне завдання: Побудовати...
54245. Что, где, когда, конкурс для школьников 49.5 KB
  У одного старика спросили сколько ему лет. Он ответил что ему 100 лет несколько месяцев и несколько дней но дней рождения у него было только 25. Чего стало больше молока в воде или воды в молоке практическая задача поровну стакана молока в воде и столько же воды в молоке Если бы завтрашний день был вчерашним то до воскресенья осталось бы столько дней сколько дней прошло от воскресенья до вчерашнего дня. Сколько задач сын решил правильно а сколько неправильно 13 правильно 7 неправильно 1312 710=86 составить систему...
54246. Розв’язування показникових рівнянь 714 KB
  Тема: Розв’язування показникових рівнянь. Ми розглянули приклади задач із фізикибіологіїекономіки які зводяться до розв’язання показникових рівнянь. Через який час після аварії кількість радіоактивних атомів цезія – 137 зменшиться у 128 разів Розв’язок Задача зводиться до розв’язування показникового рівняння. Кобальт – 60 поражає та сприяє розвитку рака печінки.
54247. Урок - путешествие в математическую сказку, 5 класс 48.5 KB
  Цель: - отработать у учащихся навыки и умения складывать, вычитать, умножать и делить натуральные числа при решении упражнений и задач; - с помощью практических заданий и теоретических вопросов развивать творческую и умственную активность; - развивать логическое мышление, смекалку и сообразительность в нестандартных ситуациях; - воспитывать целеустремленность, уверенность в своих силах, коллективизм и самооценку;
54249. Своеобразие индийской культуры 15.18 KB
  Индийская культура является одной из самых оригинальных и уникальных. Ее самобытность заключается прежде всего в богатстве и многообразии религиозно-философских учений.
54250. МАТЕМАТИЧНА СКРИНЬКА 109.5 KB
  Хто перший назве число 100? Грають двоє. Один називає будь-яке число від 1 до 9 включно. Другий додає до названого числа будь-яке ціле число від 1 до 9 включно на свій вибір і називає суму. До цієї суми перший знову додає будь-яке ціле число від 1 до 9 включно на свій вибір і називає суму, і так далі… Виграє той, хто назве число 100.
54251. Определение квадратного уравнения. Неполные квадратные уравнения и их решения 2.57 MB
  Неполные квадратные уравнения и их решения. Цель: Ввести понятия квадратного уравнения неполного квадратного уравнения. Сформировать умения различать квадратные уравнения определять коэффициенты квадратного уравнения и по ним определять вид квадратного уравнения.
54252. Математика – це цікаво! Математика – це потрібно! 59 KB
  Математика – це цікаво Математика – це потрібно Важко обійтися сьогодні без математики Усім – і дрослим і дітям – потрібна її допомога у повсякденному житті. Колись в Америці було обіцяно велику премію тому хто напише книжку під назвою Як людина жила без математикиâ€. За більше ніж 30 років викладання математики в школі я переконалася що одним із шляхів удосконалення навчання учнів такому складному предмету є нетрадиційність у його репрезентації школярам.