Le QR code

The general structure.

The symbol is a square array consisting of rows and columns (Numbered from 0). Each cell is a small black or white square called module. The symbol has 3 finder patterns at the top and bottom left corners making it well recognizable. The dimension of the symbol is called the version, there are 40 with 21 to 177 modules (In steps of 4 modules). The correction level (Among 4) is denoted L, M, Q or H
Colors can be switched : white on black ; the symbol can also be mirrored.
Extended Channel Interpretation (ECI) provides a mode for specifying a particular interpretation of byte values or for identifying a particular code page.
By default the ECI code is 000003 which designates the Latin alphabet ISO 8859-1.
If necessary, a mechanism allows more data to be spread over several symbols. (Up to 16)
The error correction mechanism is based on Reed-Solomon codes.
The symbol has a number of function modules :
- The 3 finder patterns of 8 x 8 modules
- Alignment patterns of 5 x 5 modules (Position : see table)
- 2 timing patterns : band alternating white and black module, in horizontal line 6 and in vertical column 6
- Format and version information zones contiguous to the finder patterns
The function modules (patterns, synchro, info, ...) being placed, the data are placed starting from the bottom right corner going from right to left, first by going up and down and bypassing all the modules of function.
A white margin of 4 modules must frame the code.

Low level encoding.

There are 40 versions (Sizes) of symbol. A set of parameters is attached to each version :

The version number.
The first spacing of the alignment patterns
The second spacing of alignment patterns
The number of bits for the 4 size indicators in numeric, alphanumeric, byte, and Kanji mode (See High Level Encoding)
For each of the 4 levels of error correction (See High Level Encoding) :
- The number of blocks in which to distribute the data.
- The number of RS per block .

From these parameters we can calculate other values, this is done using a spreadsheet :

We will find the calculation of the size of the symbol, the number and location of alignment patterns, the areas occupied by the various elements, etc ...

To build a QRcode you need :

Place the 3 finder patterns at the top and bottom left corners.
The markers have a size of 8 x 8, counting a margin of 1 module on the 2 internal sides ; see below the upper left corner :
Draw timing lines on line and column 6
Place the alignment patterns. These have a size of 5 X 5.
Their center is placed at the intersection of a grid whose line numbers are identical to the column numbers, we will call these numbers L / C thereafter.
The first L / C is always 6. The 3 marks that collide with the corner marks are removed..
For example in the drawing below we have 3 L / C, the number of patterns is (3 x 3) -3 = 6. With 4 L / C we would have (4 x 4) - 3 = 13 marks.
There are 2 spacing columns in the spreadsheet to use as follows :
- 2nd L / C = 6 (which is the 1st L / C) + spacing 1
- 3rd L / C (and following) = L / C previous + spacing 2
Reserve locations for format information.
The format information is a sequence of 15 bits: 5 data and 10 BCH type error correction codes.
The 5 data bits are :
- 2 bits indicating the correction level of the code : L (01), M (00), Q (11) or H (10)
- 3 bits indicating the mask pattern used (see below for masking)
The 10 correction bits are calculated as follows :
- The 5 data bits are the coefficients of a polynomial of order 14; example 01001 gives X¹³ + X¹⁰
- We divide this polynomial by X¹⁰ + X⁸ + X⁵ + X⁴ + X² + X + 1 (The coefficients of this polynomial are : 10100110111)
- The coefficients of the remainder of the division are the 10 correction bits to be added to the 5 data bits.
Finally we apply the mask 101010000010010 by doing a XOR with the 15 bits obtained previously.

Format information is placed in 2 places with a total of 31 modules (1 of which is always black)

The algorithm for creating the format string in Basic :
For version 7 and above, you must add version information.
The version information is a 18-bit sequence : 6 data bits and 12 Golay error correction codes.
The 6 data bits represent the version number.
The 12 correction bits are calculated as follows :
- The 6 data bits are the coefficients of a polynomial of order 17 ; example for version 9 : 001001 gives X¹⁵ + X¹²
- We divide this polynomial by X¹² + X¹¹ + X¹⁰ + X⁹ + X⁸ + X⁵ + X² + 1
- The coefficients of the remainder of the division are the 12 correction bits to be added to the 6 data bits.
The version information is placed in 2 places occupying a total of 36 modules

The algorithm for creating the version string in Basic :
Now let's go to the placement of the data and correction modules, we start in the lower right corner and up on 2 columns of modules. The bits of each CW are placed starting from the last one. The bits are placed first in the right column and then in the left column and the function modules are bypassed. Arrived at the top we go down on the 2 adjacent columns on the left always in right-left order.
In order to obtain a bar code as balanced as possible it is now necessary to apply a mask to the area of the data. Masking consists of applying a XOR operation between the data of each module and the corresponding module of the mask.
There are 8 different masks and we will have to find the one that gives the most balanced result :
- White ratio on black close to 1
- If possible, no further 1011101 1011101
- As few "big" blocks as possible.
The number of the selected mask will be indicated in the format information. In the following table are the 8 types of mask with the function to define the pattern of the mask. Any module for which the condition is true will be black. In the condition formula i and j are respectively the line and column number of the module. i = j = 0 corresponds to the upper left corner.
Mask number Condition 000 (i + j) MOD 2 = 0 001 i MOD 2 = 0 010 j MOD 3 = 0 011 (i + j) MOD 3 = 0 100 ((i DIV 2) + (j DIV 3)) MOD 2 = 0 101 (i j) MOD 2 + (i j) MOD 3 = 0 110 ((i j) MOD 2 + (i j) MOD 3) MOD 2 = 0 111 ((i + j) MOD 2 + (i j) MOD 3) MOD 2 = 0

High level encoding.

We will use the following operators : + -> addition, x -> multiplication, \ -> integer division, MOD -> rest of the whole division
There are 4 encoding modes (Compression) that can be mixed :

Compression mode Data to be encoded Compression rate Mode indicator Numeric ASCII digits 3 digits in 10 bits 0001 Alphanumeric Digits + capital letters + 9 symbols 2 characters in 11 bits 0010 Byte Byte 1 byte in 8 bits 0100 Kanji Asian characters / 1000

There are other indicators not studied here: 0111 = ECI, 0011 = Multi codes, 0101 et 1001 = FNC1
0000 indicate the end of datas.
Each segment begins with a 4-bit mode indicator followed by the number of characters encoded on a variable bit number (see table), followed by the datas.

The segments of each mode are then concatenated followed by a terminator composed of 4 zeros which is the end of data indicator.
The terminator can be abbreviated if it allows the complete filling of the data area of the symbol.
This stream is then cut into 8-bit CW. If necessary, the last CW is adjusted to 8 bits by adding bits 0. If the number of CWs does not completely fill the symbol add 11101100 then 00010001 and start again (236 and 17 in decimal)
The CWs are then divided into a number of blocks (see table) The size of the blocks can vary by one unit; for example 46 CWs divided into 4 blocks will give 2 blocks of 11 and 2 blocks of 12. In this case, we will place the smaller blocks first.
For each block the Reed Solomon codes are calculated.
Finally we will interleave the data then the RS codes as follows :
n is the number of blocks, m the number of CWs in each block and z the number of RS codes per block
data 1 of block 1 - data 1 of block 2 - ... - data 1 of block n
data 2 of block 1 - data 2 of block 2 - ... - data 2 of block n
...
data m of block 1 - data m of block 2 - ... - data m of block n
then :
RS 1 of block 1 - RS 1 of block 2 - ... - RS 1 of block n
RS 2 of block 1 - RS 2 of block 2 - ... - RS 2 of block n
...
RS z of block 1 - RS m of block 2 - ... - RS z of block n
- The numeric mode.
  In this mode the datas are divided into groups of 3 digits which are compressed in 10 bits.
  If only 2 digits remain, we convert them to 7 bits and if only one digit remains, we convert it to 4 bits. The segment will therefore include : the mode indicator 0001, the character counter (Length to be taken in the table) and the datas.
  
  Example :
  String : 34567
  First group : 345 soit 0101011001
  2nd group : 67 soit 1000011
  Number of characters : 5
  If version code 3 for example, length on 9 bits, ie: 000000101
  Segment : 0001 000000101 0101011001 1000011
- Alphanumeric mode.
  In this mode we can only encode 45 characters numbered 0 to 44 according to the following table :
  Value Char. Value Char. Value Char. 00 15F 30U 11 16G 31V 22 17H 32W 33 18I 33X 44 19J 34Y 55 20K 35Z 66 21L 36(Space) 77 22M 37$ 88 23N 38% 99 24O 39* 10A 25P 40+ 11B 26Q 41- 12C 27R 42. 13D 28S 43/ 14E 29T 44:
  The characters are taken in pairs and encoded on 11 bits. The code of the first character is multiplied by 45, then the code of the 2nd character is added and the sum is converted into 11-bit binary.
  If a single character remains, its code is converted to a 6-bit binary.
  
  Example :
  String : ZEBU : 35 14 11 30
  2nd group : 11 x 45 + 30 = 525 ie 01000001101
  Number of characters : 4
  If version code 3 for example, length on 10 bits, ie: 0000000100
  Segment : 0010 0000000100 11000110101 01000001101
- Byte mode.
  This mode can encode any byte.
  These are simply converted to binary.
- Kanji mode.
  This mode is not studied here.

Detection and correction of errors.

The system of correction is based on the codes of "Reed Solomon" which make the joy of the mathematicians and the terror of the others ...
The number of correction CWs depends on the version of the code and the level of correction chosen, it is given for each block of data. (See table)
The Reed Solomon codes use a polynomial in which the power of x is the number of error correction CWs used. For example, for a code version 1 with correction level L we use an equation to obtain 7 RS like this :
x⁷ + ax⁶ + bx⁵ + cx⁴ + dx³ + ex² + fx + g The numbers a, b, c, d, e, f and g are the coefficients of the polynomial equation.
For information the equation is : x⁸ + x⁴ + x³ + x² + 1 and the Galois body is modulo 285.
There are 36 Reed Solomon code block sizes (see table) including micro-codes. The coefficients of these 36 polynomial equations have been precalculated. You can see the coefficient file. We can also calculate them. But first a small explanation on the operations in a Galois body.

Arithmetic operations in a Galois body of characteristic 2.
The sum and the difference are the same function : the exclusive OR function.
A + B = A - B = A Xor B
The multiplication is more complicated ; first we need to create 2 tables containing the Logs and Antilogs of the body according to its "modulo" (Here 301) :

Now we can calculate Mult(a, b) = Alog((Log(a) + Log(b)) Mod 255)

Here is now in Basic the algorithm to calculate the factors :

And now, still in Basic, the algorithm for calculating correction CWs.

Find all the RS code calculations of the different 2D barcodes in Visual Basic 6.
It is a ZIP file without installation :
Those who have read and understood the codes of Reed Solomon will find themselves there ; for the few ignorant who have not understood everything (like me!) It will be enough to apply the "recipe" by using the codes obtained in the reverse order (last to first).

Bar code making.

Since we can create the bar code pattern it remains us to draw it on the screen and to print it on a paper sheet. Two approaches are possibles :

The graphic method where each bar is "drawn" as a full rectangle. This method enable to compute the width of each bar with a one pixel precision and so we can work with widths which are perfect multiple of the used device pixel. This give us a good accuracy specially if the device have a low density as it's the case with screens and inkjet printers. This method require special programming routines and does not allow to make bar codes with a current software.
The special font in which each character is replaced by a bar code. This method allow the use of any software like a text processing or a spreadsheet. (For example LibreOffice, the free clone of MSoffice !) The scale settings according to the selected size can bring away small misshaping of the bar drawing. With a laser printer there's no probs.

It seems there is no free fontfor datamatrix barcode on the net. I've decided consequently to draw this font and to propose it for download. Since each symbol have an even row number and an even column number, I put in each character of the font 4 modules (2 rows and 2 columns). In this manner we have 16 combinations assigned to the 16 first capital letters.
If we give a value at each dot of this 2 x 2 matrix like this :

1 2 4 8

The ASCII value of the character associated to a given matrix is the sum each dot value + 65 (65 = A = no dot, all white !)

The " datamatrix.ttf " font (Suitable for QRcodes)

This font contains the 16 character A (ASCII : 65) to P (ASCII : 80)

Copy this file in the font directory, often named : \Windows\Fonts

Encoding a QRcode

The program will have to take place in several stages :

Compacting the data in the CWs using the different modes and trying to optimize, and if necessary adding the stuffing.
Determination of the version (Size) of the code.
Placement of all function modules (Except for format information).
Cut into blocks if necessary then calculate correction CWs according to the version and the level of correction chosen.
Placement of CWs in the matrix.
Application of the different masks and choice of it after evaluation of the results.
Calculation and placement of format information.
Transform each pair of lines into a string of characters. The length of the string is: number of modules / 2. The number of line (or column) being odd, we add to the right and bottom a line of white modules.

Because of the interaction between the different modes of compression it is difficult to make a 100% optimization. However, the standard gives in Appendix J a method of optimization ...
The evaluation of the results of the different masks will be done "by eye" and by testing the codes obtained.

A little program to test all that.

Here is a small program written with Visual Basic 6.
The setup file copy the program, Visual Basic
dependencies, source files and the font.

Setup file :

ZIP file without setup :

The function QRcode$ is about 900 lines, so I do not reproduce it here, just get it in the file "form1.frm" which is with the program above ; with the self-installation program the file "form1.frm" is located in the program directory, subdirectory "sources"

The function is called as follows : resultat$ = QRcode$(Chaine$, Level%, Mask%, Version%, CodeErr%)

Chaine$ : the string to encode
Level% : Correction level
Mask% : Mask to use
Version% : Will give, on return, the code version (size)
CodeErr% : Possible error number.

These last two parameters are optional and are passed by references. CodeErr% values at the return of the function :

1 : Chaine$ is empty.
2 : Chaine$ contains too much data.

Now simply display or print the resultat$ string with the datamatrix font for example in a word processor. Office users will be able to even integrate the Datamatrix$ function into a macro in order to automate the processing. To be able to carry out all the processing in a single function, I had to use "Gosub" instead of functions with parameters; I can already hear the programming aesthetes screaming sacrilege.