Восстановление повреждённых QR-кодов с использованием кодов Рида-Соломона

О чём эта работа

В основе живучести QR лежит помехоустойчивое кодирование. К полезным данным добавляются проверочные кодовые слова, вычисленные по алгоритму Рида-Соломона, и декодер умеет восстановить исходное сообщение, пока число повреждённых слов укладывается в запас. Проект показывает этот запас на измерениях, поэтому ценность работы определяется качеством эксперимента.

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

Из каких частей собрать работу

• Устройство символа. Опиши модули, версии, поисковые и выравнивающие узоры, маскирование. Достаточно разобрать одну версию подробно, зато с картинкой и разметкой зон, которые ты дальше будешь портить.
• Теория кода. Объясни, что кодовые слова трактуются как элементы поля Галуа из 256 элементов, а проверочные слова получаются делением многочлена сообщения на порождающий многочлен. Дальше покажи главную формулу практики. Число исправляемых ошибок примерно вдвое меньше числа проверочных слов, потому что декодеру нужно найти и позицию ошибки, и её величину.
• Уровни коррекции. В стандарте их четыре, от самого экономного до самого избыточного, и они отличаются долей проверочных слов примерно от семи до тридцати процентов. Покажи на своих файлах, как с ростом уровня растёт плотность модулей при одинаковом содержимом.
• Эксперимент. Задай правило порчи и повторяй его многократно. Например, закрашивай случайно расположенный квадрат заданной площади и делай по нескольку десятков попыток на каждую комбинацию уровня и площади. Одиночная попытка ничего не доказывает, потому что результат сильно зависит от того, куда попало пятно.
• Анализ. Построй график доли успешных декодирований от площади повреждения для каждого уровня коррекции. Отдельно посчитай попытки, где пятно задело служебные зоны, и покажи, насколько резко там падает результат.

Что оценит преподаватель

Первое, что проверяют в проекте с экспериментом, это воспроизводимость. В работе должны быть указаны версия символа, уровень коррекции, содержимое кода, размер изображения, правило порчи и число повторов. Любой человек с твоим описанием обязан получить похожие числа. Второе, на что смотрят, это теоретическая часть. Фраза про поле Галуа без объяснения, зачем оно здесь нужно, вызывает вопрос на защите почти гарантированно.

Третий критерий касается честности выводов. Если декодер твоей библиотеки отказался читать код, это ещё не значит, что информация потеряна безвозвратно. Стоит оговорить, что результат относится к конкретному декодеру и конкретным условиям съёмки.

Где брать материал

Описание формата ищи в стандарте ISO/IEC 18004, он определяет версии, уровни коррекции и порядок размещения модулей. Теорию кодов Рида-Соломона бери из учебников по теории информации и помехоустойчивому кодированию. Практическую часть удобно делать на готовых библиотеках, генератор и декодер есть и в Python, и в Java, а отдельная библиотека для кодов Рида-Соломона позволит показать кодирование вручную на маленьком примере.

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

Типичная ошибка в этой теме

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

С чего начать в первый день

Сгенерируй один и тот же текст в четырёх уровнях коррекции и сохрани картинки. Закрась в каждой одинаковый квадрат в одном и том же месте и попробуй прочитать. Ты сразу увидишь разницу между уровнями и поймёшь, какого размера пятна имеет смысл брать в основном эксперименте. Заодно определишься с библиотекой декодирования.