Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



Контакти
 


Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция






Роздільні схеми

Розглянемо|розгледимо| схему алфавітного кодування і різні слова, складені з|із| елементарних кодів. Схема називається роздільною, якщо

,

тобто|цебто| будь-яке слово, складене з|із| елементарних кодів, єдиним чином розкладається на елементарні коди. Алфавітне кодування з|із| роздільною схемою допускає декодування.

Схема називається префіксною, якщо елементарний код однієї букви|літери| не є|з'являється,являється| префіксом елементарного коду іншої букви|літери|:

.

Теорема 7.1. Префіксна схема є|з'являється,являється| роздільною.

Доказ. Від осоружного|противного,супротивного|. Хай|нехай| кодування з|із| схемою не є|з'являється,являється| роздільним. Тоді існує таке слово , що

.

Оскільки , то це означає |значить|, але|та| це суперечить|перечить| тому, що схема префіксна.

Зауваження. Властивість бути префіксною є|з'являється,являється| достатньою, але|та| не є|з'являється,являється| необхідним для роздільності схеми.

Приклад|зразок| 7.2. Роздільна, але|та| не префіксна схема:,, .

Щоб схема алфавітного кодування була роздільною, необхідно, щоб довжини елементарних кодів задовольняли певному співвідношенню, відомому як нерівність Макміллана.

Теорема 7.2. Якщо схема роздільна|, то

, де .

Доказ. Позначимо: . Розглянемо|розгледимо| n-юступінь|міру| лівої частини|частки| нерівності . Розкриваючи дужки, маємо суму , де – різні набори номерів елементарних кодів. Позначимо через кількість тих, що входять в цю суму доданків вигляду |виду|, де . Для деяких може бути =0. Приводячи|призводячи,наводячи| подібні, маємо суму . Кожному доданку вигляду|виду| можна однозначно зіставити код (слово в алфавіті B) вигляду|виду| . Це слово складається з n елементарних кодів і має довжину t.

Таким чином|зображенням|, – це число деяких слів вигляду |виду|, таких що . Через роздільність схеми , інакше свідомо існували б два однакові слова , що допускають різне розкладання. Маємо

.

Отже, , і тому:|значить| , звідки

.

Нерівність Макміллана є|з'являється,являється| не тільки|не лише| необхідним, але і достатньою умовою роздільності схеми алфавітного кодування.

Приклад|зразок| 7.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.

Таким чином, нерівність Макміллана для азбуки Морзе не виконана, і ця схема не є|з'являється,являється| роздільною. Насправді в азбуці Морзе є|наявний| додаткові елементи – паузи між буквами|літерами| (і словами), які дозволяють декодувати повідомлення|сполучення|. Ці додаткові елементи визначені неформально, тому прийом і передача повідомлень|сполучень| за допомогою азбуки Морзе, особливо з|із| високою швидкістю, є|з'являється,являється| деяким мистецтвом, а не простою технічною процедурою.

 


Читайте також:

  1. VІ. Структурно-логічні схеми
  2. Алгоритми та блок-схеми
  3. Блоки схеми алгоритму
  4. Вибір схеми підключення абонентів залежно від режимів тиску.
  5. Вибір типу обмотки і складання схеми.
  6. Вибір типу обмотки і складання схеми.
  7. Види і схеми відбору одиниць
  8. Види недержавного пенсійного забезпечення та схеми фінансування пенсійних виплат.
  9. Визначення сумарної маси еквівалентної схеми V- подібного КШМ.
  10. ГЕНПЛАНИ ОЧИСНИХ СПОРУДЖЕНЬ І СХЕМИ ВИСОТНОГО РОЗТАШУВАННЯ ОЧИСНИХ СПОРУДЖЕНЬ .
  11. Гібридні системи, індексні схеми
  12. Головні завдання Регіональної схеми розселення на Україні.




Переглядів: 2780

<== попередня сторінка | наступна сторінка ==>
Алфавітне кодування | Перешкодостійке кодування

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

 

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.006 сек.