Решение: Кодирование слова по Фано
По каналу связи передаются сообщения, содержащие только буквы из набора: Г, Д, К, С, О, Р. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: С – 0, К – 1011. Для четырёх оставшихся букв Г, Д, О и Р кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КОСОГОР, если известно, что оно закодировано минимально возможным количеством двоичных знаков?
Решение по шагам
5 шаговКод С = 0 означает, что кодовые слова остальных букв должны начинаться с 1. Код К = 1011 фиксирует одну из ветвей дерева.
Чтобы минимизировать длину слова КОСОГОР, код буквы О, встречающейся три раза, нужно сделать как можно короче. Выбираем О = 11.
Оставшиеся буквы можно закодировать, например, так: Д = 1000, Г = 1001, Р = 1010. Эти коды вместе с С = 0, О = 11 и К = 1011 удовлетворяют условию Фано.
В слове КОСОГОР используются коды К один раз, О три раза, С один раз, Г один раз и Р один раз.
Общая длина кодирования равна $4 + 3 \cdot 2 + 1 + 4 + 4 = 19$.
Где здесь ошибаются
Забывают, что буква О встречается в слове три раза.
Используют кодовое слово, являющееся началом другого кодового слова.
Считают количество различных букв вместо количества букв в слове.