10.9. Статическое кодирование дискретных сообщений

Кодирование по методу Шеннона-Фано-Хаффмана называется оптимальным, т.к. при этом повышается производительность дискретного источника, и статическим, т.к для реализации оптимального кодирования используются априорные вероятности появления на выходе источника каждого элемента сообщения (учитывается статистика сообщений).

Производительность и избыточность дискретного источника согласно определениям равны, соответственно:

откуда получаем:

Из этой формулы видно, что для увеличения производительности нужно уменьшить избыточность и среднюю длительность сообщений .

Известно, что , если априорные вероятности различных элементов сообщения различны ( при равной вероятности этих элементов). Но при неравной вероятности сообщений нужно применить оптимальное (статическое) кодирование, при котором уменьшается средняя длительность сообщений.

Идея такого кодирования заключается в том, что, применяя неравномерный неприводимый код, наиболее часто встречающиеся сообщения (буквы или слова) кодируются короткими комбинациями этого кода, а редко встречающиеся сообщения кодируются более длительными комбинациями.

Рассмотрим принципы оптимального кодирования на примере.

Пусть источник сообщений вырабатывает четыре сообщения , и с вероятностями , , .

Все сообщения выписываются в кодовую таблицу (табл. 10.1) в порядке убывания их вероятностей. Затем они разделяются на две группы так, чтобы суммы их вероятностей по возможности были одинаковы. В данном примере в первую группу входит сообщение с вероятностью и во вторую – сообщения , и с суммарной вероятностью, также равной 0,5.

Комбинациям, которые соответствуют сообщениям первой группы, присваивается в качестве первого символа кода 0, а комбинациям второй группы – 1. Каждая из двух групп опять делится на две группы с применением того же правила присвоения символов 0 и 1. В идеальном случае после первого деления вероятности каждой группы должны быть равны 0,5, после второго деления 0,25 и т.д. Процесс деления продолжается до тех пор, пока в группах не останется по одному сообщению.

Таблица 10.1 – Кодовая таблица.

		Группы			Комби- нации
		I	II	III
	0,5}	0				0		1		1
	0 ,25	1}	0			10		2		2
	0,125	1	1}	0		110		3		3
	0,125	1	1}	1		111		3		3

Для сравнения рассмотрим кодирование тех же четырех сообщений , и с применением обычного равномерного кода. Количество комбинаций при этом , где – число элементов в комбинации. Так как , то , длительность кодовой комбинации .

В рассматриваемом примере средняя длительность комбинаций благодаря примененному статическому кодированию уменьшалось в раза. Во столько же раз увеличилась и производительность источника (10.13).