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

Так, наприклад, для л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 число 123 представляється в виглядi: 1·102+ 2·101+ 3·100, тобто в виглядi суми мiр десятки. При цьому кодом числа є коефiцiенти при цих мiрах, тобто в даному випадку 123. Алфавiт такого коду складається з 10 символiв 0, 1, 2, 3, ..., 9, тобто L=10. Аналогiчно в двiйковiй системi числення, числа представляються в виглядi суми мiр двiйки. Наприклад, число 14 представляється в виглядi 1·23 + 1·22 + 1·21 + 0·20 або 1110. Тут кодом є коефiцiенти при вiдповiдних мiрах двiйки, i, отже алфавiт коду мiстить два символи - 0 i 1, тобто L= 2.

Декодування - процес, зворотний кодуванню. В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 сигналом звичайно представляється за допомогою масштабного множника

х(t) =me (t). (1.86)

Тут x(t) - деяка кiлькiсна величина (повiдомлення), e(t) - безперервний фiзичний сигнал (наприклад, електрична напруга), m -масштабний множник. Безперервн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й коду Nk було бiльше або рiвне числу рiзноманiтних повiдомлень Nc, тобто

Nk і--Nc. .(1.87)

Виберемо код постiйної довжини, алфавiт якого складається з L символiв i число позицiй (довжина кодового слова) рiвно n. За допомогою такого коду можна утворити Ln рiзноманiтних комбiнацiй (за вiдсутностi в кодi обмежень)

Nk = Ln. ..(1.88)

Пiдставляючи (1.88) в нерiвнiсть (1.87), отримаємо

Ln і--Nc

або

nlogL і logNc ..(1.89)

звiдки

n і log Nc/log L..(1.90)

Умова (1.90) - це умова вибору мiнiмального коду постiйної довжини для даної системи повiдомлень. Тут n - найближче бiльше цiле число, причому якщо має мiсце знак >, то код буде надлишковим.

Так як всi Ln комбiнацiї рiвноможливi, свобода вибору коду рiвна

Hk = logNk = n logL…(1.91)

З iншого боку, максимальна свобода вибору iнформацiї буде при рiвноможливих повiдомленнях, i в цьому випадку вона рiвна

Hc= logNc…(1.92)

Порiвнюючи (1.91), (1.92) з (1.89), отримаємо, що умова (1.89) рівносильна

Hk і Hс..(1. 93)

Таким чином, свобода вибору в кодi повинна бути бiльша або рiвна свободi вибору в системi повiдомлень. Якщо ж iмовiрностi рiзноманiтних повiдомлень неоднаковi, то необхiдна рiвнiсть в (1. 87) або (1. 89) призведе до нерiвностi в (1.93) (так як log Nс>Hc), тобто в цих випадках код постiйної довжини надлишковий. При нерiвноможливих повiдомленнях отримати рiвнiсть водночас в (1. 87) i (1. 93), тобто отримати код, оптимальний в сенсi мiнiмуму довжини повiдомлень, можна тiльки за допомогою коду змiнної довжини .

1.3.2 Коди з виявленням 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 припустимо, що група з n символiв може мiстити не бiльш однiєї помилки. Для здiйснення перевiрки на кiнцi,що передає, розбиваємо кожне повiдомлення на групи з m=n-1 символiв. До кожної групи дописуємо один символ так, щоб сума цифр в отриманiй групi з n символiв була парною.

Наприклад, при n=6

сигнал Провiрочний сигнал що

символ передається

10110 1 101101

10111 0 101110

Це дозволяє на приймальному кiнцi вiдразу виявити одноразову помилку, якщо прийнятий сигнал виявиться непарним. Для цього прийняте повiдомлення дiлять на групи з n символiв i визначають парнiсть суми цифр кожної групи. Пiсля перевiрки останнiй символ в кожнiй групi вiдкидається.

Однак такий простий засiб не дозволяє з'ясувати, в якому саме мiсцi нашого коду вiдбулася помилка. Крiм того, такий пiдхiд не дозволяє виявити подвiйну помилку, бо помилковий сигнал залишиться парним.

В 1950 г. Р. Хеммiнг поклав початок дуже важливим роботам по створенню кодiв, що виявляють i виправляють помилки, запропонований ним пiдхiд полягає в додаваннi не одного, а декiлькох провiрочних символiв i здiйсненнi декiлькох перевiрок на парнiсть в вiдповiдностi з виробленими правилами.

Розглянемо основну iдею цього методу. Маємо сукупнiсть з n двiйкових символiв i припускаємо, що в кодах довжиною n не зустрiчається бiльше однiєї помилки. З n символiв кодового слова m символiв будемо використовувати для передачi сигналу (повiдомлення), а iншi k символiв - для перевiрки

n=m+ k. (1.94)

За допомогою k провiрочних символiв можна скласти 2k рiзноманiтних комбiнацiй (рiзноманiтних двiйкових чисел), кожна з котрих повинна вказувати на один з наступних фактiв:

1) помилки немає; 2) помилка в першому символi; 3) помилка в другому символi i т. д.; n+1)помилка в символi номер n. Всього одержується n+1 вказiвка. Звiдки слiдує умова

2kn+1. (1.95)

Умова (1.95) дозволяє вибрати найменше число провiрочних символiв, необхiдних для виявлення i виправлення одиничної помилки в кодi довжиною n символiв. Таким чином, k - найменше цiле число, що задовольнить (1. 95). Сказане iлюструє таблиця, в якій найбiльше число символiв n може бути перевiрене застосуванням вiд 1 до 5 проверочнiх символiв k.

Кількість перевірочних символів k	Всього символів n	Інформаційні символи m =n-k
1	1	0
2	3	1
3	7	4
4	15	11
5	31	26

Спочатку розглянемо метод Хеммінга на прикладi третього випадку таблицi, так званого коду '4 з 7', де чотири дв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сть.

Нехай y1, y2, y3, y4 - вмiст m iнформацiйних розрядiв нашого сигналу (в даному випадку m=4). Крiм того, с5, c6, c7 - вмiст k проверочнiх розрядiв (в даному випадку k=3). Тодi провiрочнi суми мають вигляд:

Сума I: y1+ y2+ y3+ c5,

Сума II: y1+ y2+ y4+ c6, (1. 96)

Сума III: y1+ y3+ y4+ c7,

В залежностi вiд конкретного змiсту символiв y1, y2, y3, y4 встановлюється змiст символiв c5, c6, c7, так, щоб суми (1. 90) були парними. На табл. 1 крестики вiдповiдають методу складання перевiрочнiх сум.На приймальному кiнцi знов складаються всi суми (1.96). Якщо вони парнi, то помилки немає. Якщо виявилася непарною одна з сум, то помилка в провiрочному символi цiєї суми, бо всi інші

Таблиця 1

Інформація							Перевірка
1	2	3	4	5	6	7
y1	y2	y3	y4	c5	c6	C7
X	X	X		X			Сума І
X	X		X		X		Сума ІІ
X		X	X			X	Сума ІІІ

символи входять i в iншi суми, а вони парнi. Якщо двi суми непарнi, то помилка в тому символi, що входить в обидвi цi суми, але нс входить в третю. Нарештi, якщо всi суми непарнi, то помилка в тому символi, що входить в всi цi суми. Як тiльки визначено, в якому символi помилка, її виправлення не представляє складностi. Потрiбно замiсть даного символу поставити протилежний (якщо стоїть 0, поставити 1, а якщо 1, поставити 0). Проiлюструємо сказане прикладом використання коду “4 з 7”.

Маємо повiдомлення, кодоване двiйковими символами.

0000100010100100.

Подiлимо його на групи по чотири символи в кожнiй

0000 1000 1010 0100.

На кiнцi ,кожної з чотиризначних груп доповнимо ще трьома символами (c5, c6, c7), вiдповiдними перевiркам на парнiсть згiдно (1.96). Тодi отримаємо

0000000 1000111 1010010 0100110.

В пiдсумку повiдомлення ,що передається буде мати вигляд 0000000100011110100100100110.

На приймальному кiнцi повiдомлення розбивається на групи по сiм знакiв, здiйснюється перевiрка на парнiсть в вiдповiдностi з сумами (1.96), якщо необхiдно виправляються помилки, а пiсля цього в кожнiй семизначнiй групi усуваються три останнi знаки. Таким чином ми вiдновимо вхiдне повiдомлення. Приклад коду '4 з 7' пояснює загальний метод, запропонований Хеммiнгом. Вiн полягає в наступному. Складаємо стiльки перевiрочних сум, скiльки перевiрочних символiв встановлює нерiвнiсть (1.95). Кожна перевiрочна сума мiстить тiльки один перевiрочний символ ci, i кожний даний провiрочний символ зустрiчається в усiх сумах тiльки один раз. Перший символ y1 (з m iнформацiйних) входить у всi суми, кожний з наступних y₂...y_k+1 символiв входить в k-1 з k проверочнiх сум. Пiсля цього, якщо m>k iншi y_k+2... символiв входять в (k - 2) провірочних сум. Так, можна розмiстити ще 1/2 k (k-1)

Таблиця 2.

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
y1	Y2	y3	y4	y5	y6	y7	y8	y9	y10	y11	c12	c13	c14	c15
X	X	X	X	-	X	X	X	-	-	-	X	-	-	-
X	X	X	-	X	X	-	-	X	X	-	-	X	-	-
X	X	-	X	X	-	X	-	X	-	X	-	-	X	-
X	-	X	X	X	-	-	X	-	X	X	-	-	-	X

символiв з залишившихся m iнформацiйних i т. д. Цей метод утворення провірочних сум наочно iлюструє приклад коду '11 з 15' (табл. 2).

Викладене поширюється i на бiльш складнi випадки, коли код може водночас мiстити двi помилки, три i т. д. При цьому умова (1.95), кiлькiсть необхiдних провірочних символiв, змiнюється. Наприклад, якщо припустити, що код може мiстити двi помилки, то до n+1 вказiвки (помилок немає, в такому-то мiсцi є одинична помилка) повиннi додатися вказiвок можливих комбiнацiй по двi помилки, тобто повинно мати мiсце

. (1.97)

Якщо в кодi можливi i три помилки, то повиннi додатися ще вказiвок можливих комбiнацiй по три помилки, тобто

2k>= (n+1) + ^l/₂n(n -1) + ¹/_3! n(n - 1), (1.98)

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 можливих N повiдомлень ми користуємось n-розрядним двiйковим кодом. Кожне n-розрядне двiйкове слово можна уявити точкою в n-мiрному просторi, координати якого - значення символiв по кожному розряду (0 або 1). Якщо n=3, то ми маємо звичайний тривимiрний простiр, де означенi точки утворять вершини одиничного куба (рис. 7).



Домовимося називати вiдстанню dij мiж двома кодовiми словами (двома вершинами куба) найменше число їхнiх ребер ,що роздiляють їх або, що те ж саме, кiлькiсть порозряднiх не-збiгiв в цих двох словах. Наприклад, вiдстань мiж двiйковими словами 101100 i 100110 рiвна dij =2. Якщо код не володiє надлишковiстю, тобто N=2n, те кожному кодовому слову вiдповiдає своє повiдомлення i мiнiмальний iнтервал при такому кодуваннi dij min рiвний 1. Природньо, що такий код не може виявити помилку, бо будь-яка помилка перекладає дане слово в iнше, вiдповiдне iншому повiдомленню. Цю помилку не можна буде вiдрiзнити вiд iншого сигналу. Якщо ж N<2n, тобто має мiсце надлишковiсть, те не всi вершини куба можна взяти в якостi кодових слiв, вiдповiдних повiдомленням, а тiльки частину з них. Тодi можна вибрати код, при якому dijmin=2, i виявити одну помилку (але не виправити). Дiйсно, наявнiсть помилки призведе до того, що помилкове слово буде стояти вiд iншого кодового слова на iнтервалi, рiвному dij=1. А це для iстинних повiдомлень неможливо. Але подвiйну помилку вже виявити не можна, бо вона переведе наше слово в iнше кодовое слово, вiдповiдне iншому iстинному повiдомленню. Якщо вибрати код з мiнiмальним iнтервалом dij min=3, то одинична помилка призведе до отримання слова, що стоїть на вiдстанi dij=1 вiд вхiдного. Але вiд iнших слiв коду, вiдповiдних iстинним повiдомленням, воно буде вiдстояти мiнiмум на двi одиницi. Це дозволяє знайти викривлене слово (вхiдне), тобто виправити помилку. Таким чином, код з dij min=3 дозволяє виправити одиничну помилку i виявити подвiйну. В загальному випадку, якщо N << 2n (бiльша надлишковiсть), то при мiнiмальнiй вiдстанi мiж словами, рiвнiй d_ijmin = 2(m+1) (m - цiле, додатнє), можна побудувати код, що виправляє v-кратну помилку (v= 1, 2,..., m) або що виявляє 2v-кратну.

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

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

Як правило той або інший тип штрихкоду вибирають, виходячи з наступних чинників:

Прикладний пакет підтримує тільки один тип коду;

Промислові стандарти диктують той або інший тип коду;

Тип коду вибирається виходячи з умови відповідності іншим системам і/або обладнанню ,що використається;

Особисті вподобання керівника.

Дуже часто штрихкоди наносять так, як про це просить майбутній продавець даного товару. В цьому випадку виробник, імпортер, або пакувальник при нанесенні EAN-коду використає номер виробника. На тару може наноситися або 13-символьний EAN-код, або 14-символьний ITF. Найбільший по розміру EAN-код, що може бути нанесений, занадто малий і тому може загубитися на великій тарі. Він також вимагає високої точності друку, що неможливо при друкуванню на такому матеріалі, як наприклад, картонні коробки. ITF-код може бути значно більшого розміру і для нього допустимі більші відхилення ширини ліній і пробілів, що робить можливим прямий друк навіть на низкоякісному субстраті. Кожному, хто використовує штрихове кодування в роздрібній торгівлі, слід подумати про використання EAN-кодів. Для торгівлі харчовими продуктами вони є узвичаєним стандартом. Але оскільки багато організацій, що торгують харчовими продуктами, продають зараз багато нехарчових, а продавці наполягають на маркуванні їх за допомогою EAN, тому безліч інших видів продукції доставляється зараз вже маркованими за допомогою EAN. Однак в торгівлі взуттям і ювелірними виробами прийняте маркування за допомогою ITF. Гнучкість цього коду відносно довжини робить його більш придатним, ніж EAN з жорстко фіксованими розмірами. Контрольна цифра в ITF необовязкова, але може використовуватися, з умовою, що прінтер і сканер штрихкода працюють в одному режимі. CODE 39 - мабуть, найбільш розповсюджений в неторгівельній сфері. Його обрали збройні сили і автомобільна промисловість. Якщо вимагаються різноманітні довжини кодів, а також використання літерних символів, найбільш зручним є CODE 39. В поштовій справі знайшов своє примінення штрихкод типу POSTNet. Для кодування великих об'ємів інформації на малій площі застосовують двомірні штрихові коди, такі як PDF-417, DATAMATRIX та ін.

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

Співвідношенням між широким і вузьким елементами - друкованим відношенням

шириною вузького елементу (часто називають ширина модуля)

комбінаціями штрихів і пробілів для кодування знаків

кількістю знаків в символі

комбінаціями штрихів і пробілів для кодування старт/стоп знаків.

допусками при друці кожного елементу

контрольним розрядом (контрольною сумою)

В даній таблиці наведено основну характеристику найбільш вживаних світових стандартів штрихових кодів.

Таблиця 3

№	Тип штрихкода	Довжина	Контрол. Розряд	Допустимі символи
1	3 of 9	Різна	-	0-9, A-Z, -.*/+% и пробіл
2	UPC-A	11 цифр	+	0-9
3	UPC-E	6 цифр	+	0-9
4	Interleaved 2 of 5	Різна	-	0-9
5	Code 128 (A,B,C)	Різна	M-103	128 символів ASCII
6	EAN-13	12 цифр	+	0-9
7	EAN-8	7 цифр	+	0-9
8	Health Industry Bar Code (HIBC)	Різна	M-43	0-9, A-Z, -.$:/. Повинен починатися з "+"
9	Codabar	Різна(Мін. 3 символа)	-	0-9,-,.,$,:,/,+, і коди старт/стопа a, b, c и d
10	Interleaved 2 of 5 without Bars	Різна	M-10	0-9
11	MSI Plessey	Різна	M-10	0-9, Якщо + останній символ, на місто символа + буде добавлена додаткова контрольна сумма MSI
12	Interleaved 2 of 5 (UPC CASE)	13	M-10	0-9
13	UPC 2 digit add	2 цифри	+	0-9
14	UPC 5 digit add	5 цифр	+	0-9
15	Code 93	Різна	-	128 символів ASCII
16	Postnet	Різна	+	0-9
17	UCC/EAN Code 128	19 цифр	+	0-9
18	UCC/EAN Code 128 K-MART NON EDI	18 цифр	+	0-9
19	UCC/EAN Code 128 Random Weight	Різна, принаймні 34 цифри	+	0-9
20	Telepen	Різна	+	128 символів ASCII
21	UPS MaxiCode	84	+	0-9, A-Z
22	FIM	1 символ	-	A, B, C або D
23	PDF-417	Різна	+	Всі символи ASCII

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

Цей код частіше інших зустрічається на упаковках імпортних продуктів харчування в супермаркетах. EAN - абревіатура European Article Number (європейський номер товару), а американський еквівалент UPC - абревиатура від Universal Product Code (унивесальный код товару).Існують 2 типи штрихового коду EAN: EAN8, що кодується вісьмома цифрами і EAN13, що кодуєтся тринадцятьма цифрами. Слово 'цифра', а не 'символ', використовується навмисне, тому що EAN (і UPC) можуть містити тільки цифри.

Штрихові коди UPC, на перший погляд, мають вигляд точнісінько такий, як і коди EAN, але вони складаються тільки з дванадцяти (UPS-A) або шести (UPS-E) цифр. EAN International - це добровільна некоммерційна і не урядова міжнародна Асоціація, що складається з національних організацій (в нинішній час 80 організацій в 89 країнах). EAN (European Article Numbering) International управляє міжнародною багатогалузевою системою товарної нумерації і стандартів штрихового кодування, що дозволить ідентифікувати і передавати дані про товари, послуги, підприємства, транспортні одиниці і адресні дані.

Розглянемо структуру штрихового коду типів ЕAN на прикладі EAN-13.

Перші 3 цифри називаються префіксом EAN і присвоюються EAN International. Ними ідентифікуються національні організації. Национальні організації товарної нумерації уповноважені EAN International використовують систему EAN на національному або регіональному рівнях в якості офіційних представників EAN. В окремо взятій країні або регіоні може існувати тільки один представник EAN Intrernational. Префікси 460-469 в коді EAN-13 присвоєні Росії. Префікс 482 присвоєно ЮНІСКАН/EAN України. Префікс завжди є зісланням на національну організацію. Так префікс 482 означає, що підприємство зареєстроване в Українському відділенні EAN, а зовсім не те, що підприємство знаходиться на території України. В національну організацію України може вступити будь-яке підприємство, наприклад, розташоване на території Німеччини, Казахстану, Росії і т. д., за умови, що воно має своє представництво в Україні. При вступі в ЮНІСКАН/EAN України підприємству буде присвоєний відповідний код, що починається префіксом 482. Аналогічно, наприклад, префікс 50 означає, що підприємство зареєстроване в національній організації Великобританії, а не те, що воно розміщене на англійській території. (Префікси деяких національних організацій складаються з 2 цифр.) Наступні 9 цифр містять номер підприємства, що зареєструвалось всередині національної організації, і номер товару. Структура 9 знаків, що належать номеру підприємства і номеру товару, визначається безпосередньо національною організацією, наприклад:

5 - підприємство/4 - товар,

6 - підприємство/3 - товар,

7 - підприємство/2 - товар і ін.

В нинішній час ЮНІСКАН/EAN України визначило наступну структуру: 4 цифри - номер підприємства, 5 цифр - номер товару. Остання 13 цифра називається контрольним розрядом. Вона призначена для перевірки правильності считування коду EAN скануючим пристроєм. Прочитавши графічне зображення штрихового коду за допомогою сканера і перетворивши його в цифровий код, комп'ютер по спеціальному алгоритму обчислює контрольний розряд і порівнює його із зісканованим з графічного зображення. Збіг зісканованого і обчисленого контрольних розрядів означає правильне считування штрихового коду. В цьому випадку на сканері з'являється відповідний світловий/звуковий сигнал. Якщо код читається погано, то одна або декілька цифр коду можуть бути при зчитуванні викривлені. В цьому випадку сканер не дасть сигнал про правильне зчитування. Аналогічно, якщо хто-небуть придумав свій код з довільних 13 цифр або, якщо контрольний розряд має довільне значення, те цей штриховий код сканером зчитуватися не буде.

Розглянемо алгоритм знаходження контрольного числа(розряду) для коду EAN13. EAN-13 CODABAR самокорегуючий програмний

В процесі знаходження контрольного числа в коді EAN 13 використовуються наступні значення:

МОДУЛЬ: 10

ВАГИ: 131313131313

СУМА: Добутків

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

КРОК 1: Починаючи з крайнього праворуч розряду, виключаючи контрольний розряд, скласти величини парних розрядів;

КРОК 2: Результат КРОКУ 1 помножити на 3;

КРОК 3: Скласти величини розрядів ,що залишалися;

КРОК 4: Скласти результати КРОКІВ 2 і 3;

КРОК 5: Значення контрольного розряду є найменшим числом, що в сумі з величиною, отриманої в КРОЦІ 4, дасть число, кратне 10.

Приклад розрахунку контрольного розряду в коді EAN-13 =467622135746С

4 6 7 6 2 2 1 3 5 7 4 6 C

Крок 1: 6+6+2+3+7+6=30

Крок 2: 303=90

Крок 3: 4+7+2+1+5+4 =23

Крок 4: крок 2+ крок 3=113

Крок 5: С=120-113=7

Роз'яснення: наступне за 113 найближче кратне 10 число рівне 120. Тому контрольний розряд в коді EAN-13 буде рівний: 120 - 113=7, а повний номер EAN-13 буде наступним: 4676221357467.

Розглянемо особливості графічної побудови кодів типу EAN-13. Штрихові коди цього типу повинні мати так-звані “тихі зони” з обох боків штрихкоду. “Тихі зони” - незаповнені області, вільні від будь-якого друку, звичайно їх ширина не повинна бути меншою десятикратної ширини найменшого бруска штрихового коду.

Якщо уважно роздивитися штриховий код EAN-13, то можна побачити, що на початку та в кінці, а також посередині штрихкоду є бруски довжина яких більша ніж у інших. Ці бруски є контрольними і використовуються для “регулювання” сканера. Перше число з 13-ти значного коду розташоване зовні цих брусків, решта 12 поділена на дві групи й записані в середині коду. Кожне число закодоване через сім брусків: чорний=1 та білий=0.

Штриховий код використовує три набори бітових рядів для представлення чисел 0-9.

Таблиця 4.№

	Набір А		Набір В		Набір С
0	0001101	13	0100111	39	1110010	114
1	0011001	25	0110011	51	1100110	102
2	0010011	19	0011011	27	1101100	108
3	0111101	61	0100001	33	1000010	66
4	0100011	35	0011101	29	1011100	92
5	0110001	49	0111001	57	1001110	78
6	0101111	47	0000101	05	1010000	80
7	0111011	59	0010001	17	1000100	68
8	0110111	55	0001001	09	1001000	72

Границі: 101

Центр: 01010

Для використання цієї таблиці необовязково знати її всю. Набори В та С можна утворити з набору А слідуючим чином. Набір С рівний запереченню набору А (тобто С=notA), а набір В є записом набору С в зворотньому порядку.

Розділимо умовно наш 13-ти значний код на три групи

N YYYYYY GGGGGG.

Числа позначені в нашій схемі буквою G будуть кодуватися бітовими рядами з набору С. Числа позначені Y кодуються бітовими рядами з групи А або В. Група YYYYYY може приймати такі значення(Таблиця 5):

Таблиця 5

№ набору	№1	№2	№3	№4	№5	№6
0	A	A	A	A	A	A
1	A	A	B	A	B	B
2	A	A	B	B	A	B
3	A	A	B	B	B	A
4	A	B	A	A	B	B
5	A	B	B	A	A	B
6	A	B	B	B	A	A
7	A	B	A	B	A	B
8	A	B	A	B	B	A
9	A	B	B	A	B	A

Номер набору вибирається в залежності від значення числа N в нашій схемі.

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

ШТРИХОВИЙ КОД: 8 000570 004257

1.Перший символ 8, тому група буде мати вигляд АВАВВА

2.Для чисел 000570 вибираємо бітові ряди зі слідуючих наборів: ABABBA, а для чисел 004257 з набору C

3.Схемою нашого числа буде: 8 ABABBA CCCCCC

Штриховой код EAN8 формується подібно коду EAN13, з тією лише різницєю, що замість пятизначных номерів для ідентифікації компанії і товару використовуються, відповідно, трьохзначні і двозначні номери. Перші дві цифри - номер країни, наступні три цифри - номер компанії, після цього іде унікальний номер товару і остання цифра - контрольна.

Для знаходження контрольного числа в EAN8 використовується той же механізм. Параметри тут будуть наступні:

МОДУЛЬ: 10

ВАГИ: 3131313

СУМА: Добутків.

Штрихові коди типів UPC є різновидами кодів EAN які використовуються виключно на території Сполучених Штатів( аналогічно в Японії використовують аналог цих кодів - JAN).

Размещено на http://www.allbest.ru/

1

58

Размещено на http://www.allbest.ru/

Рис: UPC-A Рис: UPC-E

9 червня 1997 року американська організація Uniform Code Council прийняла рішення про розширення з 1січня 2005 року кодів UPC-A та UPC-E на один сивол, тим самим привівши їх до стандартів EAN13 та EAN8.

2.3 Code39 та CODABAR

Сode39 - алфавітно-цифровий штриховий код. Він був розроблений в 1974 році, і був призначений щоб кодувати 43 символи: 26 букв латинської абетки верхнього регістру, 10 цифр і 7 спеціальних символів(знаків). Він може бути розширений на всі 128 ASCII символи(знаки), використовуючи два символи, що задають схему кодування.

Кожний знак даних, кодований в Code39 складений з 5 чорних брусків (барів) і 4 пробілів для загальної кількості 9 елементів. Кожний брусок (бар) або пробіл є або 'широким' або 'вузьким', і 3 з 9 елементів завжди широкі. Саме тому цей код і отримав свою назву.

Штриховий код включає тиху зону (10x-барів або 0.10 дюймів, що є більшим), символ початку '*', кодовані дані, символ зупинки '*', і знову тиха зона. Символ `*' зірочки використовується тільки як код зупинки і початку. X-бар - ширина самого маленького елементу в символі штрихового коду. Висота брусків(барів) повинна бути принаймні 15-ти кратною довжиною символу або 0,25 дюймів. Повна довжина символу дасться рівнянням:

L=(C+2) (3N+6) X (+C+1)I

Де

L=довжина символу включаючи «тихі зони»

C=число знаків даних

X=X-бар (ширина самого маленького елементу)

N=відношення широкого бруска до вузького

I=Ширина проміжку між знаками

Таблиця 6.

Character	B1	S1	B2	S2	B3	S3	B4	S4	B5
1	1	0	0	1	0	0	0	0	1
2	0	0	1	1	0	0	0	0	1
3	1	0	1	1	0	0	0	0	0
4	0	0	0	1	1	0	0	0	1
5	1	0	0	1	1	0	0	0	0
6	0	0	1	1	1	0	0	0	0
7	0	0	0	1	0	0	1	0	1
8	1	0	0	1	0	0	1	0	0
9	0	0	1	1	0	0	1	0	0
0	0	0	0	1	1	0	1	0	0
To	1	0	0	0	0	1	0	0	1
B	0	0	1	0	0	1	0	0	1
C	1	0	1	0	0	1	0	0	0
D	0	0	0	0	1	1	0	0	1
And	1	0	0	0	1	1	0	0	0
F	0	0	1	0	1	1	0	0	0
G	0	0	0	0	0	1	1	0	1
H	1	0	0	0	0	1	1	0	0
I	0	0	1	0	0	1	1	0	0
J	0	0	0	0	1	1	1	0	0
K	1	0	0	0	0	0	0	1	1
L	0	0	1	0	0	0	0	1	1
M	1	0	1	0	0	0	0	1	0
N	0	0	0	0	1	0	0	1	1
Or	1	0	0	0	1	0	0	1	0
P	0	0	1	0	1	0	0	1	0
Q	0	0	0	0	0	0	1	1	1
R	1	0	0	0	0	0	1	1	0
S	0	0	1	0	0	0	1	1	0
T	0	0	0	0	1	0	1	1	0
U	1	1	0	0	0	0	0	0	1
V	0	1	1	0	0	0	0	0	1
W	1	1	1	0	0	0	0	0	0
X	0	1	0	0	1	0	0	0	1
Y	1	1	0	0	1	0	0	0	0
Z	0	1	1	0	1	0	0	0	0
-	0	1	0	0	0	0	1	0	1
.	1	1	0	0	0	0	1	0	0
Space	0	1	1	0	0	0	1	0	0
*	0	1	0	0	1	0	1	0	0
$	0	1	0	1	0	1	0	0	0
/	0	1	0	1	0	0	0	1	0
+	0	1	0	0	0	1	0	1	0
%	0	0	0	1	0	1	0	1	0

B1-B5 бруски

S1-S4 - пробіли

1 широкий

2 вузький

3 В Code39 контрольне число є самим правим символом коду. Щоб обчислити його, потрібно додати ціни всіх символів коду( Таблиця 7), і знайти mod43 з суми. Так, якщо сума була 178, контрольне число буде 6.

Контрольна сума в Code39 використовується рідко, тому що Code39 весь час перевіряє себе; як-тільки що-нибудь, не відповідає формату 3 з 9, воно одразу буде відкинене як хибне.

Приклад: маємо текст “CODE-39”.

КРОК 1: Сума цін: 12+24+13+14+36+3+9=111

КРОК 2: 111mod43=25

КРОК 3: числу 25 відповідає символ “P”

Рядок після кодування: “CODE-39P”

Таблиця 7.

Cимвол	Ціна	Символ	Ціна
0	0	M	22
1	1	N	23
2	2	O	24
3	3	P	25
4	4	Q	26
5	5	R	27
6	6	S	28
7	7	T	29
8	8	U	30
9	9	V	31
A	10	W	32
B	11	X	33
C	12	Y	34
D	13	Z	35
E	14	-	36
F	15	.	37
G	16	space	38
H	17	$	39
I	18	/	40
J	19	+	41
K	20	%	42
L	21

Штрихові коди типу CODABAR будуються аналогічно до Code39.

Відмінністю між цими кодами є можливість кодувати в CODABAR тільки цифри в поєднанні з символами: “$”, “-“, ”:”, ”/”, ”.”, “+”. Як і CODE 39, штриховой код CODABAR використовує старт/стоп символи, в якості яких можуть виступати літери “a”, “b”, “c” і “d” в будь-яких комбінаціях: одна - для позначки початку коду і одна - кінця.

1.3 INTERLEAVED 2 OF 5

Інший тип штрихового коду - 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 біти 2⁴=16 (2³<10). Насправді ця кількість в нас буде дещо більшою, за рахунок введення контрольних бітів та накладення деяких умов. Однією з таких умов буде наступна.

Вимога 3. Для запобігання злиття двох сосідніх бітових рядів, необхідно щоб кожен з таких рядів розпочиновся з 0 та закінчувався 1-цею.

Вимога 4. Велика кількість підряд йдучих однакових символів збільшує імовірнісь помилки. Тому слід накласти ще одну умову: в бітовому ряді не повинно бути підряд біль ніж 3 нулів чи одиничок.

Вимога 5. Як зазначалося в вимозі 2, в наслідок виимог 3-4, на кодування одного символа потрібно 6 біт.

Наш штриховий код буде забезпечено властивістю самовиправлення помилок, яка буде базуватися на методі Хеммінга. Для цього нам необхідно вияснити яку кількість бітів ми відведемо під перевірочні. Виходячи з відомої формули 2^k>n+1, де n - загальна кількість бітів, k - кількість провірочних бітів, m=n-k - кількість інформаційних бітів, отримуємо наступну таблицю:

Таблиця 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. Це також задовільняє нашим вимогам. Ми зможемо кодувати до восьми символів. В наступній таблиці записано всі можливі бітові ряди, що задовольняють нашим умовам. Нагадаємо, що алфавіт нашого штрихового коду складається з 10 символів, а оскільки допустимих бінарних рядів 22 то в нас тепер є змога розділивши їх на дві групи, кодувати один з наших символів не бітовим рядом, а належністю бітових рядів інших символів до тієї чи іншої групи (детально цей метод кодування було описано під час опису типу штрихкоду EAN-13).

Таблиця 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

За рахунок цього можна або додати до нашого коду дев'ятий символ без збільшення кількості бітів в штриховому коді( тим самим зменшивши надлишковість нашого коду), або, залишивши наш код 8-ми символьним, зменшити кількість біт, що будуть кодувати цей код (тим самим також зменшивши надлишковість).

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

Таблиця 13

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
1	0	1	1	2	3	3	4	1	2	2	3	3	4	1	2	2	3	4	4	5	2	3
2	1	0	2	3	2	4	3	2	1	3	2	4	3	2	1	3	4	3	5	4	3	2
3	1	2	0	3	4	2	3	2	3	1	4	2	3	2	3	1	4	5	3	4	3	4
4	2	3	3	0	1	1	2	1	2	2	3	3	4	3	4	4	1	2	2	3	2	3
5	3	2	4	1	0	2	1	2	1	3	2	4	3	4	3	5	2	1	3	2	3	2
6	3	4	2	1	2	0	1	2	3	1	4	2	3	4	5	3	2	3	1	2	3	4
7	4	3	3	2	1	1	0	3	2	2	3	3	2	5	4	4	3	2	2	1	4	3
8	1	2	2	1	2	2	3	0	1	1	4	4	5	2	3	3	2	3	3	4	1	2
9	2	1	3	2	1	3	2	1	0	2	3	5	4	3	2	4	3	2	4	3	2	1
10	2	3	1	2	3	1	2	1	2	0	5	3	4	3	4	2	3	4	2	3	2	3
11	3	2	4	3	2	4	3	4	3	5	0	2	1	2	1	3	2	1	3	2	3	2
12	3	4	2	3	4	2	3	4	5	3	2	0	1	2	3	1	2	3	1	2	3	4
13	4	3	3	4	3	3	2	5	4	4	1	1	0	3	2	2	3	2	2	1	4	3
14	1	2	2	3	4	4	5	2	3	3	2	2	3	0	1	2	2	3	3	4	1	2
15	2	1	3	4	3	5	4	3	2	4	1	3	2	1	0	2	3	2	4	3	2	1
16	2	3	1	4	5	3	4	3	4	2	3	1	2	2	2	0	3	4	2	3	2	3
17	3	4	4	1	2	2	3	2	3	3	2	2	3	2	3	3	0	1	1	2	1	2
18	4	3	5	2	1	3	2	3	2	4	1	3	2	3	2	4	1	0	2	1	2	1
19	4	5	3	2	3	1	2	3	4	2	3	1	2	3	4	2	1	2	0	1	2	3
20	5	4	4	3	2	2	1	4	3	3	2	2	1	4	3	3	2	1	1	0	3	2
21	2	3	3	2	3	3	4	1	2	2	3	3	4	1	2	2	1	2	2	3	0	1
22	3	2	4	3	2	4	3	2	1	3	2	4	3	2	1	3	2	1	3	2	1	0

Виберемо з 22-х бітових рядів десять таких, щоб їх матриця кодових відстаней не містила одиниць. Отримаємо Таблицю 14.

Таблиця 14

0	0001001
1	0010001
2	0010111
3	0011011
4	0011101
5	0100111
6	0101011
7	0101101
8	0110011
9	0110101

Матриці кодових відстаней:

Таблиця 15

	0	1	2	3	4	5	6	7	8	9
0	0	2	4	2	2	4	2	2	4	4
1	2	0	2	2	2	4	4	4	2	2
2	4	2	0	2	2	2	4	4	2	2
3	2	2	2	0	2	4	2	4	2	4
4	2	2	2	2	0	4	4	2	4	2
5	4	4	2	4	4	0	2	2	2	2
6	2	4	4	2	4	2	0	2	2	4
7	2	4	4	4	2	2	2	0	4	2
8	4	2	2	2	4	2	2	4	0	2
9	4	2	2	4	2	2	4	2	2	0

Наш штриховий код буде мати слідуючу структуру:

0ххххх10ххххх10ххххх10ххххх10ххххх10ххххх10ххххх10ххххх1nnnnnn

Вона містить один невеликий недолік, останні шість бітів можуть неправильно зчитуватися. Наприклад: а) вище ми накладали обмеження на кількість однакових підряд йдучих символів "0" чи "1" , на комбінацію nnnnnn в данному випадку таке обмеження не поширюється; б) в разі, якщо остнній байт чи байти будуть рівні "1", то при графічному представленні цього коду вони будуть втрачені, оскільки зіллються з "тихою зоною". Щоб запабігти цим небажанним явищам, введемо додаткові нульові біти в кінець нашого коду. Отримаємо код наступної структури:

0ххххх10ххххх10ххххх10ххххх10ххххх10ххххх10ххххх10ххххх101nn01nn01nn010

В цьому коді всі вище перераховані недоліки усунуто.

Потрібно також для нашого коду вибрати алгоритм знаходження контрольного числа. Запозичимо алгоритм з коду типу EAN. Тоді вагами будуть "3 1 3 1 3 1 3", а контрольне число буде рівне mod10 від зваженої суми.

Таким чином створивши штриховий код( назвемо його НЕМ-8), було розвязано поставлену перед нами задачу. Нам залишилося тільки перевірити єфективність цього коду. Для початку підрахуємо ентропію нашого коду. Не важко пересвідчитися що НЕМ-8 складається з 71 біта, кількість комбінацій чисел які можна утворити 10 міліонів ( 10⁷ ), оскільки восьме число залежить тільки від перших семи, ми його не враховуємо. Кількість інформації шо несе в собі штрихкод НЕМ-8 рівна I(a)=log(10⁷). Вище була наведена формула для знаходження величини надлишковості коду, використаємо її тепер.

в нашому випадку алфавіт двозначний L=2, кількість бітів n=71 тому

Як бачимо коефіцієнт надлишковості досить великий, для порівняння надлишковість коду EAN-13 рівна

,

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

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

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

Результати отримані при виконанні цієї дипломної роботи можна умовно разділити на початкові та кінцеві. Початкові результати були отримані первоначально, при використанні програми Oldkoran. Отримавши їх:

Кількість помилок в коді	1
Кількість згенерованих помилкових кодів	71е7
В тому числі: виправлено	71е7	100%
В тому числі: виявлено але не виправлено	0	0%
В тому числі: не виявлено	0	0%
Кількість помилок в коді	2
Кількість згенерованих помилкових кодів	2.485е10
В тому числі: виправлено	1.465е10	58.9537%
В тому числі: виявлено але не виправлено	1.008е10	40.5707%
В тому числі: не виявлено	1.1818е8	0.4756%

було виявлено деяку недосконалість коду. А саме - при генерації в коді двох помилок бло виявлено деякі можливі комбінації при яких програма була не в змозі навіть виявити помилку. І хоча таких комбінацій дуже мало (всього як бачимо 0.48%), тобто імовірність того, що саме в цьому коді виникне саме ця комбінація помилок - мізерна. Але тим не менше цю ваду необхідно було виправити.

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

Проаналізувавши початкові результати, їх недоліки, та причини що їх викликали було вирішено замінити таблицю кодування чисел на таку, для якої б матриця кодових відстаней не містила одиниць. Було отримано таблицю 14. Як бачимо з нових результатів:

Кількість помилок в коді	1
Кількість згенерованих помилкових кодів	71е7
В тому числі: виправлено	71е7	100%
В тому числі: виявлено але не виправлено	0	0%
В тому числі: не виявлено	0	0%
Кількість помилок в коді	2
Кількість згенерованих помилкових кодів	2.485е10
В тому числі: виправлено	1.465е10	58.9537%
В тому числі: виявлено але не виправлено	1.02е10	41.0463%
В тому числі: не виявлено	0	0%

попередню ваду було усунуто і на цей раз помилок в коді які б не виявлялися нема. Крім того проаналізувавши матрицю кодових відстаней (табл.15), бачимо що навіть при генеруванні 3 помилок в коді, всі помилкові коди або будуть виправлені або хоча б виявлені, шо свідчить про високу ефективність коду НЕМ-8.

5. Програма

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

В ході віконання цієї дипломної роботи було створено пакет з чотирьох програм: Moonbug, Koran, Oldkoran та Hem8. В цьому розділі буде приведено їх опис та інструкції користувача.

Koran та Oldkoran по суті це одна й та сама програма, тому в цій роботі приведено лістинг тільки першої. Різниця між цими програмами тільки в таблиці кодування чисел коду. Koran використовує для кодування таблицю бітових рядів матриця кодових відстаней яких не містить одиниць, про необхідність цього наголошувалось в попередньому розділі. Цю необхідність добре було видно при порівнянні результатів роботи цих двох програм. Оldkoran використовує для кодування таблицю бітових рядів, матриця кодових відстаней яких містить одиниці, що збільшує йомовірність появи таких помилок, які не тільки не будуть виправлені, а й не будуть виявлені.

Koran та Oldkoran це DOS-програми, створені за допомогою компілятора Borland C++ 3.1. Запустивши їх побачимо слідуюче меню.

Der Diplomprojekt v.1.2 'Koran' Mishel Kozak

1. Beginn prufung

2. Fortsetzen prufung

?

Перший пункт - розпочати тест, другий - продовжити. В разі якщо ми починаемо тест, вибираємо перший пункт натиснувши "1", після якого програма поцікавиться іменем файлу в який буде записуватися інформація стосовно нашого тесту:

Der Diplomprojekt v.1.2 'Koran' Mishel Kozak

Einfurst der Filename(*.krn): [ ]

Після вводу імені файла, програмі необхідно вказати з якого коду починати тестування:

Der Diplomprojekt v.1.2 'Koran' Mishel Kozak

Einfurst anfangs kode: [ ]

Програма перевірятиме вся коди починаючи з введеного. Для повного тесту необхідно вказати код 0000000. Можливість введення початкового коду передбачена на випадок якщо тестування буде проводитися на кілкох ЕОМ. Ввівши початковий код програма виводить новий запит:

Der Diplomprojekt v.1.2 'Koran' Mishel Kozak

Einfurst anfangs kode: [1111111]

Einfurst der Anzahl fehler(1/2): [ ]

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

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

Der Diplomprojekt v.1.2 'Koran' Mishel Kozak

Einfurst der Filename(*.krn): [ ]

На відміну від випадку в першому пункті, тут очікується що такий файл уже існує, інакше програма не розпочне тестування. Решту інфомації програма отримає з цього файла й розпочне тестування.

Під час тестування на дисплеї ЕОМ періодично виводиться проміжкова інформація про процес тестування.

Der Diplomprojekt v.1.2 'Koran' Mishel Kozak

May 26 15:38:00 1999

Code: 0 0 0 0 2 6 8 8

Code: № _ _ _ + + _

Type error: 2

_ 1_ 1_ 1_ 1_ 1_ 1_ 1_ 1_1 _1 _1 _1_

Real___ __ ___ __ ___ __ ___ __ __ _ _ _ _ _ __ _ __ _ _ _ __ _ _

error___ __ ___ __ ___ __ ___ __ __ _ _ _ _ _ __ _ __ _ _ _ __ _ _

Total error: 668465

= fatal error: 274380 41.046278%

= corectly error: 394085 58.953722%

= warning error: 0 0%

For exit press 'q'...

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

Програма перебирає всі коди починаючи з початкового, який ми вказали на початку тесту. Для кожного коду програма генерую всі можливі помилки. Оскільки наш код складається з 71 біта, то в разі генерації однієї помилки буде згенеровано 71 помилковий код, а в випадку генерації двох помилок 1+2+3+ ... +69+70=70*71/2=2485. Згенерувавши помилковий код програма намагається виявити та виправити в ньому помилку. При цьому можливі три випадки:

- помилку виявлено та виправлено;

- помилку виявлено;

- помилку не виявлено.

перші два випадки є допустимими, а третій ні, бо він означає, що код було зчитано неправильно, але ЕОМ про це непідозрює. Така помилка не можлива при наявності одного помилкового біту в коді. Як буде видно з результатів програм Oldkoran допускає всі три випадки, в той час як Koran при двох помилках в коді третьго випадку не допускає. Глянувши на матрицю кодових відстаней бачимо, що й при генерації трьох помилок в коді така ситуація неможлива.