Сколько информации в сообщении и как его закодировать — короче для экономии и с избыточностью для надёжности. Ответы дают формулы Хартли и Шеннона, префиксные коды и коды, исправляющие ошибки.
Что нужно знать
- Хартли: $I = \log_2 N$ для $N$ равновероятных исходов.
- Шеннон: $H = -\sum p_i \log_2 p_i$ — энтропия; максимальна при равновероятных исходах.
- Префиксный код (условие Фано): ни одно кодовое слово не начинается с другого — декодируется однозначно.
- Коды Хаффмана и Шеннона — Фано: частым символам — короткие слова; средняя длина $\bar L = \sum p_i l_i$.
- Кодирование канала добавляет избыточность: бит чётности обнаруживает одну ошибку, повторение — исправляет.
- Расстояние Хемминга — число различающихся разрядов; при минимальном расстоянии $d$ код исправляет $\lfloor (d-1)/2 \rfloor$ ошибок.
- Код Хемминга (7, 4): 4 бита данных + 3 проверочных, исправляет одну ошибку.
Где чаще всего ошибаются
- Применять формулу Хартли к неравновероятным событиям.
- Считать код однозначным без проверки условия Фано.
- Ожидать, что бит чётности исправит ошибку.
Проверить себя
По этой же теме курса есть проверочная работа из 15 заданий на 30 минут. Проверка автоматическая, результат виден сразу — и по работе целиком, и по каждой теме.
Информационная безопасность · 10–11 классы · Количество информации и кодирование