Код з перевіркою за модулем q

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

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

Такий код має незначну надмірність R = 1 / ( k + 1) і дозволяє виявити наявність помилок у кодовій комбінації, якщо сума усіх елементів ( інформаційних та перевірочного ) за mod q відрізняється від нуля.

2. Код із повторенням

Код з простим повторенням є аналогом двійкового коду з простим повторенням ( див. розділ 7 ), в основу якого покладено просте повторення первинної кодової комбінації. Алгоритм побудови коду має вигляд:

b_i = a_i, i [ 1, k ] ,

де a_i – інформаційний елемент, що знаходиться на i-ій позиції інфор-маційної частини кодової комбінації; b_i – перевірочний елемент, що знаходиться на i-ій позиції перевірочної частини кодової комбінації; k – кількість інформаційних елементів.

Надмірність коду R = 0,5. Код дозволяє виявити всі помилки, за винятком деяких помилок на однакових позиціях в інформаційній та перевірочній частинах коду.

3. Незвідні змінно-позиційні коди

Незвідний змінно-позиційний код НЗЗПК задовольняє таким умовам:

- кожна кодова комбінація містить однакову кількість елементів, які передаються послідовно;

- кожний елемент кодової комбінації містить m позицій алфавіту потужністю q ;

- сусідні елементи кодової комбінації повинні відрізнятися хоча б однією позицією;

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

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

Послідовність побудови НЗЗПК:

- береться m символів з q позицій алфавіту;

- визначається кількість сполучень позицій за заданим числом позицій у кожному сполученні;

- вся кількість сполучень позицій розбивається на n груп, де n – кількість елементів кодової комбінації ( довжина коду ), і кожна група взаємно однозначно закріплюється за елементом кодової комбінації;

- утворюються кодові комбінації з n елементами за правилом: для кожного елемента беруться сполучення позицій із закріпленої за даним елементом групи сполучень позицій.

За методом побудови кодових комбінацій багатопозиційні НЗЗПК поділяють на такі класи:

- без розділення алфавіту коду на групи;

- з розділенням алфавіту коду на v груп, кожна з котрих має q_i символів.

Останній клас, у свою чергу, поділяють на НЗЗПК, кожний елемент якого містить m позицій, які беруться з різних груп сполучень, і НЗЗПК, кожний елемент якого містить m позицій, які беруться з однієї групи сполучень.

Кількість N ₀ кодових комбінацій для НЗЗПК без розділення алфавіту коду на групи

– у разі, коли всі сполучення позицій розподілені між n групами сполучень порівну

N₀ = ( / n ) ⁿ;

– у разі, коли вся кількість сполучень розподіляється між групами сполучень не нарівно через остачу деякої кількості сполучень

N₀= ( – Q ) ^{n – Q} ´ ( – Q + n ) ^Q / n ⁿ ,

де Q – остача від ділення /n, що є цілим додатним числом.

Для НЗЗПК з розділенням алфавіту коду на v груп з однако-вою кількістю l = q / v позицій у кожній групі та за умов, що кожний кодовий елемент містить m позицій, які вибираються з різних груп ( v ³ m ) кількість кодових комбінацій

N₀ = ( l ^m / n ) ⁿ;

якщо ж для кожного кодового елемента m різних позицій вибираються із однієї групи ( l ³ m, v = n ), то

N₀ = ( ) ⁿ.

Штрихові коди

Штрихові коди ( ШК ) широко використовуються в медицині, торгівлі, промисловості тощо. ШК – це послідовність штрихів і пробілів, що розташовані у напрямку уявленої прямої. Інформацію у ШК можуть нести як штрихи і пробіли різної ширини, так і штрихи різної висоти.

Існує багато ШК які в основному мають вузькоспеціальне призначення. Найбільш поширеними ШК є коди, що рекомендовані Міжнародною асоціацією EAN. Це коди EAN ( European Article Numbering ) та UPC ( Uniform Product Code ) .

Штрихові коди EAN призначені для кодування 10 цифр ( 0. . .9 ) і додаткових символів ( СТАРТ, СТОП та розділові знаки ). Код може мати довжину кодового слова 4, 5, 6, 7, 8, 10, 12, 13 і 14 знаків. Але існує два основні різновиди коду EAN: EAN-13 і EAN-8, де цифрою позначена довжина коду ( кількість знаків у кодовому слові ).

Код країни може мати не два, а три знаки. У цьому разі код товаровиробника має не 5, а 4 знаки.

Контрольний символ визначається за таким алгоритмом:

1- ий крок: знаходять суму цифр, розташованих на непарних позиціях кодового слова ( перегляд виконується справа наліво ), і помножують одержаний результат на 3;

2 - ий крок: знаходять суму цифр, розташованих на парних позиціях кодового слова;

3 - ій крок: визначають добуток сум, знайдених при 1-му та 2-му кроках;

4 - ий крок: обчислюють контрольну цифру, яка дорівнює найменшому числу, що не перевищує 9, яке, якщо його додати до результату, одержаному на 3-му кроці, дає кратне 10 число.

Для кодування інформації у ШК EAN використовуються чотири набори знаків: A, B, C та D (табл. 1) для кодування десяткових цифр, а також знаків СТАРТ, СТОП ( Н1, Н2, Н3 ), та розділових зна-ків ( Н4 та Н5 ). Кожний знак містить у собі два штрихи і два пробіли. Довжина кожного знака для кодування цифр дорівнює 7 модулям ( 7-ми елементам зображення ), а допоміжні знаки мають довжину 3, 5 і 6 модулів. Як знак СТАРТ використовуються набори Н1 та Н3, а знак СТОП – Н1 та Н2 у залежності від символів початку і кінця кодового слова ( табл. 2, де 0 – пробіл, 1 – штрих ).

Таблиця 1

Сим- воли	Набір А	Набір В	Набір С	Набір D
Двійковий еквівалент	Двійковий еквівалент	Двійковий еквівалент	Двійковий еквівалент
Н1		Обмежувальні знаки СТАРТ і СТОП
Н2
Н3
Н4		Розділові знаки
Н5

Примітка: При зображенні кодового слова у штриховому коді , згідно табл. 1, подають: 0 – одним, 00 – двома, 000 – трьома і 0000 – чотирма інтервалами, а 1 – тонким штрихом ( ),11 – штрихом ( ), 111 – штрихом ( ) і 1111 – штрихом ( ).

Таблиця 2

Знак СТАРТ	Кодове слово	Знак СТОП
Н1	0 . . . . . . . . . . 0	Н1
Н3	1 . . . . . . . . . . .1	Н2
Н1	0 . . . . . . . . . . .1	Н2
Н3	1 . . . . . . . . . . .0	Н1

У штрихових кодах EAN довжиною 4, 5, 6, 7 знаків для кодування цифр використовується набір А (табл. 1), а обмежувальних знаків – Н1 ( СТАРТ ) та Н2 ( СТОП ). У ШК довжиною 8, 10, 12 і 14 зна-ків кодові слова діляться на дві частини з однаковим числом знаків у кожній, які розділяються розділовим знаком Н4. Для зображення знаків лівої частини кодового слова використовуються набори А і В, а правої – С і D ( див. табл. 1 ). Такі кодові слова мають обмежу-вальні знаки СТАРТ і СТОП типу Н1.

У коді EAN-13 штрихове зображення складається з двох частин по шість знаків у кожній, які розділені знаком Н4, і має зліва та справа обмежувальні знаки Н1 ( СТАРТ і СТОП ). Першу зліва цифру ( 12-а цифра ) товарного номера не кодують у вигляді штрихів і пробілів, а тільки пишуть зліва внизу. Ця цифра визначає спосіб кодування цифр, які розташовані у лівій частині кодового слова між знаками Н1 та Н4 (табл. 3). Літерами А і В у табл. 3 позначені набори з табл. 1, якими кодують відповідні знаки лівої частини кодового слова. Цифри, які розташовані у правій частині кодового слова між знаками Н4 і Н1, кодують набором С (див. табл. 1). Обмежувальні і розділовий знаки зображають більш довшими по висоті штрихами.

Деякі товари можуть мати короткий номер, що має 7 цифр. Після доповнення його контрольною цифрою, що виконується за наведеним вище алгоритмом для коду EAN-13, одержують 8 цифр, які кодують кодом EAN-8. Кодове слово EAN-8 складається зі знака СТАРТ – Н1, чотирьох знаків набору А, розділового знака Н4, трьох знаків набору С, знака контрольної цифри у наборі С, а також знака СТОП – Н1. У коді EAN-8 перша цифра u₇ не визначає неявне кодування, а кодується як і наступні цифри u₆, u₅, u₄ набором А ( див. табл.1 ).

Таблиця 3

u12	u11 u10 u9 u8 u7 u6
	А А А А А А
	А А В А В В
	А А В В А В
	А А В В В А
	А В А А В В
	А В В А А В
	А В В В А А
	А В А В А А
	А В А В В А
	А В В А В А

Штрихові коди UPC використовуються у США та Канаді для ідентифікації товарів і також призначені для кодування 10 цифр та п’яти додаткових знаків. Коди UPC сумісні з кодами EAN з огляду на те, що використовують одну і ту ж таблицю наборів знаків (табл. 1).

Існує декілька різновидів ШК UPC, з яких найбільше поширення набули коди UPC-А і UPC-Е. Кодове слово ШК UPC-А має 12 цифр ( 12-а – контрольна ), тобто на одну цифру менше ніж у EAN-13. Це викликано тим, що код країни ( США і Канада ) має тільки дві цифри. Відмінними ознаками коду UPC-А від коду EAN-13 є:

– старша цифра ( u₁₁ ) товарного номера у штриховому зображенні кодується явно;

– штрихове зображення кодового слова у коді UPC-А містить знак СТАРТ ( Н1 ), 6 знаків набору А, розділовий знак ( Н4 ), 5 знаків набору С, знак контрольної суми набору С і знак СТОП ( Н1 ) (див. табл. 1);

– у штриховому зображенні знаки цифр u₁₁ і u_К виконуються висотою, однаковою з висотою зображення знаків Н1 і Н4, причому значення цифр під цими знаками не позначають;

– зліва від штрихового зображення друкують цифру 0, що іденти-фікує код UPC-А.

Контрольна цифра визначається за тим же алгоритмом, що використовується і у коді EAN-13.

Товарний номер у коді UPC-Е містить 6 цифр і також поділяється на дві частини по 3 цифри у кожній. Перша частина ( ліва ) кодується набором А, а друга ( права ) – набором С ( у тому числі і контрольний знак ) (див. табл. 1).

При декодуванні ШК EAN та UPC перш за все визначається контрольний знак, який повинен співпадати з переданим. Крім того, сума всіх цифр кодового слова, що подається на приймальний пристрій, повинна бути кратною 10. У цьому разі помилки нема. Якщо ж сума буде не кратною 10, це вказує на наявність помилки. Помилка виявля-ється і при неправильному прийомі знаків, що не відповідають наборам, встановленим неявним кодуванням по старшому знаку в ШК EAN-13 цифр лівої половини кодового слова, тому що набори А і В (див. табл. 1) не збігаються.

Тема 16. Кодування в системі залишкових класів.

План

1. Побудова кодів у системі залишкових класів, породжених базисом Крестенсона.

2. Переваги та недоліки кодування у системі залишкових класів.

3. Ефективність математичних операцій у системі залишкових класів.

4. Надлишковість та здатність виявляти та виправляти помилки