Решение: Кодирование слова по Фано
По каналу связи передаются сообщения, содержащие только буквы из набора: А, З, К, Л, Ч. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: Ч – 1, Л – 011. Для трёх оставшихся букв А, З и К кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КАЧАЛКА, если известно, что оно закодировано минимально возможным количеством двоичных знаков?
Решение по шагам
4 шагаКодовое слово Ч равно 1, поэтому ни одно другое кодовое слово не может начинаться с 1. Кодовое слово Л равно 011, поэтому в ветви, начинающейся с 0, оно также занимает соответствующую часть дерева.
Чтобы закодировать три оставшиеся буквы и сохранить условие Фано, им можно назначить кодовые слова 000, 001 и 010. Все они имеют длину 3 и не являются префиксами друг друга.
В слове КАЧАЛКА буква К встречается 2 раза, буква А — 3 раза, буквы Ч и Л — по одному разу. Поэтому длина кодирования равна сумме длин кодовых слов всех букв.
Подставляем длины кодовых слов:
$$2 \cdot 3 + 3 \cdot 3 + 1 \cdot 1 + 1 \cdot 3 = 18$$Где здесь ошибаются
Неверно подсчитывают количество букв К в слове КАЧАЛКА.
Пытаются использовать кодовые слова длины 1 или 2, нарушая условие Фано.
Не учитывают, что буква З в слове КАЧАЛКА не встречается.