ЕГЭ · ЗАДАНИЕ 4
Кодирование и условие Фано · №28925
Передаются буквы А, Н, Р, С, Т, Я. Известны С = 00, Р = 010, Н = 11. Для А, Т, Я коды неизвестны. Найдите минимальную длину кодирования слова ТАРАНТАС.
| Символ | Кодовое слово |
|---|---|
| С | 00 |
| Р | 010 |
| Н | 11 |
| А | ? |
| Т | ? |
| Я | ? |
Кодируемое слово: ТАРАНТАС
Напоминание: ни одно кодовое слово не должно быть началом другого кодового слова.
Источник задания
Сначала попробуй решить самостоятельно, затем открой разбор. Для автоматической проверки ответа включи JavaScript.
Показать решение по шагам
Разбор решения
Ответ: 21
1. Запишем частоты
ТАРАНТАС: А — 3 раза, Т — 2, Р, Н и С — по одному. Я не встречается, но ей нужен отдельный допустимый код.
2. Используем свободные ветви
При С = 00, Р = 010, Н = 11 свободны 10 и 011. Короткую ветвь 10 отдаём А; ветвь 011 делим между Т и Я.
| Буква | Код | Частота | Битов |
|---|---|---|---|
| А | 10 | 3 | 6 |
| Т | 0110 | 2 | 8 |
| Р | 010 | 1 | 3 |
| Н | 11 | 1 | 2 |
| С | 00 | 1 | 2 |
| Я | 0111 | 0 | 0 |
3. Сравним два полезных варианта
Если оставить А = 10, для Т и Я нужны коды длины 4: переменная часть равна 3 × 2 + 2 × 4 = 14. Если разделить ветвь 10, можно дать А и Т трёхбитовые коды, а Я — 011; тогда получим 3 × 3 + 2 × 3 = 15. Более глубокое разделение только увеличивает длины. Код 10 для Т вместо А тоже невыгоден: 2 × 2 + 3 × 4 = 16.
Прибавляем фиксированные Р, Н, С: 14 + 3 + 2 + 2 = 21 бит.
Частая ошибка: одновременно выбрать 011 и 0110 — первый код будет началом второго.
Самопроверка. Закройте разбор и повторите расчёт без подсказки.