Как устроен QR-код? [Veritasium]

Что значит «сcience» и почему оно работает? Кьюар-коды оказались настолько полезны, что теперь мы их видим повсюду. В транспорте, ресторанах, рекламе. В некоторых странах именно через кьюар-коды совершается большинство платежей. История появления кьюар-кодов пронизана человеческим духом. Они берут начало во времена наших первых попыток оцифровать информацию. 1825 год. Знаменитый живописец живет в Нью-Хэйване, штат Коннектикут, со своей женой и двумя детьми. Однажды его пригласили написать портрет героя американской революции, маркиза Делла Файета. Супруги со дня на день ожидают рождения ребенка, но такой заказ может больше не повториться. Живописец решает не упускать шанс и спешно отбывает в Вашингтон. Оказавшись в столице, он отправляет домой письмо, в котором рассказывает о встрече со знаменитостью и завершает его словами. «Скоро напишу вновь. Поцелуй за меня детей. Пусть и в спешке, но с самыми искренними чувствами твой любящий муж». Спустя пару дней пришел ответ. У супруги художника случились осложнения после родов. Причувствуя недоброе, живописец поспешил домой. Меняя лошадей и кареты, он преодолел обратный путь за несколько дней. Но было слишком поздно. Жена художника умерла. Более того, художник не успел на похороны, и тело его жены уже покоилось в земле. Этим живописцем был Сэмуэль Финли Брисс Морзе. Он принялся искать способ быстро передавать сообщения на большие расстояния. Морзе устроился в Нью-Йоркский университет, где посещал лекции по электричеству, которые тогда активно изучали. В 1836-м они с Джозефом Генри и Альфредом Уэллом разработали аппарат, который передавал электрические импульсы по проводу. Устройство не было первым в своем роде, однако отличалось простотой. Британский вариант, например, требовал для работы несколько электрических цепей и пять магнитных игол, которые указывали на буквы и цифры. В аппарате Морзе была всего одна цепь, но техническая простота требовала весьма своеобразного способа кодировки. По цепи можно передавать короткие и длинные импульсы, которые Морзе обозначил как точки и тире. Символы, которые встречались часто, передавались одним нажатием ключа. Точка — это английская «и», тире «ти». Чем реже встречается буква, тем более сложная последовательность ей соответствует. Получатель должен был записывать символы на бумажной ленте. Но довольно быстро телеграфисты научились узнавать буквы по звуку сигналов. Это кратно ускорило обмен информацией. Довольно быстро азбука Морзе стала одним из стандартов коммуникации. Ей перестукивались военные, моряки и авиация. Кстати, знакомый всем сигнал — SOS. Что он означает? Ничего. Просто этот набор символов легко передать и распознать. Азбука Морзе преобразила обмен информацией на расстояние. Но в следующем столетии благодаря ей изменилась еще одна, совсем иная сфера. В конце 40-х годов в Дрексельском университете учился Бернард Сильвер. Однажды директор местной сети универмагов попросил декана его факультета придумать, как пробивать покупки, не печатая название и цену товара вручную. В то время это приходилось делать кассирам, многие из которых из-за монотонной и однообразной нагрузки вечно страдали от туннельного синдрома. Сильвер узнал об этом и рассказал своему другу Норману Джозефу Вудленду, и они принялись за дело. Долгое время ничего не получалось. Вудленд переехал во Флориду. Однажды, сидя на пляже, он прочертил на песке несколько точек и тире из азбуки Морзе. Как-никак, Норман был бойскаутом. Он вспоминает. «Я продлил точки и тире вниз. Получились узкие и широкие линии. Так и появился первый штрих-код. На его основе возник универсальный код товара. Стандарт штрих-кода, который содержит простую последовательность из 12 цифр. Считывается он с помощью лазера. В зависимости от количества отраженного света черный и белый участки штрих-кода распознаются как точки и тире. В начале, центре и конце кода есть попарь вертикальных линий, которые помогают сканеру правильно считывать информацию. Штрих-код делится на две половины — левую и правую. Одна и та же цифра с разных сторон кодируется набором линий с противоположными цветами, чтобы сканер различал стороны даже вверх ногами. Обычно на левой половине располагается информация о производителе, а справа — о товаре. Компании платят кругленькие суммы, чтобы застолбить определенный набор цифр и не дать никому другому использовать их для своих товаров. Каждому продукту, который вы берете с полки, соответствует свой уникальный набор из 12 цифр на штрих-коде. На банке арахисовой пасты GIF будет один и тот же код, в какой бы стране вы ее ни купили. И так для любого вида пасты — мягкой, с кусочками, с сахаром и без, с низким содержанием натрия — у каждого сорта продукта свой уникальный код. Могут ли они рано или поздно закончиться? Из 12 чисел получается 10 в 12 степени, или триллион уникальных сочетаний. Этого должно хватить даже на такие странные эксперименты, как кислые печеньки Oreo или Mountain Dew с перцем. Есть, правда, один нюанс. Последнее число кода несамостоятельное. Штрих-код могут поцарапать, испачкать, испортить, а потому его создатели оставили последнее число для проверки целостности кода. Сложите все числа на нечетных позициях. Умножьте сумму на 3, прибавьте к ней сумму сложения чисел на четных местах. Далее разделите результат на 10. Если остаток 0, то и последнее проверочное число 0. В противном случае это разность 10 и остатка. Если одно число не читается, сканер по последней цифре с помощью описанного алгоритма может его восстановить. Но если повреждены сразу два числа, придется впечатывать цифры под штрих-кодом вручную. Без последней цифры количество уникальных комбинаций сокращается до 10 в 11 степени, то есть до 100 миллиардов. Уже зарегистрировано больше миллиарда штрих-кодов, и с каждым днем их становится все больше. Рано или поздно они кончатся. Но замену штрих-кодом начали искать не поэтому. Нам не хватало объема информации, который способен содержать штрих-код. 12 цифр хранят лишь название, тип и модель товара. А если мы, например, хотим узнать, где он был произведен? В 1986 году среди коров Великобритании начали проявляться симптомы губчатой энцефалопатии крупного рогатого скота или коровьего бешенства. Усыпь заболевала, если потребляла корм, содержащий прионы — неверно свернувшиеся белки. Частички головного или спинного мозга зараженной коровы, попадая вместе со съеденным мясом в организм человека, провоцировали сходные заболевания, из-за которого мозг буквально превращается в губку. У живого скота болезнь никак не зафиксировать, и миллионы особей отправили на убой. Срочно нужен был способ отслеживать источники импорта говядины. К сожалению, в обычный штрих-код вся необходимая информация просто-напросто не влезала. Американский изобретатель Дэвид Алле предложил решение поставить несколько штрих-кодов друг на друга. Его код 49 выглядел как книжная полка. Это предшественник кода PDF417, который, например, используется на посадочных талонах. Но в коде 49 не удалось решить проблему с количеством информации. Ее стало больше, но ненамного. А если расширить штрих-код в высоту и в ширину? Получится матрица данных. С помощью нее в форме верикода в НАСА в 1994-м отслеживали и идентифицировали детали шаттла. Верикод считывался не лазерами, а ранними цифровыми камерами, и это была закрытая технология. Примерно в то же время в Японии Масахиро Ахара, инженер из ДЕНСО, компании по производству автозапчастей, был недоволен тем, что на каждой коробке приходилось сканировать множество штрих-кодов. На автозаводах повсюду машинное масло. Оно часто попадало на штрих-коды, и из-за этого они не считывались. Каждый раз приходилось впечатывать данные вручную. Это дополнительные хлопоты. Хара разработал свою альтернативу, а вдохновлялся он весьма необычным источником. В игре ГО надо ставить камни на пересечение линий. Даже если один немного сместится, игроки все равно понимают, где он должен быть. Играя в ГО, я подумал, что, в принципе, получается некая структура, которую можно было бы прочитать. Это и натолкнуло меня на идею черно-белой матрицы. Чтобы нагляднее показать вам, каким образом информация хранится в QR-коде, я создам свой, причем на доске ГО, которая и вдохновила Масахиро Ахара на изобретениях. У меня обычные черные и белые камни для игры в ГО. Белый — это ноль, а черный — единица. Мой аналоговый QR-код будет содержать ссылку на YouTube-канал Veritasium. Первым делом нужно представить ссылку на канал в форме единицы нулей. В этом нам поможет байтовая кодировка. Для нее используется система ASCII. Она также восходит к азбуке Морзе. Каждому символу в ней соответствует число от 1 до 256. Далее мы переводим его в форму двоичного кода. Так как 256 — это 2 в восьмой степени, мы можем использовать комбинации восьми битов для передачи любого символа в системе ASCII. Из восьми битов и состоит один байт данных. В букве W присваивается значение 119 или 0111 0111 в двоичном коде. Проделаем то же самое с остальными символами. Вот так вся ссылка на наш канал выглядит в двоичном коде. В ней 26 символов, поэтому она занимает 26 байтов информации. На нашей доске можно создать код второй версии, размером 25 на 25 модулей. Ваш телефон способен считывать и другие размеры. Первая версия кода была размером 21 на 21. Самая большая на сегодняшний день — 177 на 177 модулей. В такой QR-код можно поместить 3 килобайта информации. 26 таких вместят всю информацию, которая позволила компьютеру корабля «Аполлон-11» доставить человека на Луну. Энтузиаст под ником Matt Casey с помощью QR-кода сроковой версии даже запрограммировал змейку. Вокруг QR-кода должна быть пустая одноцветная рамка, отделяющая его от всего остального. Отличительная черта QR-кодов — 3 квадратика по углам. Это поисковые узоры. Они позволяют сканеру понять ориентацию кода в пространстве. Почти на всех кодах также есть четвертый квадратик. Он размером поменьше. Его труднее заметить. Это выравнивающий узор. С его помощью сканер выправляет изображение, если видит его издалека или с бокового ракурса. Относительные размеры и расстояние между выравнивающим узором и поисковыми квадратами позволяют восстановить код в первоначальном виде. По периметру поисковых узоров идут пустые белые полоски, которые отделяют их от всего остального. А это полосы синхронизации, своего рода пешеходные переходы, которые соединяют левый верхний квадрат с остальными двумя. Такие зебры есть на каждом QR-коде, и не просто так. Коды разных версий выглядят похожи, а эти полосы говорят сканеру, какая перед ним версия и сколько данных в нем содержится. Если полоса состоит из пяти модулей, это первая версия, если из девяти — вторая и так далее. Также по углам расположены полосы с информацией о том, как считывать код. Пока что кладу сюда красные камни. У всех QR-кодов есть еще одна общая черта. Модуль возле нижнего поискового квадрата всегда черный. Я спросил господина Хару, стоит ли за этим какой-то смысл, а оказалось — нет. Нужно было выбрать, поставить туда черный или белый. Я выбрал черный. Остальное пространство кода содержит, собственно, данные. Информация всегда начинается с нижнего правого угла. Первые четыре модуля содержат четыре бита, которые указывают на формат данных. 0001 — числовое кодирование. 0010 — буквенно-цифровое, заглавные буквы и цифры. 0100 — байтовое. Наконец, 1000 — японские иероглифы Канзи. Следующие восемь битов определяют количество символов в нашем сообщении. У нас их 26, что в двоичной форме выглядит как 00011010. Далее мы выставляем буквы нашей ссылки в две колонки блоками по 8 бит. Блоки заполняются зигзагом от правого нижнего угла к левому верхнему. В каждом блоке, который соответствует одному байту, старший бит на позиции 2 в 7 находится в нижнем правом углу, младший 2 в 0 будет на противоположном конце. Получается 01110111, то есть W, мы выложим так. То же самое проделываем с остальными символами. После 3w.you и заполнив еще четыре бита, мы натыкаемся на выравнивающий узор. Чтобы закончить с буквой T, нужно просто перепрыгнуть через квадратик. Так же поступим и с остальными системными элементами кода. Продолжаем в том же духе, и вскоре, начиная с буквы O в .com, блоки уже не выглядят такими ровненькими, а скорее напоминают фигуры из Тетриса. Но принцип заполнения бит за битом остается тем же. Завершающие 8 битов — последняя буква. Впрочем, мы заполнили лишь половину пространства. Излишек места оставлен для корректирующего кода. Он позволит восстановить информацию, которая содержится в QR-коде, даже если он поврежден. У QR-кодов существует 4 уровня коррекции ошибок. L, низкий уровень, позволяет восстановить 7% данных. Средний M — потерянные 14%. Уровень Q — 25%. H — 30%. То есть QR-код работает, даже если отсутствует почти треть. Чем выше уровень коррекции, тем больше места нужно для исправления ошибок. Знать, сколько в коде блоков с этой функцией, очень важно. Сведения об этом кодируются двумя способами. Во-первых, уровень записан возле двух разных поисковых узоров. Ведь самый простой способ подстраховаться — продублировать информацию. Я выбрал средний уровень коррекции, а потому помещаю синий и желтый камешек слева вверху. Если эта часть повредится, у нас есть копия той же информации слева внизу. Возле узоров есть еще три важных бита, но до них мы доберемся позже. Пока поставим там по три синих камешка. А для чего остальные красные камни? Это второй уровень защиты. Оставшиеся 10 битов исправляют ошибки в первых пяти. Но как именно это работает? Представим, что надо закодировать, какая у нас степень защиты. Низкая или высокая? Если один из битов считается неверным и получится, скажем, 0.1, мы это легко заметим. Но исходное сообщение восстановить не получится. Это можно исправить, кодируя сообщение тремя битами. Низкий уровень — 0.0.0, высокий — 1.1.1. Они оказываются на противоположных вершинах куба и максимально удалены. Если адресат получит сообщение 0.1.1, стоит предполагать, что изначальное сообщение — 1.1.1. Ведь оно ближе. В этой схеме единственные правильные варианты — это 0.0.0 и 1.1.1. Все остальные сочетания — это своеобразные буферы, задача которых — обозначить ошибки в сообщении. Правильные варианты должны быть наиболее удалены друг от друга. В нашем кубе между ними три ребра. Эта дистанция называется расстоянием Хэмминга. В честь Ричарда Хэмминга, первопроходца в области исправления ошибок. Расстояние Хэмминга n дает исправить n-1, деленное на два ошибок в двоичной строке. В предыдущем примере это 1 бит. Итак, у нас есть строка из пяти бит. Если допустимы только все нули и все единицы, эти варианты можно расположить на противоположных вершинах пятимерного гиперкуба. Но в нашем случае допустимых комбинаций больше — 2 в пятой степени или 32. Чтобы максимально удалить их друг от друга, продлим наши 5 битов до 15, и тогда между допустимыми вариантами будет 7 ребер. То есть расстояние Хэмминга будет 7, что позволит исправить три перестановки битов. Восстановить сообщение можно по специальной таблице, по которой для последовательности с ошибкой ищется ближайшее соответствие, самое вероятное закодированное слово. Но для основного массива данных в QR-коде нужен метод поэффективнее, который бы позволил обойтись без таблиц или кратного увеличения объема информации. Предположим, я хочу послать вам сообщение, которое состоит из 4 чисел, 1, минус 2, 3 и 5. Одно из них может исказиться при передаче, но вы даже не узнаете, что произошла ошибка, и в каком из чисел. Поэтому мы решили перестраховаться. Я пошлю вам не 4 числа, а 6. Первые 4 — это мое сообщение, а два других, A и B, помогут вам понять, все ли верно. Считайте эти 6 чисел коэффициентами полинома пятой степени. Возьмем такие значения A и B, при которых полином можно записать в форме полинома третьей степени. Q от X, умноженное на X минус 1, умноженное на X минус 2. В скобках может быть X минус любое число, но для простоты оставим 1 и 2. Теперь, получив мой полином, вы можете подставить вместо X 1 или 2 и получить 0, потому что так составлен полином. А если нуля не получилось, вы поймете, что в сообщении есть ошибка. Чем-то похоже на синдромы в медицине, ведь синдромом называют совокупность связанных признаков, которые характеризуют определенные отклонения от нормы. Ненулевой результат при постановке проверочных значений говорит об ошибке. Но как мне найти значения переменных A и B в нашем примере? Я возьму полином без A и B и поделю его на произведения X минус 1 и X минус 2. У меня получится полином третьей степени, что мне и нужно, но есть еще и остаток. 37X минус 30. Перенесу его влево. Чтобы все сошлось, значение A должно равняться минус 37, а B — 30. Поэтому я отправляю вам сообщение 1, минус 2, 3, 5, минус 37 и 30. Вы подставляете вместо X 1 или 2, и если в обоих случаях у вас получается 0, значит, ошибок в сообщении нет. Но а если искажение все-таки случилось? Скажем, вместо пятерки вы получили 6. Теперь, если вместо X подставить 1 или 2, полином уже не будет равняться 0. Чтобы вычислить ошибку, вы по очереди подставляете вместо каждого из коэффициентов переменную. Далее находите значение этой переменной, приравняв полином к 0 при X, равном 1, а потом при X, равном 2. Если получаются разные значения переменной, значит, коэффициент, который вы проверяете, верный. Так будет со всеми коэффициентами, кроме того, в котором была ошибка. Результаты здесь не просто одинаковые, но и равны изначально переданному числу 5. Подобный метод позволяет как обнаруживать, так и исправлять ошибки ценой лишь небольшого увеличения используемых данных. Это пример кода Рида-Соломона, который в 1960 году разработали математик Ирвин Крид и Густав Соломон. Производить все эти операции, как мы только что сделали, очень тяжело. Инженеры из НАСА понимали, что по мере удаления космического аппарата Voyager от Земли количество шума и ошибок в сигнале будет расти. Однако они были столь уверены в кодах Рида-Соломона, что поместили в аппарат экспериментальный кодировщик, предполагая, что в будущем появятся более продвинутые алгоритмы декодирования. Так и произошло. Именно благодаря кодам Рида-Соломона мы до сих пор различаем далекий голос Войджера. Им же стоит сказать спасибо за то, что CD и DVD диски работают несмотря на все царапины. Они же и позволяют считывать поврежденные QR-коды. Вся информация, формат данных, блок с количеством символов, наши сообщения и отступы выставляются в линию и переводятся обратно в символы ASCII. Если составлять поленом с ними, коэффициентов мало не покажется. Поэтому проверочные значения при кодировании получают с помощью так называемых полей Галуа. Затем переводят их в двоичный код и заполняют ими остаток места в QR-коде. Что ж, наш QR-код готов. Но почему он не считывается? Посмотрите на эти области. Они смотрятся сплошными пятнами черного и белого цвета. Порой такое случается. Это может сбить с толку считывающее устройство, ведь оно ожидает увидеть более беспорядочное скопление пикселей. Вдруг это поврежденный участок? Или не QR-код вовсе? Но и это предусмотрели. Помните три синих камня, о которых я обещал рассказать позже? Они обозначают один из восьми способов маскирования, того, как можно перемешать модули кода, чтобы он выглядел беспорядочным. Скажем, эта маска заставляет сменить цвет пикселей на противоположный в каждой третьей колонке. Функциональных элементов это не касается. Они остаются нетронутыми. По стандарту существует восемь алгоритмов маскирования. Каждый из этих алгоритмов можно применить к любому коду, и сканер его считает. Главное — правильно указать тип маски. Поэтому разные генераторы создают непохожие QR-коды с одинаковой информацией. Какая же маска лучше? За каждую непрерывную последовательность пикселей одного цвета назначается штраф. Лучше считается маска с самым низким показателем. Она в итоге и применяется. Так код сканером прочитать легче всего. Для нашего самодельного QR-кода я возьму самую простую маску. Теперь QR-код наконец завершен. Сканируйте. Момент истины. Ура! Заработало. Проделав все это, я снова убедился в том, как ненавижу QR-коды. Они не для людей. Нет. Я столько ошибок наделал, пока складывал эти камешки. Прямо измучился. Ну, как мы теперь знаем, ошибки — это не критично. Главное — не делать их слишком много. Хорошо. Изначально QR-коды использовались лишь на производствах. QR-коды приняли хорошо, но мой начальник сомневался, что им найдется применение хоть где-то еще. На тот момент руководство не было уверено, что проект будет успешным. Однако уже скоро все осознали выгоду, которую предоставляла емкость QR-кода. В 2002-м в Великобританию вернулась эпидемия коровьего бешенства. От употребления зараженного мяса скончалось 179 человек. Люди были в ужасе. Нужен был способ быстро выяснять, с какой фермы пришла говядина и как именно ее хранили. На выручку пришли QR-коды. Именно тогда эти странные узоры и шашечек начали проникать в обиход. Но все же, что обеспечило им такой успех? Это не единственный подобный код. Отчасти дело в том, что Denso Wave не стали заявлять исключительные права. Как инженер, меня весьма тешит мысль о том, что QR-коды, мое изобретение, сейчас активно используют по всему миру. Мы запустили их в Токио и никак не ограничивали другие страны. Думаю, это было верное решение. Однако в Denso решили заработать на продаже считывающих устройств. Конечно, теперь почти у каждого в телефоне есть сканер, но изначально приложения для считывания QR-кодов предоставлялись сторонними разработчиками, и про них мало кто знал. Однако уже в 2017-м Android и Apple встроили сканеры в камеры своих смартфонов. Теперь кодами стали пользоваться еще больше. Этому способствовала и пандемия COVID-19. Например, в ресторанах, которые все-таки могли работать, были необходимы бесконтактные меню. В Китае и Индии стала популярной безналичная оплата с помощью QR-кодов. В одной только Индии ежемесячно производится 12 миллиардов транзакций. QR-коды пригодились для хранения сведений о вакцинации, личных данных, о состоянии здоровья. Впрочем, со временем возникли и проблемы. Хочу спросить про безопасность. В последнее время многие мошенники обманывают людей с помощью QR-кодов. Вас беспокоит, что ваше детище применяют таким образом? QR-код может сгенерировать любой, что позволяет злоумышленникам использовать их для фишинга и прочих недобросовестных действий. В Японии телефоны оснастили сканерами еще в 2002-м году. Поэтому у нас QR-коды не используют для хранения важной корпоративной и личной информации. В 2007-м году был разработан QR-код с функцией шифрования. Он используется в Японии. Мы хотим со временем добавить функцию электронной аутентификации. Можно будет узнать, кто сгенерировал QR-код. Так процесс станет прозрачнее. Как и со всем прочим в интернете, здесь тоже стоит быть начеку. Проверяйте, куда именно ведет ссылка из QR-кода, прежде чем по ней переходить. Поговорим о будущем QR-кодов. Что дальше? Пока что в них можно поместить лишь информацию в символах. Я бы хотел, чтобы в QR-коде получилось зашифровать изображение, а еще увеличить объем данных. Сейчас объясню зачем. В Японии нередко случаются природные бедствия, особенно землетрясения. В результате нарушаются коммуникации, интернет становится недоступен. Представим, что доктору необходим рентгеновский снимок пациента. Но из-за землетрясения он не может получить его в больнице. В таком случае пациент мог бы просто показать ему QR-код со снимком. Специалисты изучат его и обеспечат надлежащее лечение. В QR-кодах используются лишь два цвета — черный и белый. Мы думаем расширить палитру и таким образом включить в них больше информации. Вероятно, что закончится штрих коды крайне мала. Но для QR-кодов такое в принципе невозможно. Количество уникальных кодов первой версии с самым низким уровнем коррекции равно 2 в 152 степени. Это в 10 раз больше, чем разрешенных правилами положений шахматных фигур. Поэтому если вы просто случайно накидаете пиксели в форме QR-кода, сканер их не считает. За свою жизнь вы наверняка сканировали множество QR-кодов. Но когда вы наведете свой телефон на очередной из них, то будете представлять себе, как он работает. Кстати, а что вообще означает аббревиатура QR? Главное преимущество QR-кодов — то, что их можно быстро считать. Мы назвали их «Быстрый отклик», «Квик-респонс», потому что они быстро открываются. Какой из вариантов применения QR-кодов вас больше всего радует? Я удивился, когда узнал, что люди делают QR-коды татуировки. И таким образом обмениваются адресами и номерами телефонов. В последнее время стало популярно составлять QR-коды дронами. Когда я увидел такое впервые, то был поражен. Это очень красиво. Если говорить о печатных носителях, то переход от штрих-кодов к QR-кодам — это своего рода эволюция экспрессии. По крайней мере, так это вижу я.