Глава о двух противоположных операциях с избыточностью: помехоустойчивые коды её добавляют, чтобы заметить и исправить ошибку, сжатие — убирает, чтобы файл стал меньше.
Что нужно знать
- Бит чётности дополняет число единиц до чётного и замечает одну ошибку, но пропускает две.
- Кодовое расстояние — число позиций, в которых различаются кодовые слова. Для исправления одиночной ошибки оно должно быть не меньше 3.
- Платой за исправление ошибок служит длина сообщения: проверочные разряды увеличивают избыточность.
- Код Хаффмана даёт частым символам короткие коды. Порядок: подсчитать частоты, объединять два самых редких узла, пока не останется дерево, прочитать коды по ветвям.
- Для больших одноцветных областей эффективно кодирование длин серий: «цвет и сколько раз».
- С потерями сжимают фото, звук и видео, где часть деталей незаметна; тексты и программы — только без потерь.
- Сжатый архив повторно почти не сжимается: избыточности в нём уже нет. 900 Кбайт → 150 Кбайт — сжатие в 6 раз.
Где чаще всего ошибаются
- Думают, что бит чётности исправляет ошибку, а не только замечает.
- Назначают частым символам длинные коды.
- Сжимают с потерями текстовый документ.
- Ждут выигрыша от повторной архивации.
Проверить себя
По этой же главе есть проверочная работа из 11 заданий на 25 минут. Проверка автоматическая, результат виден сразу — и по работе целиком, и по каждой теме.
Информатика · 11 класс · Гейн, 2023 · Глава 5 · Помехоустойчивые коды и сжатие данных