2. По каналу связи передаются сообщения, содержащие только семь букв: А, Б, И, К, Л, С, Ц. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Б — 00, К — 010, Л — 111. Какое наименьшее количество двоичных знаков потребуется для кодирования слова АБСИССА?

После кодовых слов Б = 00, К = 010 и Л = 111 свободны, в частности, ветви с началами 10, 011 и 110. Подберём слова для остальных букв, соблюдая условие Фано.

Можно взять С = 10, А = 110, И = 0110, Ц = 0111. Вместе с заданными словами они образуют префиксный код: ни одно кодовое слово не является началом другого.

В слове АБСИССА две буквы А, одна Б, три С и одна И. Число двоичных знаков:

\(2\cdot3+1\cdot2+3\cdot2+1\cdot4=18\).

Для проверки минимальности: чтобы закодировать четыре оставшиеся буквы, можно получить слова длин 3, 3, 3, 3 либо длины 2, 3, 4, 4. В первом случае сумма длин для букв А, С, И составляет не менее \(2\cdot3+3\cdot3+1\cdot3=18\). Во втором случае кратчайшие длины выгоднее назначить буквам С и А, а затем И: \(3\cdot2+2\cdot3+1\cdot4=16\). С учётом Б (2 знака) получается минимум 18.

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