По каналу связи передаются сообщения, содержащие только семь букв: А, Б, К, О, Т, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 101, О — 11, Я — 011. Какое наименьшее количество двоичных знаков потребуется для кодирования слова КАТОК?

Условие Фано требует, чтобы ни одно кодовое слово не было началом другого.

Коды 101, 11 и 011 уже заняты. Можно назначить буквам К, Т, Б и Р коды 00, 010, 1000 и 1001 соответственно: полученный набор удовлетворяет условию Фано. Поэтому К можно закодировать двумя знаками, а Т — тремя. В слове КАТОК буква К встречается дважды, А и Т — по одному разу, О — один раз.

Минимальная длина: 2 + 3 + 3 + 2 + 2 = 12 знаков.

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