Лекции по теории информации. Фурсов В.А. - 79 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

79
9.3 Методы эффективного кодирования некоррелированной
последовательности знаков, код Шеннона-Фано
Теорема Шеннона отвечает на вопрос: при каких условиях возможно в
принципе построение кода, обеспечивающего передачу всех сообщений, фор-
мируемых источником. Естественно стремление строить наилучшие, с точки
зрения максимума передаваемой информации, коды. Для того чтобы каждый
символ (например, двоичного) кода нес максимум информации, символы кодо-
вой комбинации должны быть независимы и принимать значения (0 и 1) с рав-
ными вероятностями. Построение эффективных кодов в случае статистиче-
ской независимости символов сообщений опирается на методики Шеннона и
Фано (код Шеннона-Фано).
Код строится следующим образом. Кодируемые знаки выписывают в таб-
лицу в порядке убывания их вероятностей в сообщениях. Затем их разделяют на
две группы так, чтобы значения сумм вероятностей в каждой группе были
близкими. Все знаки одной из групп в соответствующем разряде кодируются,
например, единицей, тогда знаки второй группы кодируются нулем. Каждую
полученную в процессе деления группу подвергают вышеописанной операции
до тех пор, пока в результате очередного деления в каждой группе не останется
по одному знаку (таблица 9.1).
В приведенном примере среднее число символов на один знак
8 7
7
1 1
7 127
2 2 64
ср i i
i
i i
i
l p l
,
где
i
l
– число символов в
i
-м разряде, имеет такую же величину, как и энтро-
пия, рассчитанная в среднем на один знак:
8 7
7
2 2 2
7
1 1
( ) log log 2 log 2
2 2 64
i
i i
i
i i
H z p p
.
Таблица 9.1
Знаки Вероятности Коды
1
z
1/2 1
2
z
1/4 01

Страницы