Решение: Минимальная длина кодовых слов
По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.
Какое наименьшее количество двоичных знаков требуется для кодирования четырёх оставшихся букв? Найдите суммарную длину кодовых слов для букв А, Б, В, Г.
| Буква | Кодовое слово |
|---|---|
| Е | 10 |
| Ж | 010 |
| З | 011 |
| Д | 11 |
Решение по шагам
4 шагаПо условию Фано ни одно кодовое слово не может быть началом другого. Кодовые слова 10 и 11 занимают обе ветви после первого знака 1.
Кодовые слова 010 и 011 занимают обе ветви после префикса 01. Поэтому четыре оставшихся кодовых слова должны располагаться в поддереве с префиксом 00.
Для четырёх слов минимальной общей длины поддерево 00 делим на четыре равные ветви. Получаются слова 0000, 0001, 0010 и 0011.
Каждое из четырёх слов имеет длину 4, поэтому суммарная длина равна 4 + 4 + 4 + 4 = 16.
Где здесь ошибаются
Используют кодовые слова, начинающиеся с 010 или 011, хотя эти ветви уже заняты.
Считают длины только свободных префиксов, а не полную длину кодовых слов.
Нарушают условие Фано, выбирая одно кодовое слово началом другого.