Теория информации
Конспект лекций
назад | содержание | вперед

3. ПОБУКВЕННОЕ КОДИРОВАНИЕ

 

3.4 Неравенство МакМиллана

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

Теорема (МакМиллан). Для того чтобы существовал побуквенный двоичный разделимый код с длинами кодовых слов , необходимо и достаточно, чтобы

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

Докажем необходимость утверждения. Рассмотрим тождество


Положим . Тогда тождество можно переписать следующим образом


где , – число всевозможных представлений числа j в виде суммы . Сопоставим каждому представлению числа j в виде суммы последовательность нулей и единиц длины j по следующему правилу



где – элементарный код длины s. Тогда различным представлениям числа j будут соответствовать различные кодовые слова, поскольку код является разделимым. Таким образом,  и . Используя предельный переход получим  при . Теорема доказана.

 

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



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



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

 

наверх

 


назад | содержание | вперед