лабораторная работа №9


МИНОБРНАУКИ РОССИИ
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
«НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ АРХИТЕКТУРНО-СТРОИТЕЛЬНЫЙ УНИВЕРСИТЕТ» (ННГАСУ)

Кафедра информационных систем и технологий
Лабораторная работа №9
по дисциплине «Теория информационных процессов и систем».
Тема:
«Эффективное кодирование на примере кода Хаффмена»
Выполнил студент группы ИС-19: Фомичев А.А.
Проверил: Родькина О.Я.
Нижний Новгород
2013 г.
Цель работы: изучение принципа эффективного кодирования источников дискретных сообщений.
Задание:
Изучить принцип эффективного кодирования источника дискретных сообщений (метод Хаффмена).
Осуществить кодирование каждого сообщения алфавита (см. таблицу 1), используя двоичный код:
равномерный;
код Хаффмена, в соответствии с заданным вариантом.
Таблица 1 Вероятности появления сообщений алфавита
Вариант 4
Знак  
a1 0,28
a2 0,04
a3 0,16
a4 0,02
a5 0,13
a6 0,07
a7 0,30
Определить значения Hmax(x), H(x) и l1.
Рассчитать значения Ксс и Коэ.
2876554889500Метод Хаффмена
Алгоритм кодирования Хаффмена состоит в следующем:
1. Сообщения располагаются в столбец в порядке убывания вероятности их появления.
2. Два самых маловероятных сообщения объединяем в одно сообщение, которое имеет вероятность, равную сумме вероятностей сообщений. Полученные сообщения вновь располагаем в порядке убывания вероятностей.
3. Повторяем шаги 1 и 2 до тех пор, пока не получим единственное сообщение, вероятность которого равна 1.
A p(ai) Шаг 1 Шаг 2 Шаг 3 Шаг 4 2844803035301
001
Шаг 5 Шаг 6
a4 0,30 0,30 0,27 48577598425000,30 3302001162051
001
502920117475000,42 2965451517650
000
478155984240036893564135000,58 1
a7 0,28 0,28 0,28 3098801098551
001
0,28 3187701454150
000
37655585725000,30 0,42 a2 0,16 0,16 471170114935002997201358901
001
0,16 3092451295400
000
36004573025000,26 0,28 a5 0,13 2895601092201
001
0,13 2914651543050
000
353695102235000,13 0,16 a1 3340101346201
001
0,07 48450568580002889251377950
000
35877568580000,07 0,13 a6 3340101530350
000
5092701041390038417586995000,04 0,06 a3 0,02 4. Проводя линии, объединяющие сообщения и образующие последовательные подмножества, получаем дерево, в котором отдельные сообщения являются концевыми узлами. Соответствующие им кодовые комбинации можно определить, приписывая левым ветвям объединения символ “1”, а правым - “0”, обозначаем “1” ветвь идущую от узла в сторону сообщения с большей вероятностью появления, “0” с меньшей вероятностью.
Так как в процессе кодирования сообщениям сопоставляются только концевые узлы, полученный код (код Хаффмена) является префиксным и следовательно всегда однозначно декодируемым.

Кодовое дерево
26396951689101
001

22167851325880а7
00а7
29775153524250
000
38303209804400
000
361886568326000432689012534900019069059804400
000
187769573914000231330513303250011785608108950,30
000,30
29914851651000,42
000,42
20040601974850,58
000,58
33585159251951
001
138176010179051
001
22377403644901
001
1090295739140001874520166370002855595166370003206750685800003180715128651000359537064960500105410013411200018262606927850027038307493000
30283153460750,26
000,26
19659603816350,28
000,28

3837305139700,16
000,16

918845300355а4
00а4
3206750255270002593340240030004156710154940а2
00а2

28365452800351
001
2512060768350,13
000,13
33375603194050
000
3337560539750,13
000,13

2614295334010002306320356235а5
00а5
369379535623500
38303202889250,06
000,06
29502102095500,07
000,07
3732530171450031051501714500345122589598500
3693795508000
000
3337560508001
001

30359351263650041567102825750,02
000,02
33648652679700,04
000,04
2855595118110а1
00а1
403606012636500408114517145000
36937951485901
001
40386001485900
000

4358640220980003467735266065004156710311150а3
00а3

324294512700а6
00а6

Кодирование сообщений
А P(ai) код li (длинна кода)
a1 0,07 0101 4
a2 0,16 00 2
a3 0,02 01000 5
a4 0,30 11 2
a5 0,13 011 3
a6 0,04 01001 5
a7 0,28 10 2
Расчёт значений
Cреднее число двоичных символов l1 на одно сообщение алфавита объемом n, определяется выражением:
l1=i=1npai∙lil1=0,07∙4+0,16∙2+0,02∙5+0,3∙2+0,13∙3+0,04∙5+0,28∙2=2,52Энторопия – мера неопределенности в поведении источника сообщений.
Она равна нулю, если с вероятностью равной единице источником выдается всегда одно и то же сообщение.
HA=-i=1npai∙log2pai= 2,40Энтропия максимальна, если сообщения выдаваемые источником появляются независимо и с одинаковой вероятностью и равна:
HA=log2n =2,81
Kcc - коэффициентом статистического сжатия, который характеризует уменьшение числа двоичных символов на знак при применении методов эффективного кодирования по сравнению с применением равномерного кода;
Kcc = lol1 = 3,282.52 = 1,3015
lo- средняя длина кодовой комбинации при равномерном кодировании
Koэ - коэффициентом относительной эффективности, который показывает степень близости средней длины кодовой комбинации к теоретически возможному пределу H(A)
Koэ = H(A)l1 = 2,402,52 = 0,95

Приложенные файлы

  • docx 10799104
    Размер файла: 146 kB Загрузок: 0

Добавить комментарий