Избыточность кода Хаффмена

Из теоремы 8.1 следует, что для построенных по алгоритму Хаффмана кодов средняя длина кодовых слов удовлетворяет неравенству

, (8.16)

где — энтропия ансамбля.

Разность называется избыточностью неравномерного кода. При кодировании с избыточностью на каждое сообщение затрачивается на бит больше, чем в принципе можно было бы потратить, если использовать теоретичес­ки наилучший (возможно, нереализуемый) способ кодирования.

Итак, из (8.16) следует, что для кода Хаффмана избыточность г < 1. Хоте­лось бы получить более точную оценку средней длины кодовых слов. Гораздо бо­лее точную оценку избыточности получил Р. Галлагер, наложив ограничение на максимальную из вероятностей сообщений.

Теорема 8.3. Пусть — наибольшая из вероятностей сообщений конечно­го дискретного ансамбля. Тогда избыточность кода Хаффмана для этого ансамбля удовлетворяет неравенствам:

где — энтропия двоичного ансамбля; .