Разделимые схемы

Рассмотрим схему алфавитного кодирования и различные слова, составленные из элементарных кодов. Схема называется разделимой, если

,

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

Схема называется префиксной, если элементарный код одной буквы не является префиксом элементарного кода другой буквы:

.

Теорема 9.1. Префиксная схема является разделимой.

Доказательство. От противного. Пусть кодирование со схемой не является разделимым. Тогда существует такое слово , что

.

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

Замечание. Свойство быть префиксной является достаточным, но не является необходимым для разделимости схемы.

Пример 9.2. Разделимая, но не префиксная схема: , , .

Чтобы схема алфавитного кодирования была разделимой, необходимо, чтобы длины элементарных кодов удовлетворяли определенному соотношению, известному как неравенство Макмиллана.

Теорема 9.2. Если схема разделима, то

, где .

Доказательство. Обозначим: . Рассмотрим n -ю степень левой части неравенства . Раскрывая скобки, имеем сумму , где – различные наборы номеров элементарных кодов. Обозначим через количество входящих в эту сумму слагаемых вида , где . Для некоторых может быть =0. Приводя подобные, имеем сумму . Каждому слагаемому вида можно однозначно сопоставить код (слово в алфавите B) вида . Это слово состоит из n элементарных кодов и имеет длину t.

Таким, образом, – это число некоторых слов вида , таких что . В силу разделимости схемы , в противном случае заведомо существовали бы два одинаковых слова , допускающих различное разложение. Имеем

.

Следовательно, , и значит, , откуда

.

Неравенство Макмиллана является не только необходимым, но и достаточным условием разделимости схемы алфавитного кодирования.

Пример 9.3. Азбука Морзе – это схема алфавитного кодирования

,

где по историческим и техническим причинам 0 называется точкой, а 1 называется тире. Имеем

1/4+1/16+1/16+1/8+1/2+1/16+1/8+1/16+1/4+1/16+1/8+1/16+1/4+1/4+

+1/8+1/16+1/16+1/8+1/8+1/2+1/8+1/16+1/8+1/16+1/16+1\16=

=2/2+4/4+7/8+12/16=3+5/8 > 1.

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