tgoop.com/practicum_math/814
Last Update:
Как устроены QR-коды
Спасибо всем, кто вчера прошёл нашу мини-викторину! Было приятно видеть много правильных ответов. Теперь рассказываем подробнее, какая математика скрывается в чёрно-белых квадратиках.
QR-код устроен как матрица из чёрных и белых модулей. Чтобы сканер не запутался, где верх и низ, в углах есть большие маркеры, а внутри — синхронизирующие линии. Каждый квадрат модуля кодирует 0 или 1. Такая система координат позволяет «поставить сетку» и правильно считать биты информации.
Чтобы хранить текст или ссылку, одних нулей и единиц мало — нужны способы защитить данные от ошибок. И здесь в дело вступает высшая математика. Информация в QR-коде представляется как последовательность чисел, а они, в свою очередь, — как коэффициенты многочлена. Приведём пример:
Сообщение «HELLO» можно легко превратить в многочлен: M(x) = 72x⁴ + 69x³ + 76x² + 76x + 79. Коэффициенты здесь — это ASCII-коды букв.
Текст «ABC» тоже может стать многочленом: 65 + 66x + 67x², в котором ASCII-коды A, B, C — 65, 66 и 67, соответственно.
В реальных QR-кодах преобразование текста выполняется не так прямолинейно. Но идея кодирования именно та. И появилась она, потому что с многочленами удобно работать в рамках конечных полей.
Его ещё называют полем Галуа, по имени Эвариста Галуа. Это система чисел, в которой сложение, умножение и деление замкнуты внутри ограниченного набора элементов. Например, поле из 256 элементов — GF(256) — выбирают
для работы с байтами.
В QR-кодах вычисления тоже происходят в GF(256). Из этого поля берут коэффициенты многочленов, и арифметика становится очень эффективной. Числа складываются и умножаются «по модулю», так что даже при ошибках восстанавливается строгая структура.
Или, по-другому, контрольные символы. Их добавляют к исходному многочлену M(x), чтобы QR-код был устойчив к повреждениям. Это делают с помощью кодов Рида–Соломона:
Если у вас есть многочлен степени k–1, то для его однозначного восстановления достаточно знать его значения в k точках. А если вы знаете его значения в большем числе точек, то даже при потере части из них многочлен можно восстановить.
В QR-коде данные «записываются» в виде значений многочлена в разных точках конечного поля. А дальше сканер решает обратную задачу: восстанавливает многочлен по частично повреждённым данным.
Этот процесс напоминает интерполяцию: как если бы вы знали несколько точек на параболе и могли восстановить всю кривую. Современные QR-коды можно восстановить при повреждении до 30% площади!
Даже небольшой QR-код на 21×21 модуль содержит миллиарды комбинаций. А более крупные версии уходят в масштабы чисел, сопоставимых с количеством атомов во Вселенной.
Так что каждый раз, когда ваш телефон безошибочно считывает QR-код с потрёпанной временем и погодой афиши, он фактически решает задачу алгебраической интерполяции в конечном поле.
Правда, иногда технология может оказаться избыточной. Яркий пример — QR-часы: вместо времени они показывают код, который нужно отсканировать, чтобы узнать, который час. Полезно разве что в мире без смартфонов.
По ссылке вы найдёте крутую англоязычную настолку. В ней нужно восстановить QR-коды и решить головоломку. Правила можно прочитать здесь, а скачать листы с заданиями тут.
#как_устроено
