Штрихкоды UPC

Первым широко распространённым форматом штрихкода был американский стандарт штрихкода UPC (Universal Product Code). Код создавался для решения проблемы автоматизации торговли и учёта продукции, произведённой множеством различных предприятий. При разработке кода ставились следующие требования:

1. Кодирует последовательности цифр
2. Как можно более простой
3. Состоит из тёмных и светлых полос – для простоты нанесения и распознавания
4. Должен иметь механизм защиты от ошибок – на случай, если код стёрся или неправильно пропечатался
5. Должен читаться в обоих направлениях – на случай, если кассир отсканировал его “вверх ногами”
6. Каждый товар должен иметь уникальный код – даже два одинаковых товара, произведённых разными предприятиями, должны иметь различные коды

Структура UPC-A

UPC-12 (UPC-A) – наиболее распространённый вариант кода UPC. Кодирует последовательность из 12 десятичных цифр:

• первая цифра – вид продукции
• следующие пять цифр – код предприятия
• следующие пять цифр – код товара
• последняя цифра – контрольное число, нужно для обнаружения ошибок

Вид продукции

Первая цифра кода. Определяет, какую информацию несёт в себе остальная часть кода.

• 0, 1, 6-9 – для основной части товаров. Большинство штрихкодов имеет такой вид (в дальнейшем рассматривается этот вариант)
• 2 – внутренний код предприятия для весовых товаров. Предприятие само определяет, как кодировать такой товар
• 3 – лекарства
• 4, 5 – внутренний код предприятия для купонов, скидочных карт и т. п.

Код предприятия

Следующие пять цифр указывают на производителя товара. Код предприятия выдаётся специальной международной организацией, которая следит за уникальностью кодов.

Код товара

Каждый тип товара предприятие должно кодировать своим уникальным пятизначным кодом. Например, одинаковые рубашки разного размера должны кодироваться различными кодами. Вопреки частому заблуждению, код товара не несёт никакой специальной информации, и зачастую коды присваиваются товарам просто по порядку. Например, зелёная рубашка – 12345, а красная рубашка – 12346.

Контрольная цифра

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

Алгоритм расчёта контрольного числа:

1. Суммируются все цифры на нечётных позициях (считается, что самая левая цифра стоит на позиции один), результат умножается на три
2. Суммируются все цифры на чётных позициях
3. Эти суммы складываются, и из полученного результата оставляется только последняя цифра
4. Эту цифру вычитают из 10 – это и есть контрольная цифра (десятке соответствует цифра 0)

Пример:

Рассчитаем контрольную цифру для штрихкода $28836291682$

1. $(2 + 8 + 6 + 9 + 6 + 2) * 3 = 33 * 3 = 99$
2. $8 + 3 + 2 + 1 + 8 = 22$
3. $99 + 22 = 121 \equiv 1 \bmod 10$
4. $10 - 1 = 9$

Ответ: контрольная цифра для штрихкода $28836291682$ равна $9$

∎

Проверка контрольной цифры:

1. Суммируются все цифры на нечётных позициях, результат умножается на $3$
2. Суммируются все цифры на чётных позициях
3. Эти суммы складываются и оставляется последняя цифра от результата Если получилось $0$ – то проверка пройдена. В противном случае проверка не пройдена

Пример:

Проверим контрольную цифру для штрихкода $288362916829$

1. $(2 + 8 + 6 + 9 + 6 + 2) * 3 = 33 * 3 = 99$
2. $8 + 3 + 2 + 1 + 8 + 9 = 31$
3. $99 + 31 = 130 \equiv 0 \bmod 10$ – проверка пройдена успешно

∎

Основным достоинством алгоритма является его простота. Для вычисления\проверки нужно пройти по последовательности цифр, умножая на $3$ или $1$ и суммируя общий результат по модулю $10$. Разберём, насколько хорошо алгоритм распознаёт ошибки.

Теорема:

∎

Доказательство:

Запишем условие прохождения контроля:
$$3x_1 + x_2 + 3x_3 + x_4 + 3x_5 + x_6 + 3x_7 + x_8 + 3x_9 + x_{10} + 3x_{11} + x_{12} \equiv 0 \pmod{10}$$

Пусть какая-то цифра изменилась, на величину $y \ne 0$. Тогда сумма в левой части изменяется либо на $y$, либо на $3y$, а это всегда не равно $0$ по модулю $10$

∎

Теорема:

∎

Доказательство:

Запишем условие прохождения контроля:
$$3x_1 + x_2 + 3x_3 + x_4 + 3x_5 + x_6 + 3x_7 + x_8 + 3x_9 + x_{10} + 3x_{11} + x_{12} \equiv 0 \pmod{10}$$

Пусть меняются местами две соседние цифры. Тогда у одной из них коэффициент $1$ (цифра $a$), а у другой – $3$ (цифра $b$). Значит сумма изменилась на
$(a + 3b) - (3a + b) = 2(b - a)$
Если разница между соседними цифрами равна $5$, то $2(b - a) = 10 \equiv 0 \pmod{10}$ и алгоритм не выявит ошибку. Если разница не равна $5$, то выявит.
Всего возможных транспозиций (за вычетом тех, когда $a = b$) – $90$ штук. Транспозиций с разницей равной пяти $10$ штук. Тогда ошибка будет распознана в
$1 - \frac{10}{90} = \frac{8}{9}%$ случаев

∎

Внешний вид штрихкода UPC

Все символы кодируются с помощью тёмных (1) и светлых (0) вертикальных последовательных штрихов. Высота штриха не имеет значения. Код состоит из двух частей – левой и правой, по 6 цифр в каждой, а также символов начала и конца (S) и середины (M). Под штрихкодом написаны цифры для возможности ручного ввода. Перед кодом и после него находится пустое пространство шириной 9 единиц (для выделения этого участка первую и последнюю цифру внизу штрихкода часто печатают не под штрихами, а в стороне от них).

Служебные символы

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

• S – символ начала и конца, имеет вид штриховки 101
• M – символ середины, имеет вид штриховки 01010

Кодирование цифр

Каждая цифра левой или правой группы кодируется с помощью четырёх штрихов: двух светлых и двух тёмных. Каждый штрих может быть шириной от 1 до 3 единиц. Общая ширина штрихов для одной цифры всегда составляет 7 единиц.

Кодировка цифр UPC

Таблица кодирования составлена специально и обладает следующими свойствами, которые облегчают сканирование кода:

• Комбинация для каждой цифры разработана таким образом, чтобы цифры сильно отличались друг от друга
• Максимальная ширина тёмного или светлого участка не может превышать четырёх единиц
• Коды цифр в правой части – это негативное отображение кодов в левой части и наоборот. Например в левой части цифра 7 кодируется 0111011, значит в правой части код этой цифры будет 1000100 (светлый штрих заменяется на тёмный и наоборот)
• Каждая цифра имеет уникальный код и последовательность толщины линий, то есть код цифры в правой части не совпадает ни с кодом любой другой цифры в правой части, ни с кодом любой цифры в левой части

Последние два свойства решают проблему чтения в обоих направлениях. Если сканер видит, например, 2-1-1-3, то он распознаёт, что это цифра 9 в обратном направлении и значит весь штрих-код считывается в обратном направлении. Вообще в код заложено много избыточности для обеспечения бесперебойного чтения (в основном потому что был рассчитан на считывание далёкими от совершенства сканерами). Так, например, общая ширина черных полос в левой части – это всегда нечётное число, а в правой – чётное. По этому признаку сканер также может распознать, что штрихкод считывается в обратном направлении.

Штрихкоды EAN

Когда в Европе увидели как хорошо в США работают штрихкоды, то тоже захотели ввести их в торговле. При этом, помимо задач, которые ставились перед разработчиками UPC, ставилась дополнительная: возможность считывать как американские, так и европейские штрихкоды одним сканером, при этом имея один штрихкод на упаковке, а не два.

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

Разработчики решили эту проблему весьма остроумным способом: новая цифра (она пишется первой) кодируется не новыми штрихами, а способом нанесения цифр в левой части кода. В UPC цифры имеют два способа изображения L-код и R-код: различные изображения одной и той же цифры в левой и правой части. В дополнение к этому в EAN разработчики добавили ещё один способ, G-код (выглядит он как R-код справа налево).

Кодирование цифр EAN

Некоторые цифры в левой части стали кодироваться не L-кодом, а G-кодом. То, какие именно цифры закодированы G-кодом, и определяет новую дополнительную цифру.

Кодирование первой цифры EAN

Для товаров из США изображение всех цифр оставили прежним: в L-коде (первая строка в таблице). Поэтому EAN-код для товаров из США выглядел абсолютно также, как и UPC-код. Т. е. UPC-коды – это подмножество EAN-кодов. В случае товаров из других стран в левой части некоторые цифры будут представлены в G-коде и не будут совпадать с UPC-кодом.

Структура EAN

Структура EAN похожа на структуру UPC с тем отличием, что ещё кодируется код страны.

• 2-3 цифры – код страны
• 4-5 цифр (в зависимости от длины кода страны) – код предприятия
• 5 цифр – код товара
• 1 цифра – контрольная цифра

Код страны

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

Контрольная сумма

Расчёт контрольной суммы аналогичен расчёту для UPC с той лишь разницей, что, наоборот, цифры на нечётных позициях суммируются с коэффициентом 1, а на чётных – с коэффициентом 3 (помним, что для американских товаров код должен совпадать с кодом UPC, в том числе контрольная цифра, поэтому коэффициенты сдвинуты).

Достоинства и недостатки штрихкодов

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

Примеры штрихкодов