• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

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

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

,

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

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

.

Теорема 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. Головні завдання Регіональної схеми розселення на Україні.

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