6. По каналу связи передаются сообщения, содержащие только буквы: Б, К, Л, О, Н. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Б – 1001, К – 11. Для трёх оставшихся букв Л, Н и О кодовые слова неизвестны. Какое наименьшее количество двоичных знаков требуется для кодирования слова КОЛОКОЛ?

В слове КОЛОКОЛ буквы К, О и Л встречаются соответственно 2, 3 и 2 раза. Поскольку кодовое слово К = 11 имеет длину 2, на код К приходится 4 знака.

Можно выбрать код О = 0. Тогда код О имеет минимально возможную длину 1. В ветви, начинающейся с 1, код 11 уже занят буквой К, а код 1001 — буквой Б. Для двух оставшихся букв допустимы, например, коды Л = 101 и Н = 1000. Они не конфликтуют с уже заданными кодами и друг с другом.

Для выбранного кодирования длина передачи слова равна \(2\cdot2+3\cdot1+2\cdot3=13\) знакам.

Это минимум: код О не может быть короче 1 знака; два кода Л и Н не могут оба иметь длину 2, поскольку в ветви 1 свободен только узел 10, а его продолжение 100 содержит заданный код 1001. Поэтому при коде О = 0 меньшая из возможных сумм длин для Л и Н — 3 + 4, что даёт общий итог 4 + 3 + 2\(\cdot\)3 = 13.

Ответ: 13 двоичных знаков.