Решение: Минимальная длина кодов
По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны. Какое наименьшее количество двоичных знаков требуется для кодирования двух оставшихся букв? В ответе запишите суммарную длину кодовых слов для букв Ж, З.
| Буква | Кодовое слово |
|---|---|
| А | 00 |
| Б | 1000 |
| В | 010 |
| Г | 1001 |
| Д | 011 |
| Е | 111 |
Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Решение по шагам
3 шагаПроверим двузначные кодовые слова. Код 00 уже занят, 01 является началом кодов 010 и 011, 10 является началом кодов 1000 и 1001, а 11 является началом кода 111.
На следующем уровне свободными являются ветви 101 и 110. Они не являются началами известных кодов и не являются началами друг друга, поэтому их можно назначить буквам Ж и З.
Оба новых кодовых слова имеют длину 3, поэтому суммарная длина равна $3 + 3 = 6$.
Где здесь ошибаются
Используют код 01, 10 или 11, не учитывая, что он является началом уже известного кодового слова.
Пытаются назначить одной из букв код длины 2, нарушая условие Фано.