Як створюється Data Matrix?

Data Matrix є двовимірним матричним штрих кодом, що складається з світлих і темних ділянок. З допомогою такого штрих-коду можна закодувати досить великий обсяг інформації (2-3Кб). Часто Data Matrix застосовується при маркуванні невеликих предметів, наприклад мікросхем, а також у харчовій, оборонної промисловості, рекламі та інших сферах.

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

При створенні Data Matrix нам знадобиться звернутися до арифметики полів Галуа та кодів Ріда-Соломона. Розглянемо цей процес на простому прикладі.

Насамперед, подивимося на структуру матриці:



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

Візьмемо якесь коротке слово, наприклад, «Habr» (без лапок) і створимо для нього Data Matrix. Процес складається з двох етапів: на етапі високорівневого кодування потрібно отримати послідовність кодів даних і кодів корекції помилок, а на етапі низькорівневого кодування — зобразити у матриці двійкове подання цих кодів.

Високорівневе кодування
В Data Matrix, як і в QR-коді, використовуються коди Ріда-Соломона над полем Галуа (число 8 обрано, оскільки кожне кодове слово займає в матриці 8 біт). Існує кілька незвідних многочленів, що дозволяють створити таке поле. Серед них у десятковому поданні 285, використовується для QR-кодів) і (301, використовується в Data Matrix).

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

Необхідно отримати кодове слово

,

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

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

З таблиці видно, що для кодування рядка з 4х елементів потрібно взяти матрицю розміром 12x12 («корисна» область — 10x10), в яку поміщаються 5 кодів даних і 7 кодів корекції.

Для символів таблиці ASCII код виходить наступним чином: C=ASCII value+1. Наприклад, для символу 'H' C=72+1=73.

Йдуть підряд цифри об'єднуються в пари, і для них C=N+130, де N — число, отримане в результаті угруповання. Наприклад, якщо поряд стоять цифри 2 і 5, то C=25+130=155.

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

, де
— псевдовипадкове число, — номер елемента.

Для слова «Habr» отримуємо наступну послідовність кодів: 73, 98, 99, 115, 129.

Тепер ми можемо записати інформаційний многочлен:



і домножить його на ( — число кодів корекції):



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



Починаємо перемножувати дужки:





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

Після перемноження всіх дужок і зведення в ступінь отримаємо:



Остання операція, завершальна високорівневе кодування, і, мабуть, найскладніша — знаходження залишку від ділення :



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

Тепер ми можемо записати кодове слово :



Низькорівневе кодування
Кожен з отриманих вище кодів представляється в Data Matrix у вигляді квадрата розміром 3х3 осередки без правого верхнього кутка. 1 тут відповідає старшого біту, 8 — молодшому. Потрібно заповнити такими елементами всю матрицю.

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

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

Якщо , де a — сторона квадрата, то перед нами самий простий випадок, коли після розміщення всіх елементів непоместившиеся ділянки просто переносяться на протилежну сторону.

Якщо , то в правому нижньому куті залишається «зайвий» квадрат розміром 2х2, який заповнюється так:


Якщо або , то слід звернути увагу на лівий нижній і правий верхній кут, особливо на нумерацію бітів:


Є ще два випадки, які виникають тільки при побудові прямокутних матриць, тому ми їх опустимо.

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



Після перенесення які не помістилися елементів отримуємо:



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


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












Отже, наш код Data Matrix готовий:


Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.