Условие Фано — расшифровка и длина сообщения

Прочитать сообщение и посчитать биты

Условие Фано мы вводили ради одного — чтобы поток нулей и единиц читался однозначно. Пора этим воспользоваться.

Два вопроса, которые задают на экзамене: расшифровать данное сообщение и посчитать, сколько бит займёт заданное слово.

Расшифровка идёт слева направо

Код: А = 0, Б = 10, В = 110, Г = 111. Он префиксный, значит развилок не будет. Копим биты, а как совпало с чьим-то кодом — буква готова, и начинаем копить заново.

Получилось слово АБВГАБАВ. Заметь: возвращаться назад не пришлось ни разу — в этом вся ценность условия Фано.

Обратная задача: сколько бит займёт слово

Тут никакой хитрости, но есть что перепутать. Берём слово, для каждой буквы смотрим длину её кода и складываем.

Слово АБВГАБАВ: А и А и А — по 1 биту (их три), Б и Б — по 2 бита, В и В — по 3 бита, Г — 3 бита. Итого 3·1 + 2·2 + 2·3 + 1·3 = 16 бит.

И вот где путаница: «суммарная длина кодовых слов» из прошлой тетради считается по алфавиту, а «длина закодированного сообщения» — по буквам сообщения. Одна буква может встретиться пять раз, и все пять раз её код войдёт в сумму.