|
|||||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Разделимые схемыРассмотрим схему алфавитного кодирования
То есть любое слово, составленное из элементарных кодов, единственным образом разлагается на элементарные коды. Алфавитное кодирование с разделимой схемой допускает декодирование. Если таблица кодов содержит одинаковые элементарные коды, то есть если где Префиксные схемы Схема ТЕОРЕМА Префиксная схема является разделимой. Доказательство От противного. Пусть кодирование со схемой Поскольку
ЗАМЕЧАНИЕ Свойство быть префиксной является достаточным, но не является необходимым для разделимости схемы.
Пример Разделимая, но не префиксная схема:
Неравенства Макмиллана Чтобы схема алфавитного кодирования была разделимой, необходимо, чтобы длины элементарных кодов удовлетворяли определенному соотношению, известному как неравенство Макмиллана.
ТЕОРЕМА Если схема
Доказательство Обозначим
Раскрывая скобки, имеем сумму где i1...in – различные наборы номеров элементарных кодов. Обозначим через
Каждому слагаемому вида ( Таким образом, Следовательно, Неравенство Макмиллана является не только необходимым, но и в некотором смысле достаточным условием разделимости схемы алфавитного кодирования. ТЕОРЕМА Если числа l1…ln удовлетворяет неравенству то существует разделимая схема алфавитного кодирования Доказательство Без ограничений общности можно считать, что Пусть Тогда неравенство Макмиллана можно записать так: Из этого неравенства следуют m неравенств для частичных сумм:
Рассмотрим слова длины Пример Азбука Морзе – это схема алфавитного кодирования <A H O V где по историческим и техническим причинам 0 называется точкой и обозначается знаком «.», а 1 называется тире и обозначается знаком «-». Имеем: ¼+1/16+1/16+1/8+½+1/16+1/8+1/16+¼+1/16+ 1/8+1/16+1/4+1/4+1/8+1/16+1/16+1/8+1/8+ ½+1/8+1/16+1/8+1/16+1/16+1/16 = = 2/2 + 4/4 + 7/8 + 12/16 = 3+5/8 > 1. Таким образом, неравенство Макмиллана для азбуки Морзе не выполнено, и эта схема не является разделимой. На самом деле в азбуке Морзе имеются дополнительные элементы – паузы между буквами (и словами), которые позволяют декодировать сообщения. Эти дополнительные элементы определены неформально, поэтому прием и передача сообщений с помощью азбуки Морзе, особенно с высокой скоростью, является некоторым искусством, а не простой технической процедурой.
Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.007 сек.) |