Составители:
Рубрика:
46
не требуют разделительных символов (маркеров) и при этом должно
выполняться их однозначное декодирование. Коды, удовлетворяющие
этому условию, называются префиксными кодами, так как ни одно кодо-
вое слово не является передней частью ("префиксом" – приставкой) дру-
гого кодового слова.
3. Эффективные коды являются неравномерными, т. е. для передачи
разных символов сообщения m
i
используются кодовые комбинации раз-
ной длины. Наиболее вероятные сообщения кодируются самыми корот-
кими кодовыми словами, вследствие чего средняя длина кодового сло-
ва в сообщении уменьшается, что и позволяет решить задачу равенства
скорости передачи и пропускной способности канала.
При неравномерном эффективном кодировании средняя длина кодо-
вого слова
n
определяется выражением
1
(),
i
m
kk
k
nnpx
=
=
∑
(2.17)
где p (x
k
) – вероятность появления сообщения (кодового слова), при-
чем их сумма равна 1; n
k
– длина кодовых слов x
k
(k = 1, 2, ..., m
i
).
По аналогии с выражением (2.10), где предполагалось применение
равномерных кодов с постоянной длиной кодовых слов (n = const), при
использовании эффективных неравномерных кодов (n = var) избыточ-
ность кода источника
min
min
1.
k
n
nn
nn
−
χ= =−
(2.18)
Очевидно, когда n = n
min
, что эквивалентно равенству H
max
(X) = H(X),
избыточность кода χ
k
равна нулю, и при применении эффективных ко-
дов обеспечивается полное согласование источника сообщений с кана-
лом (2.16). При этом энтропия источника H(X) является оценкой сред-
него числа
n
двоичных символов, требуемых для кодирования сообще-
ний.
Процедуру построения эффективного кода, близкого к оптимально-
му, предложили практически одновременно Шеннон и Фано (код Шен-
нона – Фано). Эта процедура рассмотрена подробно в [1, разд. 3.3].
В данной лабораторной работе студенты знакомятся с процедурой
построения эффективных кодов, предложенной Хафменом. При малом
алфавите источника и неравновероятных символах x
i
выгодно кодиро-
Страницы
- « первая
- ‹ предыдущая
- …
- 46
- 47
- 48
- 49
- 50
- …
- следующая ›
- последняя »
