![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Рассмотрим схему алфавитного кодирования и различные слова, составленные из элементарных кодов. Схема
называется разделимой, если
,
то есть любое слово, составленное из элементарных кодов, единственным образом разлагается на элементарные коды. Алфавитное кодирование с разделимой схемой допускает декодирование.
Схема называется префиксной, если элементарный код одной буквы не является префиксом элементарного кода другой буквы:
.
Теорема 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.
Таким образом, неравенство Макмиллана для азбуки Морзе не выполнено, и эта схема не является разделимой. На самом деле в азбуке Морзе имеются дополнительные элементы – паузы между буквами (и словами), которые позволяют декодировать сообщения. Эти дополнительные элементы определены неформально, поэтому прием и передача сообщений с помощью азбуки Морзе, особенно с высокой скоростью, является некоторым искусством, а не простой технической процедурой.
Дата публикования: 2014-11-03; Прочитано: 1194 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!