Data matrix - can refer to: Matrix (mathematics) A rectangular array of elements Data matrix (computer) An encoded barcode. Data set A collection of data in tabular form. Data matrix (multivariate statistics) A mathematical matrix of data whose rows represent… … Wikipedia

Data Matrix - An example of a Data Matrix code, encoding the text: Wikipedia, the free encyclopedia Reading Data … Wikipedia

Data Matrix

Data Matrix - 3.8 Data Matrix: Двумерная матричная символика с коррекцией ошибок, кодирующая различные наборы знаков, включая набор цифровых и алфавитно цифровых знаков данных, все знаки по ИСО/МЭК 646 (ASCII)1), а также специальные наборы знаков. 1) Ссылка… … Словарь-справочник терминов нормативно-технической документации

data matrix - /deɪtə ˈmeɪtrɪks/ (say daytuh maytriks) noun (plural data matrixes or data matrices /deɪtə ˈmeɪtrəsiz/ (say daytuh maytruhseez)) a rectangular array of data, whether numbers, images, etc., to be used in computation … Australian English dictionary

- … Википедия

Data matrix (computer) - A Data Matrix code is a two dimensional matrix barcode consisting of black and white square modules arranged in either a square or rectangular pattern. The information to be encoded can be text or raw data. Usual data size is from a few bytes up… … Wikipedia

Data Matrix Code - DataMatrix Code als Teil von Stampit Mit dem zweidimensionalen Data Matrix Code (2D Code) kann im Vergleich zu eindimensionalen Barcodes (1D Code) die Informationsdichte pro Fläche deutlich erhöht werden. Entwickelt wurde der Data Matrix Code in… … Deutsch Wikipedia

Data matrix (multivariate statistics) - In multivariate statistics, a data matrix is a mathematical matrix of data whose rows represent different repetition of an experiment, and whose columns represent different types of datum (say, the results from a particular probe). For example,… … Wikipedia

Matrix code - The Matrix code can refer to: A two dimensional barcode (as opposed to linear and stacked symbologies), such as e.g. Data Matrix. The logo of The Matrix franchise. See Matrix digital rain. This disambiguation page lists articles associated with… … Wikipedia

Книги

• Matrix Algebra Useful for Statistics , Andre Khuri I. , A thoroughly updated guide to matrix algebra and it uses in statistical analysis and features SAS®, MATLAB®, and R throughout This Second Edition addresses matrix algebra that is useful in… Категория: Математика Издатель: John Wiley & Sons Limited , электронная книга
• Statistical Data Analytics. Foundations for Data Mining, Informatics, and Knowledge Discovery , Walter Piegorsch W. , A comprehensive introduction to statistical methods for data mining and knowledge discovery. Applications of data mining and ‘big data’ increasingly take center stage in our modern,… Категория: Математика Издатель: John Wiley & Sons Limited , электронная книга (fb2, fb3, epub, mobi, pdf, html, pdb, lit, doc, rtf, txt)

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, который заполняется так:

Если или , то следует обратить внимание на левый нижний и правый верхний угол, особенно на нумерацию битов.

Во всём мире уже довольно давно используются так называемые Bar-коды, да-да это такие картинки с полосочками разной длины и толщины, которые приклеены к товарам в ближайшем супермаркете ^_^ Вообще, Bar-коды бывают разные, для нас же наиболее интересным будет так называемый QR-код (от Quick Response - Быстрый Отклик), наиболее широко распространившийся в интернете. Это двухмерный код, в отличии от полосочек на товарах, отсюда его очень важное свойство: информационная ёмкость. В общем, не буду цитировать википедию, кому интересно, сами прочитают. Существует достаточно большое число способов представления QR-кодов в Web, самые распространённые основаны на генерации картинок на стороне сервера. Однако, мои читатели знают, как мне не нравятся такие решения.

Кратко о Bar-кодахQR-код

Существует 4 основных класса представления информации посредством QR-кода , отличающиеся видом хранимых данных и максимальным объёмом:

• Только цифровая информация - до 7089 цифр
• Алфавитно-цифровая информация - до 4296 символов
• Двоичные данные (8-битные байты) - до 2953 байт
• Кандзи/Кана - до 1817 иероглифов

QR-код имеет следующие уровни корекции ошибок, характеризующиеся объёмом информации для восстановления (от большего к меньшему):

• H(igh) - 30%
• Q(uality) - 25%
• M(edium) - 15%
• L(low) - 7%

Алгоритм коррекции ошибок основан на коде Рида-Соломона .

Кроме того, существует несколько версий представления данных (1-40), которые отличает максимальный объём хранимой информации и, соответственно, размер матрицы.

DataMatrix код

Это другой тип двумерного кода, менее распространённый в интернет, но более компактный. Код также предусматривает хранение информации для восстановления до 30%. В отличии от QR область нанесения не обязательно должна быть квадратной.

Итак, приступим

Мне конечно же не хотелось писать реализацию алгоритма генерации кодов, поэтому погуглив, нашел вполне подходящую реализацию кодирования на JavaScript от Kazuhiko Arase http://www.d-project.com/qrcode/index.html . Здесь реализован только один тип кодирования: 8-битными байтами, то есть любые данные разбираются как есть на байты, в этом же виде они считываются сканнерами. Такми образом мы можем кодировать любую строку в юникоде и любой вменяемый сканнер должен правильно её декодировать. Кроме того в данной реализации поддержка стандарта осуществлена до версии 10 включительно.

Немного погодя мне попался jQuery плагин , основаный на этой разработке доблестного японца https://github.com/jeromeetienne/jquery-qrcode . Но представление в нём было реализовано исключительно посредством Canvas , а суровые разработчики обязаны писать кросс-браузерно там, где это только возможно.

С DataMatrix кодами всё остояло сложнее, пока мне не попался jQuery плагин BarCode http://barcode-coder.com/en/barcode-jquery-plugin-201.html , который как раз таки содержал кодировщик DataMatrix от HOUREZ Jonathan . Однако сам по себе плагин показался мне слишком монструозным и труднорасширяемым, для того, чтобы как-то использовать его.

Реализация

Итак было решено реализовать различные движки рендеринга Bar-кодов в зависимости от поддержки на стороне клиента тех или иных возможностей, также поддержку различных типов кодировщиков:

;(function($){ var $$ = $.barcode = { defs: { // Опции по умолчанию type:false // Тип кода }, clas: "bar-code", // CSS класс conv: function(s){ // Функция преобразования строк return unescape(encodeURIComponent(s)); }, type: {}, // Типы кодов engine: {} // Рендереры }, T = function(t){ // Валидатор типа кода if(!$$.type[t]){ for(var i in $$.type){ t = i; break; } } return t; }, R = Math.floor; // Функция округления $.fn.bar_code = function(opts){ // Реализация плагина return this.each(function(){ var self = $(this); if(!self.hasClass($$.clas)){ self.addClass($$.clas); // Установка класса } var opt = $.extend(true, { // Инициализация опций width: self.innerWidth(), height: self.innerHeight(), text: self.text() }, $$.defs, opts), gene, inst, val = $$.conv(opt.text); // Преобразование данных opt.type = T(opt.type); // Init type self.empty(); if(!(gene = $$.type)){ // Нахождение кодера return; } if(!(inst = gene.init(opt, val))){ // Инициализация экземпляра кодера return; } var cnt = gene.read.call(inst), // Размеры матрицы est = [ // Размеры элемента матрицы R(opt.width/cnt), R(opt.height/cnt) ], p = { // Корректировка отступов w:opt.width-est*cnt, h:opt.height-est*cnt }; if(p.w > 0.01 || p.h > 0.01){ var cst = { // Отступы контейнера width:opt.width-p.w, height:opt.height-p.h, paddingLeft:R(0.5*p.w), paddingTop:R(0.5*p.h) }; cst.paddingRight=p.w-cst.paddingLeft; cst.paddingBottom=p.h-cst.paddingTop; self.css(cst); } for(var n in $$.engine){ // Поиск подходящего рендерера if($$.engine[n].check()){ $$.engine[n].render.call(self, function(col, row){ // Эта лямбда по сути запрашивает состояние элемента матрицы return gene.read.call(inst, col, row); }, cnt, est); break; } } }); }; /* Рендереры */ /* Типы кодов */ });

Как оказалось, во многих кривых браузерах, типа всем ненавистного Internet Exploder-а и Opera не целые пикселы работают совсем уж странно, поэтому для совместимости размеры каждого элементика матрицы пришлось округлять до меньшего целого, во избежание выхода матрицы за пределы области. По этой причине матрицу пришлось отделить отступами от контейнера.

Рендеринг

Теперь реализуем движки-рендереры. Поскольку более приоритетным для нас будет использование Canvas, начнём с него:

$$.engine.canvas = { check: function(){ // Проверка доступности try{ return !!window.CanvasRenderingContext2D && !!document.createElement("canvas"); }catch(e){ return false; } }, render: function(chk, cnt, est){ // Рендеринг // Для начала нам нужно получить цвета, чтобы картинка выглядела в соответствии с CSS var st = this.append("").find("span"), c = st.eq(0).css("backgroundColor"), d = st.eq(1).css("backgroundColor"), w = est.width, h = est.height; this.empty(); // А теперь инициализируем Canvas var can = this.append("").find("canvas").get(0), ctx = can.getContext("2d"); can.width = cnt*est; can.height = cnt*est; // И раскрашиваем матрицу for(var y = 0; y < cnt; y++){ for(var x = 0; x < cnt; x++){ ctx.fillStyle = chk(x, y) ? d: c; ctx.fillRect(x*est, y*est, est, est); } } } };

Если Canvas не доступен, будем тупо генерировать матрицу HTML элементами, это медленней, но работает:

$$.engine.html = { check: function(){ return true; }, render: function(chk, cnt, est){ var tab = ""; for(var y = 0; y < cnt; y++){ for(var x = 0; x < cnt; x++){ tab += ""; } } this.append(tab).find("span").css({ width:est, height:est }); } };

После тестирования в IE как обычно оказалось, что это там работает вовсе не так, как задумывалось, поэтому за неимением желания разбираться напишем табличный движок:

$$.engine.table = { check: function(){ return true; //$.browser.msie; }, render: function(chk, cnt, est){ var tab = ""; for(var y = 0; y < cnt; y++){ tab += ""; for(var x = 0; x < cnt; x++){ tab += ""; } tab += ""; } this.append("

"+tab+"").find("table").css({ width:est*cnt, height:est*cnt }).find("td").css({ width:est, height:est }); } };

Как видите, всё получилось достаточно тривиально. Только и осталось написать таблицу стилей:

Bar-code{ /* Контейнер */ overflow: hidden; margin: 10px; padding: 0; width: 100px; height: 100px; background: #fff; /* Фоновый цвет. Если у вас сплошная заливка, можно это свойство не задавать */ } .bar-code *{ /* Все элементы по-умолчанию */ display: inline-block; float: left; border: 0; padding: 0; margin: 0; border-collapse: collapse; } .bar-code .dark{ /* Затемнённые элементы */ background: #000; /* Можно задать любой цвет, главное чтобы он хорошо отличался от фонового, экспериментируйте */ }

Тут я сбрасываю некоторые свойства на всякий случай, вы можете этого не делать, если итак всё отлично выглядит.

Кодеры

Как уже было сказано выше, мы реализуем генерацию QR-кодов , испрользуя кодировщик от Kazuhiko Arase , также до кучи и ради примера добавим генератор DataMatrix кодов, это альтернатива QR-кодам, однако менее распространённая на просторах интернета и поддерживаемая меньшим числом сканнеров. В скрипте мы будем проверять, доступен ли кодировщик и только тогда инициализировать движок.

Кодировщик от Казухико требует обязательного указания типа кода, то есть числа от 0 до 10, которое в совокупности с уровнем коррекции ошибок составляет версию кода, однако разные типы кода способны хранить разные объёмы информации, поэтому я решил реализовать автоматический подбор типа, соответствующего данным, если тип не указан. Итак, QR-кодер будет выглядеть следующим образом:

If(window.QRCode){ $$.defs.QR = { // Значения опций по умолчанию level: "H", // Уровень по умолчанию type: 0 // Тип по умолчанию // 1..10 // моё расширение: 0 or null - автовыбор }; var QRAutoType = function(val, errorCorrectLevel){ // Автоматический выбор подходящего типа for(var typeNumber = 1; typeNumber