Кодирование по условию Фано
По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны:
В — 00
Г — 10
Д — 010
Е — 110
Ж — 0110
З — 111
Какое наименьшее количество двоичных знаков потребуется для кодирования двух оставшихся букв? В ответе запишите суммарную длину кодовых слов для букв А, Б.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Условие как в банке ФИПИ — открыть и сверить
| По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны:
Какое наименьшее количество двоичных знаков потребуется для кодирования двух оставшихся букв? В ответе запишите суммарную длину кодовых слов для букв: А, Б.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. | ||||||||||||
| |
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Представьте известные кодовые слова в виде дерева: новое слово не должно иметь ни одного известного слова своим началом и само не должно быть началом другого слова.
2Наводящая — какие числа считатьуровень 2 из 3
Ветвь 0110 уже занята, поэтому свободное продолжение начинается с 0111. Чтобы получить два кодовых слова, эту ветвь нужно разделить ещё на один уровень.
3Прямая — фактически решениеуровень 3 из 3
Можно взять кодовые слова 01110 и 01111. Каждое имеет длину 5, поэтому суммарная длина равна $5 + 5 = 10$.