Коды с минимальной избыточностью

Пусть имеется источник сообщений, который случайным образом последовательно порождает буквы алфавита Â Появления букв статистически независимы и подчинены распределению вероятностей где >0. Рассмотрим схему алфавита кодирования å: в алфавите Â со свойством взаимной однозначности. Пусть длина слова Введём стоимость кода при распределении P как математическое ожидание длины элементарного кода, т.е. Если нижняя грань по всем таким схемам å, то Это следует из того, что всегда можно взять в качестве кодов слова в алфавите одинаковой длины а для такой схемы

ТЕОРЕМА. Величина достигается на некоторой схеме å.

Доказательство. Для схемы, близкой к , в силу неравенства имеем Положив заметим, что а значит, существует лишь конечное число вариантов значений для которых ■

Коды стоимости называются оптимальными или кодами с минимальной избыточностью.

ТЕОРЕМА. Если оптимальный двоичный код при распределении (1)

и причём то код является оптимальным при распределении . (2)

Доказательство. Если и – стоимости кодов при распределениях (1), (2), то Действительно,

Пусть оптимальный код при распределении (2). Тогда в нём длины слов, соответствующих вероятностям q₁ и q₂, одинаковы, так как код оптимальный. На основе можно построить схему кодирования при распределении (1). Для его стоимости оптимальный код. ■