自動車工場のガロア体

Galois Field
In Auto Factory

How QR code works

The story of its birth was trashed by local newspapers and the economic press. Two years later, when it was first introduced, in a tiny article at the bottom of a page, as a mark that stores the information with a combination of black and white dots, no readers could imagine what it looked like. Nowadays, we all know what it is and how to use it. Why on earth was the QR code created and how does it work?

The QR code was developed in the early 1990s at Nippon Denso, which is now known as Denso Corporation. It was designed by an engineer who had long cherished an ambition to invent "something as a global standard" while addressing the pressing needs of the automobile production line.

Toyota Motors controls inventory on its supply chains using kanbans, signboards that list the names and quantities of parts on it, that come and go as purchase orders and delivery slips. Denso had developed the barcodes (ND codes), which were printed on kanbans, to automate data verification at every gate of the factories.

Around 1990, when the bubble economy was at its peak, the number of parts and suppliers exponentially increased to respond to the unprecedented demand for cars with rich varieties of options. The ND code had hit its limit because it could record only 63-digit numbers. The burden of manually scanning multiple codes in a row could no longer be ignored.

In those days, Denso had an overwhelming market share in barcode readers in Japan. It was Masahiro Hara, however, who was consulted by its Nishio factory to do something about barcodes. He was not in charge of barcodes but was developing OCR (Optical Character Recognition) devices that automatically read the characters on export documents. In 1992, he proposed to his boss that Denso develop a new two-dimensional code of its own instead of ad hoc revised barcodes. He had expertise in image processing.

His development team set a goal to make the code oil-blur resistant and fast to read, which was lacking in the 2D codes that had been already developed by U.S. companies. In 1994, the original specification of the code was completed and announced as QR code. It might be unfair to blame poor reporters, who did not write the debut of this outstanding invention, for their myopia since there was no real product yet. The following year, the company began a field test of the first device at its Takatana factory in Anjo, Aichi.

How QR code works

How does the QR code work? Let's try to decipher a sample code step by step.

When the reading software captures an image from the camera, it immediately processes the data as follows.

First, it determines the version (model number) of the code from the grid pattern of the image. The model number ranges from version 1, which has 21 cells vertically and horizontally, to version 40, which has 177 cells respectively. In this example, the number of cells per side is , which indicates that the version is .

Next, the software reads out the settings (format information) used for this code. This information is located next to the three squares, called cut-out symbols, in the corners. To determine the format, the software searches for the closest black-and-white pattern in the specification list.

In this example, we know that the setting is inversion mask , correction level .

The inversion mask is a kind of makeup applied to the code to make it easy to read. It must be stripped away before reading the data. When we invert the black and white according to the mask , the true face of the QR code would emerge like this.

Finally, we take every eight cells from the bottom right corner and interpret them as a binary number.

Thus obtained , are the body of data incorporated in the code.

Let's not become complacent. We are still at the threshold of decoding.

Usually, we never get worried that the result of addition or multiplication of any pair of numbers will no longer be a number since there is an infinite number of numbers in this world. However, about 200 years ago, a French mathematician realized the existence of "another number" that has a limited number of numbers but allows us to add and multiply any pair of numbers without worries. It is called the Galois field (finite field) after his name.

World of finite numbers

For most people, except mathematicians, the Galois field is of no practical use. When you keep adding 1 to a number, you will eventually exhaust all unused numbers and will have to reuse some of them. When a series of numbers is rolled back by the addition, the comparison of numbers will no longer be valid.

However, the Galois field is, anyway, a perfect number in all other aspects. For example, in a world with only eight numbers, the following addition and multiplication would work.

In this world, the rules of arithmetic we learned in elementary and junior high school are perfectly valid. When the order of addition or multiplication is changed, the answer is the same.(1 + 2 = 2 + 1) There is a "reciprocal" for every number that becomes 1 when multiplied by it. Many of you may recall that distributive law, which states that adding together first and then multiplying is the same as multiplying individually and then adding together.( (1+2)×3=1×3+2×3 )

However, even if we could do calculations with these numbers, they would still be useless. The numbers we have read from the QR code are such numbers. Mathematicians would call them elements of the Galois field with the order of 256 in their jargon.

Reed-Solomon codes

How was the series of numbers read out from the QR code created by the way? The QR code encodes data by using Reed-Solomon codes that enable us to correct misread numbers.

Firstly we will construct a polynomial with the numbers to be encoded as coefficients. If the data to be stored is , then the polynomial looks as follows.

At this point, the data is re-interpreted as a number of the Galois field with the order of 256. There is no excess or deficiency of information as there are just 256 combinations of black and white 8 cells.

Next, if we want to correct up to errors, for example, we should create a polynomial by multiplying from = 1 to = (twice the number of corrections).

And we will get the remainder polynomial by dividing by . Remember that we must use the Galois field arithmetic to calculate the coefficients.

Finally, we subtract the remainder from .

This is the series of numbers to be printed on the QR code. You will notice that the original data is followed by the coefficients of the polynomial of the remainder.

Error detection

The same procedure must have been used to create the sample QR code. By reconstructing a polynomial with numbers we have extracted from the code, we can obtain the following polynomial.

The value which can be obtained by substituting , that we used to construct , for x of this polynomial is called a syndrome. If all coefficients of the polynomial are correct, then all syndromes will be zeros because we did subtract the remainder in advance so that they would be zeros! If all the syndromes ( in this case) pass the test of being zero, the polynomial is considered to be free of error.

If there are any non-zero syndromes, then there are errors somewhere in the coefficients. In this example below, there seems to be some reading errors.

The list of syndromes above is the only clue for us to calculate which coefficients are incorrect and by how much they should be adjusted.

Error correction

A polynomial with all the syndromes as coefficients is called a syndrome polynomial .

In Reed-Solomon codes, the polynomial , which tells us where the reading error occurred, and the polynomial , which tells us how much we add to correct the error, have a special relationship with the syndrome polynomial ; is divisible by .

There are several well-known methods to solve this equation. The most famous one is called the Extended Euclidean algorithm. Like the Euclidean algorithm for finding the greatest common divisor (you must have learned it in your high school!), the divisions by and are repeated to derive two polynomials. In this case, the results are as follows.

When we substitute for the polynomial and get zero, that means there is an error in the coefficient of in the polynomial and the error is . In our example, we get final results as follows.

Now that we have the locations and the amounts of the error, the original polynomial is corrected as follows.

Remember that we are in a world with 256 numbers. The second part of correction would be .

Fundamentals of digital age

The Reed-Solomon codes are used in a wide variety of digital devices, including CDs, DVDs, hard disks, USB memory devices, digital TV, optical fiber and interplanetary probes. Our perception of digital technology as "accurate and non-degrading" is not based on the fact that data are composed of zeros and ones. It is error correction mechanism that enables us to store, send, and copy-and-paste data without errors.

The error correction mechanism in the QR code was developed by two young engineers from the Toyota Central R&D Labs. They started by reading a textbook on code theory, which was completely out of their field, and got a sense of what the Galois field is like by manual calculation. As a result, the error correction mechanism adopted for the QR code was so orthodox that it could be put straight back into the textbook.

The Galois field, which is a fundamental technology for the digital society, is usually hidden in semiconductor circuits and invisible to us. The pressing needs in the auto factory for a visible, large-capacity, accurate means of data storing that must fit on a kanban gave birth to an exceptional invention that made visible this strange world of numbers that was once reserved for mathematicians.

The numbers, after checked by the error correction mechanism, can be safely converted to characters according to the specification; The QR code has four types of mode: numeric mode, alphabetic and numeric mode, Japanese kana-kanji mode and general-purpose byte mode.

In our example, the first four cells tell this code is in byte mode and the data that follows is to be interpreted accordingly in 8-cell units.

By interpreting the bytes as characters, we obtain a string of characters "How QR code works." The QR code never speculates the data with probability theory. There is no chance of error at this stage.

Quick response

Besides strong error correction capability, the other goal was fast reading from any directions. To achieve this goal, the code must be cut out from the image reliably and in the correct orientation. The team collected lots of printed materials in five languages and found the key of detecting the code; the pattern of 1 black, 1 white, 3 blacks, 1 white and 1 black. Curiously enough, this pattern rarely appears in printed materials!

The cut-out symbol in the QR code has this 11311 pattern at the center in any orientation. Since there are three cut-out symbols (upper right, upper left, and lower left) in a code, it is easy to tell in which orientation the code is captured in the image.

The QR code can be easily retrieved by the following primitive procedure. (commercial softwares, such as ones you use with your smartphone, are more sophisticated)

1. Convert the image to black and white

This may seem simple at first glance, but the ability to distinguish black and white by taking shadows and light reflections into account directly affects the performance of the reading device, so so the algorithm is the trade secret of the manufacturers.

2. Scan each horizontal line at a time from the top and look for a pattern of 11311. The larger the pattern, the more likely it is to be a candidate for a cut-out symbol.

3. Transform the position and angle of the image so that three of the best candidates with similar sizes are in the upper right, upper left, and lower left.

In case the software selects the incorrect cut-outs, the image can be identified as unreadable thanks to an error correction algorithm. If there are other candidates, the software will recrop it and attempt decoding.

The fact that 11311 is the quintessence of this invention is reflected in the reason why there was a process of masking at the time of readout.

The following eight types of inversion masks are defined in the specification.

Since it is possible to decode it regardless of the mask applied, we can freely choose the most convenient one. One of the criteria for a better mask is the absence of the 11311 pattern. The gist is to avoid creating by ourselves the key pattern that they have painstakingly found.

Beyond auto factory

Since 1996, when newspapers introduced the first reading device from Denso, awkwardly describing it as "By encoding information with a combination of black and white dots, the code can contain over a hundred times more information than barcodes", the QR code slowly spread to the other factories in Toyota group. It was soon recognized by ISO and adopted even by non-auto companies such as Mitsubishi Electric and Pentel, a stationery manufacturer. However, this can't be the reason why you are reading this article, can it?

Starting with Sharp's model in 2002, the QR code readers were built into almost all mobile phones, which quickly became popular in Japan. In the newspapers of the time, you can find a wide variety of civic applications such as guides in the zoo, lost child searches, display of production areas for the fishery, and horse race tickets. In just a year or so, the name for this novel product changed from "mosaic pattern readable by cell phones" to "QR code" in news stories.

The error correction capability, which was originally developed in order to fight oil stains in engine factories, had found unexpected applications. By taking advantage of the high correction rate of up to 30%, advertisers designed corporate logos and PR messages into the code. In the United States, an art exhibition was held with oil paintings of QR codes showing the internet addresses of the messages. Other artists in Europe made three-dimensional sculptures that looked like different QR codes from different angles.

At the same time, widespread use of smartphones made the code an easy tool for fraud and computer virus. You will find that black-and-white marks in the field of mass surveillance, vaccination management for covid-19, vaccine passports and so on. The QR code had become symbol of social issues.

Denso registered the name as a trademark in 1995 and Denso Wave, a subsidiary separated from Denso in 2001, is now protecting the brand. Unlike patents, registered trademarks do not expire. However, such a clever corporate strategy would have gone stale once the code had become a global standard of 2D code. At last, after years of hard work and openness, the inventor's ambition was realized beyond the walls of the auto factory.

References: The Miracle of the QR Code (Susumu Ogawa), , B-Plus 2013 Autumn (The Institute of Electronics, Information)

The original version of this article was edited, except for the mathematical section, so as to fit in the maximum size of a single QR code below, which might result in lots of under-explanations and logical gaps.

本文