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

Найб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·2³ + 1·2² + 1·2¹ + 0·2⁰ або 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й коду N_k було бiльше або рiвне числу рiзноманiтних  повiдомлень N_c, тобто

N_k ³ N_c.      (1.87)

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

N_k = Lⁿ.      (1.88)

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

Lⁿ ³ N_c

або

nlogL ³ logN_c     (1.89)

звiдки 

n ³ log N_c/log L    (1.90)

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

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

H_k = logN_k = n logL.    (1.91)

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

H_c= logN_c.    (1.92)

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

H_k ³ 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_с>H_c), тобто в цих випадках код пост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в  можна скласти 2^k рiзноманiтних комбiнацiй (рiзноманiтних двiйкових чисел), кожна з котрих повинна вказувати на один з наступних фактiв:

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

2^k³n+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 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рочний символ c_i, i кожний даний провiрочний символ зустрiчається в усiх сумах тiльки один раз. Перший символ y₁ (з 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