Как устроены 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-коды и решить головоломку. Правила можно прочитать здесь, а скачать листы с заданиями тут.

#как_устроено

Где прячется центр круга❓

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

❎Линейку и циркуль использовать нельзя — в вашем распоряжении только бумага, руки и смекалка.

Пробуйте и показывайте результаты в комментариях под спойлером.

🟢А если справились, здесь лежит ещё одна задача с бумагой. Решайте!

#задача

Бумага сама знает ответ…

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

Сформулируем нашу версию:

1️⃣ Выберите угол листа и точку на окружности, находящуюся вдали от этого угла. Согните бумагу так, чтобы выбранный угол оказался точно на выбранной точке (на рисунке это точки C’ и C).

2️⃣ Пусть стороны листа, исходящие из угла C’, пересекут окружность в точках J и K. Так как угол JC’K = 90°, отрезок JK является диаметром окружности и проходит через её центр. Сделайте сгиб вдоль линии JK.

3️⃣ Затем выберите другую точку на окружности или другой угол листа, и повторите процедуру. Две построенные таким образом линии сгиба пройдут через центр окружности, а значит, пересекутся именно в нём.

Ставьте 🤓, если разобрались без наших подсказок. И делитесь с друзьями — задачу можно решить вместе на сайте GeoGebra. Вот здесь оставили готовое решение и обоснование.

#задача