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

Итак, давайте разберёмся со всем необходимым для чтения и / или записи PDF417. Ведь не всегда под рукой найдётся смартфон с программой для их чтения. А для записи — и подавно.

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

Оглавление

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

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

PDF417 придумали в компании Symbol Technologies Inc. в 1991 году, а 7 сентября 1993 года на него был выдан патент США под номером 5 243 655 (доступен, к примеру, здесь). На самом деле, патент описывает не просто метод кодирования, а комплексную систему для кодирования и декодирования информации ("System for encoding and decoding data in machine readable graphic form"). Кроме того, не все из рекомендаций в патенте используются на данный момент.

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

Единственный подводный камень: если вы хотите точно соответствовать стандарту ISO/IEC 15438:2015, описывающему PDF417, — доступ к нему стоит 198 CHF (швейцарских франков). Именно он описывает все необходимые словари и прочее, однако большую часть информации можно легко найти в интернете. Патент, упомянутый выше, этой информации не содержит.

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

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

Каждый символ (код) PDF417 (Рис. 1) — это набор строк информации, представленной в виде штрихового кода. Каждая строка состоит из стартового паттерна, набора ключевых слов (два из которых называются левым и правым индикаторами и помогают в автоматизированном декодировании) и стоп паттерна. Слова из разных строк формируют колонки (столбцы).

Как количество строк, так и количество столбцов может варьироваться. Символ PDF417 может состоять из минимум 3 и максимум 90 строк, а также от 3 до 30 столбцов включительно.

Рис. 1. Структура PDF417 символа

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

Каждое слово представляют в виде уникальной $$последовательности ($$). Все возможные слова делятся на 3 взаимоисключающие группы (кластера), то есть в каждом кластере содержаться одни и те же "значения", представленные разными "словами". Кроме того, слова могут быть представлены в виде $$последовательности, где каждое значение $$. Это также помогает избежать ошибок при сканировании кодов.

Каждая строка PDF417 символа использует только один из кластеров последовательно. Таким образом, если один из кластеров используется строками $$, то второй — строками $$, а третий — строками $$. Это нужно для правильного определения строки при автоматическом сканировании (Рис. 2), поскольку соседние строки не могут содержать слова одной группы.

Номер кластера однозначно определяется из $$ или $$последовательности по одной из формул:

$$,
$$,

где $$ — остаток от деления на 9.

На самом деле, можно было бы использовать не 3 разных кластера, а все 9 возможных, но это увеличило бы вероятность дополнительных ошибок. Номер кластера можно определить также из номера строки: $$.

Всего PDF417 использует 929 слов (от 000 до 928).

03. Компоненты символа

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

Каждый символ состоит из (Рис. 2):

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

Рис. 2. Компоненты символа PDF417

В случае, если количество слов с полезной информацией и проверочных слов недостаточно для формирования символа, между ними добавляются отступы (на практике в качестве отступа используется слово 900, об этом далее), которые занимают позиции $$.

04. Режимы

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

Как уже было сказано, коды PDF417 содержат слова от 000 до 928 в виде трёх разных кластеров. Таким образом, в коде может встретиться всего 2 787 разных слов.

Слова от 000 до 899 включительно используются для записи полезной информации в одном из возможных режимов кодирования.

Слова 900 : 928 — сервисные и не кодируют информацию (Табл. 1). На сегодня нам потребуются лишь слова 900, 901, 902, 913 и 924, которые сообщают об использовании одного из стандартных режимов кодирования.

Табл. 1. Сервисные слова PDF417. Выделены те, которые будут нам интересны

PDF macro позволяет разбить длинное сообщение на несколько PDF417 символов. При этом каждый символ содержит идентификатор сообщения, порядковый номер блока сообщения (для восстановления правильной последовательности) и другую информацию.

ECI / GLI — Extended Channel Interpretation / Global Label Identifier — система надстроек, которая позволяет кодировать нестандартные символы с помощью штриховых кодов. Так, возможно подключить один из международных наборов символов (к примеру, стандартным является GLI 0, именно эти таблицы приведены далее), наборов общего назначения либо ваших персональных наборов символов.

04.a) Текстовый режим (TC, Text Compaction Mode)

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

Этот режим стандартный для символов PDF417 (то есть именно с него начинается весь символ). У текстового режима есть 4 разных подгруппы:

• Alpha (активируется при переходе в текстовый режим);
• Lower case;
• Mixed;
• Punctuation.

Табл. 2. Подгруппы текстового режима в стандартной интерпретации GLI 0

• al, ll, ml и pl — переключения в режимы alpha, lower case, mixed и punctuation соответственно (l = latch);
• as и ps — переключения в режимы alpha и punctuation (s = shift) только для следующего слова.

Одно слово в базисе 900 содержит 2 символа из таблицы выше по правилу:

$$,

Где $$ — значение в базисе 900, $$ — первый символ, $$ — второй. Иногда символы указывают как $$ и $$ соответственно.

Если данные заканчиваются словом, в которое нужно включить только один символ, то он является $$-значением, а в качестве $$-значения используется значение 29.

Использование ещё одного перехода после shift-перехода запрещено. Ограничений на использование переходов после latch-перехода нет.

04.b) Байт-режим (BC, Byte Compaction Mode)

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

Данный режим позволяет записывать последовательность байтов с помощью последовательности кодовых слов в базисе 900. Для этого нужно совершить переход от базиса 256. Этот режим включается двумя разными сервисными словами:

• 901 (если количество байтов кратно 6);
• 924 (если не кратно).

Во втором случае, каждые 6 байтов представляются в виде 5 слов с помощью прямого перехода от базиса 256 в базис 900. К примеру, в случае последовательности байтов 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, переход будет следующим (Рис. 3).

Рис. 3. Кодирование, байт-режим

Тогда код должен содержать следующую последовательность слов:

924, 001, 620, 089, 074, 846.

Если же количество байтов не кратно 6, то все группы по 6 записываются в виде групп из 5 слов, а оставшиеся — в начальном виде. Таким образом, последовательность 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09 будет записана следующим образом:

901, 001, 620, 089, 074, 846, 007, 008, 009.

Кроме того, байт-режим кодирования можно включить лишь для следующего слова с помощью сервисного слова 913.

04.c) Числовой режим (NC, Numeric Compaction Mode)

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

Числовой режим позволяет записать данные с помощью перехода из базиса с основой 10 в базис с основой 900. Соответственно, такой режим поддерживает запись цифр от 0 до 9. В результате, каждые 44 цифры можно записать в виде 15 слов.

Данный режим активируется сервисным словом 902. Хотя таким образом можно записать число произвольной длины, рекомендуется использовать его для всех чисел начиная от 13 знаков. Такой метод, позволяющий записать 3 цифры (на самом деле, 2.93) одним словом, является более компактным, чем текстовый режим (2 символа на слово).

Для перехода в базис 900 нужно дописать 1 к числу слева, а дальше выполнить переход как показано на Рис. 4. Обратный переход вполне очевидный, остаётся лишь убрать лишнюю 1 слева.

Рис. 4. Кодирование и декодирование, числовой режим

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

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

Давайте начнём с самого простого. В любом символе PDF417 присутствует как минимум 2 слова в области ответственной за коррекцию ошибок. Кроме того, коды характеризуются уровнем коррекции ошибок, для которых нужно разное количество дополнительных символов (Табл. 3).

Табл. 3. Уровни коррекции ошибок в PDF417

Различают два вида ошибок:

• Известна позиция ошибки, но не известно правильное значение (erasures), назовём "систематической ошибкой";
• Ошибки, присутствующие в коде, положение которых не известно (errors), назовём "случайной ошибкой".

Введём следующие параметры:

$$количество систематических ошибок;
$$количество случайных ошибок;
$$уровень коррекции;
$$количество слов для коррекции ошибок.

Тогда выполняется следующее условие:

2 слова, которые присутствуют в символе в любом случае, используются для проверки, не возникла ли случайная ошибка при распознавании.

Вводится также понятие Error Correction Capacity, которое показывает, сколько же ошибок обоих видов мы можем исправить. Очевидно, что если все дополнительные слова используются для исправления систематических ошибок, то шанс случайной возрастает. Потому для всех уровней, кроме $$, считается, что:

$$.

Именно потому в патенте количество слов для коррекции ошибок на 2 меньше, чем его часто указывают сейчас. Эти 2 слова правильно называть контрольной суммой.

К примеру, с уровнем коррекции $$, можно исправить 13 систематических ошибок, либо 7 случайных, либо их комбинацию, которая всё ещё соответствует неравенству (9 систематических И 2 случайных и т.д.).

Для коррекции ошибок используются коды Рида-Соломона в поле Галуа $$. На данный момент я не буду на них останавливаться.

Существуют также рекомендации относительно минимального уровня коррекции ошибок (Табл. 4).

Табл. 4. Минимальный рекомендуемый уровень коррекции ошибок

06. Обязательные неинформационные слова

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

Как упоминалось раньше (Раздел 03), первое слово каждого кода означает длину полезных данных в символе PDF417.

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

Рис. 5. Правила записи левых и правых индикаторов

07. Словари

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

Словарь в виде x-последовательностей, 17-битных представлений на GitHub

Как упоминалось ранее (Раздел 02), словарь PDF417 состоит из 3 кластеров (0, 3 и 6) по 929 слов. Периодически их представляют в виде 17-битного числа, но я считаю такой вариант неудобным в сравнении с x-последовательностью. В любом случае, вы вольны решать, как вам удобнее, а потому выше приведены ссылки на оба варианта записи, а начало словарей приведено в Табл. 5.

Табл. 5. Первые 20 слов словаря в виде x-последовательностей

08. Стандартная 8-битная таблица символов

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

GLI 0

В качестве стандартной таблицы символов используется ASCII таблица для символов 0:127. Символы 128:255 представлены расширенным набором PC 437.

Табл. 6. Таблица GLI 0, которая используется кодами PDF417

GLI 1

Следующий набор символов соответствует стандарту ISO 8859-1 (Википедия).

09. Определяем код как PDF417, выравниваем и находим минимальный элемент

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

Пришло время прочитать наш первый PDF417 символ.

Хотя этот шаг кажется совсем необязательным, стоит помнить, что PDF417 характеризуется уникальными старт- и стоп-паттернами, которые представлены x-последовательностями 81111113 и 711311121 (18 модулей) соответственно.

Кроме того, поскольку эти паттерны одинаковы в каждой строке их легко использовать для выравнивания PDF417 символа (Рис. 6). Хотя это и более актуальная задача при автоматическом сканировании, читать код необходимо перпендикулярно к старт- и стоп-паттернам.

Рис. 6. Шаг 0 при чтении PDF417

10. Считаем и сопоставляем со словарями

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

На необходимо определить количество информационных слов. Оно содержится в первом слове кода (строка 0, слово 0). К примеру, в нашем случае это значение равно 19 (Рис. 7). Кроме того, стоит проверить уровень коррекции ошибок, который можно узнать с помощью левых или правый индикаторов (не забываем, нужно выбрать правильную строку, Раздел 06). В результате, у нас должно быть 1 слово-длина, 18 слов-данных и 8 проверочных слов, то есть 27, что соответствует действительности.

Теперь разобьём код на строки. Это поможет ускорить чтение, поскольку необходимо использовать разные кластеры словаря.

Рис. 7. Узнаём длину данных, характеристики кода

11. Переводим PDF417 в текстовый вид и проверяем режимы кодирования

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

Итак, каждому слову необходимо сопоставить одно из значений от 000 до 928 (Рис. 8). В результате, получаем последовательность чисел, с которой далее будет удобно работать.

Рис. 8. Переводим символ в текстовое представление

Следующий шаг — проверить наличие сервисных слов 900 : 928. Как видно на Рис. 8, в данном коде таких нет. Соответственно, вся информация закодирована с использованием текстового режима (TC, Раздел 04.a).

12. Переводим в привычный нам вид

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

Поскольку мы знаем, что используется только текстовый режим, каждое слово можно расшифровать как 2 символа по формуле:

То есть чтобы определить $$ необходимо выполнить целочисленное деление на 30, а для $$ — взять остаток от деления на 30.

Тогда всё сообщение можно записать как:

(27)(07) (19)(19) (15)(18) (28)(14) (19)(19) (28)(07) (27)(00) (01)(17) (29)(17) (02)(14) (12)(29) (19)(15) (14)(18) (19)(28) (19)(05) (00)(00) (09)(06) (02)(29)

Или же (используя Табл. 2):

(ll)https(ml)://(al)H(ll)abr(ps).com(ps)/post(ml)/500962(ps)

Подробнее о переключателях (ll), (ml), (al) и (ps) было в Разделе 04.a.

Что в стандартном виде будет выглядеть как:

https://Habr.com/post/500962

Итак, код скрывает ссылку на данную публикацию. С помощью дополнительных 8 символов можно проверить наличие ошибок в результатах (Раздел 05).

13. Особенности автоматизированного чтения

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

Автоматическое сканирование часто производится дважды — слева направо и наоборот. Это позволяет минимизировать количество ошибок.

Как и в случае ручного чтения, при автоматическом нужно выполнить поиск и выравнивание символа. Поскольку в жизни редко можно выровнять код и сканер идеально, необходимо чтобы линия сканирования не проходила через более чем 3 разные строки. В таком случае всегда можно будет определить, какие слова принадлежат какой строке (поскольку они находятся в разных кластерах).

Ещё один пункт, важный для неидеальных условий — чтение не $$последовательности, а $$последовательности (Раздел 02). Поскольку PDF417 рассчитаны в том числе на печать на физических носителях, возможно размытие чернил (и т.д.), которое может привести к тому, что заполненные группы модулей станут шире, а пустые — уже. Проводя сканирование от края до такого же края, такие ошибки можно минимизировать.

Следующим шагом является определение уровня коррекции ошибок и построение матрицы слов. Кроме того, строится ещё одна матрица, которая состоит из весов (уровня доверия каждому значению). Слова с низким уровнем доверия в последствии проверяются на ошибки первыми.

14. Минимизация кода

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

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

1. Пусть P - текущая точка кодирования
2. Считаем, что мы используем текстовый режим (900)
3. Пусть N - количество цифр, которые нужно закодировать, попавшие в точку P

    4. Если N ? 13
        5. Переходим в числовой режим (902)
        6. Кодируем в числовом режиме
        7. Уточняем P
        8. Переходим к шагу 3

    9. Если N < 13
        10. Пусть T - количество символов в последовательности, кодируемой в
            текстовом режиме. Последовательность прерывается при переходе в 
            другой режим (901, 902, 913, 924) или при появлении 
            последовательности в 13 цифр.

        11. Если T ? 5
            12. Переходим в текстовый режим (900)
            13. Кодируем символы
            14. Уточняем P
            15. Переходим к 3

        16. T < 5
            17. Пусть B - длина бинарной кодируемой последовательности, 
                начиная от P. Последовательность прерывается при условиях 11
                или 4.

            18. B == 1 & текущий режим - текстовый
                19. Переходим в байтовый режим на 1 слово (913)
                20. Кодируем один байт
                21. Уточняем P
                22. Переходим к шагу 3

            23. Иначе
                24. Переходим в байтовый режим (901 или 924 в зависимости от
                    количества байтов, Раздел 04.b)
                25. Кодируем
                26. Уточняем P
                27. Переходим к шагу 3

15. Размеры, пропорции и чистые зоны

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

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

Кроме того, вокруг PDF417 необходимо оставлять "чистую зону", размером не менее 2 ширин модуля.

Посчитать размер символа можно с помощью следующих формул:

где
$$ — высота;
$$ — ширина;
$$ — количество строк;
$$ — количество столбцов;
$$ — высота модуля (строки);
$$ — ширина модуля;
$$ — размер чистой зоны (минимум $$).

16. Компактный (усечённый) PDF417

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

В случае использования PDF417 в "чистой" среде (символ не может быть случайно повреждён и чистые зоны вокруг символа достаточно велики), можно использовать усечённый режим PDF417 (Truncated PDF417, Рис. 9).

Он работает следующим образом:

• Правые индикаторы упускаются (вся информация в любом случае дублируется в левых индикаторах, Раздел 06);
• Стоп-паттерн сокращается до 1 модуля.

В результате ширина символа сокращается на 34 модуля и формула из Раздела 15 может быть переписана:

Рис. 9. Усечённый PDF417 (содержит ту же информацию, что и рассмотренный ранее код)

Стоит помнить, что у такого метода кодирования есть и недостатки:

• Скорость распознавания символа падает, поскольку без правых индикаторов сложнее выровнять линию сканирования;
• Вероятность возникновения ошибок декодирования из-за деградации кода возрастает.

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

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

Описание PDF417

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

Упоминалось

• ASCII (Wikipedia)
• PC 437 (Wikipedia)
• Стандарт ISO 8859-1 (платный доступ, ISO) — один из возможных 8-битных наборов символов для кодирования в виде PDF417. Описание (Wikipedia)

Кроме того

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

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

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

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

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

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

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

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

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

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