ВУЗ:
Составители:
56
стей. Два последних сообщения объединяются в одно вспомогательное. Ему
приписывается суммарная вероятность. Вероятности снова располагаются в
порядке их убывания в дополнительном столбце, где две последние объеди-
няются. Процесс продолжается до получения вспомогательного столбца с
вероятностью, равной единице.
Согласно этой таблице, строится
кодовое дерево в виде графа. При дви-
жении из вершины дерева с P =1 ребрам графа присваиваются соответствую-
щие вероятности и кодовые символы, например − “1” при выходе из узла вле-
во и “0”при выходе из узла вправо. Движение по кодовому дереву из вершины
к сообщению, определяемому соответствующей вероятностью, дает кодовую
комбинацию для сообщения.
4.2. Типовые примеры
Пример 4.2.1. Ансамбль N9 сообщений x
i
,
i..1N
на выходе ис-
точника X имеет следующие вероятности их появлений, заданные при
ORIGIN 1 вектор-строкой
Px ( )0.04 0.06 0.08 0.10 0.10 0.12 0.15 0.15 0.20 ,
где, например,
=
<>
Px
3
0.08 и =
<>
Px
6
0.12 .
Произвести кодирование эффективным двоичным кодом по методу Шен-
нона-Хаффмена. Вычислить энтропию сообщений и среднюю длину n
ср
кодо-
вого слова. Сравнить с минимально возможной длиной n
ср.min
.
Решение. Предварительно определим единицы измерения количества эн-
тропии и информации как
nit ln ( )e
и
bit
.
nit ln ( )2 .
Составим матрицу, в которой вероятности выписываются в первый (ос-
новной) столбец в порядке их убывания, т.е.
Po reverse sort
T
Px ;
=
T
Po 0.2 0.15 0.15 0.12 0.1 0.1 0.08 0.06 0.04().
Две последних вероятности P1 объединяются в одну вспомогательную вероят-
ность Ps1:
P1
Po
N1
Po
N
; =P1
0.06
0.04
; Ps1 P1; =Ps1 0.1
Вероятности
Px
1
()0.20 0.15 0.15 0.12 0.10 0.10 0.08 0.1 0
снова располагаются в порядке их убывания в дополнительном столбце
Pd1 reverse sort
T
Px
1
;
.
Страницы
- « первая
- ‹ предыдущая
- …
- 54
- 55
- 56
- 57
- 58
- …
- следующая ›
- последняя »
