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

[музыка] Когда я впервые увидел QR код, то подумал, что они бессмысленны и никогда никогда не приживутся. Судя по мимом того времени, я был далеко не одинок. Некрасивая непонятная крошево из пикселей, ссылка на сайт или слоган, по которому можно искать в Гугле, гораздо лучше. QR код - это что-то на языке машин, а я-то человек! Но я ошибался. QR коды оказались настолько полезны, что теперь мы их видим повсюду: в транспорте, ресторанах, рекламе. В некоторых странах именно через QR коды совершается большинство платежей.

История появления QR кодов пронизана человеческим духом. Они берут начало во времена наших первых попыток оцифровать информацию. Живописец Жит в Ване, штат Коннектикут, со своей женой и двумя детьми. Однажды его пригласили написать портрет героя американской Революции маркиза де Лафайета. Супруги со дня на день ожидают рождение ребенка, но такой заказ может больше не повториться. Живописец решает не упускать шанс и спешно отбывает в Вашингтон.

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

Этим живописцем был Самуэль Финли Бриз Морз. Он принялся искать способ быстро передавать сообщения на большие расстояния. Морз устроился в Нью-Йоркский университет, где посещал лекции по электричеству, которые тогда активно изучали. В 1836 они с Джозефом Генри и Альфредом Веллом разработали аппарат, который передавал электрические импульсы по проводу. Устройство не было первым в своём роде, однако отличалось простотой. Британский вариант, например, требовал для работы несколько электрических цепей и пять магнитных игл, которые указывали на буквы и цифры.

В аппарате Морза была всего одна цепь, но техническая простота требовала весьма своеобразного способа кодировки. По цепи можно передавать короткие и длинные импульсы, которые Морз обозначил как точка и тире. Символы, которые встречались часто, передавались одним нажатием ключа. Точка - это английская "и", тире - "T". Чем реже встречается буква, тем более сложная последовательность ей соответствует. Получатель должен был записывать символы на бумажной ленте, но довольно быстро телеграфисты научились узнавать буквы по звуку сигналов. Это кратно ускорило обмен информацией.

Довольно быстро азбука Морза стала одним из стандартов коммуникации, ей перестукивали военные моряки и авиации. Кстати, знакомый всем сигнал СОС - что он означает? Ничего, просто этот набор символов легко передать и распознать. Азбука Морза преобразила обмен информацией на расстоянии, и, благодаря ей, изменилась ещё одна совсем иная сфера.

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

Долгое время ничего не получалось, Вудленд переехал во Флориду. Однажды, сидя на пляже, он прочертил, и продлил точки вниз. Получились узкие широкие линии. Штрихкод на его основе возник. Универсальный код товара - стандарт штрихкода, который содержит простую последовательность из 12 цифр, считывается он с помощью лазера. В зависимости от количества отражённого света, чёрные и белые участки штрихкода распознаются как точки и тире.

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

Каждому продукту с полки соответствует свой уникальный набор из 12 цифр на штрих-коде. На банке арахисовой пасты код будет один и тот же, в какой бы стране вы её не купили. Итак, для любого вида пасты: мягкой, с кусочками, с сахаром и без, с низким содержанием натрия, у каждого сорта продукта свой уникальный код. Могут ли они рано или поздно закончиться? Из 12 чисел получается 10 в степени ноль или триллион уникальных сочетаний. Этого должно хватить даже на такие странные эксперименты, как кислые печеньки Oreo или "Маун" с перцем.

Есть, правда, один нюанс: последнее число кода не самостоятельное. Штрихкод могут поцарапать, испачкать, испортить, а потому его создатели оставили последнее число для проверки целостности кода. Сложите все числа на нечётных позициях, умножьте сумму на три, прибавьте к ней сумму сложения чисел на чётных местах, далее разделите результат на 10. Если остаток ноль, то это и последнее проверочное число - ноль. В противном случае это разность десяти и остатка. Если одно число не читается, сканер по последней цифре с помощью описанного алгоритма может его восстановить. Но если повреждены сразу два числа, придётся пойти на впечатывание, сокращаясь до 10 в одной степени, то есть до 100 миллиардов.

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

А если мы, например, хотим узнать, где он был произведён? В 1986 году среди коров Великобритании начали проявляться симптомы губчатой энцефалопатии крупного рогатого скота или коровьего бешенства. Убив коров, содержащих прионы – неверно свернувшиеся белки, частички головного или спинного мозга – зараженной коровы, попадая вместе со съеденным мясом в организм человека, провоцировали сходное заболевание, из-за которого мозг буквально превращается в губку.

У живого скота болезнь никак не зафиксировать и миллионы особей отправили на убой. Срочно нужен был способ отслеживать источники импорта говядины. К сожалению, в обычном штрихкоде вся необходимая информация. Американский изобретатель Дэвид Алле предложил решение: поставить несколько штрихкодов друг на друга. Его код 49 выглядел как книжная полка. Это предшественник кода PDF417, который, например, используется на посадочных талонах, но в коде 49 не удалось решить проблему с количеством информации. Её стало больше, но не намного.

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

В игре Го надо ставить камни на пересечение линий. Даже если один немного сместится, игроки всё равно понимают, где он должен быть. Играя в Го, я подумал, что в принципе получается некая структура, которую можно было бы прочитать. Это и натолкнуло меня на идею чёрно-белой матрицы. Чтобы нагляднее показать вам, каким образом информация хранится в QR коде, я создам свой, причём на доске Go, которая и вдохновила Махира Хара на изобретение.

У меня обычные чёрные и белые камни для игры в Го. Белый - это ноль, а чёрный - единица. Мой аналоговый QR код будет содержать ссылку на YouTube канал Veritas. Первым делом нужно представить ссылку на канал в форме единиц и нулей. В этом нам поможет байтовая кодировка. Для неё используется система Аки, она также восходит к азбуке Морза. Каждому символу в ней соответствует число от 1 до 256, далее мы переводим его форму двоичного кода.

Так как 256 - это 2 в 8 степени, мы можем использовать комбинации 8 битов для передачи любого символа. В системе Аки из 8 битов и состоит один байт данных. Букве W присваивается значение 119 или 01110111 в двоичном коде. Проделаем то же самое с остальными символами. Вот так вся ссылка на наш канал выглядит в двоичном коде. В ней 26 символов, поэтому она занимает 26 байт информации.

На нашей доске можно создать код второй версии, размером 25 на 25 модулей. Ваш телефон способен считывать и другие размеры. Первая версия кода была размером 21 на 21, самая большая на сегодняшний день - 177 на 177 модулей. В такой QR код можно поместить 3 КБ информации. 26 таких вместят всю информацию, которая позволила компьютеру корабля Apollo 11 доставить человека на Луну.

Энтузиаст под ником KC с помощью QR кода сороковой версии даже запрограммировал Змейку. Вокруг QR кода должна быть пустая и одноцветная рамка, отделяющая его от всего остального. Отличительная черта QR кодов - три квадратика по углам. Это поисковые узоры, они позволяют сканеру понять ориентацию кода в пространстве. Почти на всех кодах также есть четвёртый квадратик, он размером поменьше, его труднее заметить. Это выравнивающий узор; с его помощью сканер выравнивается, если видит изображение издалека или из бокового ракурса.

Относительный размер и расстояние между выравнивающим узором и поисковыми квадратами позволяет восстановить код в первоначальном виде. По периметру поисковых узоров идут пустые белые полоски, которые отделяют их от всего остального. А это полосы синхронизации, своего рода пешеходные переходы, которые соединяют левый верхний квадрат с остальными двумя. Такие "зебры" есть на каждом QR коде. И не просто так коды разных версий выглядят похожи. Эти полосы говорят сканеру, какая перед ним версия и сколько данных в нём содержится.

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

Я выбрал. Пространство кода содержит, собственно, данные. Информация всегда начинается с нижнего правого угла. Первые четыре модуля содержат 4 бита, которые указывают на формат данных: 001 - числовое кодирование, 01 - буквенно-цифровое (заглавные буквы и цифры), 0 - байтовые, наконец японские иероглифы. Коды битов определяют количество символов в нашем сообщении. У нас их 26, что в двоичной форме выглядит как 00 10.

Далее мы выставляем буквы нашей ссылки в две колонки блоками по 8 бит. Блоки заполняются зигзагом от правого нижнего угла к левому верхнему. В каждом блоке, который соответствует одному байту, старший бит на позиции 2. Всё находится в нижнем правом углу, младший два в нулевой будет на противоположном конце. Получается 0 1 0 1, то есть W. Мы выложим так. То же самое проделаем с остальными символами.

После 3. you и заполнив ещё четыре бита, мы натыкаемся на выравнивающий узор. Чтобы закончить с буквой T, нужно просто перепрыгнуть через квадратик. Также поступим и с остальными системными элементами кода. Продолжаем в том же духе, и вскоре, начиная с буквы .com, блоки уже не выглядят такими ровненькими, а скорее напоминают фигуры из тетриса. Но принцип заполнения бит за битом остаётся тем же. Завершающие 8 битов, последняя буква, В.

Полвин и пространство. Излишек места оставлен для корректирующего кода. Он позволит восстановить информацию, которая содержится в QR коде, даже если он повреждён. У QR кодов существует четыре уровня коррекции ошибок: L - низкий уровень, позволяет восстановить 7% данных; средний M - потерянный 14%; уровень Q - 25%; H - 30%. То есть QR код может пережить потерю почти треть.

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

Есть ещё три важных бита, но до них мы доберёмся позже. Пока поставим там по три синих камешка. А для чего остальные красные камни? Это второй уровень защиты. Оставшиеся 10 битов исправляют ошибки в первых пяти. Но как именно это работает? Представим, что надо закодировать: какая у нас степень защиты, низкая или высокая?

Если один из битов считается неверно, и получится, скажем, 01, мы это легко заметим, но исходное сообщение восстановить не получится. Это можно исправить коди сообщением битами: уровень 00 — высокий, 11. Они оказываются на противоположных вершинах куба и максимально удалены. Если адресат получит сообщение 01, стоит предполагать, что изначальное сообщение 111, ведь оно ближе в этой схеме. Единственные правильные варианты - это 00 и 11; все остальные сочетания - это своеобразные буферы, задача которых обозначить ошибки в сообщении.

Правильные варианты должны быть наиболее га. В нашем кубе между ними три ребра, эта дистанция называется расстоянием Хэмминга в честь Ричарда Хэмминга, первопроходца в области исправления ошибок. Расстояние Хэмминга даёт исправить N - 1, что значит два ошибки в двоичной строке. В предыдущем примере это 1 бит. Итак, у нас есть рока из бит. Если допустимы только все нули и все варианты, можно расположить на противоположных вершинах пятимерного. Но в нашем случае допустимых комбинаций больше — 2 в пятой степени или 32.

Чтобы максимально удалить их друг от друга, продлим наши p битов до p-ti, и тогда между допустимыми вариантами будет семь рёбер, то есть расстояние хемминга будет семь. Что позволит исправить три перестановки битов. Восстановить сообщение можно по специальной таблице, по которой для последовательности с ошибкой ищется ближайшая соответствие самого вероятного закодированного слова.

Но для основного массива данных в QR коде нужен метод поэкземплярного. [музыка] Одно из них может исказить при передаче, но вы даже не узнаете, что произошла ошибка и в каком из чисел. Поэтому мы решили перестраховаться. Я пошлю вам не четыре числа. Первые четыре — это моё сообщение, а два других A и B помогут вам понять, всё ли верно.

Считайте эти числа коэффициентами полинома степени. Возьмём такие значения A и B, при которых полином можно записать в форме полинома третьей степени QX (у X - 1, у X - 2). В скобках может быть X минус любое число, но для простоты оставим 1 и 2. Теперь, получив мой полином, вы можете подставить вместо X 1 или 2 и получить ноль, потому что составлен полином.

А если нуля не получилось, вы поймёте, что в сообщении есть ошибка. Чем-то похоже на синдромы в медицине, ведь синдромом называют совокупность связанных признаков, которые характеризуют определённые отклонения от нормы. Ненулевой результат при постановке проверочных значений говорит об ошибке, но как мне найти значение переменных A и B?

В нашем примере полином без A и B и поделю его на произведение X - 1 и X - 2. У меня получится полином третьей степени, что мне и нужно, но есть ещё и остаток – 37X - 30. Перенесу его влево, чтобы всё сошлось. Значение A должно равняться -37, а B – 30. Поэтому я отправляю вам сообщение: 1 -2 3 5 -37 и 30. Вы подставляйте вместо X 1 или 2, и если в обоих случаях у вас получается ноль, значит ошибок в сообщениях нет.

Ну а если искажение всё-таки случилось, скажем, вместо пятёрки вы получили шесть. Теперь, если вместо X подставить один или два, полином уже не будет равняться нулю. Чтобы вычислить ошибку, вы по очереди подставляйте вместо каждого из коэффициентов переменную, далее находите значение этой переменной. Приведите полином к, ну, при X равном 1, а потом при X равном 2. Если получаются разные значения переменной, значит коэффициент, который вы проверяете, верный. Так будет со всеми коэффициентами, кроме того, в котором была ошибка.

Результаты здесь не просто одинаковы, но и равны изначально переданному числу. Похожий метод позволяет как обнаруживать, так и исправлять ошибки, ценой лишь небольшого увеличения используемых данных. Это пример кода Рида-Соломона, который в 1960 году разработали математик Ирвин Крит и Густав Соломон.

[музыка] Производить все эти операции, как мы только что сделали, очень тяжело. Инженеры из НАСА понимали, что по мере удаления космического аппарата VO от Земли количество шума и ошибок в сигнале будет расти. Однако они были столь уверены в кодах Рида-Соломона, что поместили в аппарат экспериментальный кодировщик, предполагая, что в будущем появятся более продвинутые алгоритмы декодирования. Так и произошло. Именно благодаря кодам мы пор различаем. Дай голос "во"! Спасибо за то, что CD и DVD диски работают, несмотря на все царапины.

Они же позволяют считывать повреждённые QR коды. Вся информация: формат данных, блок с количеством символов, наши сообщения, и отступы выставляются в линию и переводятся обратно в символы Аски. Если составлять полином с ними, коэффициентов мало, не покажется. Поэтому проверочные значения при кодировании получают с помощью так называемых полей Галуа, затем переводят их в двоичный код и заполняют ими остаток места в коде.

Что ж, наш QR код готов! Но почему он не считывается? Посмотрите на эти области: они смотрятся сплошными пятнами чёрного и белого цвета. Такое случается, это может сбить с толку считывающее устройство, ведь оно ожидает увидеть более беспорядочное скопление пикселей. Вдруг это повреждённый участок или не QR код вовсе, но и это предусмотрели.

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

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

Для нашего самодельного теперь QR кода наконец завершён. Сканируйте! Момент истины! Ура! Заработало! Проделав всё это, я снова убедился в том, как ненавижу QR коды. Они не для людей! Нет, я столько ошибок наделал, пока складывал эти камешки - прямо излил критично! Главное, не делать их слишком много.

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

В 2002 Великобританию вернулась эпидемия коровьей бешенства. От употребления заражённого мяса скончалось 179 человек. Люди были в ужасе! Нужен был способ быстро выяснять, с какой фермы пришла говядина и как именно её хранили. На выручку пришли QR коды. Именно тогда эти странные узоры шашек начали проникать в обиход.

Но всё же, что обеспечило им такой успех? Это не единственный подобный код. Отчасти дело в том, что заявлять исключительные права как инженер меня весьма тешит! Мысль о том, что QR коды - моё изобретение, сейчас активно используют по всему миру. Мы запустили их в Токио и никак не ограничивали другие страны. Думаю, это было верное решение.

Однако ВН решили заработать на продаже считывающих. Конечно, теперь почти у каждого в телефоне есть сканер, но изначально приложение для считывания QR кодов предоставлялись сторонними разработчиками, и про них мало кто знал. Однако уже в 2017 Android и Apple встроили сканеры в камеры своих смартфонов. Теперь кодами стали пользоваться ещё больше! Этому способствовала и пандемия COVID-19. Например, в ресторанах, которые всё-таки могли работать, были необходимы бесконтактные меню.

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

QR код может сгенерировать любой, что позволяет злоумышленникам использовать их для фишинга и прочих недобросовестных действий. В Японии телефоны оснастили сканерами ещё в 2002 году, поэтому у нас QR коды не используют для хранения важной корпоративной и личной информации. В 2007 году был разработан QR код с функцией шифрования. Он используется в Японии. Мы хотим со временем добавить функцию электронной аутентификации.

Можно будет узнать, кто сгенерировал QR код. Так процесс станет прозрачнее. Как и со всем прочим в интернете, здесь тоже стоит быть на чеку. Проверяйте, куда именно ведёт ссылка из QR кода, прежде чем по ней переходить. Поговорим о будущем QR кодов. Что дальше? Пока что в них можно поместить лишь информацию в символах. Я бы хотел, чтобы в QR коде получилось зашифровать изображение, а ещё увеличить объём данных.

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

Но для QR кодов такое в принципе невозможно. Количество уникальных кодов в первой версии с самым низким уровнем коррекции равно 2 в 152 степени. Это в 10 раз больше, чем разрешённых правилами положений шахматных фигур. Поэтому, если вы просто случайно накидайте пиксели в форме QR кода, сканер их не считает за свою жизнь. Вы наверняка отсканировали множество QR кодов, но когда вы наведёте телефон на очередной из них, то будете представлять себе, как он работает.

Кстати, а что вообще означает аббревиатура QR? Главное преимущество QR кодов - то, что их можно быстро считать. Мы назвали их "быстрый отклик" - ре, потому что они быстро открываются. Какой из вариантов применения QR кодов вас больше всего радует? Я удивился, когда узнал, что люди делают QR коды татуировки и таким образом обмениваются адресами и номерами телефонов. В последнее время популярно составлять QR коды дронами. Когда я увидел такое впервые, то был поражён, это очень красиво.

Если говорить о печатных носителях, то переход от штрих-кодов к QR кодам – это своего рода эволюция экспрессии, по крайней мере, так это вижу я. Переведено и озвучено студией Вертдайдер.