Составители:
Рубрика:
47
вать не отдельные символы, а целые блоки из нескольких символов
(букв). В этом студенты убеждаются, исследуя в лабораторной работе
метод кодирования Хафмена.
Код Хафмена
Д. А. Хафменом был предложен систематический метод кодирова-
ния, который всегда приводит к получению оптимального множества
кодовых слов для кодирования данного множества сообщений.
Для дискретных систем с двоичным алфавитом кодера (m = 2) мето-
дика построения кода Хафмена сводится к следующей процедуре:
1. Все m
i
= M сообщений (буквы алфавита источника) выписывают-
ся в порядке убывания вероятностей p (x
i
) (табл. 2.1).
2. Две последние буквы алфавита, имеющие наименьшие вероятнос-
ти p (x
М–1
) и p (x
M
), группируются вместе и объединяются в одну вспо-
могательную букву, которой приписывается суммарная вероятность p
∑
=
= p (x
M–1
) + p (x
M
).
3. Вероятности букв, не участвовавших в объединении, и получен-
ная суммарная вероятность снова располагаются в порядке убывания
вероятностей (в следующем столбце табл. 2.1). Объем нового алфавита
таким образом уменьшается на единицу: М–1.
4. Производят второе укрупнение алфавита, состоящего уже из М–1
символов, путем объединения двух символов с наименьшими вероят-
ностями и вычисляют их общую вероятность. Получают новый алфа-
вит объемом М–2.
5. Упорядочивают по вероятности символы этого нового алфавита.
6. Образуют последовательность укрупненных алфавитов путем пос-
ледовательного повторения операций пп. 4 и 5, пока в ансамбле не
останется единственное сообщение с вероятностью, равной 1 (шаговая
процедура, записываемая в столбцах табл. 2.1).
7. Проведя линии, соединяющие символы при последовательном ук-
рупнении алфавита, получают так называемое кодовое дерево, концы вет-
вей которого являются символами исходного алфавита источника сооб-
щений. Приписывая ветвям дерева, исходящим из каждого промежуточ-
ного узла, различные символы алфавита кодера (0 или 1), получают кодо-
вые слова, соответствующие кодируемым сообщениям источника.
Страницы
- « первая
- ‹ предыдущая
- …
- 47
- 48
- 49
- 50
- 51
- …
- следующая ›
- последняя »
