Алгоритм QR-кода

01.10.2015

6501

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

Как прочитать QR-код без специального приложения

Для наглядности и в качестве примера для чтения взят код цифры «5.

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

Для корректировки ошибок в QR-кодировании используются коды Рида-Соломона (RS), записываемые после всей остальной информации. Нередко RS-коды занимают наибольшую часть самого QR-кода, делая проще чтение матрицы кода. «Перемешивание» информации содержащей RS-коды происходит согласно одному из 8 алгоритмов. После «перемешивания» коды записывают в специальную последовательность на картинку-шаблон. Туда же записывают данные необходимые устройствам дешифрации.

Порядок чтения из QR-матрицы:

перевод формата данных в биты;
наложение маски;
извлечение данных;
декодирование;

Полезная для чтения информация делится на два типа:

системная информация;
данные;

Области детектирования не содержат ни той, ни другой, но помогают понять версию кода, обуславливающую вместимость QR-матрицы. Чем ниже версия – тем проще код.

Для снижения появления ошибок системную информацию дублируют. Всего ее размер составляет 15 бит, только 5 из которых несут в себе пользу. Оставшиеся 10 бит это так называемый BCH код – используемый для корректировки ошибок.

Чтение информации по матрице QR-кода

Чтение QR-кода происходит в несколько этапов, на каждом из которых выполняются определенные действия:

1 этап. Прочтение системной информации

Для этого понадобится лишь первая пятерка бит. 2 бита – показатели коррекционного уровня, оставшиеся определяют применяемую маску.

Для данной матрицы первая пятерка бит представляет собой последовательность 10110

2 этап. Применение маски

К последовательности применяется статическая маска, первая пятерка бит которой выглядит как 10101. Затем проводится операция xor (исключающее или). В результате полученная информация будет 00011.

Первые два значения (00) – это уровни коррекции ошибок. У данной матрицы уровень M, что соответствует возможности корректировки ошибок - 15%.

Последние три значения (011) соответствуют типам применяемых масок. (011) соответствует (i+j) mod3 = 0.

3 этап. Чтение заголовка

В заголовке, который состоит из 4 бит содержатся данные о режиме. Читают «змейкой», начиная с правого нижнего угла и двигаясь справа налево, снизу вверх.

Возможные режимы QR-кода:

0110 – ECI;
0001 – числовые;
0010 – число-буквенные;
0100 – 8-битные или инача байтные;
1000 – Kanji;
0011 – структурированное дополнение;
0101 и 1001 – FNC1 (1 и 2 позиция соответственно).

4 этап. Накладывание макски на заголовок

К извлеченным 4 режимным битам применяется маска, определенная во втором этапе. Если выражение описывающее маску TRUE (т.е. вернно) бит должен быть инвертирован, в противном случае с ним ничего не делается. Начало масочных координат будет находиться вверху слева (0,0).

После применения маски будет получен режим.

Индикатор режима для рассматриваемого QR-кода будет представлен последовательностью (0111). Применив к нему соответствующую маску, получим режим (0001) – числовой.

5 этап. Чтение данных

Наиболее простой для чтения считается числовая и буквенно-числовая информация. Режим зависит от версии кода. От его типа так же зависит число пакетов данных. С 1 по 9 версию, блочная длина для числового режима может составлять 10 бит или 4 бита.

Первые 10 бит, следующие за первым блоком указателя режима, содержат информацию о числе символов в коде.

Считанные данные из заголовка выглядят как: 00 01 10 00 00 11 01 01 10 00.

Применив к ним маску соответствующей длины 00 01 10 00 01 10 00 01 10 00, получим последовательность: 00 00 00 00 01 01 01 00 00 00.

Первые 10 бит полученной последовательности (00 00 00 00 01) – это и есть 1 пакет. Биты (01 01) представляют собой число «5».

Числовой режим может использовать как 10 так и 4 битные блоки, если нет нужды в большем чем 4 бита объеме. Это сделано специально, для экономии места.

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

Читать дальше: