2.3.4.Оптимальное кодирование

До сих пор не учитывалось, что сообщения могут иметь различную вероятность появления. Пусть необходимо передать четыре сообщения A,B,C,D. Если их закодировать двоичным кодом, то получим четыре кодовых комбинации 00, 01, 10, 11. При равной вероятности каждого сообщения использование такого способа кодирования очевидно. Если же одно из сообщений встречается чаще других, то его следует кодировать более коротким словом, тогда как более редкие сообщения можно кодировать более длинным словом.

Один из способов построения оптимальных кодов заключается в следующем:

1. Сообщения разбиваются на две группы таким образом, чтобы сумма вероятностей в каждой группе была примерно одинакова. Одной группе приписывается символ 1, другой – 0.

Далее каждая из групп разбивается по такому же правилу, и вновь образовавшимся подгруппам также приписываются символы 1 и 0.

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

Пусть . Тогда процесс построения оптимального кода будет следующий:

• после первого разбиения в первой группе останется единственное сообщение , во второй - ;

• после второго разбиения в первой группе - , во второй - ;

• после третьего разбиения в первой группе - , во второй - .

Третье разбиения будет последним, т.к. после него в каждой группе останется по одному сообщению. Данный процесс проиллюстрирован в таблице 2.2 и на рис.2.6.

Таблица 2.2
Процесс построения оптимальных кодов
Сообще-ние	Вероятность появления сообщения	Разбиения			Код сообщения
		1	2	3
A	0.5	1			1
B	0.25	0	1		01
C	0.125	0	0	1	001
D	0.125	0	0	0	000

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

Среднюю длину кода, т.е. среднее число бит, приходящихся на одно сообщение, вычислим по формуле , где - число бит, требуемое для кодирования i-го сообщения. Для полученного оптимального кода имеем: . При равномерном кодировании , в нашем случае (коды 00,01,10,11) : .

При рассмотренном способе оптимального кодирования среднее число бит, приходящихся на одно сообщение находится в пределах от H до . Энтропия - это минимально возможное среднее число бит, которым может быть закодировано одно сообщение. В рассмотренном алгоритме построения оптимальных кодов n=H получается не всегда. Есть другие способы построения оптимальных кодов, позволяющие получить n=H, например, алгоритм арифметического кодирования.