Решение: Минимальная длина кодовых слов
По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.
| Буква | Кодовое слово |
|---|---|
| В | 00 |
| Г | 1000 |
| Д | 111 |
| Е | 1001 |
| Ж | 01 |
| З | 110 |
Какое наименьшее количество двоичных знаков потребуется для кодирования двух оставшихся букв? Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова.
Решение по шагам
4 шагаПостроим двоичное дерево кодов. Кодовые слова 00 и 01 полностью занимают ветви, начинающиеся с 0.
В ветви, начинающейся с 1, слова 1000 и 1001 занимают подветвь 100, а слова 110 и 111 — подветви 11. Единственная свободная ветвь — 101.
Нельзя назначить одно из оставшихся слов 101, поскольку второе слово тогда должно быть его продолжением, а 101 стало бы началом другого кодового слова. Поэтому ветвь 101 делим на два слова одинаковой минимальной длины: 1010 и 1011.
Суммарная длина двух кодовых слов равна:
$$4+4=8$$Где здесь ошибаются
Выбирают кодовые слова 101 и 1010, нарушая условие Фано.
Считают длину только одного из двух оставшихся кодовых слов.
Пытаются использовать ветви, уже занятые известными кодовыми словами.