По каналу связи передаются сообщения, содержащие только восемь букв:
А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано.
Кодовые слова для некоторых букв известны:
А 000
Б 001
В 0101
Г 0100
Д 011
Е 101
Какое наименьшее количество двоичных знаков потребуется для кодирования двух оставшихся букв? В ответе запишите суммарную длину кодовых слов для букв: Ж, З.
Рассмотрим условие: по каналу передаются 8 букв, для 6 из которых уже заданы двоичные кодовые слова по условию Фано (то есть, никакое кодовое слово не является префиксом другого). Известны следующие кодовые слова:
А: 000
Б: 001
В: 0101
Г: 0100
Д: 011
Е: 101
Нужно назначить кодовые слова для оставшихся двух букв (Ж и З) так, чтобы удовлетворялась условие Фано и суммарная длина (т.е. общее количество двоичных знаков для этих двух букв) была минимальной.
Шаг 1. Построение бинарного дерева кодирования
Найдем, какие «ветви» дерева уже заняты. Разобьем имеющиеся коды по пер...