Застосування штрих-коду для кодування інформації

 

 

 

 

 

 

 

ДИПЛОМНА  робота

 

застосування штрих-коду    для кодування   інформації

 

 

 

 

 

 

 

 

 

ЗМIСТ

 

Вступ            3

1. Теоретичні  відомості

1.1  Побудова  та класифікація штрихових кодів   5

1.2 Деякі поняття теорії інформації     7

1.2.1 Міра інформації       7

1.2.2 Інформаційна  ентропія      10

1.2.3 Умовна ентропія. Iнформацiя,  що мiститься в   одному дослiдi  вiдносно iншого    13

       1.2.4 Надлишковість       17

1.2.5 Цiннiсть  iнформацiї      19

1.2.6 Экспоненциальный закон збiльшення  числа 

повiдомленнь       20

1.3 Коди з  виявленням та виправленням помилок   22

1.3.1 Кодування  інформації      22

1.3.2 Коди з  виявленням та виправленням помилок 24

2. Огляд найбільш  вживаних типів штрихових кодів

2.1 Загальний  огляд        28

2.2 Тип EAN-13, UPC та EAN-8      31

2.3  Code39 та CODABAR       35

2.4  INTERLEAVED 2 OF 5       38

3.  Створення  самокорегуючого штрихового коду

3.1  Постановка  задачі       40

3.2  Хід роботи         40

4.  Результати  та їх аналіз

4.1  Початкові  результати       46

4.2  Кінцевий результат       46

5.  Програми

5.1  Iнструкція  користувача       48

5.2  Текст програм        53

 

Висновки           99

 

Джерела                     100

 

ВСТУП

 

За  останні півтора-два десятиліття  штрихові коди щільно увійшли в наше життя, зараз ми зустрічаємо їх в повсякденному житті на кожному кроці. Їх можна побачити на харчових продуктах в крамниці, на поштових конвертах та бандеролях, ними маркують коробки на складах та різного роду посвідчення особи.

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

Широке використання штрихових  кодів було зумовлене необхідністю забезпечити  автоматизоване введення інформації в комп'ютерні системи управління, що відрізнялося б високою надійністю, простотою і економічністю. Штриховий код — це не щось особливе, існуюче саме по собі, а передусім елемент системи управління. В відриві від комп'ютерної системи управління, поза зв'язком з її інформаційною базою він не має жодного сенсу. Технологія штрихового кодування застосовується в багатьох сферах людської діяльності, але найбільш широко і ефективно вона використовується в оптовій і роздрібній торгівлі, управлінні матеріальними запасами, управлінні перевезеннями. Ми стикаємось зі штриховыми кодами, купуючи товар в крамницях, здаючи багаж в аеропортах... Цей список можна продовжити, але вже наведених прикладів достатньо, щоб переконатися, що потреба в їхньому виготовленні значна.

Чому саме штрихові коди вийшли на перше місце серед безлічі  відомих засобів ідентифікації? Що зумовило їхню перевагу в більшості  практичних додатків перед іншими оптичними  засобами, не говорячи вже про такі, як магнітні або, скажемо, пов'язані  з застосуванням радіоізотопів? Як вже було сказано, переваги різних засобів оцінюються з точки зору надійності, простоти застосування і економічності. Штрихові коди характеризуються високою надійністю. До них застосовні ті засоби захисту від помилок, що широко використовуються в зв'язку та комп'ютерній справі. За рахунок деякої надмірності можна створювати самоконтролюючі і самокорректуючі коди, тобто такі, що здатні шляхом перевірки по  спеціальним алгоритмам забезпечити відшукання помилок і навіть їх автокоррекцію за умови, що кількість помилкових знаків в коді не перевищує встановленої межі (звичайно 65-70%). При існуючих засобах захисту лінійного коду, що забезпечують імовірність помилки не більш однієї на 30 млн. зчитаних знаків, надмірність коду залишається в розумних межах — звичайно це одна контрольна цифра.

Простота застосування штрихового коду визначається його природою: його наявність чи відсутність одразу видно (на відміну від магнітних  або радіохвильовх засобів, що застосовуються передусім там, де вміст і навіть присутність коду бажано приховати), він легко розміщується на упаковці виробу або на паперовому етікетці, добре зчитується приладами, з'єднаними з комп'ютером. При цьому такі прилади не є складними в проектуванні та виробництві, будучи різновидністю звичайних сканерів.

По економічності технологія штрихового кодування не має собі рівних, навіть в виробництві дешевих  товарів масового попиту, виготовлення штриховых кодів не має помітного  впливу на собівартість товару для  виробника.

В залежності від потреб створено велику різноманітність типів штрихових кодів. Кожна конкретна область застосування цих кодів формулює власні вимоги до них. Так в одному випаду головною умовою є простота коду, можливість легкого його читання навіть людиною, в інших вимагається висока щільність інформації на одиниці площі штрихового коду. Якщо при використанні деякого штрихкоду у нас немає змоги зіскановувати його по декілька разів, наприклад при швидкій автоматизованій обробці інформації, тоді до такого типу штрихкоду головною вимогою є надійність закодованої інформації.

Звичайно ж надійність інформації, закодованої тим чи іншим  способом, важлива завжди, але різні  характеристики коду нерідко обернено-залежні. Тому нам доводиться в тій чи іншій  мірі жертвувати надійністю, наприклад: при спробі збільшити кількість інформації на одиницю площі штрихового коду.

В цій дипломній роботі було розвязано задачу по максимізації надійності штрихового коду. Було створено ефективний код, здатний запобігати неправильному зчитуванню закодованої інформації. Це було зроблено за допомогою використання матода Хеммінга при побудові штрихового коду. Необхідно зазначити, що подібних типів штрихових кодів в світі на даний момент не існує, а його надзвичайну ефективність буде продемонстровано згодом. Також в ході виконаня цієї дипломної роботи було розглянуто різноманітні методи побудови штрихових кодів, а також проаналізовано та порівняно найчастіше уживані їх типи.

 

 

 

 

1. Теоретичні відомості

1.1. CПОСОБИ ПОБУДОВИ ШТРИХОВИХ КОДІВ ТА МЕТОДИ КЛАСИФІКАЦІЇ

 

Розглянемо основнi принципи та правила, що використовуються про створеннi штрихових кодiв i якi є обов'язковими для будь-якого їх типу. Одразу потрiбно  зазначити, що інформація яку ми кодуемо  представлена в двійковому виді, тобто  кодується двома значеннями: '0' та '1'. В штриховому кодуванні існує два способи задання цих значень, першим є спосіб, коли значення '0' та '1' кодуються відповідно двома кольорами - білим та чорним. Наприклад: бітова послідовність 10110011101100011 буде мати слідуюче штрихове представлення:

(рис1)

В цьому способі штрихи що відповідають '0' та '1' мають одинакову  ширину. В разі якщо в бінарній послідовності  йдуть одне за одним кілька одинакових n значень '0' чи '1' їм буде відповідати  білий чи чорний штрих n-кратної ширини.

Другим способом представлення  бітової послідовності в виді штрихового коду є спосіб коли '0' та '1' задані не різними кольорами, а  різними значеннями ширини штрихів. Тобто маємо чотири атомарні графічні символи два вузькі штриха та два  широкі білого та чорного кольорів. В такому штриховому коді білі та чорні штрихи весь час йдуть почергово, а значенням '0' та '1' відповідають відповідно широкі та візькі штрихи. В цьому разі наведена вище бінарна послідовність буде мати вигляд:

 

                     (рис2)

В кожному з цих  варіантів є як переваги так і  недоліки. Так в першому варіанті штриховий код буде коротшим в  наслідок того, що всі біти кодуються  однаковими по ширині штрихами. По цій  самій причині в першому варіанті штриховий код бінарної послідовності зі сталим числом бітів буде мати сталий розмір, в той час як в другому варіанті розмір штрихового коду буде залежати від співвідношення нулів та одиниць. Але недоліком першого варіанту є те, що при великій кількості йдучих один за одним одинакових бітів їх графічне представлення може неправильно тлумачитися. Так, наприклад буде важко розрізнити штрихкоди для 100001 та для 1000001.

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

     (рис3)      (рис4)

 

 Розглянемо інші особливості побудови штрихових кодів, які також використовуються для класифікації штрихових кодів. Однією з таких особливостей є наявність чи відсутність контрольних штрихів(бітів). Вони використовуються в разі потреби стабілізації швидкості зчитування нашого коду від початку до кінця. В випадку відсутності контрольних штрихів, при нерівномірній швидкості зчитування штрихкоду, цей код можливо буде інтерпретовано неправильно. Щоб цьому запобігти, на початку та в кінці нашого коду розміщується набір з принаймні двох контрольних штрихів. Після зчитування ЕОМ цього коду, обчислювальна машина може судити про зміну швидкості сканування штрихового коду і відповідно корегувати процес декодування. Прикладом застосування контрольних штрихав може бути штриховий код типу EAN-13. В ньому контрольні штрихи наявні не тільки на початку та в кінці, а і в середині коду.

(рис5)

Детально даний тип  штрихового коду буде розглянуто пізніше.

Ще  однією особливістю при побудові штрихового коду є наявність чи відсутність  контрольної суми. Для гарантування правильності декодування штрихового коду в деяких типах штрихового коду до інформації, що кодіється додається деяка контрольна сума яка функціонально залежить від кодованої інформації. Ця контрольна сума кодується в штриховий код разом з основною інформацією, а при декодуванні ЕОМ знову вираховує контрольну суму цього коду і порівнює з заданим. Зрозуміло що в разі неспівпадання цих двох контрольних сум штриховий код був не правильно зіскановано.

В наслідок використання всіх цих додаткових засобів надійності штрихового коду, виникає питання, а  скільки справді корисноі інформації несе той чи інший штриховий код? Яким буде в ньому відношення кількості допоміжної контрольної інформації до справді корисної - тієї котру ми хотіли кодувати? Щоб відповісти на це питання, вводять поняття ентропії, міри інформації та надлишковості.

 

 

 

1.2 Деякі поняття теорії інформації

 

1.2.1 Мiра iнформацiї

 

Кожне повiдомлення, кожна iнформацiя про той або iнший фактi має немов би двi сторони: конкретний змiст даного повiдомлення, даного факту, i статистичнi (ймовiрноснi) властивостi, що дозволяють порiвнювати цiлком разнорiднi повiдомлення по тій різноманітності станiв, з якими цi повiдомлення зв'язанi.

Наприклад, повiдомлення про те, що в технiчнiй системi управлiння  вийшов з ладу один з двох однаково надiйних (або, краще сказати, ненадiйних) підсилювачів, i повiдомлення, що Н. народила хлопчика, зв'язанi з однiєю i тіею же різноманітністю - з появою одного з двох рівноможливих фактiв.

В сенсi зв'язаної з цими фактами різноманітності цi два  повiдомлення цiлком однаковi, хоча їхнiй  конкретний змiст iстотно різниться. Відмічена нами спiльнiсть має далеко iдучі наслiдки, а саме: як ми побачимо нижче, ефективнi системи зв'язку для передачi повідомлень одного типу будуть настiльки ж хороші i для передачi вiдомостей другого типу. Ця спiльнiсть i дозволяє ввести деякi загальнi поняття, зв'язанi з рiзноманiтними повiдомленнями, незважючи на їхню різнорідність. Таким поняттям, що висловлює мiру різноманітності ситуацiї, зв'язаної з тим або iншим повiдомленням або фактом, є iнформацiя.

Вiдзначимо, що поняття кiлькостi iнформацiї, укладеної в тому або iншому повiдомленнi, зв'язане з iмовiрнiстю цього повiдомлення, тобто з деякою статистичною сукупнiстю. Введемо бiльш точне визначення iнформацiї як деякої кiлькiсної величини - деякої мiри.

По визначенню кiлькiсть власної iнформацiї, укладеної в повiдомленнi А_i рiвна логарифму його iмовiрностi, взятому зі зворотнім знаком

I (А_і) = -log(P(A_i)).     (1.14)

   Знак мiнус в  формулi (1. 14) введений для того, щоб  зробити цей вираз iстотно позитивним [0£Р(А_i)£1, Þ логарифм Р (A_i) - величина вiдємна]. Виразу (1. 14) можна придати вигляд

I(А_i)=log 1/P(A_i)                (1.15)

 з якого слiдує,  що чим менша iмовiрнiсть появи  повiдомлення A_i, тим бiльшою кiлькiстю iнформацiї воно володiє.

Сенс вводу логарифмичної мiри в виразах (1.14) i (1.15) полягає в наданнi кiлькостi iнформацiї властивостi адитивності. Справдi, якщо ми маємо дiло зi складним повiдомленням, що полягае в одночасному повiдомленнi двох фактiв A_i i В_j, i якщо цi факти (подiї) незалежнi в iмовiрносному розумiннi, то, згiдно (1. 14),

  I (A, B_j) = logP (A_iÇB_i).

 Або, застосовуючи  теорему про множення iмовiрностей,  маємо

I(А_i,B_j) = - log[ Р(А_i)Р(B_j)] = -1оg Р(A_i) - log P(В_j) = I(A_i) - I(B_j).     (1.16)

Іншими словами, кiлькiсть iнформацiї, вкладеної в два незалежних повiдомлення, рiвна сумi кiлькостi iнформацiї, вкладеної в кожне повiдомленнi. З наведеного вище визначення власної iнформацiї (1. 14) слiдує надто важливий висновок: з деяким повiдомленням А_i можна зв'язати поняття власної iнформацiї тiльки в тому випадку, якщо iснує поняття iмовiрностi цього повiдомлення (тобто, якщо його можна зв'язати з деяким статистичним ансамблем). Наприклад, окреме повiдомлення, не зв'язане з якою-небуть рiзноманiтнiстю, не володiє в розумiннi теорiї iнформацiї поняттям власної iнформацiї.