ЕГЭ · ЗАДАНИЕ 4
Кодирование и условие Фано · №31350
По каналу передаются только буквы Б, Е, Л, П, Н. Известны коды Б = 0001, П = 01. Для Е, Л и Н коды неизвестны. Какое минимальное число двоичных знаков нужно для кодирования слова ПЕЛЕПЕЛ?
| Символ | Кодовое слово |
|---|---|
| Б | 0001 |
| П | 01 |
| Е | ? |
| Л | ? |
| Н | ? |
Кодируемое слово: ПЕЛЕПЕЛ
Напоминание: ни одно кодовое слово не должно быть началом другого кодового слова.
Источник задания
Сначала попробуй решить самостоятельно, затем открой разбор. Для автоматической проверки ответа включи JavaScript.
Показать решение по шагам
Разбор решения
Ответ: 13
1. Посчитаем буквы в слове
В ПЕЛЕПЕЛ буква Е встречается 3 раза, П и Л — по 2. Коды Б и Н тоже должны существовать, хотя этих букв в слове нет.
2. Заполним свободные ветви
Уже заняты Б = 0001 и П = 01. Ветвь 1 свободна целиком — отдадим её Е. Для Л подходит 001, для Н остаётся 0000.
| Буква | Код | В слове | Вклад в длину |
|---|---|---|---|
| П | 01 | 2 | 2 × 2 = 4 |
| Е | 1 | 3 | 3 × 1 = 3 |
| Л | 001 | 2 | 2 × 3 = 6 |
| Б | 0001 | 0 | 0 |
| Н | 0000 | 0 | 0 |
3. Почему короче не получится
Без однобитового кода для Е или Л даже оценка снизу даёт 3 × 2 + 2 × 2 + 2 × 2 = 14 бит. Если код 1 отдать Л, Е потребуется минимум 3 бита: 2 × 1 + 3 × 3 + 2 × 2 = 15. При Е = 1 свободного двухбитового кода для Л нет: 00 начинается как Б, 01 уже занят, а 10 и 11 начинаются с кода Е. Значит, найденные 4 + 3 + 6 = 13 бит — минимум.
Частая ошибка: выбрать Е = 0 — такой код стал бы началом уже заданных кодов.
Самопроверка. Закройте разбор и повторите расчёт без подсказки.