Вопрос № 6. Теорема 2.2.1. (Неравенство Крафта.) Пусть ансамбль источника X содержит L сообщений
Теорема 2.2.1. (Неравенство Крафта.) Пусть ансамбль источника X содержит L сообщений
При неравномерном кодировании длина кодового слова случайна, поэтому мерой экономности кодирования может служить среднее количество символов на сообщение – средняя длина кодового слова
Следующие две теоремы, приводимые без доказательства, связывают среднюю длину неравномерного кода со статистикой источника. Теорема 2.2.2. Пусть задан ансамбль
Следует отметить, что равенство в (2.3) достигается только при Определение 2.2.2. Код источника, для которого средняя длина кодовых слов равна наименьшему из возможных значений, называется оптимальным. Теорема 2.2.3. Для дискретного источника с энтропией H (X) существует неравномерный префиксный код, средняя длина кодовых слов которого подчиняется неравенству
Приведенные теоремы 2.2.2 и 2.2.3 представляют собой обратную и прямую теоремы кодирования элементарных сообщений источника. Прилагательное «элементарное» здесь использовано для того, чтобы отличить данный вариант кодирования от варианта, при котором в кодовые слова отображаются не отдельные сообщения, а блоки сообщений, выдаваемых источником последовательно во времени.
|
. Тогда для существования двоичного префиксного кода с длинами слов 
, необходимо и достаточно выполнение неравенства:
(2.1)
, определяемая соотношением
. (2.2)
с энтропией H (X). Тогда средняя длина слова произвольного однозначно декодируемого неравномерного кода не меньше энтропии источника:
(2.3)
, и значит, 
. Так как 
– целое, то указанные равенства выполняются для всех x, если их вероятности являются степенями двойки с целым отрицательным показателем.
(2.4)
