Составители:
Рубрика:
48
Методика поясняется примером, представленным в табл. 2.1, где для
алфавита источника с объемом М = 8 приняты произвольные значения
вероятностей p(x
i
) , но
1
()1.
M
i
i
px
=
=
∑
Для составления кодовой комбинации, соответствующей данному
сообщению x
i
,
необходимо проследить путь перехода сообщения по
строкам и столбцам таблицы. Для наглядности кодовое дерево постро-
ено в поле табл. 2.1. Целесообразно строить кодовое дерево, начиная с
первого столбца таблицы, располагая ветви против группируемых по-
парно вероятностей p (x
i
) и соединяя их со значением суммарной веро-
ятности p
∑
, располагаемой в следующем столбце. Ветвям с большей
вероятностью присваивается символ 1, а с меньшей – 0 (или наоборот).
Такое последовательное ветвление продолжается до тех пор, пока ветвь
не закончится узлом с вероятностью p (x
i
) каждой буквы алфавита
источника. Отдельно кодовое дерево для алфавита источника, рассмат-
риваемого в примере, приведено на рис. 2.2.
Перемещаясь по кодовому дереву сверху вниз, можно записать для
каждой буквы алфавита x
i
соответствующую ей кодовую комбинацию
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8
1 011 010 001 00011 00010 00001 00000
Код Хафмена при любом распределении вероятностей p (x
i
) дает
однозначный ансамбль набора кодовых слов, в то время как при коде
Шеннона – Фано на выходной ансамбль кодовых слов влияет субъек-
1
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8
0,729
0,081
0,081
0,081
0,009
0,009
0,009
0,001
0
x
i
Шаговая процедура (кодовое дерево)
p(x
i
)
1
Вероят-
ности
Кодовые
слова
0,729
0,081
0,081
0,081
0,010
0,009
0,009
0,729
0,081
0,081
0,081
0,018
0,010
0,729
0,081
0,081
0,081
0,028
0,729
0,109
0,081
0,081
0,729
0,162
0,109
0,729
0,271
1
0
1
0
1
0
0
1
1
0
0
1
1
1
011
010
001
00011
00010
00001
00000
Таблица 2.1
Страницы
- « первая
- ‹ предыдущая
- …
- 48
- 49
- 50
- 51
- 52
- …
- следующая ›
- последняя »
