По каналу зв'язку передаються повідомлення, містять лише сім літер: А, Б, Р, І, М, Р, Я. Для передачі використовується двійковий код, який задовольняє умові Фано. Кодові слова для деяких букв відомі: А-010, Б-011, Р-100. Яка найменша кількість двійкових знаків знадобиться для кодування слова МАГІЯ?
Примітка. Умова Фано означає, що жодне кодове слово не є початком іншого кодового слова.
Примітка. Умова Фано означає, що жодне кодове слово не є початком іншого кодового слова.
Answers & Comments
Verified answer
Наступна буква повинна кодуватися як 11, оскільки 10 ми не можемо взяти. 100 взяти не можемо через Г, отже, наступна буква повинна бути закодована кодом 101. Наступна буква повинна кодуватися як 000, оскільки 00 взяти не можемо, інакше не залишиться кодових слів для літери, що залишилися, які задовольняють умові Фано. Отже, остання буква кодуватиметься як 001. Тоді найменша кількість двійкових знаків, які потрібні для кодування слова МАГІЯ дорівнює 2 + 3 + 3 + 3 + 3 = 14.
Відповідь: 14.
Умова Фано стверджує, що найкоротші кодові слова повинні призначатися найбільш частим символам, і жодне кодове слово не повинно бути префіксом іншого кодового слова.
Ми знаємо кодові слова для букв А, Б, і Р. З них найкоротше слово має 3 двійкових знаки. Оскільки за умовою Фано жодне кодове слово не повинно бути префіксом іншого кодового слова, то кодові слова для інших букв, які нам невідомі, також будуть мати принаймні 3 двійкових знаки.
Отже, кожна літера слова "МАГІЯ" буде кодуватися принаймні 3 двійковими знаками.
МАГІЯ має 5 літер. Тому найменша кількість двійкових знаків, яка знадобиться для кодування цього слова, буде: 5 літер * 3 двійкових знаки/літеру = 15 двійкових знаків.
Відповідь: найменша кількість двійкових знаків, яка знадобиться для кодування слова МАГІЯ, дорівнює 15.