Доказательство оптимальности кода. Докажем, что код Хаффмана является оптимальным кодом

Докажем, что код Хаффмана является оптимальным кодом. Доказывать будем аналогично доказательству оптимальности кода Шеннона-Фано, поэтому опустим теоретические обоснования и, просто выполнив необходимые расчеты, сделаем вывод.

1. Код Хаффмана - неравномерный код. Чтобы он был оптимальным, необходимо, чтобы средняя длина кодовой комбинации для определенного алфавита, закодированного этим кодом, была меньше длины кодовой комбинации равномерного двоичного кода, которым можно закодировать этот алфавит.

По формуле (5) найдем среднюю длину кодовой комбинации для нашего алфавита (количество символов алфавита n = 16), закодированного кодом Хаффмана, и получим следующее значение:

,

то есть в среднем на один символ нашего алфавита приходится 3,8131 двоичных символов.

Длина кодовой комбинации равномерного двоичного кода, которым можно закодировать наш алфавит, будет равняться 4, поскольку таким кодом можно закодировать алфавит, максимальное количество символов которого будет равняться 2⁴ = 16.

Это означает, что необходимая длина кодовой комбинации равномерного двоичного кода больше средней длины кодовой комбинации Хаффмана.

2. Сравним энтропию источника первичного ансамбля сообщений A (нашего алфавита) с энтропией этого же источника при кодировании его ансамбля сообщений кодом Хаффмана.

Рассчитаем энтропию источника сообщений вторичного алфавита B - H(B). Для этого необходимо найти вероятность появления символов этого алфавита. Положим, что длина текста

.

Таблица 6

Подсчет количества “0” и “1” в закодированном тексте (исходный текст длиной L = 10 000 символов)

Символ первичного алфавита	Вероятность появления символа первичного алфавита	Закодированный кодом Хаффмена символ	Количество символов в кодовой комбинации	Количество символов в тексте
о	0,1067
а	0,1067
и	0,0933
в	0,0933
к	0,08
н	0,08
с	0,08
е	0,08
л	0,0667
я	0,0667
ч	0,0533
й	0,0267
т	0,0267
ь	0,0133
р	0,0133
г	0,0133
Количество каждого из двоичных символов в закодированном тексте
Длина закодированного текста

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

По формуле (3) рассчитаем энтропию источника вторичного ансамбля сообщений B - H(B) (количество символов алфавита n = 2):

Теперь по формуле (6) найдем энтропию источника при кодировании его первичного ансамбля сообщений A кодом Хаффмана:

.

Энтропия источника первичного ансамбля сообщений A:

.

Следовательно:

≈ .

Вывод: из двух пунктов доказательства следует, что код Хаффмана является оптимальным.

Коды, обнаруживающие ошибки

Код с проверкой на чётность