Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Теорія інформації та кодування. Тема 2. Ефективне кодування. Носов В.В.
Лекція 9(3). Штрихові коди
Навчальні питання
1. Штрихові коди 1
2. Приклади розв’язання задач 7
Час – 2 год.
Література.
Вступ
До ефективного кодування можна в певній мірі віднести і штрихові коди, розглянемо деякі з них.
Штрихові коди (ШК) широко використовуються в медицині, торгівлі, промисловості тощо. ШК – це послідовність штрихів і пробілів, що розташовані у напрямку уявленої прямої. Інформацію у ШК можуть нести як штрихи і пробіли різної ширини, так і штрихи різної висоти.
Існує багато ШК які в основному мають вузькоспеціальне призначення. Найбільш поширеними ШК є коди, що рекомендовані Міжнародною асоціацією EAN. Це коди EAN (European Article Numbering) та UPC (Uniform Product Code).
Штрихові коди EAN.
European Article Number, EAN (європейський номер товару) - європейський стандарт штрих-коду, призначений для кодування ідентифікатора товару і виробника. Є надмножиною американського стандарту UPC.
Різновиди коду:
Штрихові коди EAN призначені для кодування 10 цифр (0. . .9) і додаткових символів (СТАРТ, СТОП та розділові знаки). Код може мати довжину кодового слова 4, 5, 6, 7, 8, 10, 12, 13 і 14 знаків. Але існує два основні різновиди коду EAN: EAN-13 (реально кодується тільки дванадцять цифр) і EAN-8, де цифрою позначена довжина коду (кількість знаків у кодовому слові).
Знаки штрихового коду EAN складаються з двох штрихів та двох проміжків. Штрихове зображення всіх цифр становить в цілому символ коду EAN. Крайові знаки (подовжені штрихи знаки СТАРТ і СТОП) визначають його межі; ділиться символ на дві частини (для кодів довжиною 8, 10, 12 і 14 знаків) розділовим знаком (подовжені штрихи в центрі символу), як показано на рис. 1.
Рис. 1.
Код EAN-13 має структуру, яка наведена на рис. 2.
u12
u11
u10
u9
u8
u7
u6
u5
u4
u3
u2
u1
uk
Код країни
Контрольний символ
Код товару (найменування,
характеристика)
Код товаровиробника
Код країни
Код товаровиробника
Рис. 2. Структура штрихового коду EAN-13
Як видно з рисунка 2, код країни може мати не два, а три знаки. У цьому разі код товаровиробника має не 5, а 4 знаки.
Контрольний символ визначається за таким алгоритмом:
1- ий крок: знаходять суму цифр, розташованих на непарних позиціях кодового слова (перегляд виконується справа наліво), і помножують одержаний результат на 3;
2 - ий крок: знаходять суму цифр, розташованих на парних позиціях кодового слова;
3 - ій крок: знаходять остаточну суму – складують результати, одержані на 1-му та 2-му кроках ;
4 - ий крок: обчислюють контрольну цифру, яка дорівнює найменшому числу, що не перевищує 9, яке, якщо його додати до результату, одержаному на 3-му кроці, дає кратне 10 число.
Приклад розрахунку контрольного символу для кода EAN-13
По поводу кодирования контрольного числа можно услышать три вопроса:
1. Почему всё так сложно, зачем умножать на 3, почему нельзя просто сложить цифры друг с другом без этого умножения?
Ответ: Потому, что коды рассчитаны не только для ввода сканером, иногда кассир может вводить его вручную. Человек ведь иногда не только ошибается, вводя другую цифру. Часто он переставляет правильные цифры местами. То есть, например, вместо 2252 может ввести 2522. Или другой вариант — он может ввести лишний ноль в одной части кода и убрать в другой. Например, вместо 00300 может ввести 00030. Простое сложение цифр не сможет отследить ошибки такого типа, а вышеуказанный метод на это способен.
2. Почему умножается на 3, а не на 2 или 5?
Ответ: Если взять таблицу умножения из школьной тетради и посмотреть на результаты умножения цифр на 3, то можно заметить, что для каждого числа последняя цифра в результате умножения разная и не повторяется. То есть, каждому исходному числу от 0 до 9 соответствует другое уникальное число от 0 до 9.
Альтернативный ответ: чтобы сохранить количество классов вычетов, число m, на которое мы умножаем, должно быть взаимно просто с n (n = 10, для дес. системы счисления). С 10 взаимно просты четыре числа: 1, 3, 7, 9.
3. Почему при вычислении контрольного числа на 4-м шаге из 10 вычитается последняя цифра суммы, ведь можно было просто записать эту цифру, полученную на шаге 3 и дело с концом, к чему такие сложности?
Ответ: Упрощение контроля. При контроле единственный правильный ответ — ноль.
Для кодування інформації у ШК EAN використовуються три набори знаків: A, B, C (табл.1 ) для кодування десяткових цифр, а також знаків СТАРТ, СТОП (Н1, Н2, Н3 ), та розділових знаків (Н4 та Н5). Кожний знак містить у собі два штрихи і два пробіли. Ширина (довжина у поперек) кожного знака для кодування цифр дорівнює 7 модулям (7-ми елементам зображення), а допоміжні знаки мають довжину 3, 5 і 6 модулів. Як знак СТАРТ використовуються набори Н1 та Н3, а знак СТОП – Н1 та Н2 у залежності від символів початку і кінця кодового слова (табл. 2, де 0 – пробіл, 1 – штрих ).
Таблиця 1
|
Сим- воли |
Набір А |
Набір В |
Набір С |
|
Двійковий еквівалент |
Двійковий еквівалент |
Двійковий еквівалент |
|
|
ліва частина кодового слова |
права частина кодового слова |
||
|
0 |
0001101 |
0100111 |
1110010 |
|
1 |
0011001 |
0110011 |
1100110 |
|
2 |
0010011 |
0011011 |
1101100 |
|
3 |
0111101 |
0100001 |
1000010 |
|
4 |
0100011 |
0011101 |
1011100 |
|
5 |
0110001 |
0111001 |
1001110 |
|
6 |
0101111 |
0000101 |
1010000 |
|
7 |
0111011 |
0010001 |
1000100 |
|
8 |
0110111 |
0001001 |
1001000 |
|
9 |
0001011 |
0010111 |
1110100 |
|
Н1 |
101 |
Обмежувальні знаки СТАРТ і СТОП |
|
|
Н2 |
010101 |
||
|
Н3 |
101010 |
||
|
Н4 |
01010 |
Розділові знаки |
|
|
Н5 |
10101 |
Примітка: При зображенні кодового слова у штриховому коді, згідно табл. 1, подають: 0 – одним, 00 – двома, 000 – трьома і 0000 – чотирма інтервалами, а 1 – одинарним штрихом, 11 – подвоєним штрихом, 111 – потроєним штрихом і 1111 – почетвереним штрихом.
Приклад зображення цифри 4 набором С – 1011100 на штрих-коді (рис. 3):
Рис. 3.
Таблиця 2
|
Знак СТАРТ |
Кодове слово |
Знак СТОП |
|
Н1(101) |
0 . . . . . . . . . . 0 |
Н1(101) |
|
Н3(101010) |
1 . . . . . . . . . . .1 |
Н2(010101) |
|
Н1(101) |
0 . . . . . . . . . . .1 |
Н2(010101) |
|
Н3(101010) |
1 . . . . . . . . . . .0 |
Н1(101) |
У штрихових кодах EAN довжиною 4, 5, 6, 7 знаків для кодування цифр використовується набір А (табл. 1), а обмежувальних знаків – Н1 (СТАРТ) та Н2 (СТОП).
У ШК довжиною 8, 10, 12 і 14 знаків кодові слова діляться на дві частини з однаковим числом знаків у кожній, які розділяються розділовим знаком Н4(01010). Для зображення знаків лівої частини кодового слова використовуються набори А і В, а правої – С (див. табл. 1). Такі кодові слова мають обмежувальні знаки СТАРТ і СТОП типу Н1(101).
У коді EAN-13 штрихове зображення складається з двох частин по шість знаків у кожній, які розділені знаком Н4(01010), і має зліва та справа обмежувальні знаки Н1(101) (СТАРТ і СТОП).
Кодировка цифр
|
Кодировка цифр для правых и левых частей кода |
|||
|
Цифра |
Левый код |
Правый код |
Ширина линий |
|
0 |
0001101 |
1110010 |
3-2-1-1 |
|
1 |
0011001 |
1100110 |
2-2-2-1 |
|
2 |
0010011 |
1101100 |
2-1-2-2 |
|
3 |
0111101 |
1000010 |
1-4-1-1 |
|
4 |
0100011 |
1011100 |
1-1-3-2 |
|
5 |
0110001 |
1001110 |
1-2-3-1 |
|
6 |
0101111 |
1010000 |
1-1-1-4 |
|
7 |
0111011 |
1000100 |
1-3-1-2 |
|
8 |
0110111 |
1001000 |
1-2-1-3 |
|
9 |
0001011 |
1110100 |
3-1-1-2 |
|
Кодировка защитных шаблонов |
|||
|
Шаблон |
Слева |
По центру |
Справа |
|
Левый защитный шаблон |
101 |
||
|
Средний защитный шаблон |
01010 |
||
|
Правый защитный шаблон |
101 |
При проектировании структуры кода, в условиях ещё не слишком развитой электроники, было важным сделать его как можно более простым для считывания сканером и упростить аппаратную часть самого сканера. Одной из сложностей была проблема вероятного считывания кода в обратном направлении, то есть считывания кода на товаре, который кассир поднёс к сканеру «вверх ногами». Поэтому очень важно было, чтобы чередование полос было одинаковым в обоих направлениях — сначала тёмный штрих, потом белый, потом опять тёмный и так далее. Да, и ещё было бы неплохо, чтобы положение защитных шаблонов было всегда на одном и том же месте.
Решение было найдено. Можно обратить внимание, что код выглядит очень симметрично, то есть количество штрихов справа и слева от центра всегда равно, а ширина правой и левой части штрихкода одинаковы. То есть механизм считывания штрихкода всегда одинаков, как этот код ни поверни.
Что касается одинаковой последовательности чередования светлых и тёмных штрихов при прямом и обратном чтении, то разработчики добились этого тем, что кодировка правой и левой групп цифр немного отличается — правые символы имеют фотографически негативное начертание относительно левых. То есть шаблоны штрихов для одной и той же цифры идентичны, но позитивны или негативны. Иначе говоря, отличие только в том, что если для левой части кода это светлый штрих, то для правой — тёмный.
Проблема распознавания прямого или обратного считывания точно так же легко разрешается логически. Например, если сканер считывает цифру с толщиной штрихов 3-2-1-1, то он понимает, что это цифра «ноль» и её прямое считывание, а если он считывает штрихи толщиной 1-1-2-3, то он понимает, что это тот же «ноль», но считанный в обратном направлении. Считывая числа, закодированные зеркально относительно обычной кодировки, сканер понимает, что весь штрихкод считывается в обратном направлении, следовательно, и всю полученную последовательность из 12 цифр нужно передать компьютеру в обратном порядке.
Всё это было определённой перестраховкой, и по современным меркам излишеством, но и год был 1973.
Першу зліва цифру (12-а цифра) товарного номера не кодують у вигляді штрихів і пробілів, а тільки пишуть зліва внизу. Ця цифра визначає спосіб кодування цифр, які розташовані у лівій частині кодового слова між знаками Н1 та Н4 (табл. 3). Літерами А і В у табл. 3 позначені набори з табл.1, якими кодують відповідні знаки лівої частини кодового слова. Цифри, які розташовані у правій частині кодового слова між знаками Н4 і Н1, кодують набором С (див. табл. 1). Обмежувальні і розділовий знаки зображають більш довшими по висоті штрихами.
Таблиця 3
|
u12 |
u11 u10 u9 u8 u7 u6 |
|
0 |
А А А А А А |
|
1 |
А А В А В В |
|
2 |
А А В В А В |
|
3 |
А А В В В А |
|
4 |
А В А А В В |
|
5 |
А В В А А В |
|
6 |
А В В В А А |
|
7 |
А В А В А А |
|
8 |
А В А В В А |
|
9 |
А В В А В А |
Деякі товари можуть мати короткий номер, що має 7 цифр. Після доповнення його контрольною цифрою, що виконується за наведеним вище алгоритмом для коду EAN-13, одержують 8 цифр, які кодують кодом EAN-8. Кодове слово EAN-8 складається зі знака СТАРТ – Н1, чотирьох знаків набору А, розділового знака Н4, трьох знаків набору С, знака контрольної цифри у наборі С, а також знака СТОП – Н1. У коді EAN-8 перша цифра u7 не визначає неявне кодування, а кодується як і наступні цифри u6, u5, u4 набором А ( див. табл. 1 ).
Штрихові коди UPC (Universal Product Code) використовуються у США та Канаді для ідентифікації товарів і також призначені для кодування 10 цифр та п’яти додаткових знаків. Коди UPC сумісні з кодами EAN з огляду на те, що використовують одну і ту ж таблицю наборів знаків ( табл.6.1 ).
Існує декілька різновидів ШК UPC, з яких найбільше поширення набули коди:
Кодове слово ШК UPC-А має 12 цифр (12-а – контрольна), тобто на одну цифру менше ніж у EAN-13. Це викликано тим, що код країни (США і Канада) має тільки дві цифри. Відмінними ознаками коду UPC-А від коду EAN-13 є:
Контрольна цифра визначається за тим же алгоритмом, що використовується і у коді EAN-13.
Товарний номер у коді UPC-Е містить 6 цифр і також поділяється на дві частини по 3 цифри у кожній. Перша частина ( ліва ) кодується набором А, а друга ( права ) – набором С ( у тому числі і контрольний знак ) ( див. табл.6.1 ).
При декодуванні ШК EAN та UPC перш за все визначається контрольний знак, який повинен співпадати з переданим. Крім того, сума всіх цифр кодового слова, що подається на приймальний пристрій, повинна бути кратною 10. У цьому разі помилки нема. Якщо ж сума буде не кратною 10, це вказує на наявність помилки. Помилка виявляється і при неправильному прийомі знаків, що не відповідають наборам, встановленим неявним кодуванням по старшому знаку в ШК EAN-13 цифр лівої половини кодового слова, тому що набори А і В (див. табл.6.1) не збігаються.
Общее описание структуры UPC
Код UPC — простой и практически симметричный линейный штрихкод. Эта простота, симметричность и высокая помехозащищённость обусловлена недостаточно развитой техникой времён создания этих кодов. Код состоит из 2 групп цифр, по 6 цифр в каждой группе — левой и правой. Группы цифр окаймляются так называемыми защитными, или ограждающими, штрих-шаблонами (Guard Patterns), которые выделены на рисунке для наглядности зелёным цветом. Эти шаблоны содержат штрихи единичной ширины, которые служат для синхронизации сканера штрихкода. Наличие именно трёх таких полей обусловлено в первую очередь возможным нанесением штрихкода на закруглённую поверхность. И если сейчас это не является особой проблемой, то во времена создания этого кода сканеру требовалось знать ширину единичного штриха в начале, середине и конце кода. Левые и правые защитные шаблоны состоят из 3 штрихов единичной ширины — двух тёмных и одного светлого между ними. Средний защитный шаблон состоит из 5 штрихов — трёх светлых и двух тёмных. Всё остальное — цифры.
Каждая цифра левой или правой группы кодируется с помощью четырёх штрихов: двух светлых и двух тёмных. Каждый штрих может иметь относительную ширину в одну, две, три или четыре единицы. Общая ширина штрихов для одной цифры всегда составляет семь единиц. Битовая комбинация для каждой цифры разработана таким образом, чтобы цифры, насколько это возможно, отличались друг от друга. Максимальная длина тёмного или светлого участка не может превышать четырёх единиц. Общая ширина всего кода всегда равна 95 единицам. В любом коде 29 светлых и 30 тёмных штрихов. Все эти технические решения очень важны для надёжности и простоты сканирования этого кода.
Первая цифра кода — это так называемый префикс — имеет некоторое логическое значение, но не столь важна с технической точки зрения. Последняя цифра — контрольное число, служит для выявления возможной ошибки при чтении кода сканером или ручного ввода цифр кода с клавиатуры.
Направление чтения комбинации штрихов значения не имеет, код специально разрабатывался так, чтобы он одинаково просто считывался как в прямом, так и обратном направлении (если товар перевёрнут). Также не имеет значения то, какое исполнение имеет весь штрихкод — фотографически позитивное или негативное. То есть штрихкод, нанесённый светлыми полосками по тёмному фону читается абсолютно так же, как и тёмными полосками по светлому фону. Мало того, цвета штрихов и фона не обязательно должны быть белыми и чёрными, возможны и другие цветовые комбинации.
Задача 6.2.1
Побудувати кодове слово у коді EAN-13, якщо країна товаровиробник – Україна, код товаровиробника –1229, код товару – 03458.
Розв’язання. 12 цифр кодового слова, яке треба закодувати кодом EAN-13, мають вигляд: 482122903458 ( код країни – 482 ). Необхідно доповнити це кодове слово контрольною цифрою uK, яку визначаємо згідно з алгоритмом для коду EAN:
а) визначаємо суму цифр, які розміщені на непарних місцях кодового слова ( справа наліво ): 8 + 4 + 0 + 2 + 1 + 8 = 23;
б) помножимо одержану суму на 3: 23 3 = 69;
в) визначаємо суму цифр, які розташовані на непарних місцях кодового слова: 5 + 3 + 9 + 2 + 2 + 4 = 25;
г) визначаємо суму двох результатів за п. п. б та в:
69 + 25 = 84;
д) визначаємо контрольну цифру як різницю між числом кратним 10, що є найближчим більшим за одержаний результат у п. г, і числом одержаним у п. г: 90 – 84 = 6, тобто uK = 6.
У коді EAN-13 штрихове зображення має дві частини, по 6 знаків у кожній, які розділені знаком Н4, і має зліва і справа обмежувальні знаки Н1 ( СТАРТ і СТОП ). За першою зліва цифрою визначаємо набори кодових комбінацій, якими кодуються цифри першої частини кодового слова ( табл.6.3 ). У зв’язку з тим, що u12 = 4, згідно табл. 6.3 маємо: u11, u9 та u8 – кодуються набором А, а u10, u7 та u6 – набором В. Цифри u5, . . . , u1, а також контрольна цифра uК, кодуються відповідними знаками набору С ( табл.6.1 ). Таким чином, кодове слово EAN-13 у двійковому еквіваленті має такий вигляд:
Н1 8 2 1 2 2 9 Н4
1110010 1000010 1011100 1001110 1001000 1010000 101
0 3 4 5 8 6 Н1.
Задача 6.2.2
Зчитувальним пристроєм фіксується кодове слово у коді EAN-13: 4821223034586, у якому міститься помилка. Показати процес виявлення помилки.
Розв’язання. Для виявлення помилки у кодовому слові коду EAN-13 виконуємо перевірку на відповідність контрольної цифри ( uК = 6 ) цифрам кодового слова, що надійшло до декодера зчитувального пристрою. Для цього знаходимо контрольну цифру uK* для прийнятого кодового слова 482122303458 ( без uK ) згідно з алгоритмом для коду EAN-13 та порівнюємо її з uK :
8 + 4 + 0 + 2 + 1 + 8 = 23;
23 3 = 69;
5 + 3 + 3 + 2 + 2 + 4 = 19;
69 + 19 = 88;
90 – 88 = 2 uK* = 2, uK* uK.
Таким чином, контрольні цифри у прийнятому кодовому слові і обчислені декодером не збігаються. Це вказує на наявність помилки у прийнятому кодовому слові.
Висновки
Задачі
6.3.1. Побудувати, згідно заданого варіанту (таблиця 6.3.1), кодове слово у коді EAN-13 або UPC-A, якщо задані: країна товаровиробник, код товаровиробника та код товару. Запис виконати у двійковому еквіваленті. Відзначити особливості штрихового зображення одержаного коду.
Таблиця 6.3.1
|
№ варі-анта |
Країна |
Код товаро-виробника |
Код товару |
Штриховий код |
|
1 |
Японія |
04734 |
22029 |
EAN-13 |
|
2 |
Китай |
1144 |
03220 |
EAN-13 |
|
3 |
Україна |
3539 |
11027 |
EAN-13 |
|
4 |
Білорусія |
2535 |
45391 |
EAN-13 |
|
5 |
Польща |
4335 |
67820 |
EAN-13 |
|
6 |
Туреччина |
7390 |
22029 |
EAN-13 |
|
7 |
Угорщина |
0897 |
77194 |
EAN-13 |
|
8 |
Італія |
44900 |
10272 |
EAN-13 |
|
9 |
Португалія |
12491 |
23479 |
EAN-13 |
|
10 |
Великобританія |
78013 |
05537 |
EAN-13 |
|
11 |
Німеччина |
34650 |
77112 |
EAN-13 |
|
12 |
Бразилія |
9945 |
00202 |
EAN-13 |
|
13 |
Румунія |
8750 |
55339 |
EAN-13 |
|
14 |
Чехія |
1521 |
70027 |
EAN-13 |
|
15 |
Словаччина |
0033 |
12020 |
EAN-13 |
|
16 |
США |
1007 |
20122 |
UPC-A |
|
17 |
США |
2190 |
81076 |
UPC-A |
|
18 |
США |
0733 |
56520 |
UPC-A |
|
19 |
Канада |
7688 |
31327 |
UPC-A |
|
20 |
Канада |
0457 |
90142 |
UPC-A |
|
21 |
США |
2880 |
00110 |
UPC-A |
|
22 |
США |
1100 |
34541 |
UPC-A |
|
23 |
США |
3155 |
55120 |
UPC-A |
|
24 |
Канада |
4410 |
87807 |
UPC-A |
|
25 |
Канада |
9191 |
03225 |
UPC-A |
6.3.2. Зчитувальним пристроєм фіксується кодове слово у штриховому коді, у якому міститься помилка. Штриховий код заданий таблицею варіантів 6.3.2. Показати процес виявлення помилки.
Таблиця 6.3.2
|
№ варіанта |
Штриховий код |
Кодове слово ШК |
|
1 |
EAN-13 |
5600412100724 |
|
2 |
EAN-13 |
4821300223640 |
|
3 |
EAN-13 |
8313747410049 |
|
4 |
EAN-13 |
4401110022212 |
|
5 |
EAN-13 |
4501110021110 |
|
6 |
EAN-13 |
4901110022223 |
|
7 |
EAN-13 |
4810002344207 |
|
8 |
EAN-13 |
6010011003335 |
|
9 |
EAN-13 |
4601110022216 |
|
10 |
EAN-13 |
7790401110650 |
|
11 |
UPC-A |
001043316088 |
|
12 |
UPC-A |
016630112028 |
|
13 |
UPC-A |
030395509184 |
|
14 |
UPC-A |
042236081024 |
|
15 |
UPC-A |
068801702446 |