How is Data Matrix created?

Data Matrix is a two-dimensional matrix barcode consisting of light and dark areas. With this barcode, you can encode a sufficiently large amount of information (2-3Kb). Often, Data Matrix is used for labeling small items, such as microchips, as well as in the food, defense, advertising and other areas.

There are many sites for creating such codes, but I was always wondering how the text turns into a set of black and white squares? Should there be some kind of algorithm?

When creating the Data Matrix, we will need to turn to Galois field arithmetic and Reed-Solomon codes. Consider this process with a simple example.

First of all, let's look at the structure of the matrix:
')

Our matrix consists of two parts: a search pattern and coded data. Of course, the size of the matrix is directly proportional to the size of the input data. Around our code there must be a free zone separating the code from the rest of the image.

Take some short word, for example, “Habr” (without quotes) and create a Data Matrix for it. The process consists of two stages: at the stage of high-level coding, it is necessary to obtain a sequence of data codes and error correction codes, and at the stage of low-level coding, to represent the binary representation of these codes in a matrix.

High level coding

In Data Matrix, as in the QR code, Reed-Solomon codes are used over the Galois field.

(the number 8 is chosen because each codeword occupies 8 bits in the matrix). There are several irreducible polynomials that allow one to generate such a field. Among them

(in decimal notation 285, used for QR codes) and

(301, used in Data Matrix).

For calculations, we need a table of powers of two for each field element. Creating this table is quite simple: if the exponent is

, then exponentiation is performed as usual. Otherwise

then a bitwise addition modulo 2 is made with a decimal representation of the irreducible polynomial taken, if

. For example,

etc.

You must get a code word

,

Where

- information polynomial,

- generating polynomial,

- the total length of the code together with the correction,

- the number of information codes (together with codes of indentation, about them - below),

- the operation of taking the remainder of the division.

Let's create an information polynomial for the beginning. To do this, we need to know what size the matrix should be in order to be able to place all information codes:

The table shows that to encode a row of 4 elements, you need to take a 12x12 matrix (the “useful” area is 10x10), into which 5 data codes and 7 correction codes are placed.

For characters in the ASCII table, the code is obtained as follows: C = ASCII value + 1. For example, for the character 'H' C = 72 + 1 = 73.

The consecutive digits are combined in pairs, and for them C = N + 130, where N is the number obtained as a result of grouping. For example, if the numbers are 2 and 5, then C = 25 + 130 = 155.

Since we have fewer elements than we should have (instead of five, only four), we need to add special indentation codes. The first such code is always 129. Subsequent indentation codes, before the first error correction code, are calculated as follows:

where

- pseudo-random number,

- item number.

For the word “Habr” we get the following sequence of codes: 73, 98, 99, 115, 129.

Now we can write the information polynomial:

and multiply it by

(

- number of correction codes):

Let us turn to the creation of a generating polynomial. It is calculated by the following formula:

Start multiplying the parentheses:

Addition in our field is defined as bitwise addition modulo 2. First, exponentiation is performed using the table, then they are added and the “logarithm” of the resulting number is found to return to powers of two. If, after the addition of powers, a number greater than 254 is obtained, we take its remainder from division by

.

After multiplying all the brackets and exponentiation, we obtain:

The last operation, the final high-level coding, and perhaps the most difficult - finding the remainder of the division

Polynomials are divided into columns, but taking into account the fact that subtraction, defined exactly the same as addition, and multiplication, are performed in the Galois field.

Now we can write the code word

in full:

Low level coding

Each of the codes obtained above is represented in Data Matrix in the form of a square with the size of 3x3 cells without an upper right corner. 1 here corresponds to the highest bit, 8 - the younger. It is necessary to fill the entire matrix with such elements.

Prepare a 10x10 grid (just this size should be the matrix in this case), on which we draw the contours of the first five elements, as in the figure to the right. Regardless of the size of the matrix, these elements are always arranged exactly this way and in no other way.

The remaining elements are placed in a similar way, but before drawing them, it is necessary to note a few special cases related to the corners of the matrix.

If a

where a is the side of the square, then we face the simplest case when, after placing all the elements, the non-plots are simply transferred to the opposite side.

If a

then in the lower right corner there remains an “extra” small square of 2x2, which is filled with:

If a

, you should pay attention to the lower left and upper right corner, especially the numbering of bits:

There are two more cases that arise only when constructing rectangular matrices, so we omit them.

Let us return to our matrix and add all the other elements, and also indicate what code word each element corresponds to. The arrows show how the numbering is performed: