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

Определения.

Неравномерными называют коды, кодовые слова которых имеют различную длину.

Оптимальность можно понимать по-разному, в зависимости от критерия. В данном случае таким критерием является средняя длина кодового слова. Оптимальность с учетом этого критерия понимается в смысле минимальной длины средней длины кодового слова.

Дальнейшие выводы будем делать при следующих условиях:

Пусть буквы источника а₁, а₂, …, а_k имеют вероятности появления p₁, p₂, … , p_k Упорядочим буквы в порядке убывания вероятностей их появления в сообщении и пронумеруем их в этом порядке. В результате . Для кодирования будем использовать вторичный алфавит, состоящий из 2 букв – 0 и 1, т.е. двоичный код.

Пусть x₁, x₂, … , x_k − множество кодовых слов, имеющих длину n₁, n₂, … , n_k. Ограничимся также рассмотрением только префиксных кодов. Результаты, полученные в отношении длин кодовых слов для префиксных кодов, согласно теоремам 1 и 2 можно распространять на весь класс однозначно декодируемых кодов, а результаты, полученные для двоичных кодов несложно обобщить на коды с любым объемом вторичного алфавита.

 

Докажем 2 леммы[9].