По каналу связи передаются сообщения, содержащие только шесть букв: Я, Н, В, А, Р, Ь. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Н – 00, В – 01, Р – 10, Ь – 111. Укажите минимально возможную длину закодированной последовательности для слова ВАРВАР.
Мы знаем, что алфавит состоит из 6 букв: Я, Н, В, А, Р, Ь.
Некоторые кодовые слова уже заданы (и их менять нельзя):
Н – 00 (длина = 2),
В – 01 (длина = 2),
Р – 10 (длина = 2),
Ь – 111 (длина = 3).
Нам осталось назначить кодовые слова для двух букв – А и Я – так, чтобы весь набор удовлетворял условию Фано (то есть никакое кодовое слово не являлось префиксом другого).
Шаг 1. Определим «свободное пространство» с точки зрения неравенства Крафта. Равенство (при оптимальной кодировке) должно быть выполнено для всех 6 кодовых слов: 2^(–l(Н)) + 2^(–l(В)) + 2^(–l(Р)) + 2^(–l(Ь)) + 2...