ПОЖАААЛУУУЙСТАААА, ОБЪЯСНИТЕ ДЛЯ ТУПЫЫХХХХ
По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, М, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 010, Б — 00, Г — 101. Какое наименьшее количество двоичных знаков потребуется для кодирования слова МАГИЯ?
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, М, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 010, Б — 00, Г — 101. Какое наименьшее количество двоичных знаков потребуется для кодирования слова МАГИЯ?
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
More Questions From This User See All
Answers & Comments
Verified answer
Ответ:
15
Объяснение:
Коды с условием Фано удобно изображать в виде дерева, в котором левый лист получается из родителя путем дописывания 0, а правый - 1 (см. рисунок). Условие Фано означает, что если что-то является кодовым словом, то это лист (из него не могут идти стрелочки к другим элементам)
Кодовые слова отмечены зелёным цветом (А = 010, Б = 00, Г = 101). Нам нужно распределить ещё 4 кода так, чтобы 3 из них (для М, И и Я) были по возможности короче.
Если одним из кодовых слов будет 11 (для определенности, для буквы М), то останется только два кода из 3 символов (011 и 100) на 3 оставшиеся буквы И, Я и Р. Поэтому как минимум 2 кодовых слова придется делать 4-буквенными, например, И = 011, Я = 1000, Р = 1001. МАГИЯ кодируется как 11 010 101 011 1000 - 15 знаков.
Если 11 - не кодовое слово, то всего кодовые слова можно выбрать из 3 символов (например, М = 011, И = 100, Я = 110, Р = 111). МАГИЯ кодируется как 011 010 101 100 110 - 15 знаков.