По каналу связи передаются сообщения, содержащие только семь букв: А, Б, В, Д, Е, И, Н. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А – 110, Б – 01, И – 000. Какое наименьшее количество двоичных знаков потребуется для кодирования слова ВВЕДЕНИЕ?
Примечание: условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
После построения дерева Фано можно заметить, что свободными остаются ветви 111, 10 и 001. Однако, у нас остались незакодированными 4 буквы — В, Д, Е, Н, т.е. четыре буквы. Так как буква Е встречается в слове 3 раза, то присвоим ей код длины 2. Буква В встречается в слове 2 раза — ей присвоим код длины 3. Продолжим ветвь 001 до 0010 и 0011. Тогда буквы Д и Н будут закодированы кодами длиной 4. Тогда итоговая длина всех семи кодовых слов равна: 