close

Вход

Забыли?

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

?

IT labs part1 twoside

код для вставкиСкачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное бюджетное образовательное
учреждение высшего профессионального образования
Санкт-Петербургский государственный университет аэрокосмического
приборостроения
ТЕОРИЯ ИНФОРМАЦИИ
КОДИРОВАНИЕ ДИСКРЕТНЫХ
ИСТОЧНИКОВ
Методические указания
к выполнению лабораторной работы
Санкт-Петербург
2011
Составители: Е. А. Беляев, С. С. Осипов , А. М. Тюрликов
Рецензент кандидат технических наук Г. С. Евсеев
Методические указания предназначены для выполнения лабораторных работ по курсу ѕТеория информацииї студентами направления ѕИнформационные системыї. Включают исследование классических алгоритмов кодирования дискретных источников информации на
примере кодов Хаффмана.
Подготовлены кафедрой информационно-сетевых технологий и рекомендованы к изданию редакционно-издательским советом СанктПетербургского государственного университета аэрокосмического приборостроения.
©
ГОУ ВПО Санкт-Петербургский государственный универси-
тет аэрокосмического приборостроения, 2011
Редактор
А.В. Подчепаева
Подписано к печати 19.04.11. Формат 60Ч84 1/16.
Бумага офсетная. Печать офсетная.
Усл. печ. л. 1,2. Тираж 100 экз. Заказ ќ442.
Редакционно-издательский центр ГУАП
190000, Санкт-Петербург, Б.Морская ул., 67
Лабораторная работа
КОДЫ ХАФФМАНА
Целью работы является приобретение практических навыков построения кода Хаффмана, а также программная реализация алгоритмов кодирования и декодирования.
1.
Предварительные сведения
В лабораторной работе рассматриваются дискретные стационарные
источники без памяти. Более сложные модели источников информации
рассмотрены в литературе [1, 2].
Пусть X = {x0 , x1 , ..., xM ?1 } дискретное множество, состоящее
из M элементов. В каждый момент времени источник выбирает одно из сообщений множества X . Такой источник называется дискретным. Источник задан, если для любых n ? {1, 2, ..., } и i ? {0, 1, ..., } и
любой последовательности сообщений xi+1 , ..., xi+n определена вероятность p(xi+1 , ..., xi+n ) появления этой последовательности. Здесь xi+j ,
j ? {1, 2, .., n} элемент множества X , появившийся в момент i + j .
Источник является стационарным, если для любых xi+1 , ..., xi+n вероятность p(xi+1 , ..., xi+n ) не зависит от i.
Источник называется источником без памяти, если для любых n и
i и для любых xi+1 , ..., xi+n выполняется равенство
p(x0 , x1 ..., xn ) = p(x0 )p(x1 )...p(xn ).
(1)
Количеством информации в сообщении xi ? X называется число
I(xi ), определяемое соотношением
I(xi ) , ? log p(xi ), i = 0, 1, ..., M ? 1.
(2)
Если основание логарифма равно 2, то информация измеряется в битах.
Для дискретного стационарного источника без памяти математическое ожидание количества информации, приходящейся на одно сообщение, называется энтропией :
H(X) = M [I(xi )] = ?
M
?1
X
i=0
3
p(xi ) log p(xi ).
(3)
Пусть дискретный стационарный источник без памяти порождает
сообщения из алфавита X = {x0 , x1 , ..., xM ?1 }. Побуквенным кодированием называется сопоставление каждому сообщению xi ? X двоичной
последовательности ci из множества кодовых слов C = {c0 , c1 , ..., cM ?1 }.
Побуквенное кодирование называется равномерным, если каждому сообщению сопоставляются кодовые слова одинаковой длины равной
dlog2 M e. В противном случае кодирование является неравномерным.
Код является однозначно декодируемым, если любая последовательность двоичных символов, порожденных кодером, единственным способом разбивается на отдельные кодовые слова. Если ни одно кодовое
слово не является началом другого, код называется префиксным. Префиксные коды являются однозначно декодируемыми.
Средней длиной кодового слова называется величина
l = M [li ] =
M
?1
X
p(xi )li ,
(4)
i=0
где li длина слова ci .
Разность r = l ? H(X) называется избыточностью кода. Избыточность характеризует эффективность кода: чем меньше избыточность,
тем код эффективнее. Коды с нулевой избыточностью называются оптимальными.
Если вероятности p(x0 ), p(x1 ), ..., p(xM ?1 ) можно представить как
степень двойки, т.е. p(xi ) = 2?k , где k положительное целое число, то
оптимальными являются коды Хаффмана. В противном случае избыточность кода Хаффмана удовлетворяет неравенствам [2, 3]:
r?
pmax + 0.087, при pmax < 1/2,
2 ? h(pmax ) ? pmax , при pmax ? 1/2,
(5)
где pmax наибольшая из вероятностей появления символа на выходе
источника, h(x) = ?x log x ? (1 ? x) log(1 ? x).
4
2.
2.1.
Код Хаффмана и его построение
Построение кода Хаффмана с обходом дерева
Результатом построения кода Хаффмана является список кодовых
слов и список длин кодовых слов, которые необходимы для кодирования
и декодирования. В лабораторной работе рассматриваются два способа
построения кода Хаффмана: с обходом и без обхода кодового дерева.
Построение кода Хаффмана с обходом дерева можно проиллюстрировать на следующем простом примере.
Пример 1. Пусть дискретный источник порождает сообщения из множества
X = {x0 , x1 , x2 , x3 } с вероятностями p(x0 ) = 0.5, p(x1 ) = 0.25, p(x2 ) = 0.125 и
p(x3 ) = 0.125. Процедура построения кода осуществляется за три шага:
1. На первом шаге (см. рис. 1) из множества сообщений X выбираются два
сообщения с наименьшими вероятностями: x2 и x3 . Эти сообщения объединяются в одно новое сообщение x23 , которому приписывается вероятность
p23 = p2 +p3 = 0.25. Затем новое сообщение x23 соединяется ребрами с исходными сообщениями x2 и x3 . Одному ребру приписывается значение 0, дру-
гому значение 1. В результате получается источник с тремя сообщениями
X = {x0 , x1 , x23 } и вероятностями p(x0 ) = 0.5, p(x1 ) = 0.25 и p(x23 ) = 0.25.
x0 0.5
x1 0.25
x2 0.125
x3 0.125
0
1
x23
0.25
Рис. 1. Первый шаг построения кода Хаффмана
2. На втором шаге (см. рис. 2) сообщения x1 и x23 имеют наименьшие вероятности. Поэтому они объединяются в одно сообщение x123 , которому приписывается вероятность p(x123 ) = p1 + p23 = 0.5. Затем сообщение x123 соединяется
ребрами с сообщениями x1 и x23 . Одному ребру приписывается значение 0,
другому значение 1. В результате получается источник с двумя сообщениями X = {x0 , x123 } и вероятностями p(x0 ) = 0.5, p(x123 ) = 0.5.
x0 0.5
x1 0.25
x2 0.125
x3 0.125
x123
0
x23 1
0
1 0.25
0.5
Рис. 2. Второй шаг построения кода Хаффмана
5
3. На третьем шаге (см. рис. 3), оставшиеся два сообщения объединяются в
сообщение x0123 , которое соединяется ребрами с сообщениями x0 и x123 . Одному ребру приписывается значение 0, другому значение 1.
x0 0.5
x1 0.25
x2 0.125
x3 0.125
x0123
0
x123
0
0 x23 1
1 0.25
1
1.00
0.5
Рис. 3. Третий шаг построения кода Хаффмана
В результате этих шагов было построено кодовое дерево Хаффмана. Кодовое
слово для каждого сообщения определяется значениями ребер в дереве на пути от
узла x0123 до этого сообщения. Например, для сообщения x2 необходимо пройти
1
1
0
путь x0123 ? x123 ? x23 ? x2 , которому соответствует кодовое слово 110 длины 3.
Аналогично, сообщению x3 соответствует кодовое слово 111 длины 3, сообщению x1
соответствует кодовое слово 10 длины 2, сообщению x0 соответствует кодовое слово
0 длины 1.
Таблица 1.
Сообщение
Кодовые слова для примера 1
Вероятность
p(xi )
Равномерный
код
Кодовое слово Хаффмана ci
Длина кодового
слова
Хаффмана li
x0
0.5
00
0
1
x1
0.25
01
10
2
x2
0.125
10
110
3
x3
0.125
11
111
3
Таким образом, код Хаффмана можно представлять в виде кодового
дерева, узлы которого размещаются на ярусах. На начальном (нулевом)
ярусе расположен один узел, называемый корнем дерева (в примере 1
это узел x0123 ). Узлы следующих ярусов связаны с узлами предыдущих
ярусов ребрами. Из каждого промежуточного узла (в примере 1 это узлы x23 и x123 ) исходит два ребра, которым приписаны кодовые символы
(0 или 1). Узел называется концевым, если из него не исходит ни одного
ребра (в примере 1 это узлы x0 , x1 , x2 и x3 ).
6
В построенном коде наиболее вероятные сообщения имеют короткие слова, а менее вероятные длинные слова (см. табл. 1). При передаче информации короткие слова будут встречаться чаще длинных,
что и позволяет получить средний выигрыш в длине битового потока
по сравнению с равномерным кодированием сообщений.
В общем случае алгоритм построения кода Хаффмана с обходом
дерева описывается следующим образом.
Алгоритм 1. Построение кодового дерева Хаффмана
Входные данные.
Алфавит X = {x0 , x1 , ..., xM ?1 }.
Вероятности появления символов p0 , p1 , ..., pM ?1 .
Шаг 1.
Сформировать M концевых узлов с номерами 0, 1, ..., M ? 1.
Каждому узлу i приписать сообщение xi и вероятность pi .
k := (M ? 1).
Шаг 2.
Найти два узла i и j с наименьшими вероятностями.
k := (k + 1).
Сформировать промежуточный узел с номером k .
Приписать узлу k вероятность pk = pi + pj .
Cвязать узел k с узлами i и j .
Приписать ребру (i, k) значение 0.
Приписать ребру (j, k) значение 1.
Удалить узлы i и j из дальнейшего рассмотрения.
Шаг 3.
Если k > 1, то перейти к шагу 2,
иначе построение кодового дерева окончено.
Здесь и далее символ ѕ:=ї обозначает операцию присваивания.
После построения дерева, кодовое слово для сообщения xi определяется обходом дерева от концевого узла, соответствующего xi , до корневого узла.
7
x0 0.4
0
x1 0.25
x2 0.08
x3 0.07
x4 0.09
x5 0.06
x6 0.05
0
0
1 0.15
0
1
1
0
0
1
1
1
0.6
0.35
0.2
0.11
Рис. 4. Пример построения кодового дерева Хаффмана
Пример 2. На рис. 4 показан пример построения кодового дерева для источника
с семью сообщениями. В табл. 2 показаны вероятности появления символов, равномерный код для каждого символа, а также множество кодовых слов C и множество
длин кодовых слов L кода Хаффмана. Энтропия на сообщение в приведенном примере H(X) ? 2.36, средняя длина кодового слова Хаффмана составляет l = 2.41.
Избыточность построенного кода r = H(X) ? l ? 0.05 бит на символ. Выигрыш по
отношению к равномерному кодированию в среднем составляет 0.59 бит на символ.
Таблица 2.
Сообщение
Пример построения кода Хаффмана
Вероятность
p(xi )
Равномерный
код
Кодовое слово Хаффмана ci
Длина кодового
слова
Хаффмана li
x0
0.4
000
0
1
x1
0.25
001
10
2
x2
0.08
010
1100
4
x3
0.07
011
1101
4
x4
0.09
100
1110
4
x5
0.06
101
11110
5
x6
0.05
110
11111
5
8
2.2.
Построение кода Хаффмана без обхода дерева
Множество кодовых слов Хаффмана может быть получено и без
построения кодового дерева. Пусть P матрица, в которой хранятся
вероятности появления сообщений, L матрица длин кодовых слов и C
матрица кодовых слов размером M Ч M . Дополнительно введем матрицу T размером M Ч M , в которой будут храниться потомки узлов.
Строка i матрицы T содержит номера концевых узлов дерева Хаффмана, которые являются потомками для промежуточного узла с номером i.
Рассмотрим пример построения кода Хаффмана без обхода кодового дерева для источника сообщений из примера 1.
Пример 3. Матрицы P , C , T и L инициализируются следующим образом. В
матрицу P заносятся вероятности появления символов:
?
?
0.5
? 0.25 ?
?
P =?
? 0.125 ? .
0.125
В каждый элемент нулевого1 столбца матрицы T заносится номер соответствующей строки. В остальные элементы матрицы заносится символ (для удобства будем
использовать символ ѕї), означающий, что элемент матрицы не определен:
?
?
?
?
?
0
? 1
T =?
? 2
3
?
?
?
?
?
?
? ?
?.
? ?
?
Аналогично, в каждый элемент матрицы C заносится символ, означающий, что
элемент матрицы не определен, а в каждый элемент матрицы L заносится ноль:
?
? ?
C=?
? ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
? ?
,L = ?
?
?
?
?
?
0
0 ?
?.
0 ?
0
1 Здесь и далее нумерация строк и столбцов матриц начинается с нуля.
9
Алгоритм выполняется за три шага.
1. На первом шаге два сообщения x2 и x3 с минимальными вероятностями появления объединяются в одно сообщение x23 с вероятностью появления p2 + p3 .
Вероятность нового сообщения записывается во вторую строку матрицы P .
В третью строку матрицы P заносится любой символ, означающий, что элемент матрицы не определен:
?
?
0.5
? 0.25 ?
?
P =?
? 0.25 ? .
?
В матрице C по адресу [2, L[2]] записывается2 значение 0, а по адресу [3, L[3]]
записывается значение 1:
?
? ?
C=?
? 0
1
?
?
?
?
?
?
?
?
?
?
?
? ?
?.
? ?
?
Формирование объединенного сообщения x23 соответствует тому, что во вторую строку матрицы T записываются номера потомков объединенного узла,
то есть все номера узлов, которые находились в строках 2 и 3. В третью
строку матрицы T заносятся символы, означающие, что элементы матрицы
не определены:
?
0
? 1
T =?
? 2
?
?
?
3
?
?
?
?
?
?
?
? ?
?.
? ?
?
В матрице L значения, соответствующие сообщениям 2 и 3, увеличиваются
на единицу:
?
?
0
? 0 ?
?
L=?
? 1 ?.
1
2 В примере 1 эти действия соответствует тому, что на шаге 1 новое сообщение
x23 соединяется ребрами с исходными сообщениями x2 и x3 . Одному ребру припи-
сывается значение 0, другому ребру приписывается значение 1.
10
2. На втором шаге два сообщения x1 и x23 с минимальными вероятностями
появления объединяются в одно сообщение x123 с вероятностью появления
p1 + p23 . Вероятность нового сообщения записывается в первую строку матрицы P . Во вторую строку матрицы P заносится символ, означающий, что
элемент матрицы не определен:
?
?
0.5
? 0.5 ?
?
P =?
? ? ?.
?
В матрицу кодовых слов C для всех сообщений, номера которых находятся
в первой строке матрицы T , добавляется ноль, а для всех сообщений, номера которых находятся во второй строке матрицы T , добавляется единица3 .
Таким образом, в матрице C по адресу [1, L[1]] записывается значение 0, а
по адресам [2, L[2]] и [3, L[3]] записывается значение 1:
?
? 0
C=?
? 0
1
?
?
?
1
1
?
?
?
?
?
?
? ?
?.
? ?
?
Формирование объединенного сообщения x123 соответствует тому, что в
первую строку матрицы T записываются номера потомков объединенного узла, то есть все номера узлов, которые находились в первой и второй строках.
Во вторую строку матрицы T заносятся символы, означающие, что элементы
матрицы не определены:
?
0
? 1
T =?
? ?
?
?
2
?
?
?
3
?
?
?
?
? ?
?.
? ?
?
В матрице L значения, соответствующие сообщениям, номера которых находятся в первой строке матрицы T , увеличиваются на единицу:
?
0
? 1 ?
?
L=?
? 2 ?.
2
?
3. На третьем шаге сообщения x0 и x123 объединяются в одно сообщение x0123
с вероятностью появления 1. Вероятность нового сообщения записывается в
нулевую строку матрицы P . В первую строку матрицы P заносится символ,
означающий, что элемент матрицы не определен:
3 В примере 1 эти действия соответствуют тому, что на шаге 2 новое сообщение x123 соединяется ребрами с исходными сообщениями x1 и x23 . Одному ребру
приписывается значение 0, другому ребру приписывается значение 1.
11
?
?
1.0
? ? ?
?
P =?
? ? ?.
?
В матрицу кодовых слов C для всех сообщений, номера которых находятся
в нулевой строке матрицы T , добавляется ноль, а для всех сообщений, номера которых находятся в первой строке матрицы T , добавляется единица4 .
Таким образом, в матрице C по адресу [0, L[0]] записывается значение 0, а
по адресам [1, L[1]], [2, L[2]] и [3, L[3]] записывается значение 1:
?
0
? 0
?
C=?
0
1
?
1
1
1
?
?
1
1
?
?
? ?
?.
? ?
?
Формирование объединенного сообщения x0123 соответствует тому, что в нулевую строку матрицы T записываются номера потомков объединенного узла, то есть все номера узлов, которые находились в строках 0 и 1. В первую
строку матрицы T заносятся символы, означающие, что элементы матрицы
не определены:
?
0
? ?
T =?
? ?
?
1
?
?
?
2
?
?
?
?
3
? ?
?.
? ?
?
В матрице L значения соответствующие сообщениям, номера которых находятся в нулевой строке матрицы T , увеличиваются на единицу:
?
?
1
? 2 ?
?
L=?
? 3 ?.
3
4 В примере 1 эти действия соответствуют тому, что на шаге 3 новое сообщение x0123 соединяется ребрами с исходными сообщениями x0 и x123 . Одному ребру
приписывается значение 0, другому ребру приписывается значение 1.
12
В общем случае алгоритм построения кода Хаффмана без обхода
кодового дерева можно описать следующим образом.
Алгоритм 2. Построение кода Хаффмана без обхода дерева
Входные данные.
Алфавит X = {x0 , x1 , ..., xM ?1 }.
Вероятности появления символов P = {p0 , p1 , ..., pM ?1 }.
Шаг 1.
Для i = 0, ..., M ? 1
l[i] := 0.
Для j = 0, ..., M ? 1
c[i, j] := ѕї.
t[i, j] := ѕї.
Для i = 0, ..., M ? 1
t[i, 0] := i.
Шаг 2.
Найти в P две наименьшие вероятности pi и pj .
pi := pi + pj .
Исключить pj из множества P .
Для k = 0, ..., M ? 1
Если t[i, k] 6= ѕї, то
приписать 0 к кодовому слову с номером t[i, k].
Если t[j, k] 6= ѕї, то
приписать 1 к кодовому слову с номером t[j, k].
В строку i матрицы T добавить все дочерние узлы из строки j .
Увеличить на единицу длины кодовых слов,
относящихся к строке i.
Шаг 3.
Если P содержит более одного элемента, то перейти к шагу 2,
иначе построение списка кодовых слов окончено.
В результате выполнения алгоритма в матрице L будут находиться длины кодовых слов, а в матрице C будут находится кодовые слова.
Причем нулевой столбец матрицы C содержит последние символы каждого кодового слова.
13
Пример 4. В табл. 3 показан процесс построения кода Хаффмана без обхода
кодового дерева для источника сообщений из примера 2.
Таблица 3.
P
Построение кода Хаффмана без обхода кодового дерева
T
0
1
2
3
4
5
6
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0
1
2
3
4
5
?
?
?
?
?
?
6
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
? ?
0
1
2
?
4
5
?
?
?
3
?
?
6
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
? ?
? ?
0.4
0
? 0.25 ? ? 1
?
? ?
? 0.15 ? ? 2
?
? ?
?
? ?
? ? ? ? ?
?
? ?
? 0.2 ? ? 4
?
? ?
? ? ? ? ?
?
?
?
?
3
?
5
?
?
?
?
?
?
6
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
? ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0.4
0.25
0.08
0.07
0.09
0.06
0.05
? ?
0.4
0.25
0.08
0.07
0.09
0.11
?
? ?
0.4
0.25
0.15
?
0.09
0.11
?
? ?
C
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
14
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
L
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
? ?
?
?
?
?
?
0
1
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
? ?
?
?
0
1
?
0
1
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
? ?
?
?
0
1
0
0
1
?
?
?
?
?
1
1
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
? ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0
0
0
0
0
0
0
?
0
0
0
0
0
1
1
?
0
0
1
1
0
1
1
?
0
0
1
1
1
2
2
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
Окончание табл. 3
P
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
T
0.4
0.25
0.35
?
?
?
?
? ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0.4
0.6
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
1.0
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
L
C
0
1
2
?
?
?
?
?
?
3
?
?
?
?
?
?
4
?
?
?
?
?
?
5
?
?
?
?
?
?
6
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
? ?
0
1
?
?
?
?
?
?
2
?
?
?
?
?
?
3
?
?
?
?
?
?
4
?
?
?
?
?
?
5
?
?
?
?
?
?
6
?
?
?
?
?
?
?
?
?
?
?
?
? ?
0
?
?
?
?
?
?
1
?
?
?
?
?
?
2
?
?
?
?
?
?
3
?
?
?
?
?
?
4
?
?
?
?
?
?
5
?
?
?
?
?
?
6
?
?
?
?
?
?
? ?
15
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0
1
0
0
1
?
?
0
0
1
1
1
?
?
?
?
?
1
1
?
?
?
?
?
?
?
?
?
?
?
?
?
?
? ?
?
0
0
1
0
0
1
?
?
0
0
1
1
1
?
?
1
1
1
1
1
?
?
?
?
?
1
1
?
?
?
?
?
?
?
? ?
0
0
0
1
0
0
1
?
1
0
0
1
1
1
?
?
1
1
1
1
1
?
?
1
1
1
1
1
?
?
?
?
?
1
1
? ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0
0
2
2
2
3
3
?
0
1
3
3
3
4
4
?
1
2
4
4
4
5
5
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
3.
Кодирование и декодирование кода Хаффмана
3.1.
Программная реализация кодера
Кодер Хаффмана сопоставляет каждому сообщению xi ? X
двоичную последовательность ci из множества кодовых слов C =
{c0 , c1 , ..., cM ?1 } и помещает еј в выходной битовый поток, который передается по каналу связи.
Пример 5. Пусть для источника с сообщениями X = {x0 , x1 , x2 , x3 } и кодовыми
словами C = {0, 10, 110, 111} необходимо осуществить кодирование последовательности сообщений x0 , x2 , x1 . Сообщению x0 кодер сопоставляет слово 0, cообщению x2
слово 110, cообщению x1 слово 10. Таким образом, формируется битовый поток
011010.
При практической реализации кодера Хаффмана следует учитывать, что подавляющее число современных вычислительных систем используют байт (8 бит) как минимальную единицу информации при хранении и обработке. Так как длины кодовых слов кода Хаффмана, как
правило, не делятся нацело на 8, при реализации кодера необходимо
использовать промежуточный буфер. В простейшем случае в качестве
промежуточного буфера используется дополнительная переменная размером в один байт. При помощи арифметических операций эта переменная поразрядно заполняется очередным двоичным символом кодового
слова. После заполнения восьми разрядов значение переменной помещается в выходной битовый поток.
Следует обратить внимание, что после кодирования последнего символа источника информации в промежуточном буфере часть разрядов
могут быть ѕлишнимиї. Это объясняется тем, что длина битового потока, как правило, не делится нацело на 8. В случае, если эти ѕлишниеї разряды совпадают с одним или более кодовыми словами, декодер
неверно декодирует последние сообщения источника. Для устранения
данного эффекта в начале битового потока можно записать количество
сообщений источника. Однако такой подход приводит к увеличению
суммарной длины битового потока. Альтернативный подход заключается в том, что вместо ѕлишнихї бит записывается часть любого кодового
слова, длина которого превышает количество ѕлишнихї бит в промежуточном буфере. При таком подходе не увеличивается длина битового
потока и декодер корректно обрабатывает конец битового потока.
16
3.2.
Программная реализация декодера
Как и кодер, декодер извлекает значения двоичных символов кодовых слов при помощи промежуточного буфера. Затем каждому кодовому слову сопоставляется сообщение из исходного алфавита.
Пример 6. Для источника с сообщениями X = {x0 , x1 , x2 , x3 } и кодовыми словами C = {0, 10, 110, 111} битовый поток |{z}
0 110 10 декодируется как последова|{z} |{z}
тельность сообщений x0 , x2 , x1 .
При практической реализации декодера Хаффмана используется
заранее подготовленная таблица декодирования. Каждой строке таблицы сопоставляется адрес a, номер i декодированного символа x[a], адреса переходов A[a, bj ], которые зависят от значения очередного двоичного
символа bj ? {0, 1} на позиции j в битовом потоке, флаг f [a] ? {0, 1},
который принимает значение 0, если текущий узел дерева Хаффмана
является концевым и значение 1 в противном случае, а также величина
смещения в битовом потоке l[a] после обработки текущей строки.
Алгоритм декодирования кода Хаффмана на основе таблицы декодирования может быть описан следующим образом.
Алгоритм 3. Декодирование кода Хаффмана
Входные данные.
Таблица декодирования.
Шаг 1.
a := 0, j := 0.
Шаг 2.
a := a + bj .
Если f [a] = 1, то
a := A[a].
Иначе
выдать декодированный символ x[a],
a := 0.
j := j + 1.
Шаг 3.
Если битовый поток закончен, то остановить декодирование,
иначе перейти к шагу 2.
17
Алгоритм построения таблицы декодирования может быть описан
следующим образом.
Алгоритм 4. Построение таблицы декодирования кода Хаффмана
Входные данные.
Множества кодовых слов C и длин кодовых слов L.
Шаг 1.
s := 0.
Для i = 0, ..., 2M ? 2
x[i] := ѕї, A[i] := ѕї.
Шаг 2.
Для i = 0, ..., M ? 1
k := 0.
Для j = 1, ..., li
k := k + cij .
Если j = li , то
f [k] := 0, X[k] := xi .
Иначе
f [k] := 1.
Если A[k] =ѕї, то
s := s + 2, A[k] := s.
k := A[k].
18
Пример 7. Табл. 4 показана в качестве примера побитного декодирования кода
Хаффмана, для источника сообщений из примера 2.
Таблица 4.
Побитное декодирование кода Хаффмана
Адрес, a
bj
f [a]
Aдрес перехода, A[a]
Сообщение, x[a]
0
0
0
x0
1
1
1
2
2
0
0
x1
3
1
1
4
4
0
1
6
5
1
1
8
6
0
0
x2
7
1
0
x3
8
0
0
x4
9
1
1
10
10
0
0
x5
11
1
0
x6
3.3.
Способ уменьшения времени декодирования
Для уменьшения времени декодирования таблица может быть модифицирована таким образом, чтобы за один раз осуществлялся анализ более одного разряда двоичного потока. Это позволит выполнять
меньшее количество переходов в таблице при декодировании очередного символа, а значит уменьшить время декодирования в целом.
Пример 8. Для кода Хаффмана, построенного в примере 2, рассмотрим модификацию, при которой анализируются сразу два двоичных разряда битового потока.
Этот случай соответствует ситуации, при которой исходное кодовое дерево дополняется мнимыми узлами так, чтобы сформировалось четверичное дерево (рис. 5).
Каждому мнимому концевому узлу четверичного дерева приписывается символ, соответствующий родительскому узлу. Данному дереву может быть сопоставлена таблица декодирования (табл. 5), в каждой строке которой осуществляется анализ двух
очередных двоичных разрядов битового потока bj bj+1 . Отметим, что переход к модифицированной таблице позволяет декодировать символы x5 и x6 за три перехода,
по сравнению с пятью переходами при использовании табл. 4 и т.д. Аналогичным образом данный подход может быть применен и при анализе большего числа двоичных
разрядов.
19
x0
0
0
1
1
0
1
x0
x1
x2
0
0
1
1
0
1
x3
x4
x5
0
0
1
1
0
1
x5
x6
x6
Рис. 5. Дерево Хаффмана при двухбитном декодировании
4.
Порядок выполнения лабораторной работы
1. Использовать в качестве ѕисточника информацииї символы текстового файла. Объем файла должен быть не менее 2 мегабайт.
Построить одномерное распределение вероятностей символов в
текстовом файле. Исключить из рассмотрения символы с нулевой вероятностью. Вычислить энтропию источника информации
H(X) по формуле (3).
2. Построить код Хаффмана в соответствии с вариантом задания.
Вычислить среднюю длину кодового слова l по формуле (4) и
избыточность кода. Убедиться, что избыточность кода удовлетворяет оценке (5).
3. Реализовать кодер в соответствии с вариантом задания. Сформировать сжатый файл. Убедиться, что размер сжатого файла
примерно равен ln, где n количество символов в исходном текстовом файле.
4. Реализовать декодер в соответствии с вариантом задания. Убедиться, что исходный и восстановленный текстовые файлы полностью совпадают как по размеру, так и по содержимому.
20
Таблица 5.
Двухбитное декодирование кода Хаффмана
Адрес,a
bj bj+1
f [a]
l[a]
Адрес перехода, A[a]
Сообщение, x[a]
0
00
1
1
x0
1
01
1
1
x0
2
10
1
2
x1
3
11
0
4
4
00
1
4
x2
5
01
1
4
x3
6
10
1
4
x4
7
11
0
8
8
00
1
5
x5
9
01
1
5
x5
10
10
1
5
x6
11
11
1
5
x6
5.
Требования к содержанию отчета
1. Постановка задачи.
2. Описание алгоритмов построения кода Хаффмана, кодера и декодера в соответствии с вариантом задания; значение энтропии,
средней длины кодового слова и избыточности кода.
3. Выводы по работе.
21
6.
Варианты заданий
ќ
Алгоритм
построения кода
Размер
промежуточного
буфера кодера,
бит
Количество
анализируемых
разрядов в
декодере
Способ передачи конца
файла
1
С обходом
дерева
8
1
Добавление
неполного
кодового слова
2
С обходом
дерева
16
1
Добавление количества
символов в файле
3
С обходом
дерева
16
1
Добавление
неполного
кодового слова
4
С обходом
дерева
32
1
Добавление количества
символов в файле
5
С обходом
дерева
32
1
Добавление
неполного
кодового слова
6
С обходом
дерева
64
1
Добавление количества
символов в файле
7
Без обхода
дерева
8
1
Добавление
неполного
кодового слова
8
Без обхода
дерева
16
1
Добавление количества
символов в файле
9
Без обхода
дерева
16
1
Добавление
неполного
кодового слова
10
Без обхода
дерева
32
1
Добавление количества
символов в файле
11
Без обхода
дерева
32
1
Добавление
неполного
кодового слова
12
Без обхода
дерева
64
1
Добавление количества
символов в файле
13
Без обхода
дерева
8
2
Добавление количества
символов в файле
14
Без обхода
дерева
8
4
Добавление количества
символов в файле
22
Библиографический список
1.
Колесник В.Д. Полтырев Г.Ш.
,
Курс теории информации. М., 1982.
2.
Кудряшов Б.Д.
Теория информации: учебник для вузов, СПб., 2009.
3.
Кудряшов Б.Д. Овсянников Е.П. Шехунова Н.А.
,
,
Кодирование источников информации: методические указания к выполнению лабораторных работ / ЛИАП. Л., 1991.
23
Документ
Категория
Без категории
Просмотров
0
Размер файла
1 566 Кб
Теги
part, labs, twoside
1/--страниц
Пожаловаться на содержимое документа