Коды и однозначное декодирование
Равномерный код отводит каждому символу одинаковое число разрядов.
В этом занятии
- Самостоятельно решить задачу по теме «Коды и однозначное декодирование» и объяснить проверку результата.
- Придумай префиксный код четырёх значков. Закодируй и декодируй сообщение, затем найди ошибку в испорченном потоке.
Пригодится: informatics10-data-knowledge
Разберёмся перед практикой+
Коды и однозначное декодирование
Равномерный код отводит каждому символу одинаковое число разрядов. При k двоичных разрядах доступно 2^k слов. Неравномерный код может использовать короткие слова для частых символов, но требует правила однозначного декодирования.
Прямое условие Фано: ни одно кодовое слово не является началом другого. Оно достаточно для однозначного чтения слева направо. Нарушение этого условия не всегда доказывает неоднозначность всего кода: достаточное условие нельзя выдавать за необходимое.
А=0, Б=10, В=11: поток 01011 читается как АБВ. Код А=0, Б=01 не удовлетворяет прямому условию Фано.
- Проверь, не начинается ли одно слово другим.
- Читай поток до завершённого слова.
- Повтори с оставшимся хвостом.
Открываем цифровую мастерскую…
Попробуй самостоятельно
Запиши рассуждения в черновик или сделай построение на бумаге. Эти задания для самостоятельной работы: автоматической проверки и XP за них пока нет.
- Придумай префиксный код четырёх значков. Закодируй и декодируй сообщение, затем найди ошибку в испорченном потоке.
- Сначала предположи результат, затем проверь и объясни, что изменилось.
Источники и дальнейшее чтение
Материал изложен своими словами. Здесь можно проверить научные основания и подробнее изучить тему; часть источников — на английском.
Читай и разбирай пример в своём темпе. К практике можно перейти, когда будешь готов.