Теорема кодирования источников. Неравенство Крафта. Префиксный код.

Теорема Шеннона о кодировании источников устанавливает связь между средней длинной кодового слова и энтропией источника:

Для любого дискретного источника без памяти X с конечным алфавитом и энтропией H(X) существует D-ичный префиксный код, в котором средняя длинна кодового слова , удовлетворяет неравенству:

 

В префиксном коде никакое кодовое слово не является префиксом другого кодового слова. Это значит, что поток кодовых слов может использоваться без специального разделения этих слов. Например, если код 101 является кодом какой-то буквы, то в качестве кодов других букв нельзя использовать следующие комбинации: 1,10,10101, …и т.д.

Из теоремы Шеннона следует, что тем ближе к энтропии источника, тем более эффективно кодирование. В идеальном случае, когда , код называют эффективным. Эффективность кода оценивается величиной:

.

 

Если средняя длина =min, то код является оптимальным.

Теорема кодирования источников доказывается с использованием неравенства Крафта:

Для существования однозначно декодируемого D-ичного кода, содержащего k кодовых слов с длинами n₁,n₂,…,n_k, необходимо и достаточно, чтобы выполнялось неравенство Крафта: