Question

ПОЖАААЛУУУЙСТАААА, ОБЪЯСНИТЕ ДЛЯ ТУПЫЫХХХХ
По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, М, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 010, Б — 00, Г — 101. Какое наименьшее количество двоичных знаков потребуется для кодирования слова МАГИЯ?

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Answer 1

Ответ:

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 знаков.