Прямая теорема неравномерного кодирования

Теорема 8.1. Для ансамбля с энтропией существует побуквенный неравномерный префиксный код со средней длиной кодовых слов

. (8.13)

Обсудим полученную оценку длины кодовых слов. Мы знаем, что дости­жимая скорость кодирования примерно равна энтропии. Теорема гарантирует, что средняя длина слов хорошего кода отличается от энтропии не более чем на 1. Ес­ли энтропия велика, то проигрыш по сравнению с минимально достижимой ско­ростью можно считать небольшим. Но предположим, что . Теорема га­рантирует, что существует код со средней длиной кодовых слов не более 1,1 бита. Но нам хотелось бы затрачивать на передачу одного сообщение примерно в 10 раз меньше бит. Этот пример показывает, что либо теорема дает неточную оценку, либо побуквенное кодирование в этом случае не эффективно.

На этом же примере мы убедимся в том, что теорема достаточно точна и ее результат не может быть улучшен, если не использовать никакой дополнительной информации об источнике. Действительно, предположим, что дан двоичный ис­точник Х= {0,1} с вероятностями букв . Минимально достижимая длина кодовых слов наилучшего кода, очевидно, равна 1. Теорема говорит, что средняя длина кодовых слов не больше , т. е. стремится к 1 при . Таким обра­зом, для данного примера двоичного источника теорема верна.

Достижение скоростей (затрат на передачу одной буквы источника), мень­ших 1, невозможно при побуквенном кодировании, поскольку длина кодового слова не может быть меньше 1. Однако переход к кодированию блоков сообще­ний решает эту проблему и позволяет сколь угодно близко подойти к теоретическому пределу, равному энтропии . Конструктивным ре­шением данной задачи является арифметическое кодирование.