Автор работы: Пользователь скрыл имя, 21 Января 2014 в 12:54, дипломная работа
Широке використання штрихових кодів було зумовлене необхідністю забезпечити автоматизоване введення інформації в комп'ютерні системи управління, що відрізнялося б високою надійністю, простотою і економічністю. Штриховий код — це не щось особливе, існуюче саме по собі, а передусім елемент системи управління. В відриві від комп'ютерної системи управління, поза зв'язком з її інформаційною базою він не має жодного сенсу. Технологія штрихового кодування застосовується в багатьох сферах людської діяльності, але найбільш широко і ефективно вона використовується в оптовій і роздрібній торгівлі, управлінні матеріальними запасами, управлінні перевезеннями.
Вступ 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
Штрихові коди типу CODABAR будуються аналогічно до Code39. Відмінністю між цими кодами є можливість кодувати в CODABAR тільки цифри в поєднанні з символами: “$”, “-“, ”:”, ”/”, ”.”, “+”. Як і CODE 39, штриховой код CODABAR використовує старт/стоп символи, в якості яких можуть виступати літери “a”, “b”, “c” і “d” в будь-яких комбінаціях: одна - для позначки початку коду і одна - кінця.
Інший тип штрихового коду - INTERLEAVED 2 OF 5, або ITF, подібно EAN - коду складається тільки з цифр, але, на відмінність від останнього, може мати різну довжину. Основне обмеження штрихового коду ITF - необхідність використання парної кількості цифр, що зв'язано з сумісництвом зі считувальними приладами. ITF код широко використовується в індустрії, де цифрового коду достатньо для опису маркованого об'єкту. Зокрема, при роздрібних продажах на Заході використовується так званий 'зовнішній' код. Цей код формується подібно коду EAN13, але, на відмінність від нього, містить 14 цифр. Перші 3 цифри вказують на країну маркування (для Великобританії - '050'), наступні 5 - номер компанії ('Продукти від Фреда' - '44016'), після цього ідуть п'ять цифр, що вказують на конкретний товар компанії (ці цифри повинні відрізнятися для різних модифікацій товару), і остання, контрольна цифра одержується в результаті арифметичних дій над тринадцятьма попередніми. Змінна довжина коду ITF дозволяє включати в штриховой код конкретні характеристики товару. Наприклад, при роздрібному продажі взуття штриховий код може містити розмір виробів і т. д.
Щоб зрозуміти принцип кодування ITF-кодів, розглянемо спочатку коди 2of5, а потім - їхні відмінності від INTERLEAVED 2 OF 5. В кодах 2 of 5 кожний символ представлений в вигляді 5 ліній, поділлених 4 пробілами, з 1 кінцевим пробілом. 2 з цих 5 ліній жирні, а 3 - тонкі (звідси назва - 2 OF 5). Жирні лінії як правило товщі від тонких в 2.5 рази, але це співвідношення може коливатися від 2,2:1 до 3:1.
В Таблиці 8 наведений принцип кодування (0 означає тонку лінію, 1 - жирну):
Таблиця 8.
Цифрове значення |
Комбінація ліній |
0 |
00110 |
1 |
10001 |
2 |
01001 |
3 |
11000 |
4 |
00101 |
5 |
10100 |
6 |
01100 |
7 |
00011 |
8 |
10010 |
9 |
01010 |
INTERLEAVED2OF5 відрізняється тільки тим, що для кодування цифр використовуються і пробіли. Перші 5 ліній представляють першу цифру, перші 5 пробілів - другу, наступні 5 ліній - третю, 5 пробілів - четверту і т. д.. Отже, код повинен містити парну кількість цифр.
3. Створення самокорегуючого
штрихового коду
3.1 Постановка задачі
Задача, яка буде описана тут, була сформульована під час введення на деякому великому підприємстві комп'ютеризованої системи пропусків. Кожен працівник мав свій 6-ти значний ідинтифікаційний код, котрий разом з фотографією та іменем працівника був нанесений на пластикову картку-перепустку. Але для автоматизації контролю за переміщенням працівників необхідно було забезпечити можливість зчитувати та аналізувати інформацію з цих карток-перепусток і для ЕОМ. Таку можливість можна забезпечити наявністю на перепустці магнітної стрічки або ж штрихового коду. Магнітна стрічка в данній ситуіції не є оптимальним вибором, в звязку з більшою вартістю як виготовлення такої картки так і її обслуговування. Головною перевагою магнітної картки є можливість збереження більшої інформації про власника, ніж при застосуванні штрихового коду, але в нашому випадку такої потреби немає - достатнь зберігати інформацію про ідинтифікаційний код робітника, та можливо ще яку-небуть (рівень доступу, час роботи, і т.п.).
Таким чином оптимальним
рішенням ціеї задачі є застосування
штрихового коду, який здатний кодувати
6-8 числових символів. Але використання
якого-небуть із загальновживаних типів
штрихових кодів виявилося
Всі ці проблеми в кінці-кінців привели до формулювання слідуючої постановки задачі: необхідно створити новий тип штрихового коду, основними вимогами до якого є простота, не вибагливість до скануючого пристрою, можливість кодування 6-8 числових символів та висока стійкість до помилок.
3.2 Хід роботи
Розглянувши основні методи, що застосовуються до побудови штрихових кодів, та зформулювавши постановку задачі, що стоїть перед нами, можемо безпосередньо приступати до її розв'язання.
Введемо наступну термінологію:
Алфавітом штрихкоду назвемо множину символів з яких складається інформація закодована в цьому штриховому коді.
Бітовий ряд - це послідовність скінченого числа "0" та "1" (в графічному представленні - білих та чорних штрихів), яка задає один символ алфавіту штрихкоду.
Вияснимо детальніще вимоги до нашого штрихового коду:
Вимога 1. Мінімальна кількість символів, яку повинен містити штрихкод - 6, але можливо це число варто збільшити до 7 або 8 символів вводячи резервне або контрольне число.
Вимога 2. Алфавіт нашого штрихового коду складається тільки з 10 цифр 0,1, ...,9. Одже на кодування одного символа нам знадобиться min 4 біти 24=16 (23<10). Насправді ця кількість в нас буде дещо більшою, за рахунок введення контрольних бітів та накладення деяких умов. Однією з таких умов буде наступна.
Вимога 3. Для запобігання злиття двох сосідніх бітових рядів, необхідно щоб кожен з таких рядів розпочиновся з 0 та закінчувався 1-цею.
Вимога 4. Велика кількість підряд йдучих однакових символів збільшує імовірнісь помилки. Тому слід накласти ще одну умову: в бітовому ряді не повинно бути підряд біль ніж 3 нулів чи одиничок.
Вимога 5. Як зазначалося в вимозі 2, в наслідок виимог 3-4, на кодування одного символа потрібно 6 біт.
Наш штриховий код
буде забезпечено властивістю
Таблиця 9.
k |
n |
m=k-n |
1 |
1 |
0 |
2 |
3 |
1 |
3 |
7 |
4 |
4 |
15 |
11 |
5 |
31 |
26 |
6 |
63 |
57 |
7 |
127 |
120 |
8 |
255 |
247 |
Мінімальне число бітів в бітовому ряді 6, якщо під інформаційні ми відведемо 26 біт, то ми зможемо кодувати 26/6=4 символи. Така кількість є недостатньою для нашої задачі, тому виділимо під інформаційні 57 бітів, так ми зможемо кодувати до 57/6=9 символів, що є навіть надлишково для нас.
В наступній таблиці записано всі можливі 6-ти значні бітові ряди, що задовільняють нашим умовам.
Таблиця 10.
1 |
000101 |
2 |
000111 |
3 |
001001 |
4 |
001011 |
5 |
001101 |
6 |
010001 |
7 |
010011 |
8 |
010101 |
9 |
010111 |
10 |
011001 |
11 |
011011 |
12 |
011101 |
Цієї кількості бітових рядів достатньо, щоб кожному символові нашого алфавіту штрихового коду поставити у відповідність один з них. Але розглянувши також і матрицю кодових відстаней цих бітових рядів(Таблиця11), мусимо зазначити деякі недоліки цього набору бітових рядів.
Таблиця 11.
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
0 |
1 |
2 | |
1 |
0 |
1 |
2 |
3 |
1 |
2 |
3 |
1 |
2 |
3 |
4 |
2 |
2 |
1 |
0 |
3 |
2 |
2 |
3 |
2 |
2 |
1 |
4 |
3 |
3 |
3 |
2 |
3 |
0 |
1 |
1 |
2 |
3 |
3 |
4 |
1 |
2 |
2 |
4 |
3 |
2 |
1 |
0 |
2 |
3 |
2 |
4 |
3 |
2 |
1 |
3 |
5 |
1 |
2 |
1 |
2 |
0 |
3 |
4 |
2 |
3 |
2 |
2 |
1 |
6 |
2 |
3 |
2 |
3 |
3 |
0 |
1 |
1 |
2 |
1 |
2 |
2 |
7 |
3 |
2 |
3 |
2 |
4 |
1 |
0 |
2 |
1 |
2 |
1 |
3 |
8 |
1 |
2 |
3 |
4 |
2 |
1 |
2 |
0 |
1 |
2 |
3 |
1 |
9 |
2 |
1 |
4 |
3 |
3 |
2 |
1 |
1 |
0 |
3 |
2 |
2 |
0 |
3 |
4 |
1 |
2 |
2 |
1 |
2 |
2 |
3 |
0 |
1 |
1 |
1 |
4 |
3 |
2 |
1 |
3 |
2 |
1 |
3 |
2 |
1 |
0 |
2 |
2 |
2 |
3 |
2 |
3 |
1 |
2 |
3 |
1 |
2 |
1 |
2 |
0 |
В різі виникнення однієї помилки в нашому штриховому коді, вона буде виправлена за допомогою алгоритму Хеммінга. В разі виникнення двох помилок метод Хеммінга перестає бути ефективним, в такій ситуації принаймні повинно бути виявлено наявність помилки. Ми забезпечуємо перевірку на наявність подвійних помилок, ввівши восьмий контрольний символ. Він функціонально залежить від інших символів, і ця залежність вибирається так щоб при зміні одного з перших семи символів, восьмий контрольний також обов'язково змінився. Якщо при виникненні двох помилок вони обі знаходяться в одному бітовому ряді, то наявність такої помилки буде виявлено контрольним символом, але якщо ці помилки з'являться в різних бітових рядах, тобто будуть змінені два числа в нашому коді, то можливі такі комбінації символів коли помилка не буде виявлена взагалі. Для запобігання таких помилок набір бітових рядів потрібно підібрати так, щоб матриця кодових відстаней цього набору не містила одиниць. Тоді при виникненні двох помилок в різних бітових рядах, ці новоутворені бітові ряди не будуть належати нашому наборові, і таким чином буде виявлено наявність помилок. В разі, якщо матриця кодових відстаней не буде містити одиниць, для того щоб було згенеровано помилку, яка не виявиться, необхідно, щоб ці помилки виникли по дві в двох різних бітових рядах. Тобто вивівши з матриці кодових відстаней одиниці, ми значно покращимо стійкість до помилок нашого коду.
Але тут виникає проблема: для того щоб вивести з матриці кодових відстаней одиниці, потрібно скоротити набір бінарних рядів, але тоді цього набору буде замало щоб поставити один бітовий ряд у відповідність одному симолу нашого алфавіту. Ми приходимо до потреби збільшення довжини наших бітових рядів з 6-ти до 7-ми символів.
57/7=8. Це також задовільняє
нашим вимогам. Ми зможемо
Таблиця 12.
1 |
0001001 |
2 |
0001011 |
3 |
0001101 |
4 |
0010001 |
5 |
0010011 |
6 |
0010101 |
7 |
0010111 |
8 |
0011001 |
9 |
0011011 |
10 |
0011101 |
11 |
0100011 |
12 |
0100101 |
13 |
0100111 |
14 |
0101001 |
15 |
0101011 |
16 |
0101101 |
17 |
0110001 |
18 |
0110011 |
19 |
0110101 |
20 |
0110111 |
21 |
0111001 |
22 |
0111011 |
Информация о работе Застосування штрих-коду для кодування інформації