Минимальное кодирование слова
По каналу связи передаются сообщения, содержащие только буквы из набора: Б, К, Л, О, Н. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Б — 1001, К — 11. Для трёх оставшихся букв Л, Н и О кодовые слова неизвестны. Какое количество двоичных знаков требуется для кодирования слова КОЛОКОЛ, если известно, что оно закодировано минимально возможным количеством двоичных знаков?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Условие как в банке ФИПИ — открыть и сверить
| По каналу связи передаются сообщения, содержащие только буквы из набора: Б, К, Л, О, Н. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Б 1001, К 11. Для трёх оставшихся букв Л, Н и О кодовые слова неизвестны. Какое количество двоичных знаков требуется для кодирования слова КОЛОКОЛ, если известно, что оно закодировано минимально возможным количеством двоичных знаков? Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. | |||
| |
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Какие буквы встречаются в слове КОЛОКОЛ и сколько раз каждая из них встречается?
2Наводящая — какие числа считатьуровень 2 из 3
Нужно подобрать кодовые слова, не нарушающие условие Фано, и более короткие слова назначить буквам, которые встречаются чаще.
3Прямая — фактически решениеуровень 3 из 3
Можно взять коды О = 0, Л = 101, Н = 1000. Тогда длина кодирования равна $3 \cdot 1 + 2 \cdot 3 + 2 \cdot 2 = 13$.