Декодирование

Содержание и основные понятия

← Вернуться к оглавлению
Alterna · глава 26 · страница 26.3
Декодирование
Пошаговое декодирование префиксных кодов.
Декодирование
— восстановление исходного сообщения из битовой строки с помощью кодового дерева.
ФГОС
ОГЭ №2,4
ЕГЭ №4
Связь.
Декодирование — обратный процесс к кодированию. Используем то же дерево, но двигаемся от корня, читая биты.
01
Алгоритм декодирования
Алгоритм
(для префиксного кода):
Начать с корня дерева.
Читать следующий бит: 0 → влево, 1 → вправо.
Если достигли лист — вывести символ, вернуться к корню.
Повторять, пока не обработаны все биты.
Для непрефиксного кода декодирование
неоднозначно
— одна битовая строка может дать разные тексты.
Пример
Код: A=0, B=10, C=110, D=111. Декодируем
01101110
:
Читаем 0 → лист A. Результат:
A
. Код:
1101110
Читаем 1 → вправо, читаем 1 → вправо, читаем 0 → лист C. Результат:
A C
. Код:
1110
Читаем 1 → вправо, читаем 1 → вправо, читаем 1 → вправо, читаем 0 → лист D. Результат:
A C D
. Код:
0
Читаем 0 → лист A. Результат:
A C D A
02
Пошаговый декодер
📡
Декодер с пошаговым выводом
Коды (A=0;B=10;C=110;D=111)
Биты
Введите коды и биты.
03
Задание ЕГЭ №4
📋
ЕГЭ №4 — Интерактивные задачи
04
Ошибки декодирования
Непрефиксный код — неоднозначность
Если код не удовлетворяет условию Фано, одна битовая строка может декодироваться по-разному.
Пример: код {0, 01}
Строка
01
:
Как 0 + 01 → A + B → «AB»
Как 01 → C → «C»
Два варианта!
Такой код нельзя декодировать однозначно.
Проверка декодируемости
Для префиксного кода декодирование всегда однозначно — алгоритм «корень → лист → корень» даёт唯一的 результат.