Вам ведь ещё не надоели коды? Надеюсь, что нет, поскольку сегодня мы рассмотрим Aztec Code — именно их вы могли видеть на своих смартфонах в электронной версии посадочных талонов на авиарейсы, а может на железнодорожных билетах или ещё где.

Один из таких кодов показан слева от данного текста. Конечно, можно просто взять телефон, открыть специальное приложение для чтения кодов и просто "прочитать" его. А вот если вам интересно, как эти коды записываются, читаются и какую информацию могут содержать, то добро пожаловать под кат.

Aztec Code — следующий в списке кодов, о которых я хочу вам рассказать во всех подробностях. Начнём.

Внимание, под катом — 8 изображений общим размером в 0.8 МБ, 5 таблиц и немного формул.

---

Оглавление

---

01. История Aztec Code и право использования

(Назад | Оглавление | Вперёд)

Эти коды созданы в 1995 году в Welch Allyn Data Collection Inc, а в 1997 на него был выдан патент США номер 5 591 956 (доступен на Google Patents). Часть из рекомендаций и описаний в патенте более не используется. Потому такие коды могут быть несовместимы с современными стандартами. Кроме того, он описывает лишь стандартный вид Aztec Code, но не "компактный" вид, который появился позже.

На данный момент использовать любую версию Aztec Code можно свободно и без ограничений.

Как обычно, есть и ограничивающий фактор, если вы хотите точно соответствовать стандарту ISO/IEC 24778:2008, а доступ к нему — платный (158 CHF — швейцарских франков). Хотя когда это кого-то останавливало?

Чем этот код отличается от любого другого?

• Aztec Code содержит специальную мишень, которая (вместе с дополнительными элементами) позволяет не только точно определить центр кода, но и его ориентацию и точку начала строки данных (Раздел 02), а также размер символа.
• Код использует принцип записи информации от важной (сервисной) к наиболее легко восстанавливаемой (самому информационному сообщению) от центра символа (мишени) к периферии слоями (Раздел 04).
• Вокруг символа Aztec Code не обязательно оставлять "чистую зону". Это связано с тем, что размер символа записан в сервисной информации сразу вокруг мишени (Раздел 06) и вероятность её успешного чтения считается максимальной.
• Aztec Code позволяет использовать произвольное количество слов для коррекции ошибок с помощью кодов Рида-Соломона. Таким образом, степень коррекции ошибок можно контролировать просто добавлением дополнительных слоёв символа (Раздел 07).
• Коды этого вида не требуют добавления "слов-смещений" (пустых слов) между данными и словами коррекции. В результате, все не занятые данными слова используются для коррекции.

---

02. Графическое представление и структура

(Назад | Оглавление | Вперёд)

Рис. 1. Схематическая структура Aztec Code

Каждый стандартный символ Aztec Code (именно такой, как его описывает патент, Рис. 1) состоит из следующих компонентов:

• Мишень (13 х 13 элементов, однозначно определяет центр кода);
• 4 ориентира (определяют ориентацию кода и точку с которой необходимо начать чтение);
• Описания символа (всего 40 бит, содержит информацию о количестве слоёв символа — 5 бит, количестве информационных блоков — 11 битов и коды Рида-Соломона для коррекции ошибок описания — 24 бита);

Все вместе они называются ядром (Core structure) кода (размером 15 x 15).

• Специальная сетка из чередующихся элементов 1 и 0 (Reference), которая позволяет увеличить скорость чтения кода и уменьшить количество ошибок, связанных с позиционированием и геометрической коррекцией тех слоёв, которые находятся далеко от ядра.

Сетку можно поделить на набор вертикальных и горизонтальных линий, шириной в 1 элемент. В таком случае, расстояние между соседними линиями будет 15 элементов, а пересечения любой горизонтальной и вертикальной линии — элемент 1. Такая сетка делит весь Aztec символ на квадраты 15 х 15 элементов, которые называют областями данных (data fields).

Кроме того, существует компактная версия Aztec Code, которая отличается отсутствием reference-сетки, меньшей мишенью (9 x 9 элементов) и ограничением в максимум 4 слоя (Рис. 2).

Рис. 2. Схематическая структура компактного Aztec Code

Количество системной информации в компактной версии кода тоже меньше, потому оно содержит лишь 2 бита для количества слоёв и 6 бит для описания количества данных. Остальные 20 битов содержат коды для коррекции.

---

03. Блоки данных

(Назад | Оглавление | Вперёд)

Рис. 3. Блок данных Aztec Code 5 х 2, как описано в патенте

Пожалуй, это самая сложная часть. Согласно патенту, вся информация в коде представляется в виде блоков размером 5х2 бит (квадратов / элементов). Расположение битов происходит по схеме, показанной на Рис. 3, где "1" представляет собой старший бит, а "10" — младший.

Существует лишь два исключения, при которых блок будет содержать не 10, а лишь 9 информационных битов. Это происходит, если биты от "1" до "9" содержат либо все значения 0 либо все 1. В таком случае, младший бит будет содержать значение 1 либо 0 соответственно. В такой ситуации, последний информационный бит будет находиться уже в следующем блоке данных.

Этот принцип (такая ситуация может возникнуть в 1/256 случаев) используют для того, чтобы любой блок состоящий полностью из 0 или 1 рассматривался сканером как недействительный и был включён в блоки с "наиболее вероятным наличием ошибок".

Если все данные уже распределены (а свободные биты остались), последний блок дополняется элементами 1 (за исключением случая, когда старшие 9 битов получаются всеми 1, тогда младший бит — 0).

В последствии решили, что можно улучшить Aztec Code, а особенно — коррекцию ошибок в нём, если сделать блоки данных переменного размера. Естественно, в одном коде размер всех блоков — константа, а вот для кодов разного размера придумали специальные рекомендации (Табл. 1).

Табл. 1. Размер блока данных Aztec Code в зависимости от размера символа

Несмотря на вариации длины блока, все правила для блоков универсальны, а принцип про невозможность всех одинаковых битов в блоке звучит следующим образом:

Если все $$ старшие биты в блоке равны 0 или 1, то младший бит будет 1 или 0 соответственно, где $$ — количество бит в блоке данных.

---

04. Заполнение

(Назад | Оглавление | Вперёд)

Блоки данных располагаются начиная от ориентира 1 по часовой стрелке. Два блока 5 х 2 бита (3 х 2, 4 х 2 или 6 х 2) находятся рядом друг с другом, соединяясь по короткой стороне.

Для упрощения понимания блоков, стоит рассматривать их как домино размером 1х2 бита, которые являются неделимыми.

Ни один из блоков данных не может "наползать" на reference-сетку. Если же блок не помещается с одной стороны от линий сетки, он делится на две части (Рис. 4), располагаемые вокруг.

Рис. 4. Блок 5 х 2 можно делить так (4 варианта поделить по принципу домино и горизонтальное деление для слоёв 12 и 27)

Когда один слой символа заполнен, начинает заполнятся следующий. Чтобы не путаться в том, как располагать биты в коде "на углах", нужно помнить два правила (которые куда более очевидны из Рис. 5):

• При повороте слоя, бока домино (сторона длиной 2), которые идут после поворота, выравниваются с низом двух домино (2 сторонами длиной 1 каждая) идущих перед поворотом;
• При переходе в следующий слой, низ двух домино нового слоя (2 стороны по 1 биту) выравниваются с боком домино в предыдущем слое.

Рис. 5. Принцип записи слоёв для домино-структуры

Слои 12 и 27 отличаются от всех остальных. Поскольку между параллельными линиями reference-сетки 15 элементов, в них нельзя поместить целое число блоков 5х2 битов. В результате, половину битов размещают с одной стороны сетки, а половину — с другой. Для этого блок делят горизонтально (Рис. 4).

Важным является последовательность заполнения информации в коде. Первым блоком при чтении от ядра кода является последний блок всего сообщения (последний блок коррекции ошибок). Последним же блоком (на наружной части кода) будет первый блок сообщения (первый информационный блок). Такой принцип авторы основывали увеличением вероятности возникновения ошибок при отдалении от ядра кода. Именно по этой же причине сервисная информация (описание символа, Раздел 02) находится в ядре.

---

05. Размер кода и количество информации в нём

(Назад | Оглавление | Вперёд)

Современная размерно-информационная таблица для Aztec Code (Табл. 2) достаточно велика, поскольку кодирование позволяется для слов разной длины. Тем не менее, её достаточно удобно использовать для понимания, сколько же информации помещается в какое количество слоёв.

Подобная таблица есть и для компактных Aztec Code (Табл. 3).

Табл. 3. Количество информации в компактном Aztec Code в зависимости от количества слоёв.

Если ваше сообщение умещается в компактный Aztec Code, рекомендуется использовать его, а не полную версию.

---

06. Служебная информация

(Назад | Оглавление | Вперёд)

Чтение символа мы начнём с ядра. Итак, как было указано ранее (Раздел 02), у нас есть сервисная информация, состоящая из следующих частей.

Количество слоёв

В обычном Aztec Code за эту информацию отвечают первые 5 битов. Соответственно, записанное число $$ может принимать значение от 0 до 31, что соответствует количеству слоёв $$ от 1 до 32.

В компактном Aztec Code есть лишь 2 бита, а потому их значение от 0 до 3 означает количество слоёв $$ от 1 до 4.

Поскольку количество слоёв $$ определяет также размер символа, то определена также ёмкость кода ($$) и количество битов в одном слове ($$).

Длина сообщения

Дальше идёт 6 (значения от 0 до 63, компактный AC) либо 11 битов (значения от 0 до 2 047, обычный AC) значения $$. В результате, количество информационных слов в коде $$ может быть от 0 и до 64 либо 2 048 слов в зависимости от типа символа.

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

Существуют специальные Aztec Code символы для инициализации (программирования) сканеров. В таких символах старший бит длины сообщения равен 1, что обозначает длину сообщения большую чем $$.

Коррекция ошибок

Размер слова сервисной информации — 4 бита, а коррекцию производят с помощью кодов в поле Галуа $$ с многочленом $$. На данный момент я не буду останавливаться на коррекции ошибок, поскольку это отдельная большая тема, которая не касается конкретно Aztec Code.

Направление

Важно знать, что системная информация читается начиная от ориентира 1 (Рис. 1, Рис. 2) по часовой стрелке (ориентиры 1 -> 2 -> 3 -> 4 -> 1). При этом, в словах первым идёт старший бит, а последним — младший.

---

07. Запись данных

(Назад | Оглавление | Вперёд)

Для записи данных используется следующий принцип:

• Символы исходного сообщения последовательно преобразуют в двоичные значения согласно Табл. 4;
• Полученную двоичную строку разбивают на слова длиной $$, учитывая запрет на все одинаковые биты в слове — получают $$ информационных слов;
• К информационным словам добавляются слова для коррекции в количестве $$;
• Полученную последовательность $$ слов размещают в $$ слоёв символа начиная от ориентира 1 (Раздел 02) по принципу, который описан в Разделе 04;
• Если все данные записаны, а наружному слою недостаёт заполненных битов, их заполняют с помощью символов 0.

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

Табл. 4. Кодовые наборы ASCII, которые используются в Aztec Code по умолчанию

• ul, ll, ml, pl, dl — переключения в режимы upper, lower, mixed, punctuation и digit соответственно (l = latch);
• us, ps — переключения в режимы upper и punctuation (s = shift) только для следующего знака (5 битов).

FLG(n) — специальный флаг, который используют для представления разных знаков (не данных). Сюда относится использование других кодовых наборов с помощью ECI (Extended Channel Interpretation) и ещё некоторые специфические функции.

Будьте внимательны, таблица, представленная в патенте на Aztec Code, отличается и на данный момент не используется в кодах.

Байт-режим

Переключатель bs представляет переход в байтовый режим записи с динамической кодировкой длины. За этим символом следует 5 битов.

• Если значение этих 5 битов от 1 до 31 — это количество последующих байтов;
• Если их значение 0, далее следует 11 битов, которые записывают количество байтов минус 31.

В результате, можно записать как отдельные байты, так и строки длиной до 2 047 + 31 байтов.

---

08. Исправление ошибок

(Назад | Оглавление | Вперёд)

Итак, как уже было неоднократно сказано, коррекция ошибок в Aztec Code осуществляется с помощью кодов Рида-Соломона. В отличии от множества других кодов, здесь количество слов для коррекции не фиксировано. Существуют лишь рекомендации касательно их количества.

Неудобство Aztec Code состоит в вариации длины слов. С другой стороны, это улучшает качество исправления ошибок, что может быть доказано математически.

Как используемое поле Галуа, так и примитивный многочлен для расчётов, зависят от количества бит в слове (Табл. 5). В остальном процедура расчётов ничем не отличается от любого другого расчёта кодов Рида-Соломона.

Табл. 5. Параметры для коррекции ошибок с использованием кодов Рида-Соломона

---

09. Определяем Aztec Code

(Назад | Оглавление | Вперёд)

Итак, у нас есть КДПВ. Давайте прочитаем её. Наша мишень — размером 9 х 9 (Рис. 6). Соответственно у нас компактный вариант Aztec Code.

Рис. 6. Наш тестовый код с КДПВ

Поскольку код уже расположен ровно, осталось лишь определить в какую сторону его читать и где начало. Смотрим на ориентиры — всё просто. У нас не отражение и последовательность 1 -> 2 -> 3 -> 4 -> 1 идёт по часовой стрелке — так и будем читать.

---

10. Читаем сервисную информацию

(Назад | Оглавление | Вперёд)

Рис. 7. Читаем сервисную информацию

Следующий шаг — прочитать сервисную информацию (Рис. 7).

Поскольку это компактная версия кода, первые 2 бита означают количество слоёв (3 слоя, поскольку записано 2), а следующие 6 битов — количество слов (22 слова, поскольку записано число 21).

Зная количество слоёв, можно определить, что каждое слово состоит из 8 бит (Раздел 05).

---

11. Читаем весь код

(Назад | Оглавление | Вперёд)

Рис. 8. Читаем код. Для удобства, выделены слова по 8 бит

Воспользовавшись описанным ранее принципом чтения (Раздел 04), можно получить следующую строку, начиная от ядра:

10000101 01110111 10111001 01110110 10110100 10001000 00110110 01100001 00101110 00111010 00001100 01110110 00110110

10010010 01100001 00111100 11110011 11110010 11101010 01010101 11011111 01100100 01010001 10000101 11010110 10000110 01001011 11010001 10010101 10010101

01010001 00100111 00111100 10100000 10101001 01000011 00010010 10000001 11000001 00100110 01000001 10011100 00100010 01000101 10000000 10100000 10101000 00001011 00011010 11010110 01000111

Внимательно посмотрев на код, можно заметить, что использование слов длиной 8 бит позволяет заполнить весь символ без пропусков.

Итак, нам нужно развернуть строку, поскольку информация записана в обратном порядке. Кроме того, нам нужно всего 22 слова.

11100010 01101011 01011000 11010000 00010101 00000101 00000001 10100010 01000100 00111001 10000010 01100100 10000011 10000001 01001000 11000010 10010101 00000101 00111100 11100100 10001010 10101001

Наша информация кодируется лишь 5 битами. Тогда строка буде выглядеть следующим образом:

11100 01001 10101 10101 10001 10100 00000 10101 00000 10100 00000 11010 00100 10001 00001 11001 10000 01001 10010 01000 00111 00000 01010 01000 11000 01010 01010 10000 01010 01111 00111 00100 10001 01010 10100 1

Для удобства переведём в десятичное представление

28 09 21 21 17 20 00 21 00 20 00 26 04 17 01 25 16 09 18 08 07 00 10 08 24 10 10 16 10 15 07 04 17 10 20

(ll)https(ps):(ps)/(ps)?cp xohqgf(ps)%hwiioinfcpis

В общем, получаем ерунду. Попытка #2. Почему так произошло знаете? Всё из-за слова 10000000. В нём лишь 7 бит, а не 8, а потому нужно было быть внимательнее и это увидеть. Помните, не может быть слов из всех 0 или всех 1?

Тогда правильная последовательность (уже развёрнутая) будет такая:

11100010 01101011 01011000 11010000 00010101 00000101 00000001 01000100 10001000 01110011 00000100 11001001 00000111 00000010 10010001 10000101 00101010 00001010 01111001 11001001 00010101 01010011

Что означает:

11100 01001 10101 10101 10001 10100 00000 10101 00000 10100 00000 10100 01001 00010 00011 10011 00000 10011 00100 10000 01110 00000 10100 10001 10000 10100 10101 00000 10100 11110 01110 01001 00010 10101 01001 1

Или

28 09 21 21 17 20 00 21 00 20 00 20 09 02 03 19 00 19 04 16 14 00 20 17 16 20 21 00 20 30 <- переход в Digit режим, дальше идут символы из 4 битов

(0111 0010 0100 0101 0101 0100 11)

-> 07 02 04 05 05 04

Последние два бита 11 — смещение

В результате, в "читаемом виде" строка будет выглядеть следующим образом:

(ll)https(ps):(ps)/(ps)/habr(ps).com(ps)/post(ps)/(dl)502332

Что даёт ссылку на данную публикацию:

https://habr.com/post/502332

Но если вы не верите, попробуйте воспользоваться коррекцией ошибок.

---

12. Полезно знать

(Назад | Оглавление | Вперёд)

Существуют специальные символы Aztec Runes. Они могут кодировать ровно 1 байт информации (значения от 000 до 255). В них используется только ядро компактного Aztec Code, а тот самый один байт записан вместо сервисной информации. Интересно то, что такие руны также поддерживают коррекцию ошибок. Чтобы прочитать Aztec Rune, необходимо выполнить операцию XOR 1010 с каждым из 4-битных слов. Хотя эти коды являются полноценным видом Aztec Code и их поддержка сканерами является обязательной для всех устройств соответствующих стандартам, остальные сканеры (в том числе приложения для смартфонов) не всегда их распознают.

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

Aztec Code поддерживают запись длинных сообщений с разбитием на разные символы. При этом в каждый Aztec Code символ дописывается заголовок, содержащий идентификатор сообщения, отделённый пробелами с обеих сторон и порядковый номер символа. Так одно сообщение можно распределить в максимум 26 символах.

---

13. Полезные ссылки

(Назад | Оглавление | Вперёд)

Описание Aztec Code

• Патент US5591956A (Google Patents)
• Стандарт ISO/IEC 24778:2008 (платный доступ, ISO)

Упоминалось

• ASCII (Wikipedia)

Кроме того

• Таблицы и рисунки этой статьи (GitHub)

---

14. Послесловие

(Назад | Оглавление | Вперёд)

Мы рассмотрели принципы кодирования информации в формате Aztec Code. Хотя они используются, возможно, и не так широко, как некоторые другие двумерные коды, Aztec Code обладают существенными преимуществами. Среди них — возможность широкой вариации количества слов для коррекции ошибок, что недоступно для многих кодов.

Возможно, вам будут также интересны другие статьи цикла Коды step by step:

• о кодах PDF417
• об Aztec Code (данная публикация)

Также, могу предложить прочитать что же делать, когда инструкции к коду нет, а прочесть его интересно (на примере PDF417).

Не забывайте, всегда лучше знать, как что-то работает. Вдруг, оно работает неправильно.

Спасибо за внимание!

---

P.S. Если вы нашли опечатки или ошибки в тексте, пожалуйста, сообщите мне. Это можно сделать выделив часть текста и нажав "Ctrl / ? + Enter", если у вас есть Ctrl / ?, либо через личные сообщения. Если же оба варианта недоступны, напишите об ошибках в комментариях. Спасибо!
P.P.S. Я буду признателен, если вы потратите ещё 60 секунд и ответите на 2 небольших опроса ниже. Спасибо!