Кодирование информации. Шикина В.Е. - 11 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

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

Рубрика: 

8
Теперь, двигаясь по кодовому дереву сверху вниз, можно записать для
каждой буквы соответствующую ей кодовую комбинацию:
z
l
z
2
z
3
z
4
z
5
z
6
z
7
z
8
01 00 111 110 100 1011 10101 10100
1.5. Префиксные коды
Рассмотрев методики построения эффективных кодов, нетрудно убедиться
в том, что эффект достигается благодаря присвоению более коротких кодовых
комбинаций более вероятным буквам и более длинных – менее вероятным
буквам. Таким образом, эффект связан с различием в числе символов кодовых
комбинаций. А это приводит к трудностям при декодировании. Конечно, для
различения кодовых комбинаций можно
ставить специальный разделительный
символ, но при этом значительно снижается желаемый эффект, так как средняя
длина кодовой комбинации по существу увеличивается на символ.
Более целесообразно обеспечить однозначное декодирование без введения
дополнительных символов. Для этого эффективный код необходимо строить
так, чтобы ни одна комбинация кода не совпадала с началом более длинной
комбинации.
Коды, удовлетворяющие этому условию, называются
префиксными кодами. Последовательность комбинаций префиксного кода,
например, кода
z
1
z
2
z
3
z
4
00 01 101 100
декодируется однозначно:
100 00 01 101 101 101 00
z
4
z
1
z
2
z
3
z
3
z
3
z
1
Последовательность комбинаций непрефиксного кода, например кода
z
1
z
2
z
3
z
4
00 01 101 010
(комбинация 01 является началом комбинации 010), может быть декодирована
по-разному:
00 01 01 01 010 101
z
1
z
2
z
2
z
2
z
4
z
3
,
00 010 101 010 101
z
1
z
4
z
3
z
4
z
3
или
00 01 010 101 01 01
z
1
z
2
z
4
z
3
z
2
z
2
.
Нетрудно убедиться, что коды, получаемые в результате применения
методики Шеннона – Фэно или Хаффмена, являются префиксными.

Страницы