3.3. ТЕОРЕМА КОДИРОВАНИЯ ДЛЯ ИСТОЧНИКА

Теорема 3.3.1. При заданных конечном ансамбле источника с энтропией и кодовом алфавите из символов можно так приписать кодовые слова буквам источника, что будет выполняться свойство префикса и средняя длина кодового слова будет удовлетворять условию

Более того для любого однозначно декодируемого множества кодовых слов

Доказательство. Покажем вначале справедливость (3.3.2), установив, что

Пусть вероятности букв источника и пусть длины кодовых слов. Имеем

Помещая под знак логарифма и объединяя слагаемые, будем иметь

Используя неравенство при получаем

Последнее неравенство в (3.3.6) следует из неравенства Крафта (3.2.3), которое справедливо для любого однозначно декодируемого кода. Это доказывает (3.3.2). Заметим, что равенство в (3.3.2) имеет место тогда и только тогда, когда

Это условие совпадает с ранее полученным условием (3.2.2) для каждой кодовой буквы и приводит к максимуму энтропии.

Покажем далее, как выбрать код, удовлетворяющий (3.3.1). Если бы длины кодовых слов не обязательно были целыми числами, то можно было бы просто подобрать чтобы удовлетворить условию (3.3.7). Однако можно приближенно удовлетворить (3.3.7), выбирая целые числа так, чтобы удовлетворялись неравенства

Суммирование (3.3.8) по превращает левое неравенство в неравенство Крафта (3.2.3), и существует префиксный код с этими длинами. Логарифмируя правое неравенство в (3.3.8), получаем

Умножая (3.3.9) на и суммируя по всем получаем (3.3.1), что завершает доказательство теоремы.

Можно получить более сильные результаты, если кодовые слова приписывать не отдельным буквам источника, а прямо последовательностям букв источника.

Теорема 3.3.2. Для заданных дискретного источника без памяти с энтропией и кодового алфавита из символов возможно так приписать кодовые слова последовательностям букв источника, что

будет выполняться свойство префикса и средняя длина кодовых слов на одну букву источника будет удовлетворять условию

Более того, левое неравенство справедливо для любого однозначно декодируемого множества кодовых слов.

Доказательство. Рассмотрим произведение ансамблей для последовательностей букв источника. Энтропия произведения ансамблей равна а средняя длина кодовых слов равна где означает среднюю длину на одну букву источника. Теорема 3.3.1 утверждает, что минимально достижимое значение (при сопоставлении кодового слова неравномерного кода каждой последовательности букв источника) удовлетворяет неравенствам

Разделив эти выражения на получим результат теоремы.

Теорема 3.3.2 очень похожа на теорему 3.1.1. Если выбрать достаточно большим и затем применить закон больших чисел к длинной последовательности, состоящей, в свою очередь, из последовательностей букв источника, то можно заметить, что из теоремы 3.3.2 следует первая часть теоремы 3.1.1. Однако теорема 3.3.2 немного сильнее, чем теорема 3.1.1, так как она предлагает относительно простой метод кодирования, а также альтернативу случайным ошибкам, а именно случайные длинные задержки.