3.5. Основная теорема кодирования

Мы приступаем теперь к доказательству следующей основной теоремы.

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

Число не может быть сделано меньше, чем нижняя граница в выражении (3.18).

Вывод нижней границы в (3.18). Этот вывод уже приводился в разд. 3.1. Однако ввиду важности этой нижней границы желательно дать прямое доказательство ее, не прибегая к использованию мер информации, определенных в гл. 2. Обозначая снова через вероятность появления сообщения а через число символов в кодовом слове, соответствующем сообщению имеем следующее выражение для среднего числа символов на сообщение

Мы хотим показать, что когда удовлетворяет выражению (3.4), то

Пусть

Тогда, используя (2.91) и (3.4), получаем

Это соотношение в совокупности с соотношением (3.4) дает неравенство (3.20). Ч. Т. Д.

Вывод верхней границы выражении (3.18) подсказывается следующей леммой.

Лемма. Для существования множества кодовых слов со средней длиной

необходимо и достаточно, чтобы для каждого сообщения выполнялось условие

Когда это условие выполнено,

Доказательство леммы. Знак равенства в выражении (3.22) имеет место тогда и только тогда, когда имеет место знак равенства в выражении (2.91). В этом частном случае

и поэтому

Отсюда следует, что знак равенства имеет место в выражении (3.20) тогда и только тогда, когда выполнено равенство (3.28). С другой стороны, должно быть целым, поскольку оно является числом символов в кодовом слове, соответствующем Следовательно, условие (3.24) необходимо. Это же условие

является достаточным, так как равенство (3.27) влечет за собой неравенство (3.4), а оно в свою очередь достаточно для существования кодовых слов с указанными длинами. Ч. Т. Д.

Вывод верхней границы. Правая часть равенства (3.25), вообще говоря, не есть целое число. Но приведенная выше лемма подсказывает возможность выбрать число символов в кодовом слове, соответствующем сообщению равным наименьшему целому числу, большему, чем правая часть равенства (3.25). Рассмотрим поэтому множество целых , определяемых из соотношения

Эти целые числа удовлетворяют неравенству (3.4), так как оно справедливо для чисел (не обязательно целых), определяемых равенством (3.25). Следовательно, множество кодовых слов, соответствующее множеству целых , может быть фактически построено. Среднее число символов для такого множества кодовых слов должно удовлетворять неравенству, полученному усреднением соотношения (3.29) по ансамблю сообщений, что и дает неравенство (3.18). Ч. Т. Д.

Теорема, сформулированная в начале этого раздела, дает непосредственную практическую интерпретацию энтропии ансамбля сообщений. В случае двоичного алфавита она устанавливает, что среднее число двоичных единиц, требуемых для представления сообщения из данного ансамбля не меньше энтропии ансамбля и может превосходить ее не более чем на одну единицу. Так что, если то оценивает (с малой относительной ошибкой) среднее число двоичных символов, требуемых для кодирования сообщений из ансамбля Кроме того, из неравенства (3.29) видно, что когда целью является минимизация то собственная информация сообщения является точной оценкой (в том же смысле малости относительной ошибки) числа символов в двоичном кодовом слове, соответствующем Эти результаты подтверждают приемлемость нашего определения собственной информации.