close

Вход

Забыли?

вход по аккаунту

?

лаба 3 кодирование

код для вставкиСкачать
Цель:Изучение методик эффективного кодирования.
Задание
1. Построить код Шеннона-Фано по выбранным вариантам и результаты свести в
таблицы.
2. Построить код Хаффмана по выбранным вариантам и результаты свести в
таблицы. Для каждого построенного кода построить кодовое дерево.
Теоретическая часть
До появления работы Шеннона, кодирование символов алфавита при передаче
сообщения по каналам связи осуществлялось одинаковым количеством бит, получаемым
по формуле Хартли. С появлением этой работы начали появляться способы, кодирующие
символы разным числом бит в зависимости от вероятности появления их в тексте, т.е.
более вероятные символы кодируются короткими кодами, а редко встречающиеся
символы - длинными (длиннее среднего). Наиболее известными методами данного класса
являются способы кодирования Хаффмана и Шеннона-Фано.
Код Хаффмана - статистический способ сжатия, который дает снижение средней
длины кода используемого для представления символов фиксированного алфавита. Код
Хаффмана является примером кода, оптимального в случае, когда все вероятности
появления символов в сообщении - целые отрицательные степени двойки. Код Хаффмана
может быть построен по следующему алгоритму:
1. Выписываем в ряд все символы алфавита в порядке возрастания или убывания
вероятности их появления в тексте;
2. Последовательно объединяем два символа с наименьшими вероятностями
появления в новый составной символ, вероятность появления которого полагается равной
сумме вероятностей составляющих его символов; в конце концов мы построим дерево,
каждый узел которого имеет суммарную вероятность всех узлов, находящихся ниже него;
3. Прослеживаем путь к каждому листу дерева помечая направление к каждому узлу
(например, направо - 1, налево - 0).
Для заданного распределения частот символов может существовать несколько
возможных кодов Хаффмана, - это дает возможность определить каноническое дерево
Хаффмана, соответствующее наиболее компактному представлению исходного текста.
Близким по технике построения к кода Хаффмана являются коды Шеннона-Фано,
предложенные Шенноном и Фано в 1948 - 49 гг. независимо друг от друга. Их построение
может быть осуществлено следующим образом:
1. Выписываем в ряд все символы в порядке возрастания вероятности появления их в
тексте;
2. Последовательно делим множество символов на два подмножества так, чтобы
сумма вероятностей появления символов одного подмножества была примерно равна
сумме вероятностей появления символов другого. Для левого подмножества каждому
символу приписываем "0", для правого - "1". Дальнейшие разбиения повторяются до тех
пор, пока все подмножества не будут состоять из одного элемента.
Алгоритм создания кода Хаффмана называется снизу-вверх, а Шеннона-Фано сверху-вниз. Преимуществами данных методов являются их очевидная простота
реализации и, как следствие этого, высокая скорость кодирования/раскодирования.
Основным недостатком является их неоптимальность в общем случае.
Практическая часть
Вариант 25
0,062
0,080
0,068
0,092
0,092
0,052
0,097
0,105
0,061
0,120
0,057
0,088
0,051
0,110
0,116
0,105
0,076
0,085
0,101
0,050
0,113
0,075
0,092
0,063
0,084
0,053
0,057
0,054
0,074
0,110
Знаки
Z1
Вероятность
0,12
Код Шеннона-Фано
111
Код Хаффмана
100
Z2
0,105
110
011
Z3
0,101
101
001
Z4
0,097
1001
000
Z5
0,092
1000
1111
Z6
0,085
011
1110
Z7
0,084
0101
1101
Z8
0,075
0100
1100
Z9
0,074
0011
1011
Z10
0,062
0010
1010
Z11
0,054
0001
0101
Z12
0,051
0000
0100
0,074
0,113
0,080
0,085
0,098
0,107
Энтропия
Среднее число символов на знак
(по коду Шеннона-Фано)
Среднее число символов на знак
(по коду Хаффмана)
0,592
0,
21
01
05
0,1
0,0
54
6
0,13
4
0,07
84
0,0
92
0,0
0,1
Z12
97
Кодовое дерево для первого ряда
Z11
0
1
Z10
1
Z3
1
0,0
Z2
0,05
0
0
05
Z9
0,
19
0 8
0,1
Z8
Z1
1
62
1
0
0,0
75
Z7
0,0
Z6
0
20
9
1
1
0,408
1
0,1
15
0,
85
Z5
0
0,0
1
0
0
0 0,256
36
0,3 1
77
0,1 1
1
0
Z4
Знаки
Z1
Вероятность
0,113
Код Шеннона-Фано
111
Код Хаффмана
100
Z2
0,110
110
011
Z3
0,105
101
010
Z4
0,098
1001
000
Z5
0,092
1000
1111
Z6
0,092
011
1110
Z7
0,080
0101
1101
Z8
0,076
0100
1100
Z9
0,074
0011
1011
Z10
0,057
0010
1010
Z11
0,053
0001
0101
Z12
0,050
0000
0010
Энтропия
Среднее число символов на знак
(по коду Шеннона-Фано)
Среднее число символов на знак
(по коду Хаффмана)
0.584
5
03
0.
21
0.1
0.05
3
10
1
0.13
4
0,07
80
0.0
92
0.1
Z10
Кодовое дерево для второго ряда
Z11
98
1
0.0
Z3
1
0
Z4
0
50
0
Z2
0
0.0
Z9
Z1
1
05
Z8
0.
20
0 1
1
0.1
0.0
0.416
57
1
0
0.0
0
76
Z7
0.0
Z6
1
13
6
1
0.1
15
0.
92
Z5
0
0.0
1
0
0
0 0.244
4
0.3 1
84
0.1 1
1
Z12
Знаки
Z1
Вероятность
0,116
Код Шеннона-Фано
111
Код Хаффмана
100
Z2
0,113
110
011
Z3
0,110
101
010
Z4
0,107
1001
000
Z5
0,088
1000
1111
Z6
0,085
0111
1110
Z7
0,080
0110
1101
Z8
0,068
0101
1100
Z9
0,063
0100
1011
Z10
0,061
001
1010
Z11
0,057
0001
0011
Z12
0,052
0000
0010
Энтропия
Среднее число символов на знак
(по коду Шеннона-Фано)
Среднее число символов на знак
(по коду Хаффмана)
0.561
3
09
0.
23
0.1
0.05
7
13
4
0.12
3
0.06
80
0.0
88
0.1
Z10
Кодовое дерево для третьего ряда
Z11
07
1
0.1
Z3
1
0
Z4
0
52
0
Z2
0
0.0
Z9
Z1
1
10
Z8
0.
21
0 6
1
0.1
0.0
0.439
61
1
0
0.0
0
68
Z7
0.0
Z6
1
16
8
1
0.1
14
0.
85
Z5
0
0.0
1
0
0
0 0.24
21
0.3 1
73
0.1 1
1
Z12
ГОУ ВПО
ДВГУПС
Кафедра: «ОСС»
ЛАБОРАТОРНАЯ РАБОТА
«Эффективное кодирование»
21040165
03
941
Выполнил: Д.С, Черных
Проверил: И.А. Кривошеев
Хабаровск, 2009г.
Документ
Категория
Математика
Просмотров
26
Размер файла
740 Кб
Теги
кодирование, лаба
1/--страниц
Пожаловаться на содержимое документа