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