Статистическое компрессирование аудио сигналов. Вологдин Э.И. - 24 стр.

UptoLike

ВУЗ: 

СПбГУТ | Санкт-Петербург

Составители: 

Рубрика: 

24
Хаффманом, был двухпроходный. На первом проходе строится частотный словарь кодо-
вых символов и генерируются коды. На втором проходе происходит непосредственно ко-
дирование.
Код Хаффмана задается алфавитом
1 2 3
, , ,...
n
A a a a a
- из
n
различных символов с
известной частотой их появления
1 2 3
, , ,...
n
P p p p p
. Под термином «частота» пони-
мается относительная частота событий, их вероятность, специалисты в области теории
информации это понятие определяют абстрактным термином «вес». Этому алфавиту со-
ответствует набор двоичных кодовых комбинаций
1 2 3
, , ,...
n
C c c c c
длиной
1 2 3
, , ,...
n
L l l l l
. В коде Хаффмана:
(1)
i
c
не является префиксом
j
c
,
(2)
минимальна,
поэтому он называется минимально-избыточным префиксным кодом . Длина кода Хафф-
мана всегда не превосходит
2
ceil log
i
P
, где
ceil
означает округление числа в скоб-
ках до целого значения в большую сторону.
Свойство (1) называется свойством префиксности. Оно позволяет однозначно декоди-
ровать коды переменной длины. Сумму в свойстве (2) можно трактовать как размер зако-
дированных данных в битах. Это позволяет оценить степень сжатия, не прибегая непо-
средственно к кодированию.
Известно, что любому бинарному префиксному коду соответствует определенное би-
нарное дерево. Бинарное дерево, соответствующее коду Хаффмана, называется деревом
Хаффмана. Строится оно на основе таблицы частот (кодовая таблица) встречаемости сим-
волов в сообщении. Задача построения кода Хаффмана равносильна задаче построения
соответствующего ему дерева.
Алгоритм построения дерева Хаффмана рассмотрим на конкретном простейшем при-
мере. Корень дерева располагается сверху, его листьями служат символы алфавита
1 2 3
, , ,...
n
A a a a a
, а ветви – это линии соединяющие корень дерева с листьями (рис.4.22)
. Построение дерева начинается снизу вверх до корня дерева, затем начинается спуск
вниз по дереву, чтобы построить двоичный код для каждого символа. Он строится спра-
ва налево (от младшего разряда к старшему). Алгоритм кодирования включается в себя
следующие шаги.
Составляется список кодируемых символов с указанием их вероятностей, удобно
расположить их в таблице в порядке убывания их вероятности (рис.22.)
Рис.22. Коды Хафмана

Страницы