Решение: Минимальная длина кодов
По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Какое наименьшее количество двоичных знаков потребуется для кодирования двух оставшихся букв? В ответе запишите суммарную длину кодовых слов для букв: Ж, З.
| Буква | Кодовое слово |
|---|---|
| А | 000 |
| Б | 001 |
| В | 0101 |
| Г | 0100 |
| Д | 011 |
| Е | 101 |
Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Решение по шагам
3 шагаРассмотрим свободные ветви двоичного дерева. Кодовое слово 101 уже занято, поэтому в ветви 10 можно использовать слово 100 длины 3.
Ветвь 11 свободна полностью, поэтому для второй буквы можно взять кодовое слово 11 длины 2. Эти слова не являются началами друг друга и не нарушают условие Фано.
$$l_1 + l_2 = 3 + 2 = 5$$Одно кодовое слово длины 1 использовать нельзя: слово 1 было бы началом уже имеющегося слова 101. Поэтому меньшую суммарную длину получить невозможно.
Где здесь ошибаются
Используют кодовое слово 1, забывая, что оно является началом слова 101.
Выбирают два слова, одно из которых является началом другого.
Суммируют не длины кодовых слов, а их числовые значения.