3.7.4. Коды Шеннона−Фэно

Ранее, независимо друг от друга Шенноном и Фэно¹³ была предложена другая процедура построения эффективного кода. Получаемый при ее помощи код называют кодом Шеннона−Фэно.

Код Шеннона−Фэно строится следующим образом:

1. буквы алфавита сообщений выписываются в таблицу в порядке убывания вероятностей;

2. затем они разделяются на две группы так, чтобы суммы вероятностей в каждой из групп были по возможности одинаковы;

3. всем буквам верхней половины в качестве первого символа приписывается 1, а всем нижним 0;

4. каждая из полученных групп, в свою очередь, разбивается на две подгруппы с одинаковыми суммарными вероятностями и т. д. ;

5. процесс повторяется до тех пор, пока в каждой подгруппе останется по одной букве.

Рассмотрим алфавит из восьми букв. Ясно, что при обычном (не учитывающем статистических характеристик) кодировании для представления каждой буквы требуется три символа.

Наибольший эффект сжатия получается в случае, когда вероятности букв представляют собой целочисленные отрицательные степени двойки. Среднее число символов на букву в этом случае точно равно энтропии. Убедимся в этом, вычислив энтропию: и среднее число символов на букву где n(Zi) —число символов в кодовой комбинации¹⁴, соответствующей букве Zi. Характеристики такого ансамбля и коды букв представлены в таблице 3.4.

Таблица 3.4.

Буквы	Вероятности	Ступени разбиения							Кодовые комбинации
		1	2	3	4	5	6	7
Z1	1/2	1							1
Z2	1/4	0	1						01
Z3	1/8	0	0	1					001
Z4	1/16	0	0	0	1				0001
Z5	1/32	0	0	0	0	1			00001
Z6	1/64	0	0	0	0	0	1		000001
Z7	1/128	0	0	0	0	0	0	1	0000001
Z8	1/128	0	0	0	0	0	0	0	0000000

В более общем случае для алфавита из восьми букв среднее число символов на букву будет меньше трех, но больше энтропии алфавита H(Z). Для ансамбля букв, приведенного в таблице 3.5, энтропия равна 2,76, а среднее число символов на букву 2,84.

Таблица 3.5

Буквы	Вероят-ности	Ступени разбиения								Кодовые комбинации
		1	2	3	4	5	6	7
Z1	0,22	1	1						11
Z2	0,20	1	0	1					101
Z3	0,16	1	0	0					100
Z4	0,16	0	1						01
Z5	0,10	0	0	1					001
Z6	0,10	0	0	0	1				0001
Z7	0,04	0	0	0	0	1			00001
Z8	0,02	0	0	0	0	0			00000

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

Рассмотрим сообщения, образованные с помощью алфавита, состоящего всего из двух букв Z₁ и Z₂, с вероятностями появления соответственно p(Z_i)=0,9 и р(Z₂) =0,1.

Поскольку вероятности не равны, то последовательность из таких букв будет обладать избыточностью. Однако при побуквенном кодировании никакого эффекта не получается.

Действительно, на передачу каждой буквы требуется символ либо 1, либо 0, в то время как энтропия равна 0,47.

При кодировании блоков, содержащих по две буквы, получим коды, показанные в табл. 3.6.

Таблица 3.6

Буквы	Вероятности	Ступени разбиения							кодовые комбинации
		1	2	3	4	5	6	7
Z1 Z1	0,81	1								1
Z2 Z1	0,09	0	1							01
Z3 Z1	0,09	0	0	1						001
Z4 Z1	0,01	0	0	0						000

Так как буквы статистически не связаны, вероятности блоков определяются как произведение вероятностей составляющих букв.

Среднее число символов на блок получается равным 1,29; а на букву − 0,645.

Кодирование блоков, содержащих по три буквы, дает еще больший эффект. Соответствующий ансамбль и коды приведены в табл. 3.7.

Таблица 3.7.

Буквы	Вероят ности	Ступени разбиения							кодовые комбинации
		1	2	3	4	5	6	7
Z1 Z1 Z1	0,729	1							1
Z2 Z1 Z1	0,081	0	1	1					01
Z1 Z2 Z1	0,081	0	1	0					010
Z2 Z2 Z1	0,081	0	0	1					001
Z1 Z1 Z2	0,009	0	0	0	1	1			00011
Z2 Z1 Z2	0,009	0	0	0	1	0			00010
Z1 Z2 Z2	0,009	0	0	0	0	1			00001

Среднее число символов на блок равно 1,59; а на букву − 0,53; что всего на 12% больше энтропии. Теоретический минимум Н(Z) = 0,47 может быть достигнут при кодировании блоков, включающих бесконечное число букв_: .

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

Рассмотренная нами методика Шеннона—Фэно не всегда приводит к однозначному построению кода. Ведь при разбиении на подгруппы можно сделать большей по вероятности как верхнюю, так и нижнюю подгруппу.

Множество вероятностей, приведенных в таблице 3.5, можно было бы разбить иначе, например, так, как это показано в табл. 3.8.

Таблица 3.8.

Буквы	Вероятности	Ступени разбиения								кодовые комбинации
		1	2	3	4	5	6	7
Z1	0,22	1	1						11
Z2	0,20	1	0						10
Z3	0,16	0	0	1					001
Z4	0,16	0	1	0					010
Z5	0,10	0	0	1					001
Z6	0,10	0	0	0	1				0001
Z7	0,04	0	0	0	0	1			00001
Z8	0,02	0	0	0	0	0			00000

При этом среднее число символов на букву оказывается равным 2,80. Таким образом, построенный код может оказаться не самым лучшим. При построении эффективных кодов с основанием m>2 неопределенность становится еще большей.

От указанного недостатка свободна методика Хаффмена. Она гарантирует однозначное построение кода с наименьшим для данного распределения вероятностей средним числом символов на букву.