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