Задание 7. Неравномерное кодирование и декодирование сообщений по условию Фано (Прототип ОГЭ № 2). Для сжатия текстовых сообщений алгоритм архивации использует неравномерный префиксный двоичный код (символам с высокой частотностью присваиваются более короткие коды): кодовая таблица символов: О → 0, Л → 10, К → 110, _ → 111 (знак подчеркивания обозначает пробел). 1. Проверьте, выполняется ли для данной таблицы прямое условие Фано (никакое кодовое слово не должно являться началом другого кодового слова). Возможно ли однозначное декодирование закодированного сообщения? 2. Декодируйте двоичную последовательность: 110010011001011101100100. Запишите полученное текстовое сообщение. 3. Подсчитайте длину закодированного сообщения в битах. Сколько байт потребовалось бы для хранения этого сообщения при стандартном 8-битном кодировании ASCII и сколько бит удалось сэкономить благодаря архивации?

1. Кодовые слова — 0, 10, 110 и 111. Ни одно из них не является началом другого: после 0 другие слова начинаются с 1, а слова 10, 110 и 111 не являются началами друг друга. Условие Фано выполняется, поэтому сообщение декодируется однозначно.
2. Читаем последовательность слева направо, каждый раз выделяя кодовое слово: 110 | 0 | 10 | 0 | 110 | 0 | 10 | 111 | 0 | 110 | 0 | 10 | 0. Получаем: КОЛОКОЛ ОКОЛО.
3. Длина кода: 3 + 1 + 2 + 1 + 3 + 1 + 2 + 3 + 1 + 3 + 1 + 2 + 1 = 24 бита. В сообщении 13 символов, поэтому при расчёте по 8 бит на символ ASCII потребовалось бы 13 × 8 = 104 бита, то есть 13 байт. Экономия: 104 − 24 = 80 бит.

Ответ: условие Фано выполняется; сообщение — «КОЛОКОЛ ОКОЛО»; длина кода — 24 бита; для ASCII понадобилось бы 13 байт; сэкономлено 80 бит.