Кодовое дерево для множества кодовых слов.

Наглядное графическое изображение множества кодовых слов можно получить, установив соответствие между сообщениями и концевыми узлами двоичного дерева. Пример двоичного дерева изображен на рис. 5.1. Две ветви, идущие от корня дерева к узлам первого порядка, соответствуют выбору между «0» и «1» в качестве первого символа кодового слова: левая ветвь соответствует «0», а правая — «1». Две ветви, идущие из узлов первого порядка, соответствуют второму символу кодовых слов, левая означает «0», а правая — «1» и т. д. Ясно, что последовательность символов каждого кодового слова определяет необходимые правила продвижения от корня дерева до концевого узла, соответствующего рассматриваемому сообщению.

Формально кодовые слова могут быть приписаны также промежуточным узлам. Например, промежуточному узлу второго порядка на рис. 5.1 можно приписать кодовое слово 11, т. е. первые два символа кодовых слов, соответствующих концевым узлам, порождаемых этим узлом. Однако кодовые слова, соответствующие промежуточным узлам, не могут быть использованы для представления сообщений, так как в этом случае нарушается требование префиксности кода.

Рис. 5.1. Пример двоичного кодового дерева

Рис. 5.2. Кодовые деревья для кодов 2 (а) и 3 (б)

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

На рис. 5.2 изображены кодовые деревья, соответствующие кодам 2 и 3 (см. табл. 5.1).

Вернемся к рассмотренному ранее примеру 5.1. Пусть вероятность появления в сообщении буквы равна 0,2; буквы а, — 0,5. Тогда среднее число двоичных символов, приходящихся на одну букву для кода 3 составляет , а для кода , т. е. код 2 в среднем экономичнее кода 3.

Рассмотрим еще один код — код 4, который букве ставит в соответствие . Среднее число двоичных символов, приходящихся на одну букву этого кода: т. е. код 4 экономичнее и кода 3, и кода 2. Спрашивается, можно ли предложить код, который будет экономичнее кода 4? Как построить самый экономичный код для данного сообщения? Ответы на эти и многие другие вопросы дает основная теорема кодирования, сформулированная и доказанная впервые К- Шенноном.

Пусть буквы , входного алфавита А порождаются независимо с вероятностью некоторым источником сообщений. Количество информации, приходящееся на сообщение равно —

Среднее количество информации в битах на одно сообщение (букву) обозначается и называется энтропией источника сообщений (см. гл. 1):

Энтропию можно рассматривать как меру «неопределенности» сообщения до того, как оно было принято.

В приведенной ниже основной теореме кодирования устанавливается связь между и средним числом I символов «0» и «1» в кодовом слове.

Теорема 5.1. Для любого однозначно декодируемого кода всегда выполняется неравенство и существует однозначно декодируемый код, для которого выполняется неравенство Доказательство этой теоремы можно найти в [1.1].

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

Обозначим среднее число «0» и «1», приходящихся на один блок из букв, взятых из алфавита А, через Тогда среднее число символов, приходящихся на одну букву алфавита, определяется формулой

Теорема 5.2. При любом сколь угодно малом положительном можно найти натуральное число N, такое, что среднее число символов на одно сообщение 7 при удовлетворяет неравенству

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

Доказательство. Эта теорема вытекает из теоремы 5.1. Подставляя в нее вместо 7, получаем

Разделив (5.6) на и учитывая (5.2) и (5.3), получим

Из неравенства (5.7) следует неравенство (5.4), если положить

В то же время неравенство (5.5) несовместимо с неравенством (5.7). Теорема доказана.

Из теоремы 5.2 следует, что, используя кодирование блоков, можно получить среднее число символов на сообщение (букву), сколь угодно мало отличающееся от энтропии, но при этом увеличивается сложность кодирования.