Условие Фано для кодов
По каналу связи передаются шифрованные сообщения, содержащие только шесть букв: А, Б, В, Г, Д, Е. Для передачи используется неравномерный двоичный код. Для букв А, Б, В и Г используются кодовые слова $1$, $00$, $0100$, $0111$ соответственно.
Укажите минимальную сумму длин кодовых слов для букв Д и Е, при которых код будет удовлетворять условию Фано.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Условие как в банке ФИПИ — открыть и сверить
| По каналу связи передаются шифрованные сообщения, содержащие только шесть букв: А, Б, В, Г, Д, Е. Для передачи используется неравномерный двоичный код. Для букв А, Б, В и Г используются кодовые слова 1, 00, 0100, 0111 соответственно. Укажите минимальную сумму длин кодовых слов для букв Д и Е, при которых код будет удовлетворять условию Фано. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений. | |||
| |
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Рассмотрите двоичное дерево кодов и найдите свободные ветви, которые не будут иметь общих начал с кодовыми словами $1$, $00$, $0100$ и $0111$.
2Наводящая — какие числа считатьуровень 2 из 3
Так как кодовое слово $1$ уже заняло всю ветвь, новые слова должны начинаться с $0$. Ветвь $00$ занята, а после слов $0100$ и $0111$ свободные листья появляются только на следующем уровне.
3Прямая — фактически решениеуровень 3 из 3
Можно выбрать кодовые слова $0101$ и $0110$. Их длины равны $4$ и $4$, поэтому минимальная сумма равна $4+4=8$.