Средняя длина кода из таблицы 1 будет равна

бит,

что совпадает со значением энтропии:

бит.

Еще одним способом построения оптимальных кодов является метод Хаффмана. Код Хаффмана строится следующим образом:

1) располагают символы в порядке убывания их вероятностей;

2) складывают вероятности двух последних символов и из них образуют новый составной символ с вероятностью, равной получившейся сумме;

3) повторяют шаги 1 и 2, пока не останется только один символ с вероятностью 1;

4) приписывают компонентам составных символов 0 и 1 – первой компоненте приписывают 0, а второй – 1.

Покажем процесс построения кодов Хаффмена для алфавита сообщений

X = (x₁, x₂, x₃, x₄, x₅, x₆, x₇, x₈)

с распределением вероятностей появления символов

.

1. Исходный список букв X = {x₁, x₂, x₃, x₄, x₅, x₆, x₇, x₈} уже упорядочен, так как .

2. Объединим буквы x₇ и x₈ в одну букву x¹ с вероятностью и переупорядочим список:

, X¹ = {x₁, x₂, x₃, x₄, x¹, x₅, x₆}.

3. Повторим шаг 2 до тех пор, пока не останется одна буква в списке:

, X² = {x₁, x₂, x₃, x₄, x¹, x²};

, X³ = {x₁, x₂, x³, x₃, x₄};

, X⁴ = {x₁, x₂, x³, x⁴};

, X⁵ = {x⁵, x₁, x₂};

, X⁶ = {x⁵, x⁶};

, X⁷ = {x⁷}.

4. Присвоим двоичные коды символам:

x⁷: x⁵ = 0, x⁶ = 1;

x⁶: x₁ = 10, x₂ = 11;

x⁵: x³ = 00, x⁴ = 01;

x⁴: x₃ = 010, x₄ = 011;

x³: x¹ = 000, x² = 001;

x²: x₅ = 0010, x₆ = 0011;

x¹: x₇ = 0000, x₈ = 0001.

Таким образом, получены следующие коды исходных символов:

x₁ = 10, x₂ = 11, x₃ = 010, x₄ = 011, x₅ = 0010, x₆ = 0011, x₇ = 0000, x₈ = 0001.

Средняя длина кода равна

бит,

что совпадает со средней длиной кода Шеннона-Фано и с энтропией.

Способом добиться наименьшей средней длины кода на один символ является блочное кодирование. При блочном кодировании коды присваиваются не отдельным символам сообщений, а их сочетаниям. При увеличении числа символов в сочетании средняя длина кода на один символ приближается к энтропии. Например, пусть имеются две буквы алфавита – A и B, с вероятностями появления 0.9 и 0.1 соответственно. Закодировать их можно, присвоив 0 одному символу и 1 – другому:

A = 0, B = 1.

Средняя длина кода в этом случае будет равна 1 биту:

,

тогда как энтропия равна

бит.

Избыточность составляет около 53%. Если же закодировать двухбуквенные сочетания X_iX_j, X_i, X_j  {A, B} с вероятностями p(X_iX_j) =p_ip_j, то по методу Шеннона-Фано можно получить коды, представленные в таблице 2.

Таблица 2

Блочное кодирование Шеннона-Фано

XiXj	pipj	Шаг			Код
		1	2	3
AA	0.81	0			0
AB	0.09		0		10
BA	0.09	1	1	0	110
BB	0.01			1	111

Тогда средняя длина кода двухбуквенного блока будет равна бит, а на одну букву будет приходиться бит. Избыточность в этом случае будет составлять уже только около 17%. Если мы возьмем сочетания из трех букв, то получим еще лучший результат и т.д. Увеличивая длину блоков можно как угодно близко приблизиться к оптимальному значению энтропии.