close

Вход

Забыли?

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

?

Pract3

код для вставки
Практическое занятие № 3
Методы эффективного кодирования. Код Хаффмена
Задание на практическое занятие №3
Закодировать (построить таблицу кодовых комбинаций) двоичным
кодом Хаффмена ансамбль {ai} (i=1,2,...,16), если вероятности символов ai
имеют значения в соответствии с таблицей вариантов (табл. 3.1). Построить
кодовое дерево. Найти коэффициент избыточности кода. Сравнить результат
с результатом предыдущей работы.
Табл. 3.1
№ вар.
ai
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
a16
1
pi
0,25
0,125
0,125
0,0625
0,0625
0,0625
0,054688
0,03125
0,03125
0,03125
0,03125
0,03125
0,03125
0,03125
0,023438
0,015625
2
pi
0,25
0,125
0,125
0,0625
0,0625
0,0625
0,0625
0,046875
0,03125
0,03125
0,03125
0,03125
0,03125
0,015625
0,015625
0,015625
3
pi
0,25
0,125
0,125
0,078125
0,0625
0,0625
0,0625
0,046875
0,03125
0,03125
0,03125
0,03125
0,015625
0,015625
0,015625
0,015625
4
pi
0,25
0,125
0,125
0,09375
0,0625
0,0625
0,0625
0,046875
0,046875
0,03125
0,015625
0,015625
0,015625
0,015625
0,015625
0,015625
5
pi
0,125
0,125
0,125
0,21875
0,0625
0,0625
0,0625
0,046875
0,046875
0,03125
0,015625
0,015625
0,015625
0,015625
0,015625
0,015625
№ вар.
ai
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
a16
№ вар.
ai
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
a16
6
pi
0,125
0,125
0,125
0,125
0,125
0,0625
0,0625
0,0625
0,0625
0,03125
0,015625
0,015625
0,015625
0,015625
0,015625
0,015625
11
pi
0,125
0,0625
0,0625
0,0625
0,0625
0,03125
0,125
0,125
0,125
0,125
0,015625
0,015625
0,015625
0,015625
0,015625
0,015625
7
pi
0,25
0,125
0,125
0,09375
0,0625
0,0625
0,0625
0,046875
0,03125
0,03125
0,03125
0,03125
0,015625
0,015625
0,007813
0,007813
12
pi
0,03125
0,03125
0,03125
0,03125
0,015625
0,015625
0,007813
0,007813
0,25
0,125
0,125
0,09375
0,0625
0,0625
0,0625
0,046875
8
pi
0,25
0,125
0,117188
0,09375
0,0625
0,0625
0,0625
0,046875
0,046875
0,03125
0,023438
0,015625
0,015625
0,015625
0,015625
0,015625
Табл. 3.1 (продолжение)
9
10
pi
pi
0,125
0,125
0,125
0,125
0,125
0,125
0,195313 0,109375
0,078125
0,125
0,0625
0,078125
0,0625
0,0625
0,046875
0,0625
0,046875
0,0625
0,03125
0,03125
0,023438 0,015625
0,015625 0,015625
0,015625 0,015625
0,015625 0,015625
0,015625 0,015625
0,015625 0,015625
13
pi
0,0625
0,0625
0,0625
0,046875
0,25
0,125
0,117188
0,09375
0,015625
0,015625
0,015625
0,015625
0,046875
0,03125
0,023438
0,015625
Табл. 3.1 (продолжение)
14
15
pi
pi
0,078125
0,125
0,0625
0,078125
0,0625
0,0625
0,046875
0,0625
0,125
0,125
0,125
0,125
0,125
0,125
0,195313 0,109375
0,015625 0,015625
0,015625 0,015625
0,015625 0,015625
0,015625 0,015625
0,046875
0,0625
0,03125
0,03125
0,023438 0,015625
0,015625 0,015625
№ вар.
ai
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
a16
№ вар.
ai
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
a16
16
pi
0,125
0,125
0,015625
0,015625
0,125
0,0625
0,0625
0,0625
0,015625
0,015625
0,015625
0,015625
0,0625
0,03125
0,125
0,125
21
pi
0,015625
0,015625
0,015625
0,015625
0,0625
0,03125
0,125
0,125
0,125
0,125
0,015625
0,015625
0,125
0,0625
0,0625
0,0625
17
pi
0,25
0,125
0,125
0,09375
0,03125
0,03125
0,03125
0,03125
0,0625
0,0625
0,0625
0,046875
0,015625
0,015625
0,007813
0,007813
22
pi
0,0625
0,0625
0,0625
0,046875
0,015625
0,015625
0,007813
0,007813
0,25
0,125
0,125
0,09375
0,03125
0,03125
0,03125
0,03125
18
pi
0,015625
0,015625
0,015625
0,015625
0,0625
0,0625
0,0625
0,046875
0,046875
0,03125
0,023438
0,015625
0,25
0,125
0,117188
0,09375
Табл. 3.1 (продолжение)
19
20
pi
pi
0,015625 0,015625
0,015625 0,015625
0,015625 0,015625
0,015625 0,015625
0,078125
0,125
0,0625
0,078125
0,0625
0,0625
0,046875
0,0625
0,046875
0,0625
0,03125
0,03125
0,023438 0,015625
0,015625 0,015625
0,125
0,125
0,125
0,125
0,125
0,125
0,195313 0,109375
23
pi
0,046875
0,03125
0,023438
0,015625
0,25
0,125
0,117188
0,09375
0,015625
0,015625
0,015625
0,015625
0,0625
0,0625
0,0625
0,046875
Табл. 3.1 (продолжение)
24
25
pi
pi
0,046875
0,0625
0,03125
0,03125
0,023438 0,015625
0,015625 0,015625
0,125
0,125
0,125
0,125
0,125
0,125
0,195313 0,109375
0,015625 0,015625
0,015625 0,015625
0,015625 0,015625
0,015625 0,015625
0,078125
0,125
0,0625
0,078125
0,0625
0,0625
0,046875
0,0625
№ вар.
ai
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
a16
26
pi
0,0625
0,03125
0,015625
0,015625
0,015625
0,015625
0,015625
0,015625
0,125
0,0625
0,0625
0,0625
0,0625
0,03125
0,125
0,125
27
pi
0,03125
0,03125
0,03125
0,03125
0,015625
0,015625
0,007813
0,007813
0,03125
0,03125
0,03125
0,03125
0,015625
0,015625
0,007813
0,007813
28
pi
0,046875
0,03125
0,023438
0,015625
0,015625
0,015625
0,015625
0,015625
0,0625
0,0625
0,0625
0,046875
0,25
0,125
0,117188
0,09375
Табл. 3.1 (окончание)
29
30
pi
pi
0,046875
0,0625
0,03125
0,03125
0,023438 0,015625
0,015625 0,015625
0,015625 0,015625
0,015625 0,015625
0,015625 0,015625
0,015625 0,015625
0,078125
0,125
0,0625
0,078125
0,0625
0,0625
0,046875
0,0625
0,125
0,125
0,125
0,125
0,125
0,125
0,195313 0,109375
Методические указания к практическому занятию № 3
От неоднозначностей построения эффективного кода, имеющихся у
кода Шеннона-Фано, свободен код Хаффмена. Для двоичного кода методика
Хаффмена
сводится
выписываются
в
к
следующему.
основной
столбец
Символы
таблицы
алфавита
в
порядке
источника
убывания
вероятностей. Далее два последних символа объединяются в один
вспомогательный с вероятностью, равной сумме вероятностей объединяемых
символов. Вероятности символов, не участвовавших в объединении, и
полученная суммарная вероятность снова располагаются в порядке убывания
в дополнительном столбце таблицы, после чего два последних символа вновь
объединяются. Процесс повторяется до тех пор, пока не буде получен
единственный вспомогательный символ с вероятностью, равной 1. Для
составления кодовых комбинаций, соответствующих символам, необходимо
проследить пути переходов по строкам и столбцам таблицы.
Для наглядного представления этого процесса удобнее всего построить
граф, называемый кодовым деревом. Процедура построения кодового дерева
выглядит следующим образом. Из вершины, соответствующей последнему
единственному вспомогательному символу с вероятностью, равной 1,
направляются
две
ветви,
причем
ветви
с
большей
вероятностью
присваивается кодовый символ 1, а с меньшей - 0. Такое последовательное
ветвление из вершин, соответствующих
вспомогательным символам,
продолжается до получения вершин, соответствующих основным исходным
символам.
Пример 3.1. Закодировать двоичным кодом Хаффмена ансамбль,
представленный таблицей:
ai
pi
a1
0,22
a2
0,20
a3
0,16
a4
0,16
a5
0,10
a6
0,10
a7
0,04
a8
0,02
Метод Шеннона-Фано даёт нам два решения:
Решение.1
ai
a1
a2
a3
a4
a5
a6
a7
a8
pi
кодовая комбинация
0,22
11
0,20
101
0,16
100
0,16
01
0,10
001
0,10
0001
0,04
00001
0,02
00000
с коэффициентом избыточности
К  1 
n m in
n СР
1
2 ,75
2 ,84
ni
2
3
3
2
3
4
5
5
pini
0,44
0,6
0,48
0,32
0,30
0,40
0,20
0,10
H(ai)
0,4806
0,4643
0,4230
0,4230
0,3322
0,3322
0,1857
0,1129
ni
2
2
3
3
3
pini
0,44
0,40
0,48
0,48
0,30
H(ai)
0,4806
0,4643
0,4230
0,4230
0,3322
 0 ,032 .
Решение.2
ai
a1
a2
a3
a4
a5
pi
0,22
0,20
0,16
0,16
0,10
кодовая комбинация
11
10
011
010
001
a6
a7
a8
0,10
0001
0,04
00001
0,02
00000
с коэффициентом избыточности
К  1 
n m in
n СР
1
2 ,75
2 ,84
4
5
5
0,40
0,20
0,10
0,3322
0,1857
0,1129
 0 ,018 .
Решение методом Хаффмена представлено на рис. 3.1.
а1
0,22
0,22
0,22
0,26
0,32
0,42
0,58
а2
0,20
0,20
0,20
0,22
0,26
0,32
0,42
а3
0,16
0,16
0,16
0,20
0,22
0,26
а4
0,16
0,16
0,16
0,16
0,20
а5
0,10
0,10
0,16
0,16
а6
0,10
0,10
0,10
а7
0,04
0,06
а8
0,02
Рис. 3.1
Кодовое дерево для этого примера изображено на рис. 3.2.
1,00
1
0 ,58
0 ,42
1
0
0,32
0 ,22
0 ,26
1
0 ,16
a1
0 ,16
1
0
a2
0
0
a3
0 ,20
1
a4
0 ,10
0 ,16
0
1
0 ,06
0,10
1
a5
0
0 ,02
0 ,04
a6
1
0
a7
a8
Рис. 3.2
Составленная в соответствии с кодовым деревом таблица кодовых
комбинаций представлена ниже.
ai
a1
a2
a3
a4
a5
a6
a7
a8
кодовая комбинация
01
00
111
110
100
1011
10101
10100
ni
2
2
3
3
3
4
5
5
Таким образом, получены те же параметры в смысле избыточности, что
и в решении 2 для кода Шеннона – Фано, хотя кодовые комбинации по
составу другие.
Из рассмотрения методов построения эффективных кодов следует, что
эффект уменьшения избыточности достигается за счет различия в числе
разрядов в кодовых комбинациях, т.е. эти эффективные коды являются
неравномерными, а это приводит к дополнительным трудностям при
декодировании. Как вариант, можно для различения кодовых комбинаций
ставить специальный разделительный символ, но при этом снижается
эффект, т.к. средняя длина кодовой комбинации увеличивается на один
разряд.
Более целесообразно обеспечить однозначное декодирование без
введения дополнительных разрядов. Для этого эффективный код необходимо
строить так, чтобы ни одна комбинация кода не совпадала с началом другой
более длинной кодовой комбинации. Коды, удовлетворяющие этому
условию, называются префиксными.
Наличие или отсутствие свойства префиксности отражается и на
кодовом дереве. Если свойство префиксности отсутствует, то некоторые
промежуточные вершины кодового дерева могут соответствовать кодовым
комбинациям.
Префиксные коды иногда называют мгновенно декодируемыми,
поскольку конец кодовой комбинации опознается сразу, как только мы
достигаем конечного символа кодовой комбинации при чтении кодовой
последовательности. В этом состоит преимущество префиксных кодов перед
другими однозначно декодируемыми неравномерными кодами, для которых
конец каждой кодовой комбинации может быть найден лишь после анализа
одной или нескольких последующих комбинаций, а иногда и всей
последовательности.
осуществляется
с
Это
приводит
запаздыванием
к
тому,
по
что
отношению
декодирование
к
приему
иметь
только
последовательности.
Очевидно,
префиксные
префиксными.
что
коды.
практическое
Коды
применение
Шеннона–Фано
и
могут
Хаффмена
являются
Документ
Категория
Без категории
Просмотров
1
Размер файла
66 Кб
Теги
trening2019
1/--страниц
Пожаловаться на содержимое документа