Минимальное кодирование слова
По каналу связи передаются сообщения, содержащие только буквы из набора: А, З, К, Н, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: К – 1, Н – 001. Для трёх оставшихся букв А, З и Т кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КАНТАТА, если известно, что оно закодировано минимально возможным количеством двоичных знаков?
Условие как в банке ФИПИ — открыть и сверить
| По каналу связи передаются сообщения, содержащие только буквы из набора: А, З, К, Н, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: К – 1, Н – 001. Для трёх оставшихся букв А, З и Т кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КАНТАТА, если известно, что оно закодировано минимально возможным количеством двоичных знаков? | |||
| |
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Постройте дерево кодов с уже занятыми кодовыми словами $1$ и $001$. Какие самые короткие свободные ветви можно использовать?
2Наводящая — какие числа считатьуровень 2 из 3
Из-за кодового слова $К=1$ все остальные слова должны начинаться с $0$. Код $Н=001$ запрещает использовать его как начало другого кодового слова.
3Прямая — фактически решениеуровень 3 из 3
Можно взять длины кодов для трёх неизвестных букв равными $2$, $4$ и $4$. Самое короткое слово назначьте букве А, которая встречается три раза, а длину $4$ — букве Т, встречающейся два раза.