ЕГЭ · ЗАДАНИЕ 4
Кодирование и условие Фано · №31142
Передаются буквы Д, И, К, О, Р, Н. Известны Н = 00, К = 01. Для Д, И, О, Р коды неизвестны. Найдите минимальную длину кодирования слова КОРИДОР.
| Символ | Кодовое слово |
|---|---|
| Н | 00 |
| К | 01 |
| Д | ? |
| И | ? |
| О | ? |
| Р | ? |
Кодируемое слово: КОРИДОР
Напоминание: ни одно кодовое слово не должно быть началом другого кодового слова.
Источник задания
Сначала попробуй решить самостоятельно, затем открой разбор. Для автоматической проверки ответа включи JavaScript.
Показать решение по шагам
Разбор решения
Ответ: 20
1. Выделим свободную часть дерева
Н = 00, К = 01. Любой новый код с началом 0 нарушит условие Фано. Размещаем Д, И, О и Р под вершиной 1.
2. Закодируем слово КОРИДОР
| Буква | Код | Частота | Битов |
|---|---|---|---|
| К | 01 | 1 | 2 |
| О | 100 | 2 | 6 |
| Р | 101 | 2 | 6 |
| И | 110 | 1 | 3 |
| Д | 111 | 1 | 3 |
| Н | 00 | 0 | 0 |
3. Проверим, можно ли сократить
Четырём буквам нельзя выдать код 1: он занял бы всё оставшееся место. Если все четыре кода имеют длину не меньше 3, нижняя граница — 6 × 3 + 2 = 20 бит.
Если одну из частых букв поместить на глубину 2, для остальных трёх минимальные длины станут 3, 4 и 4. Лучшее распределение снова даёт 2 × 2 + 2 × 3 + 4 + 4 + 2 = 20. Значит, 20 бит — минимум.
Частая ошибка: забыть повторные О и Р. Считаем длину сообщения, а не сумму длин всех кодов алфавита.
Самопроверка. Закройте разбор и повторите расчёт без подсказки.