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.


 

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

24950. Обязательства из односторонних действий 48.5 KB
  Обязательства из односторонних действий Для реализации обязанностей составляющих содержание рассматриваемых обязательств необходимы односторонние сделки дополнительные юридические факты несколькими последовательно совершаемыми односторонними сделками центральное место среди которых занимает первоначальная сделка определяющая содержание обязательства. Но заключенная в ней обязанность реализуется при условии совершения других действий иными лицами поэтому она является условной под отлагательным условием п. 3 вида обязательств из...
24951. Субъекты обязательства. Обязательства со множественностью лиц 38.5 KB
  Субъекты обязательства. Обязательства со множественностью лиц. Но обязательства могут различаться по своему субъектному составу. Возможны обязательства со множественностью лиц на стороне должника пассивная множественность либо на стороне кредитора активная множественность либо с обеих сторон конкретного обязательства при участии не одного а нескольких лиц например несколько наследников.
24952. Принципы исполнения обязательств 58.5 KB
  Принципы исполнения обязательств. Правовая природа односторонняя сделка либо юридический поступок спор 1 Принцип надлежащего исполнения. Предполагает необходимость точного и своевременного исполнения обязательств в строгом соответствии с условиями соглашения и требованиями законодательства. выделяет 6 элементов надлежащего исполнения: 1.
24953. Условия действительности сделок. Гражданско-правовые средства, применяемые в случае совершения недействительной сделки и их значение 34.5 KB
  Гражданскоправовые средства применяемые в случае совершения недействительной сделки и их значение 1. Условия действительности сделок Действительность сделки признание за ней качества юридического факта порождающего тот правовой результат к которому стремились стороны сделки. Способность физических и юридических лиц совершающих сделки к участию в сделке. Данная способность связана с вопросом о дееспособности или недееспособности физического лица вопросом о характере правоспособности юридического лица общая или специальная вопросом о...
24954. Способы и порядок заключения правовых договоров 72.5 KB
  Заключение договора достижение сторонами в надлежащей форме соглашения по всем существенным условиям договора в порядке предусмотренном законодательством. Договор считается заключенным при соблюдении двух необходимых условий: сторонами должно быть достигнуто соглашение по всем существенным условиям договора; достигнутое сторонами соглашение по своей форме должно соответствовать требованиям предъявляемым к такого рода договорам ст. Два случая заключения договора: между присутствующими и между отсутствующими .
24955. Виды договоров в гражданском праве 32 KB
  В зависимости от основания классифицировать можно договоры как угодно. Поэтому делит все договоры на: договоры направленные на передачу имущества в собственность в аренду в пользование и т.; договоры направленные на выполнение работ; договоры направленные на оказание услуг; договоры направленные на создание коллективных обязанностей учредительные договоры; договоры направленные на использование результатов интеллектуальной деятельности. Учебник классифицирует гражданскоправовые договоры как соглашения сделки и договорные...
24956. Залог как способ обеспечения исполнения обязательств 80 KB
  Основной формой залога являлась фидуция архаичное право продажа закладываемой вещи с правом ее обратного выкупа. Однако этот вид залога являлся чрезвычайно обременительным для должника поскольку кредитор став собственником вещи мог ей распорядиться в результате чего должник лишался возможности выкупа вещи. В связи с этим Уложением Юстиниана такой вид залога был запрещен. Это вызвало к жизни другую форму залога пигнус ручной заклад.
24957. Банковская гарантия, удержание, задаток как способы обеспечения исполнения обязательств 80 KB
  Признаки способов обеспечения исполнения обязательств: o имущественный характер; обеспечивают интерес кредитора и направлены на исполнение обязательства; устанавливаются либо на основании закона либо по соглашению сторон; дополнительный акцессорный характер то есть они обеспечивают исполнение основного обязательства поэтому прекращение или недействительность основного обязательства влечет прекращение или недействительность его обеспечения за исключением банковской гарантии; они применяются вне зависимости от того причинены ли...
24958. Договор купли-продажи недвижимости 55.5 KB
  К отношениям по продаже недвижимого имущества часто применяются особые требования к договорам продажи недвижимости заключаемым на торгах в том числе на публичных правила ФЗ Об исполнительном производстве к ДПН в процессе приватизации нормы законодательства о приватизации; при этом положения ГК регулирующие порядок приобретения и прекращения права собственности применяются если законами о приватизации не предусмотрено иное. Переход права собственности на недвижимость от продавца к покупателю подлежит государственной регистрации...