НОУ ІНТУЇТ | лекція | Морзе, Брайль, Фано

  1. Дивитися лекцію на: ІНТУЇТ | youtube.com

Анотація: Подання тексту у вигляді різних кодів.

Дивитися лекцію на: ІНТУЇТ | youtube.com

Якщо проблеми з відео, натисніть вище посилання youtube

Якщо проблеми з відео, натисніть вище посилання youtube

Алфавіт, що складається з двох символів, використовується не тільки в комп'ютерах. У різних варіаціях він використовується людством вже сотні років. Розглянемо два відомих варіанти застосування такого алфавіту - код Морзе і код Брайля. Код Морзе використовується при передачі радіосигналів. І сьогодні все морські судна використовують рації, передають повідомлення кодом Морзе. При передачі використовуються сигнали різної тривалості. Короткий сигнал прийнято називати точкою, довший сигнал - тире.

У комп'ютерах, як ми бачили, символи алфавіту кодуються словами однакової довжини. У кодуванні Unicode вихідний текст, що складається з n символів, буде представлений двійковим словом довжини 16n. Такий спосіб представлення інформації зручний при роботі з комп'ютерами, пам'ять яких величезна за людськими мірками (10000 книг можна зберігати в 8 Гб), швидкість обробки інформації перевершує межі розуміння. З цієї причини при роботі з комп'ютером зручність роботи з довільними текстами набагато важливіше надмірності коду і не самого економічного способу зберігання інформації.

Зовсім інша справа, коли кодуванням і декодуванням повинна займатися людина. В цьому випадку слід вибирати економічний спосіб кодування, намагаючись зменшити довжину закодованого тексту. Природним рішенням цієї проблеми є:

  • Використання при кодуванні слів різної довжини;
  • Кодування часто використовуваних символів алфавіту короткими словами, рідко використовуваних - довгими словами.

Ці принципи використовуються в коді Морзе. Наведу кодування одного символу латиниці і кирилиці в коді Морзе:

В англійському символи E і T - найбільш часто використовувані символи, тому вони кодуються словами довжини 1. Для російських текстів використовується стандартне відповідність символів кирилиці і латиниці.

Завдання: Закодуйте слово SOS кодом Морзе.

Рішення:

Завдання: Закодуйте слово "мама" кодом Морзе

Рішення:

При кодуванні символів словами різної довжини виникає проблема декодування, оскільки неясно, де кінчається код одного символу і починається код наступного символу. В азбуці Морзе ця проблема вирішується таким чином. Крім двох символів коду - точки і тире вводиться третій символ - роздільник символів. Роздільник починає код кожного символу. Так що фактично алфавіт Морзе складається з трьох символів - трьох сигналів різної тривалості - точки тире і паузи. На листі пауза позначається прогалиною.

У коді Морзе використовуються слова довжини від 1 до 5 (не враховуючи роздільник, супроводжуючого символ). Тому код дозволяє кодувати алфавіт з 63-х різних символів. Для кодування цього алфавіту словами фіксованої довжини мінімальна довжина слова дорівнює 6. Наскільки ефективний код Морзе? Наскільки скорочується довжина переданого повідомлення? Однозначної відповіді немає - все залежить від самого переданого повідомлення. У кодуванні, де всі символи кодуються словами довжини 6, слово довжини n, матиме довжину 6n, так слово "мама" в результаті кодування матиме довжину 24. Це ж слово "мама" в коді Морзе матиме довжину -12, по два символу для букв "м" і "а" плюс роздільники символів. Виграш становить 50%. - довжина слова зменшилася в два рази. При передачі чисел такого ефекту не буде. У коді Морзе кожна цифра кодується словом довжини 5. Якщо додати роздільник, то на цифру потрібно ті ж 6 знаків, так що довжина числа в коді Морзе збігається з довжиною числа, коли алфавіт кодується словами довжини 6.

Звичайно, текст в коді Морзе істотно коротше того ж тексту в кодуванні Unicode. Слово "мама" в кодуванні Unicode матиме довжину 64, а в коді Морзе - 12.

Чи можна обійтися без роздільників при кодуванні символів словами різної довжини?

Розглянемо спочатку приклад неоднозначного кодування. Нехай у нас є алфавіт з 3-х символів - А, М, П. Введемо наступну кодування: А - 0, М - 1, П - 10. Розглянемо закодований текст: 1010. Цьому тексту при декодуванні відповідають два слова - МАМА і ПП . Як бачите, введена кодування не забезпечує однозначне декодування.

Чи можна ввести обмеження на спосіб кодування, що гарантують однозначне декодування? Відповідь позитивний.

Декодування однозначно, якщо код задовольняє умові Фано.

Сформулюємо цю умову. Код називається префіксним, якщо існує пара символів, така, що код одного символу є префіксом коду іншого символу.

У нашому прикладі код є префіксним, оскільки для символів М і П код символу М є префіксом (початком) коду символу П.

Якщо код не є префіксним, то умова Фано виконується ,. Умова Фано є достатньою умовою для однозначного декодування. Воно не є необхідною умовою.

Розглянемо кілька завдань, вирішення яких передбачає використання умови Фано.

Завдання 13:

Для трьохбуквені алфавіту {А, М, П} використовується кодування А - 01, М - 10, П - 001. Який код мінімальної довжини слід задати для кодування літери Т, що додається в алфавіт?

Відповідь: Т - 11.

Рішення: Використовувана кодування задовольняє умові Фано, - жоден код не є префіксом іншого коду, що гарантує однозначність декодування. Для нового символу, який додається в алфавіт, можна використовувати код, що складається з одного символу, оскільки буде порушено умова Фано. Для коду, що складається з двох символів, можливий тільки один варіант, що задовольняє умові Фано, - Т - 11.

Завдання 14:

Для чотирибуквене алфавіту {А, М, П, Т} використовується кодування А - 01, М - 10, П - 001, Т - 11. Чи можна зменшити довжину коду одного з символів, зберігаючи однозначність декодування?

Відповідь: Можна. П - 00.

Рішення: Використовувана кодування задовольняє умові Фано, - жоден код не є префіксом іншого коду, що гарантує однозначність декодування. Не порушуючи умови Фано, для кодування літери П можна використовувати код 00. Зауважте, в цьому випадку все символи кодуються словами постійної довжини. Для такої кодування умова Фано виконується автоматично, оскільки всі слова різні і мають однакову довжину, так що жодна з них не може бути префіксом іншого слова. Можна, якщо на код накласти додаткові обмеження, зване умовою Фано. Нагадаємо, префіксом слова називається початковий відрізок слова. Код називається префіксним, якщо існує така пара символів алфавіту s1 і s2, що код s1 є префіксом коду s2. Умова Фано каже, що для однозначного декодування тексту досить, щоб код не був префіксним, тобто жоден код символу ні префіксом коду іншого символу.

завдання:

Розглянемо алфавіт, що складається з 6-и символів {А, Б, В, Г, Д, Е}. Розглянемо код, що задовольняє умові Фано: А - 00, Б - 10, В - 010, Г - 011, Д -110, Е - 111. Закодуйте текст БАГГАВ і запишіть його в шістнадцятковій системі:

Рішення: В двійковій системі текст виглядає так: 100001101100010, в шістнадцятковій системі: 4362

завдання:

Дан закодований текст, записаний цифрами шістнадцятковій системи АВ12:

Декодуючими текст, використовуючи кодування, запропоновану в попередньому завданні

АВ12 = 1010101100010010 = БББДАБВ

завдання:

Розглянемо алфавіт, що складається з 4-х символів {А, Б, В, Г}. Розглянемо код, що задовольняє умові Фано: А - 00, Б - 10, В - 010, Г - 011. Чи можна, зберігши умова Фано, поліпшити кодування, зменшивши довжину слова деяких символів.

Рішення: Довжину коду символу А зменшити не можна, інакше код стане префіксним. Довжину коду символу Б можна зменшити, поклавши Б - 1. Після цього можна зменшити довжину В і Г. Рішення не єдино. Можна залишити код Б без зміни, і зменшити код для Г - 11

Код Брайля допомагає читати тексти людям, позбавленим зору і зі слабким зором. Алфавіт також складається з двох символів і роздільник, що дозволяє відокремлювати символи. Символи алфавіту є опуклі і неопуклі точки, які розпізнаються на дотик. У коді Брайля мінімізація довжини коду не має особливого значення. Більш важливо зручність запису і розпізнавання тексту. Тому використовується кодування символів алфавіту словами довжини 6. Алфавіт кодованого тексту, отже, містить 64 символи. Кожен символ в коді Брайля записується з 6 точок, розташованих у два стовпці по три точки в стовпці. Тому для запису символу досить вказати положення тільки опуклих точок, - є опуклість - символ 1, немає опуклості - символ 0. Ось як виглядає текст "мама", записаний кодом Брайля:

6. Наскільки ефективний код Морзе?
Наскільки скорочується довжина переданого повідомлення?
Чи можна ввести обмеження на спосіб кодування, що гарантують однозначне декодування?
001. Який код мінімальної довжини слід задати для кодування літери Т, що додається в алфавіт?
11. Чи можна зменшити довжину коду одного з символів, зберігаючи однозначність декодування?

Уважаемые партнеры, если Вас заинтересовала наша продукция, мы готовы с Вами сотрудничать. Вам необходимо заполнить эту форму и отправить нам. Наши менеджеры в оперативном режиме обработают Вашу заявку, свяжутся с Вами и ответят на все интересующее Вас вопросы.

Или позвоните нам по телефонам: (048) 823-25-64

Организация (обязательно) *

Адрес доставки

Объем

Как с вами связаться:

Имя

Телефон (обязательно) *

Мобильный телефон

Ваш E-Mail

Дополнительная информация: