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.


 

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

24535. Физические организации файловой системы FAT 68.16 KB
  Физические организации файловой системы FAT.6 Физическая организация файловой системы FAT. Как уже отмечалось аббревиатура FAT file allocation table расшифровывается как таблица размещения файлов. Файловая система FAT поддерживает всего два типа файлов: обычный файл и каталог.
24536. Физические организации файловой системы NTFS 42.33 KB
  Физические организации файловой системы NTFS. Физические организации файловой системы NTFS. Аббревиатура NTFS означает New Technology File System новая технология файловой системы. NTFS содержит ряд значительных усовершенствований существенно отличающих ее от других файловых систем.
24537. Системы программирования: состав систем программирования. Этапы разработки ПО 124.23 KB
  Современные системы программирования как правило представляют собой интегрированную среду разработки integrated development environment IDE к компонентам которой относятся следующие программные средства: текстовый редактор editor предназначенный для создания текстов исходной программы на языке высокого уровня ЯВУ или ассемблере макроассемблере; компилятор compiler составитель предназначенный для трансляции перевода исходного текста входной программы в эквивалентную ей выходную программу объектный код на языке нижнего...
24538. Виды ресурсов вычислительной системы 14.16 KB
  Ресурсы запрашиваются используются и освобождаются процессами. По форме реализации различают: аппаратные ресурсы Hard; программные ресурсы Soft; информационные ресурсы. По способу выделения ресурса различают: неделимые ресурсы предоставляются процессу в полное распоряжение; делимые ресурсы предоставляются процессу в соответствии с запросом на требуемое количество ресурса. Делимые ресурсы в свою очередь можно разделить на те которые могут использоваться процессами одновременно или попеременно.
24539. Структура и виды программного обеспечения (ПО). Характеристика системного ПО 15.33 KB
  ПО Прикладное Операционные системы Система управления файлами Операционные оболочки Утилиты Системы программирования Базы данных САПР Электронные таблицы Издательские системы ПО для математических расчетов Системное Рис. Cистемное ПО можно разделить на следующие группы: операционные системы ОС; системы управления файлами; операционные оболочки; утилиты; системы программирования. Современные системы программирования представляют собой интегрированную среду разработки IDE объединяющую редактор текста компилятор языка...
24540. Классификация ОС 13.63 KB
  Примером таких ОС является семейство Windows и Linux. Среди ОС специального назначения можно выделить следующие разновидности: ОС для карманных компьютеров сотовых телефонов и другой бытовой техники например PalmOS и Windows CE Consumer Electronics бытовая электроника; ОС для встроенных систем телевизоров СВЧ печей стиральных машин и т. По режиму обработки задач различают однозадачные например MSDOS MSX и многозадачные ОС OC EC OS 2 UNIX Windows. По способу взаимодействия пользователя с системой различают...
24541. Назначение и основные функции операционной системы (ОС) для автономного компьютера 13.74 KB
  Назначение и основные функции операционной системы ОС для автономного компьютера.2 Операционные системы для автономного компьютера Операционная система компьютера представляет собой комплекс взаимосвязанных программ который действует как интерфейс между приложениями и пользователями с одной стороны и аппаратурой компьютера с другой стороны. В соответствии с этим определением ОС выполняет две группы функций: предоставление пользователям и программистам вместо реальной аппаратуры компьютера расширенной виртуальной машины с которой удобней...
24542. Сетевые операционные системы: функциональные компоненты и варианты построения 46.02 KB
  Сетевые операционные системы: функциональные компоненты и варианты построения.3 Сетевые операционные системы. Различают сетевые и распределенные ОС. Распределенная ОС предоставляет пользователю сетевые ресурсы в виде ресурсов единой централизованной виртуальной машины.
24543. Одноранговые и серверные операционные системы 79.16 KB
  В зависимости от того как распределены функции между компьютерами сети они могут выступать в трех разных ролях: выделенный сервер сети компьютер обслуживающий запросы других компьютеров т. В одноранговых сетях рабочих группах на все компьютеры устанавливается такая ОС которая предоставляет всем компьютерам в сети потенциально равные возможности. Схема одноранговой сети При потенциальном равноправии всех компьютеров в одноранговой сети часто возникникает функциональная несимметричность которая обусловлена тем что одни компьютеры...