Основы сжатия информации. Основы помехоустойчивого кодирования

1. Алфавит. Сжатие данных

• Алфавит – множество символов (например, A–Z, 0–9).
• Сжатие данных = уменьшение числа бит для представления информации.
• Без потерь (например, ZIP, PNG).
• С потерями (например, JPEG, MP3).

2. Алгоритм Шеннона–Фано

• Метод префиксного кодирования.
• Часто встречающиеся символы кодируются короткими кодами.
• Реализует статистическое сжатие.

3. Алгоритм Хаффмана

• Совершенное префиксное кодирование.
• Построение двоичного дерева: символы с большей вероятностью → короче код.
• Применяется в ZIP, JPEG, MP3.

4. Код Хэмминга

• Используется для обнаружения и исправления ошибок.
• В сообщение добавляются проверочные (избыточные) биты.
• Позволяет исправлять одиночные ошибки, обнаруживать двойные.
• Широко применяется в памяти компьютеров, передаче данных.