По каналу связи передаются сообщения, содержащие только буквы слова М А Н Г. Для передачи используется двоичный код, удовлетворяющий условию Фано. Для буквы М используется кодовое слово 00; для буквы Н используется кодовое слово 1.
Какое наименьшее количество двоичных знаков потребуется для кодирования слова МАНГА?
Примечание: условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Построим дерево Фано, из которого очевидно, что свободное место только одно – 01. Но нам нужно закодировать ещё две буквы, А и Г, поэтому пустим ветки из этого места. Теперь имеется 2 свободных позиции, нам не важно каким образом мы расставим буквы на свободные позиции, так как от этого сумма длин кодов не изменится: 2+3+1+3+3 = 12.