По каналу связи передаются сообщения, содержащие только буквы слова СОТОЧКА. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: Ч – 01, О – 101. Для оставшихся букв кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КАКТАК, если известно, что оно закодировано минимально возможным количеством двоичных знаков?
Решение:
Для начала самым кратким кодовым словом мы должны сделать букву К, так как она встречается в слове КАКТАК чаще всего, следующей буквой будет А, а затем остальные. Нам надо закодировать буквы А, К, Т, Ч, С
По условию Фано, самым кратким кодовым словом для буквы К будет 00, для буквы А будет 11, для буквы Т будет 1001. Остальные буквы можно закодировать любыми последовательностями, так как они не используются в слове КАКТАК.
Итого, кратчайшее количество знаков будет 2 + 2 + 4 + 2 + 2 + 2 = 14.