Ацтекский кодекс
 | Эта статья нуждается в дополнительных цитатах для проверки . ( июль 2010 г. ) |
Кодекс ацтеков — это матричный код, изобретенный Эндрю Лонгакром-младшим и Робертом Хасси в 1995 году. [1] Кодекс был опубликован компанией AIM, Inc. в 1997 году. Хотя ацтекский кодекс был запатентован , этот патент официально стал общественным достоянием . [2] Кодекс ацтеков также опубликован как стандарт ISO/IEC 24778:2008. Названный в честь сходства центрального шаблона искателя с ацтекской пирамидой , Aztec Code потенциально может использовать меньше места, чем другие матричные штрих-коды, поскольку не требует окружающей пустой «тихой зоны».
Структура
[ редактировать ]Символ построен на квадратной сетке с рисунком «яблочко» в центре для поиска кода. Данные кодируются концентрическими квадратными кольцами вокруг шаблона «яблочко». Центральное яблочко имеет размер 9×9 или 13×13 пикселей , а один ряд пикселей вокруг него кодирует основные параметры кодирования, образуя «ядро» из квадратов 11×11 или 15×15. Данные добавляются «слоями», каждый из которых содержит два кольца пикселей, что дает общие размеры 15×15, 19×19, 23×23 и т. д.
В углах ядра имеются метки ориентации, позволяющие читать код при вращении или отражении. Декодирование начинается с угла с тремя черными пикселями и продолжается по часовой стрелке к углам с двумя, одним и нулем черных пикселей. Переменные пиксели в центральном ядре кодируют размер, поэтому нет необходимости отмечать границу кода пустой «тихой зоной», хотя некоторые считыватели штрих-кодов требуют ее.
Ядро компактного ацтекского кода (красная восходящая диагональная штриховка), показывающее центральный яблочко, четыре метки ориентации (синяя диагональная штриховка) и место для 28 бит (по 7 бит на каждую сторону) кодовой информации (зеленая горизонтальная линия). штриховка). Первое кольцо данных начинается за его пределами (серая нисходящая диагональная штриховка).
Ядро полного кода ацтеков. Между метками ориентации для параметров кодирования доступно 40 бит.
Данные сообщения размещаются по спирали вокруг ядра. Сообщение режима начинается с «01011100», указывая 01 2 +1 = 2 уровня и 011100 2 +1 = 29 кодовых слов данных (по 6 бит каждый).
Компактное ядро ацтекского кода может быть окружено от 1 до 4 слоев, создавая символы размером от 15×15 (место для 13 цифр или 12 букв) до 27×27. Дополнительно существует специальная «руна» размером 11×11, кодирующая один байт информации. Полное ядро поддерживает до 32 слоев размером 151×151 пиксель, которые могут кодировать 3832 цифры, 3067 букв или 1914 байт данных.
Какая бы часть символа не использовалась для основных данных, она используется для коррекции ошибок Рида-Соломона , а разделение полностью настраивается, между пределами 1 слова данных и 3 контрольных слов. Рекомендуемое количество контрольных слов составляет 23% от емкости символа плюс 3 кодовых слова. [3]
Предполагается, что Aztec Code будет создавать читаемые коды с помощью различных технологий печати. Он также хорошо подходит для дисплеев сотовых телефонов и других мобильных устройств.
Кодирование
[ редактировать ]Процесс кодирования состоит из следующих этапов:
- Преобразование исходного сообщения в строку битов
- Вычисление необходимого размера символа и сообщения режима, которое определяет размер кодового слова Рида – Соломона.
- Побитовая вставка сообщения в кодовые слова Рида – Соломона.
- Дополнение сообщения до границы кодового слова
- Добавление проверочных кодовых слов
- Расположение полного сообщения по спирали вокруг ядра
Все преобразования между битовыми строками и другими формами выполняются в соответствии с соглашением с прямым порядком байтов (сначала наиболее значимый бит).
Набор символов
[ редактировать ]Могут быть закодированы все 8-битные значения плюс два escape-кода:
- FNC1 — escape-символ, используемый для обозначения наличия идентификатора приложения, так же, как в стандарте GS1-128 .
- ECI, escape, за которым следует 6-значный код интерпретации расширенного канала , который определяет набор символов, используемый для интерпретации следующих байтов.
По умолчанию коды 0–127 интерпретируются в соответствии с ANSI X3.4 ( ASCII ), а 128–255 интерпретируются в соответствии с ISO/IEC 8859-1 : латинский алфавит № 1. Это соответствует ECI 000003.
Байты преобразуются в 4- и 5-битные коды в зависимости от текущего режима декодирования с кодами сдвига и фиксации для изменения режима. Байтовые значения, недоступные таким образом, могут быть закодированы с использованием общего кода «двоичного сдвига», за которым следует длина и количество 8-битных кодов.
При изменении режимов сдвиг влияет только на интерпретацию одного следующего кода, тогда как защелка влияет на все последующие коды. В большинстве режимов используются 5-битные коды, но в цифровом режиме используются 4-битные коды.
| Код | Режим | Код | Режим | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| Верхний | Ниже | Смешанный | Точка | цифра | Верхний | Ниже | Смешанный | Точка | |||
| 0 | P/S | P/S | P/S | ФЛГ( н ) | P/S | 16 | ТО | тот | ^\ | + | |
| 1 | СП | СП | СП | ЧР | СП | 17 | П | п | ^] | , | |
| 2 | А | а | ^ А | ЧР ЛФ | 0 | 18 | вопрос | д | ^^ | - | |
| 3 | Б | б | ^ Б | . СП | 1 | 19 | Р | р | ^_ | . | |
| 4 | С | с | ^ С | , ИП | 2 | 20 | С | с | @ | / | |
| 5 | Д | д | ^ Д | : СП | 3 | 21 | Т | т | \ | : | |
| 6 | И | и | ^Э | ! | 4 | 22 | В | в | ^ | ; | |
| 7 | Ф | ж | ^Ф | " | 5 | 23 | V | v | _ | < | |
| 8 | Г | г | ^Г | # | 6 | 24 | В | В | ` | = | |
| 9 | ЧАС | час | ^ Ч | $ | 7 | 25 | Х | х | | | > | |
| 10 | я | я | ^Я | % | 8 | 26 | И | и | ~ | ? | |
| 11 | Дж | дж | ^Дж | & | 9 | 27 | С | С | ^? | [ | |
| 12 | К | к | ^К | ' | , | 28 | Л/Л | НАС | Л/Л | ] | |
| 13 | л | л | ^Л | ( | . | 29 | М/Л | М/Л | Е/Л | { | |
| 14 | М | м | ^М | ) | Е/Л | 30 | Д/Л | Д/Л | прибыль/убыток | } | |
| 15 | Н | н | ^[ | * | НАС | 31 | Б/С | Б/С | Б/С | Е/Л | |
- Начальный режим «Верхний».
- x/S = переход в режим x на один символ; B/S = переход к 8-битному двоичному коду
- x/L = фиксация режима x для следующих символов
- Пункт-коды 2–5 кодируют по два байта каждый.
- В таблице перечислены символы ASCII, но закодированы значения байтов, даже если используется набор символов, отличный от ASCII.
За B/S (двоичным сдвигом) следует 5-битная длина. Если значение не равно нулю, это означает, что следуют 1–31 8-битные байты. Если ноль, 11 дополнительных битов длины кодируют количество следующих байтов меньше 31. (Обратите внимание, что для 32–62 байтов две 5-битные последовательности сдвига байтов более компактны, чем одна 11-битная.) В конце двоичной последовательности: возобновляется предыдущий режим.
За FLG( n ) следует 3-битное значение n . n =0 кодирует FNC1. За n = 1–6 следуют 1–6 цифр (в цифровом режиме), которые дополняются нулями, образуя 6-битный идентификатор ECI. n =7 зарезервировано и в настоящее время незаконно.
Сообщение о режиме
[ редактировать ]Сообщение режима кодирует количество уровней ( L слоев, закодированных как целое число L -1) и количество кодовых слов данных ( кодовых слов D , закодированных как целое число D -1) в сообщении. Все остальные кодовые слова используются в качестве проверочных кодовых слов.
Для компактных ацтекских кодов количество слоев кодируется как 2-битное значение, а количество кодовых слов данных — как 6-битное значение, в результате чего получается 8-битное слово режима. Для полных кодов ацтеков количество слоев кодируется 5 битами, а количество кодовых слов данных кодируется 11 битами, что составляет 16-битное слово режима.
Слово режима разбивается на 2 или 4 4-битных кодовых слова в GF(16) и добавляются 5 или 6 контрольных слов Рида-Соломона, образуя 28- или 40-битное сообщение режима, которое заворачивается в 1-пиксельный код. слой вокруг ядра.
Поскольку компактный ацтекский код с L+1-слоем может содержать больше данных, чем полный код с L-слоем, полные коды с менее чем 4 слоями используются редко.
Самое главное, количество слоев определяет размер используемых кодовых слов Рида-Соломона. Это варьируется от 6 до 12 бит:
| Биты | Поле | Полиномиальный | Используется для |
|---|---|---|---|
| 4 | ГФ(16) | х 4 + х +1 | Сообщение о режиме |
| 6 | ГФ(64) | х 6 + х +1 | 1–2 слоя |
| 8 | ГФ(256) | х 8 + х 5 + х 3 + х 2 +1 | 3–8 слоев |
| 10 | ГФ(1024) | х 10 + х 3 +1 | 9–22 слоя |
| 12 | ГФ(4096) | х 12 + х 6 + х 5 + х 3 +1 | 23–32 слоя |
Размер кодового слова b — это наименьшее четное число, которое гарантирует, что общее количество кодовых слов в символе меньше предела в 2. б −1, что можно исправить кодом Рида–Соломона.
Как упоминалось выше, рекомендуется зарезервировать для исправления не менее 23% доступных кодовых слов плюс 3, а размер символа выбирать такой, чтобы сообщение помещалось в доступное пространство.
Битовая начинка
[ редактировать ]Биты данных разбиваются на кодовые слова, причем первый бит соответствует наиболее значимому коэффициенту. При этом кодовые слова «все нули» и «все единицы» избегаются путем вставки битов : если первые b -1 бит кодового слова имеют одинаковое значение, в поток данных вставляется дополнительный бит с дополнительным значением. Эта вставка происходит независимо от того, имел ли последний бит кодового слова то же значение или нет.
Также обратите внимание, что это применимо только к строкам из b -1 бит в начале кодового слова . Допускаются более длинные строки идентичных битов, если они выходят за границу кодового слова.
При декодировании кодовое слово, состоящее из всех нулей или всех единиц, может считаться стиранием и корректироваться более эффективно, чем общая ошибка.
Этот процесс делает сообщение длиннее, и окончательное количество кодовых слов данных, записанных в сообщении режима, неизвестно до тех пор, пока оно не будет завершено. В редких случаях может потребоваться перейти к следующему по величине символу и начать процесс заново, чтобы сохранить минимальную долю контрольных слов.
Заполнение
[ редактировать ]После заполнения битов строка данных дополняется до границы следующего кодового слова путем добавления 1 бита. Если это приведет к тому, что кодовое слово будет состоять из всех единиц, последний бит изменится на ноль (и будет проигнорирован декодером как бит вставки битов). При декодировании биты заполнения могут быть декодированы как коды сдвига и фиксации, но это не повлияет на содержимое сообщения. Читатель должен принять и игнорировать частичный код в конце сообщения, если он состоит из одних единиц.
Кроме того, если общее количество битов данных, доступных в символе, не кратно размеру кодового слова, к строке данных добавляется соответствующее количество нулевых битов, чтобы занять дополнительное пространство. Эти биты не включаются в вычисление контрольного слова.
Проверьте кодовые слова
[ редактировать ]И к слову режима, и к данным должны быть добавлены контрольные слова, чтобы заполнить доступное пространство. Это вычисляется путем добавления K контрольных слов так, что все сообщение кратно полиному Рида – Соломона ( x −2)( x −4)...( x −2 К ).
Обратите внимание, что контрольные слова не подлежат заполнению битами и могут быть «все ноль» или «все единицы». Таким образом, невозможно обнаружить стирание контрольного слова.
Размещение сообщения
[ редактировать ]
Полный символ ацтекского кода, помимо ядра, имеет «опорную сетку» из чередующихся черных и белых пикселей, занимающих каждую 16-ю строку и столбец. Эти известные пиксели позволяют читателю поддерживать выравнивание по пиксельной сетке больших символов. Для четырех слоев (31×31 пикселей) он состоит только из одиночных линий, идущих наружу от ядра, продолжающих чередующийся узор. Однако внутри 5-го слоя вставляются дополнительные строки и столбцы чередующихся пикселей ±16 пикселей от центра, поэтому 5-й слой расположен ±17 и ±18 пикселей от центра, а 5-слойный символ имеет размер 37×37 пикселей. .
Аналогично, дополнительные строки и столбцы эталонной сетки вставляются в пределах ±32 пикселей от центра, что делает 12-слойный символ размером 67×67 пикселей. В этом случае 12-й слой занимает кольца ±31 и ±33 пикселя от центра. Шаблон продолжается бесконечно наружу, с 15-пиксельными блоками данных, разделенными строками и столбцами опорной сетки.
Один из способов создания символа — полностью удалить опорную сетку и начать с ядра размером 14×14 пикселей с центром в белом квадрате размером 2×2 пикселя. Затем разбейте его на блоки размером 15×15 пикселей и вставьте между ними справочную сетку.
Сообщение о режиме начинается в верхнем левом углу ядра и обтекает его по часовой стрелке слоем толщиной в 1 бит. Он начинается со старшего бита числа слоев и заканчивается контрольными словами. Компактный ацтекский код разбивается на четыре 7-битные части, чтобы оставить место для меток ориентации. Полный ацтекский код разбивается на четыре 10-битных фрагмента, каждый из которых делится пополам опорной сеткой.
В некоторых случаях общая емкость матрицы не делится поровну на полные кодовые слова. В таких случаях основное сообщение вначале дополняется нулевыми битами. Эти биты не включаются в расчет контрольного слова и их следует пропускать во время декодирования. Общую емкость матрицы для полного символа можно рассчитать как (112+16*L)*L для полного ацтекского кода и (88+16*L)*L для компактного ацтекского кода, где L — размер символа в слоях. . [4] Например, общая емкость матрицы компактного ацтекского кода с 1 слоем составляет 104 бита. Поскольку кодовые слова состоят из шести битов, это дает 17 кодовых слов и два дополнительных бита. Два нулевых бита добавляются к сообщению в качестве дополнения и должны быть пропущены во время декодирования.
Дополненное основное сообщение начинается в верхнем левом углу всего символа и вращается вокруг него против часовой стрелки слоем толщиной в 2 бита, заканчиваясь непосредственно над верхним левым углом ядра. При этом заполненные битами слова данных, для которых могут быть обнаружены стирания, помещаются во внешние слои символа, которые наиболее склонны к стиранию. Контрольные слова хранятся ближе к ядру. Последнее контрольное слово заканчивается чуть выше верхнего левого угла яблочка.
Когда ядро находится в стандартной ориентации, первый бит первого слова данных помещается в верхний левый угол, а дополнительные биты размещаются в столбце шириной 2 бита слева направо и сверху вниз. Это продолжается до тех пор, пока не останется 2 строки от нижней части символа, когда шаблон повернется на 90 градусов против часовой стрелки и продолжится в строке высотой 2 бита снизу вверх и слева направо. После четырех четвертных слоев одинакового размера спираль продолжается с верхнего левого угла следующего внутреннего слоя и, наконец, заканчивается на один пиксель выше верхнего левого угла ядра.
Наконец, 1 бит печатается как черные квадраты, а 0 бит — как белые квадраты.
Использование
[ редактировать ]
Транспорт
[ редактировать ]Коды Aztec широко используются для оформления транспортных билетов.
Ацтекский код был выбран авиакомпаниями ( стандарт IATA BCBP ) для электронных посадочных талонов. Некоторые авиакомпании отправляют ацтекские коды на мобильные телефоны пассажиров в качестве посадочных талонов. Они часто интегрируются с приложениями на телефонах пассажиров, включая Apple Wallet .
Ацтекские коды также используются на железных дорогах, в том числе в Тегеранском метро , Британской национальной железной дороге , [5] Eurostar , Deutsche Bahn , TCDD Tasımacılık , DSB , SJ , České dráhy , Словацкие железные дороги , Словенские железные дороги , Хорватские железные дороги , Trenitalia , Nederlandse Spoorwegen , Pasažieru vilciens , PKP Intercity , VR Group , Via Rail , Швейцарские федеральные железные дороги , SNCB и SNCF для билетов продаются онлайн и распечатываются покупателями или отображаются на экранах мобильных телефонов. Код Aztec сканируется ручным сканером персоналом поезда или на турникете для проверки билета.
Правительственный
[ редактировать ]Документы о регистрации автомобиля в Польше содержат краткую информацию, сжатую алгоритмом NRV2E и закодированную как Aztec Code. Ведутся работы по тому, чтобы автостраховщики могли автоматически заполнять соответствующую информацию на основе цифровых фотографий документа в качестве первого шага при заключении нового договора страхования.
Федеральная налоговая служба России кодирует информацию о платежах в налоговых уведомлениях как Aztec Code.
Коммерческий
[ редактировать ]Многие законопроекты в Канаде теперь также используют эту технологию, включая EastLink , Shaw Cable и Bell Aliant .
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ * US 5591956 , Лонгакр-младший, Эндрю и Хасси, Роберт, «Структура и символика кодирования двумерных данных для использования с оптическими считывателями», опубликовано 7 января 1997 г.
- ^ Официальный вестник . Патентное ведомство США. 17 июня 1997 г.
Настоящим объявляю для общественности весь срок действия указанного патента.
Нажмите «изображения», затем «исправление», чтобы увидеть переход в общественное достояние. - ^ Адамс, Расс. «Страница двумерного штрих-кода» . Архивировано из оригинала 30 апреля 2010 года . Проверено 14 июля 2022 г.
- ^ «Спецификация Aztec Code (без Small Aztec)» [Спецификация Aztec Code (без Small Aztec)] (на русском языке). Архивировано из оригинала 25 февраля 2020 года.
- ^ «Реверсивные билеты на мобильные железные дороги Великобритании» . эта.ст. 31 января 2023 г. Проверено 5 февраля 2023 г.
