Вопрос № 6. Теорема 2.2.1. (Неравенство Крафта.) Пусть ансамбль источника X содержит L сообщений

Теорема 2.2.1. (Неравенство Крафта.) Пусть ансамбль источника X содержит L сообщений . Тогда для существования двоичного префиксного кода с длинами слов , необходимо и достаточно выполнение неравенства:

(2.1)

При неравномерном кодировании длина кодового слова случайна, поэтому мерой экономности кодирования может служить среднее количество символов на сообщение – средняя длина кодового слова , определяемая соотношением

. (2.2)

Следующие две теоремы, приводимые без доказательства, связывают среднюю длину неравномерного кода со статистикой источника.

Теорема 2.2.2. Пусть задан ансамбль с энтропией H (X). Тогда средняя длина слова произвольного однозначно декодируемого неравномерного кода не меньше энтропии источника:

(2.3)

Следует отметить, что равенство в (2.3) достигается только при , и значит, . Так как – целое, то указанные равенства выполняются для всех x, если их вероятности являются степенями двойки с целым отрицательным показателем.

Определение 2.2.2. Код источника, для которого средняя длина кодовых слов равна наименьшему из возможных значений, называется оптимальным.

Теорема 2.2.3. Для дискретного источника с энтропией H (X) существует неравномерный префиксный код, средняя длина кодовых слов которого подчиняется неравенству

(2.4)

Приведенные теоремы 2.2.2 и 2.2.3 представляют собой обратную и прямую теоремы кодирования элементарных сообщений источника. Прилагательное «элементарное» здесь использовано для того, чтобы отличить данный вариант кодирования от варианта, при котором в кодовые слова отображаются не отдельные сообщения, а блоки сообщений, выдаваемых источником последовательно во времени.