Помехоустойчивые коды и сжатие данных — тест

Чтобы заметить ошибку, достаточно одного лишнего бита. Чтобы её исправить, избыточности нужно заметно больше — и это плата за надёжность.

Что проверяется

Коды, обнаруживающие ошибки: бит чётности, контрольная сумма, какие искажения такой код замечает, а какие пропускает. Кодовое расстояние и его связь с числом обнаруживаемых и исправляемых ошибок. Коды, исправляющие ошибки: идея добавления проверочных разрядов, принцип кода Хэмминга, определение позиции искажённого бита. Избыточность как плата за надёжность, применение помехоустойчивых кодов в связи и на носителях. Экономные коды: неравномерное кодирование, условие однозначного декодирования, алгоритм Хаффмана и построение кодового дерева, средняя длина кодового слова, сравнение с равномерным кодом. Алгоритмы сжатия без потерь: кодирование повторов, словарные методы, коэффициент сжатия и зависимость от свойств данных. Необратимое сжатие: отбрасывание малозаметных деталей, применение к звуку, изображению и видео, границы допустимых потерь.

Кодовое расстояние

Если любые два кодовых слова различаются не менее чем в трёх позициях, одиночную ошибку можно не только обнаружить, но и исправить. При расстоянии два ошибка лишь замечается.

Сжатие не бывает бесплатным

Универсального алгоритма, сжимающего любой файл, не существует: выигрыш на одних данных всегда компенсируется проигрышем на других. Сжатие работает там, где есть избыточность.

Как устроена работа

Одиннадцать заданий: выбор варианта, соответствие между приёмом кодирования и его возможностями, восстановление пропусков, упорядочивание шагов построения кода Хаффмана и расчёты длины сообщения и коэффициента сжатия. Разбор к каждому заданию показывает ход вычислений. Работа рассчитана примерно на двадцать пять минут, отметка выставляется по шкале пятьдесят, семьдесят и восемьдесят пять процентов. Отдельные вопросы посвящены биту чётности и сжатию с потерями.

Организация тестирования

Тестирование одинаково удобно и на компьютере, и на смартфоне. Так как время доступа к тесту настраивается, его спокойно можно выполнять вне школы, дома. Встроенная защита от списывания отмечает, когда учащийся уходит со страницы теста в другие окна или программы.