The use of TWO-DIMENSIONAL code in daily life has been everywhere, payment code, wechat business card, health code, bus code…… A simple QR code invades every aspect of our lives. Black and white blocks of limited area, how to carry information. Will qr codes be duplicated in different application scenarios, or will they be exhausted like IPV4? If you have questions about any of these, please read this article with questions.

One. You must not have seen the QR code

There are many types of TWO-DIMENSIONAL code. At present, the mainstream includes PDF417 code, QR code, Hanxin code, color bar code, EZ code, Aztec code, QuickMark and Data Matrix. The QR Code, or Quick Response Code, that we use every day to pay for and order food, was invented in Japan in 1994.

According to the implementation principle, two-dimensional code can be divided into two categories:

  • Stacked/row type (the principle is based on one-dimensional bar code, stacked into two or more lines as needed)

  • Matrix TWO-DIMENSIONAL code (the principle is to encode in a rectangular space through the different distribution of black and white pixels in the matrix)

Little knowledge:

  1. There are many types of TWO-DIMENSIONAL code, we usually say the TWO-DIMENSIONAL code is QR code, just a two-dimensional code
  2. QR codes were invented by the Japanese

The bottom right corner of the QR code to our most common, this paper to QR code cut, analysis of the implementation principle.

How is information transmitted?

Qr code on the compiled code clever use of which form the basis of computer logic “0”, “1”, the use of a number of corresponding to the binary geometric shapes to represent text numerical information, these particular geometric figure according to certain rules in the distribution of the plane (2 d), black and white, recorded data graphical symbol information. Identify the TWO-DIMENSIONAL code by scanning the code gun, mobile phone APP, etc., restore the information. Much like encryption and decryption.

The overall structure

QR code from the structure can be basically divided into positioning area, functional area, data area three parts

1. The location area

Common TWO-DIMENSIONAL code, whether you are standing, lying on your stomach, kneeling, left, right, up and down can be identified, all rely on these three data modules:

  1. Location marker. On the left, right, left there are three large “back” word of the black and white concentric square, for THE QR code identification positioning mark, losing one of the identification will affect.
  2. Timing flag. For positioning, two-dimensional code if the size is too large, easy to scan distortion, the role of time sequence pattern is to prevent the generation of scanning distortion;
  3. Calibration flags. Required above Version2

2. The functional areas

  1. Format information. Store formatted data, indicating the correction level of the two-dimensional code, divided into L, M, Q, H;
  2. Version information: For Version 7 or later, two 3 x 6 areas must be reserved to store part of the Version information.

3. Data

Actual saved two-dimensional code information and error correction code element (used to correct errors caused by two-dimensional code damage)

Version classification

QR codes are available in different versions (categories) from 1 to 40, each with its own code structure (code number). “Symbol structure” refers to the code element in the TWO-DIMENSIONAL code (symbol refers to the square black and white dots that constitute the QR code) number. Starting with Version 1 (21 by 21 codes), it increases by 4 codes vertically and horizontally, respectively, until version 40 (177 by 177 codes).

How is the code generated?

The generation of a TWO-DIMENSIONAL code is roughly divided into the following steps:

The data analysis

  1. Determine the character type of encoding and convert it into symbolic characters according to the corresponding character set;
  2. Select the error correction level. Under certain specifications, the higher the error correction level, the smaller the real data capacity

Data encoding

  1. Similar to theutf8Encoding, given a string and then encoding it as a string of binary numbers.
  2. Generate the data encoding of the original information according to the selected encoding mode, version information and error correction level.

Error correction coding

  1. Error correction codes can be calculated according to the coding results of source data, using reed-Solomon error correction algorithm

Structure matrix

  1. According to the selected version information and the three parts mentioned in the overall structure, the matrix cells are filled with 0 and 1 respectively

mask

The uneven distribution of black and white may lead to large areas of white or black after the above drawing, resulting in the difficulty of scanning recognition. The QR code provides 8 Mask Mask patterns:

Let me give you an example

Suppose we generate a QR code for the string “01234567” with the following steps:

1. Select a mode

QR codes support the following encoding modes:

Different versions of the TWO-DIMENSIONAL code capacity is different, refer to:

We chose Version 1, and the error correction level H is sufficient. In each version, the number of bits to be encoded in different encoding modes is as follows:

Because we came to the conclusion:

  1. 01234567 indicates the numeric encoding
  2. Select Version 1 H for qr code
  3. Every three digits are encoded into 10 bits, and the remaining 1 or 2 bits are converted into 4 or 7bits

2. The coding

Divided into three groups, 012 and 345 and 67. Where, 012 becomes 0000001100 (10th bit); 345 to 0101011001 (10th); 67 to 1000011 (less than 3 numbers, encoded in 7 bits)

Three binary strings: 0000001100 0101011001 1000011

There are 8 digits in total, 8 translated into binary is 0000001000 (10 bits), plus the identifier 0001 of our chosen numeric pattern, resulting in the binary string:

0001 0000001000 0000001100 0101011001 1000011 0000

Eight digital Numbers | | 012 | | 345 | 67 terminator

A total of 45 bits are rearranged in groups of 8 bits instead of 8 multiples. We need to add enough zeros to make 8 multiples:

00010000 00100000 00001100 01010110 01100001 10000000

The number of bits is 48, and the maximum number of bits is not reached, so we need to add the Padding Bytes at the end of the encoding. We select the H level of version 1, and the capacity is 72 bits. Now there are only 48 bits. There are still 24 bits to be completed. Padding Bytes (11101100, 00010001)

00010000 00100000 00001100 01010110 01100001 10000000 11101100 00010001 11101100

The above codes are called Data Codewords, and each 8 bits is called a codeword. We also need to add error correction information to these Data codes.

3. Error coding

With the error correction code, can make some two-dimensional code with incomplete, defiled can also try to scan code parsing out; Can make the two-dimensional code center location for some businesses to add unnecessary ICONS to the analysis

We select level H and refer to the definition of error-correcting code grouping:

  • Number of error-correction blocks: indicates the Number of error-correction blocks to be divided.
  • Correction Code Per Blocks: The number of Code words in each block, i.e. the number of Bytes;

(26, 9, 8) indicates that in Version 1 H, there are a total of 26 codewords, among which 9 are original data codes and 17 are error correction codes, among which each error correction code occupies 8 bits

We assume that the calculated (calculated method) good error correction codes are 17 codewords, respectively E1, E2, E3… E17

4. Final coding

Original Data Codewords, including 9 Codewords in total:

00010000 00100000 00001100 01010110 01100001 10000000 11101100 00010001 11101100

Let’s call them D1, D2, D3… D9

Source code and error correction code, the final formation of data is: D1 D2 D3 D3 D3 D3 D3 D3 D3 D3 D3 D3 E1 E2 E3…… E17

5. Construct the matrix

With the code, we can draw the image.

First determine the overall size of the matrix based on version. We are Version 1, so we are a 21 * 21 matrix.

Next, fill the positioning marks in the upper left, lower left and upper right positions.

Fill the checkbox, determine the calibration mark, fill the format information, fill the version information

Finally, fill in the data and error correction codes. Starting from the lower right corner of the QR code, fill in every bit of our data coding along the red line. 1 means black, 0 means white, and bypass or skip non-data areas. As shown:

6. Mask

And then we have our diagram. However, the dots may be uneven, and scanning can be difficult if large areas of blank space or black blocks are present. So, we also have to do Masking. QR has 8 masks that can be used. For the diagrams and algorithms of each Mask, refer to the figure in the Mask section of Part 3.

Mask is XOR with the graph generated above, and only XOR with the data area, does not affect the functional area.

We need to take the above generated pattern and mask pattern to do an XOR operation, so that the black and white distribution will be much more uniform! Which mask pattern to choose? There is also a very complicated calculation scheme. The general procedure is to do xOR of the original pattern and each mask pattern respectively, and then calculate the uniformity according to a set of rules, and finally choose the most uniform one. Explore the principles and applications of TWO-DIMENSIONAL code by referring to Data Masking or in depth.

The qr code after the mask is the final image.

Five. What should I do when I run out?

This is the wechat background download of the official account name card, using 37 * 37 matrix (believe me, in order to count clearly, small eyes are blind). Take this matrix:

The three locations are all 7 * 7 in size, so the number of available cells on this matrix is 37 * 37-3 * 7 * 7 = 1222. And given the mask and placeholder and all that stuff that we talked about in the first half of the book, let’s say there are only 1,000 grids available. Each cell can be black or white, with only 0 or 1 to choose from, and the combination of 1000 cells is 2 ^ 1000, which is expressed as a decimal number:

10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376

That’s just the theoretical number, but if you subtract out all black, all white and all the other things that don’t work, it’s still a super large number. 37 * 37 is only version 5. We mentioned in the first half that there are 40 versions of the QR code. Therefore, the two-dimensional code is used up, there is a theoretical possibility, but you and I must not wait for that day. Even if the end of the day, see IPV4 to IPV6 can continue to expand the size.

Six. Will it be repeated?

Two-dimensional code as the carrier of information, as long as the information is consistent, the generated two-dimensional code will be repeated. In the real world, each APP or each enterprise can ensure the uniqueness of information in the internal environment, so the TWO-DIMENSIONAL code generated by us is unique. The uniqueness of wechat TWO-DIMENSIONAL code is the only one within the wechat system. The arrangement of black and white dots on the TWO-DIMENSIONAL code is not random meaningless, but the original binary code, representing some meaning, and the two-dimensional code of different people to represent things is different, so there will be no repetition.

other

Now there are color QR codes on the market, or irregular QR codes. This does not conflict with the generation process described in this article. Color two-dimensional code is scanned by the camera, the image is not directly analyzed, the program will cut the two-dimensional code, denoising, gray processing and so on. And the so-called gray processing, is to process the picture into gray picture, gray image is also known as “black and white” image. Eventually the image will be transformed into a matrix of only “0s” and “1s”.

reference

QR Code’s official website

wikipedia

Data Masking

Deep exploration of two-dimensional code principle and application

Pay attention to my

If you read on wechat, please click the link to follow me. If you read on PC, please scan the code to follow me. Welcome to communicate with me and point out mistakes at any time