[PYTHON] Create a QR code that displays "Izumi Oishi" by scratch

"Oishi Izumi Suki" Advent Calendar I will be in charge of the 5th day. This is my first time to participate in the Advent calendar. I'm excited.

This time, I will introduce the procedure to create a QR code from scratch without relying on an existing library. Now that the existing libraries are extensive, it is not particularly useful, but please see it as a reading material that feels like QR code is created like this.

About the contents of this article

We will create a QR code that stores the text "Izumi Oishi" as data, and explain how to read it with an existing QR code reader. The QR code specifications will be explained focusing on only the necessary parts.

Referenced site

First of all, this article is not the original, but a follow-up challenge based on information on sites that are doing similar things on the web.

Create a QR code (http://www.swetake.com/qrcode/qr1.html)

In this article, I will focus on the points that have been blocked while referring to this.

In addition, JIS information, which is a standard, is indispensable for implementing QR codes. You can read the standard document on the JIS site (printing is not possible). Since you cannot get the URL to fly directly, please search the database with "JIS X 0510". The referenced version is "X0510: 2018" updated in 2018.

I got information from many other sites, so I will introduce them at the end of this article.

Decide the type of QR code

Although it is a QR code, there are actually many types. There are over 40 versions, from compact and large squares to insanely large and fine-grained ones.

What is different is basically two points, capacity and strength of error correction. The capacity is from 5 bytes to about 3700 bytes, and error correction recovers from 7% to 30% of the total even if a part cannot be read.

This time, I want to make a simple code that only includes the text "Izumi Oishi", so I will select a small one. Specifically, it is a QR code with 25 squares on each side called version 2-H. The capacity is 16 bytes (Table 7 on page 31 of the standard). In addition, we selected the one with the highest error correction power of 30%. Enter 9 characters for kanji and hiragana. "Anastasia Suki" is safe. Unfortunately, "Eve Santa Claus likes" is not included.

The overall data structure for this version is as follows. It looks like this.

The large eye-catching pattern in the three corners is the "position detection pattern" (and the adjacent white "separation pattern"). The pattern like a pedestrian crossing that connects them is the "timing pattern", and the small eyeball on the lower right side is the "alignment pattern". These are called "functional patterns" and are always colored.

On the other hand, the coded area changes depending on the data to be stored. There are three types below.

Other types of QR codes may have other "model number information", but this time they do not have them, so I will omit them. In addition, there are the following parts.

If you can make these, the QR code is complete. It's a long way to go, but please keep in touch.

Prepare the data that can be included in the QR

The detailed structure of the data section is as follows.

Mode type

Since the capacity of the QR code is valuable, there are several modes that are specialized for the type of data to be entered. This time, select the kanji mode that is specialized for kanji. Only the characters included in the Shift-JIS character code can be used, but this time it is sufficient. The identification code for Kanji mode is 1000 (binary). If you use another mode, you can use Unicode strings.

word count

In Kanji mode, the length of the character string is stored in 8 bits. In other modes it is different from 9 bits or 10 bits. This time it's 5 characters, so it's 00000101.

Character data

The target character type depends on Shift-JIS (UTF-8 has become so popular these days that it is not used much ...). In Shift-JIS, one character is represented by 16 bits, but since it is a little over 7,000 characters in total, it can be represented by 13 bits (2 ^{13 </ sup> = 8096). Follow the steps below to convert the Shift-JIS character code to a dedicated 13-bit code.}

The processing is divided into two types because Shift-JIS itself is roughly divided into two sections (strictly four). (Reference) (or standard P.89)

As a result, "Oishi Izumisuki" is converted as follows.

Termination pattern

Information to indicate that this is the end of the data. Fixed to 0000 with 4 bits. However, if the remaining capacity is 3 bits or less, cut part or all of it so that it does not protrude.

Buried grass bit

~~ It grows grass. ~~ If the total number of bits is not a multiple of 8 in the process up to this point, fill it with grass-filling bits = bit 0 until it becomes a multiple of 8. This time, 4 + 8 + 13 * 5 + 4 = 81 so far, so fill in 7 bits. 0000000

Buried grass bite

If there is still space left in the process up to this point, 11101100 and 00010001 will be filled alternately until the capacity is full.

Finally

To summarize the contents so far

1000 00000101 0110010100101 0101111001110 0101111110010 0000100110111 0000100101011 0000 0000000 11101100 00010001 11101100 00010001 11101100

If you organize it by 8 bits,
10000000 01010110 01010010 10101111 00111001 01111110 01000001 00110111 00001001 01011000 00000000 11101100 00010001 11101100 00010001 11101100

Convert to decimal integer
128 86 82 175 57 126 65 55 9 88 0 236 17 236 17 236

It's done.

Calculate error correction code (very hard)

This was the most difficult task. In the QR code, an error correction code is added by a method called Reed-Solomon code (hereinafter referred to as RS code) so that the data can be correctly decoded even if part of the data (that is, black or white) cannot be read correctly. This calculation method is very difficult for those who are not good at math.

It's a very long section, so it might be a good idea to skip here first and read to the end.

problem

To put it briefly, the problems that need to be solved here are as follows.

Primitive polynomial x^8+x^4+x^3+x^2+1 was used\\Enlarged Galois GF(2^8)In\\
N = 44, K = 16 \\
I(x) = d_1x^{15}+d_2x^{14}+d_3x^{13}+d_4x^{12}+d_5x^{11}+d_6x^{10}+d_7x^9+d_8x^8 + \\ d_9x^7+d_{10}x^6+d_{11}x^5+d_{12}x^4+d_{13}x^3+d_{14}x^2+d_{15}x+d_{16}
\\
G(x) =
x^{28}+α^{168}x^{27}+α^{223}x^{26}+α^{200}x^{25}+α^{104}x^{24}+α^{224}x^{23}+α^{234}x^{22}+α^{108}x^{21}+ \\
α^{180}x^{20}+α^{110}x^{19}+α^{190}x^{18}+α^{195}x^{17}+α^{147}x^{16}+α^{205}x^{15}+α^{27}x^{14}+ \\α^{232}x^{13}+
α^{201}x^{12}+α^{21}x^{11}+α^{43}x^{10}+α^{245}x^{9}+α^{87}x^{8}+α^{42}x^{7}+ \\
α^{195}x^{6}+α^{212}x^{5}+
α^{119}x^{4} +α^{242}x^{3}+α^{37}x^{2}+α^{9}x +α^{123}
\\When\\
P(x) = x^{N-K} I(x) \quad mod \quad G(x) 
\\ 
Ask for

...

...

...
** What? ** I don't know what it means?

It's tempting to run away while yelling "Murry" when you see a high-order polynomial like a fool, but of course, it's designed to be solvable. I would like to proceed while explaining one by one.

About GF2

Before we start the problem, I think we need to explain the concept of mathematics called GF (2). I can't explain it because I just remembered it, but to put it simply, it means "a world with special calculation rules that has only two types of numbers, 0 and 1." In this world, the rules of addition and subtraction are as follows.

addition

subtraction

Yes, addition and subtraction have exactly the same result. Also, as you can see from this result, this matches the XOR (Exclusive OR) of the bits. There is something convenient for the computer around here. By expanding this steadily, various applications will be possible.

By the way, GF is an abbreviation for Galois Field, and in Japanese it is called Galois field or finite field.

About primitive polynomials and GF (2 ^{8 </ sup>)}

Primitive polynomials are special polynomials used to extend and apply GF (p ^{m </ sup>). It is also used to extend GF (2) (p = 2, m = 1).}

GF (2 ^{8 </ sup>) is an extension of GF (2), which also has special calculation rules. GF (2) contained only two numbers, 0 and 1, but GF (2 8 </ sup>) contains 2 8 </ sup> = 256 numbers. .. This seems to be often used because it is very convenient for 8-bit arithmetic.}

Primitive polynomials are used when extending GF (2) to GF (2 ^{8 </ sup>), but there are several types of primitive polynomials, and which one is used when calculating the RS code. Since the calculation result changes depending on the usage, when creating the QR code, x 8 </ sup> + x 4 </ sup> + x 3 </ sup> + x < You are clearly instructed to use sup> 2 </ sup> + 1.}

What is α?

The α that appears in the function G (x) is the primitive polynomial F (x) = x ^{8 </ sup> + x 4 </ sup> + x 3 </ sup> It is the solution when the root of + x 2 </ sup> + 1, that is, F (x) = 0. And it is a very important existence that composes 256 numerical values (also called original in technical terms) included in GF (2 8 </ sup>). Since the property of α is necessary to solve this problem, I will explain it carefully though it is long.}

Since α satisfies F (α) = 0, the following equation holds.

α^8+α^4+α^3+α^2+1 = 0 \tag{1}

At this time, all the coefficients of each term belong to the world of GF (2). That is, it takes only two values, 0 and 1, and the result of addition and subtraction is both equal to XOR. Based on that, (1) is transformed.

α^8 = α^4+α^3+α^2+1 \tag{2}

You may think "Hmm?", But it is not a mistake that there is no minus when transposing. Since addition and subtraction are the same, it is safe to say that there is no distinction between +/- in this world (α ^{8 </ sup> = 1α 8 </ sup> = (0-1) α. 8 </ sup> =-α 8 </ sup>).}

Find the power of α

The power of α has a very important property. To talk about that, we will first calculate a ^{e </ sup> (e is an integer greater than or equal to 0). α 8 </ sup> is equal to α 4 </ sup> + α 3 </ sup> + α 2 </ sup> + 1, so α 9 </ sup>, α 10 </ sup>, α 11 </ sup>}

α^9 = α^5 + α^4 + α^3 + α \\
α^{10} = α^6 + α^5 + α^4 + α^2 \\
α^{11} = α^7 + α^6 + α^5 + α^3 \\

It will be. In α ^{12 </ sup>}

\begin{align}
α^{12} &= α^8 + α^7 + α^6 + α^4 \\
       &= (a^4 + a^3 + a^2 + 1) + a^7 + a^6 + a^4 \\
       &= a^7 + a^6 + (1+1)a^4 + a^3 + a^2 + 1 \\
       &= a^7 + a^6 + a^3 + a^2 + 1
\end{align}

In the third line, 1 + 1 = 0 holds for the coefficient of α, so the term of α ^{4 </ sup> disappears. As you can see, thanks to the replacement of α 8 </ sup>, no matter how high the degree of α is, it will be at most 8 terms below α 7 </ sup>. Can be replaced.}

α^e = b_1α^7 + b_2α^6 + b_3α^5 + b_4α^4 + b_5α^3 + b_6α^2 + b_7α + b_8

b _{1 </ sub> ~ b 8 </ sub> is a number (0 or 1) that belongs to GF (2). You can feel the bit operation.}

And if you keep increasing the order of α,

α^{255} = 1

Can be obtained. Since α ^{0 </ sup> = 1, α e </ sup> loops in 255 cycles.}

It's been a long time, but here's the most important thing.

*** About α ^{e </ sup> In the range where e is 0 to 254, the coefficients b _{1 </ sub> ~ b 8 </ sub> are uniquely determined ** *}}

In other words, e and b _{1 </ sub> ~ b 8 </ sub> can each have a 1: 1 correspondence. It should look like the table below.}

All are too long, so only some are listed. Here and [Here (Linked Table 4)](http: / /www.swetake.com/qrcode/qr3.html).

Also, below is the code to generate the table. Only those who want to see it.

#   e     0, 1, 2, 3, 4, 5, 6, 7, 8
buffer = [1, 0, 0, 0, 0, 0, 0, 0, 0]
print('e  b1 b2 b3 b4 b5 b6 b7 b8 d10')
for e in range(1, 255):
    #Shift the buffer to the right
    buffer = [0] + buffer[0:8]
    if buffer[8]:
        buffer[8] = 0
        # a^8 has occurred, so a^4+a^3+a^2+a^Replace with 0
        added = [1, 0, 1, 1, 1]
        for i in range(len(added)):
            # GF(2)In the digit-to-digit addition is equal to XOR(And there is no advance)
            buffer[i] = buffer[i] ^ added[i]
    n = sum([buffer[i] * (2 ** i) for i in range(8)])
    print(e, list(reversed(buffer[:8])), n)

load("gf")$
gf_set_data(2, x^8+x^4+x^3+x^2+1)$
binmap(n) := makelist(coeff(gf_exp(x, n), x^k), k, 7, 0, -1)$
exp2num(n) := lreduce(lambda([x,y],2*x+y), binmap(n))$
for n : 0 thru 254 do print(n, binmap(n), exp2num(n));

For α ^{e </ sup>, I found that the same value can be expressed in two ways, e or b _{1 </ sub> to b 8 </ sub>. In the article, we will refer to them as ʻe expressionandb expression`, respectively. The key is how to use these two expressions properly.}}

About operations between powers of α

I will explain the law of operation between powers of α.

First is multiplication.

When multiplying the two values α ^{i </ sup> and α j </ sup>}

α^iα^j = α^{i+j} \tag{3}

It will be. This is a range that I can learn in high school mathematics, so I don't think it's a problem. I will use it later.

Next is addition and subtraction.

α^i + α^j = ? \\
α^i - α^j = ?

This calculation cannot be done with the ʻe expression. But you can do it with b expression`.

α^i = b_{i1}α^7+b_{i2}α^6+b_{i3}α^5+b_{i4}α^4+b_{i5}α^3+b_{i6}α^2+b_{i7}α+b_{i8} \\
α^j = b_{j1}α^7+b_{j2}α^6+b_{j3}α^5+b_{j4}α^4+b_{j5}α^3+b_{j6}α^2+b_{j7}α+b_{j8} \\
If you leave\\
\begin{align}
α^i + α^j = α^i - α^j &= (b_{i1} \oplus b_{j1})α^7 + (b_{i2} \oplus b_{j2})α^6 + (b_{i3} \oplus b_{j3})α^5 \\
&+ (b_{i4} \oplus b_{j4})α^4 + (b_{i5} \oplus b_{j5})α^3 + (b_{i6} \oplus b_{j6})α^2 \tag{4} \\ &+ (b_{i7} \oplus b_{j7})α + (b_{i8} \oplus b_{j8}) 
\end{align}

• In 〇 is a symbol representing XOR (Exclusive OR). This means that addition and subtraction in the e expression are equal to the XOR for each coefficient in the b expression. More simply, it is equal to the XOR of 8 bits in a table.

The necessary tools are available according to equations (3) and (4).

What is d?

Next, the coefficient d that appears in the function I (x) will be explained.

I will write I (x) again.

I(x) = d_1x^{15}+d_2x^{14}+d_3x^{13}+d_4x^{12}+d_5x^{11}+d_6x^{10}+d_7x^9+d_8x^8 + \\ d_9x^7+d_{10}x^6+d_{11}x^5+d_{12}x^4+d_{13}x^3+d_{14}x^2+d_{15}x+d_{16}

d _{1 </ sub> ~ d 16 </ sub> contains the data to be protected by the RS code, that is, the 16 bytes of data obtained in advance, each containing 8 bits. It is a higher-order expression of the variable α that has information. The definition is as follows.}

d = b_1α^7 + b_2α^6 + b_3α^5 + b_4α^4 + b_5α^3 + b_6α^2 + b_7α^1 + b_8

Yes, it is the same as the b expression corresponding to α ^{e </ sup>. Therefore, the input data can be converted to the form of d = α e </ sup> every 8 bits. Let's do it for a moment.}

The first 4 bytes of data were 10000000`` 01010110 01010010`` 10101111. If you convert this while looking at the correspondence table (find the value of e from the right side to the left side),

d_1 = α^7 \\
d_2 = α^{219} \\
d_3 = α^{148} \\
d_4 = α^{97}

(Sorry, d _{3 </ sub> and d 4 </ sub> are not listed due to the omission of the table.)}

It will convert all the data as well. Only one point needs attention. Since there is no e that makes α ^{e </ sup> = 0 only when the data is 00000000, I give up and give up the term itself to express this in the form of α e </ sup>. I will cut it.}

As a result, I (x) looks like this:

I(x) = α^{7}x^{15}+α^{219}x^{14}+α^{148}x^{13}+α^{97}x^{12}+α^{154}x^{11}+α^{167}x^{10}+α^{191}x^9+α^{185}x^8 + \\ α^{223}x^7+α^{241}x^6+0x^5+α^{122}x^4+α^{100}x^3+α^{122}x^2+α^{100}x+α^{122}

The data corresponding to d _{11 </ sub> was 00000000, so the x ^{5 </ sup> section disappeared.}}

Find the remainder P (x)

Recall the function P (x) we want to find here.

\begin{align}
P(x) &= x^{N-K} I(x) \quad mod \quad G(x) \\
     &= x^{28} I(x) \quad mod \quad G(x)
\end{align}

So replace x ^{28 </ sup> I (x) with another function.}

M(x) = x^{28}I(x) \\
= α^{7}x^{43}+α^{219}x^{42}+α^{148}x^{41}+α^{97}x^{40}+α^{154}x^{39}+α^{167}x^{38}+α^{191}x^{37}+α^{185}x^{36} + \\ α^{223}x^{35}+α^{241}x^{34}+0x^{33}+α^{122}x^{32}+α^{100}x^{31}+α^{122}x^{30}+α^{100}x^{29}+α^{122}x^{28}

Then, if you write G (x) again,

G(x) =
α^{0}x^{28}+α^{168}x^{27}+α^{223}x^{26}+α^{200}x^{25}+α^{104}x^{24}+α^{224}x^{23}+α^{234}x^{22}+α^{108}x^{21}+ \\
α^{180}x^{20}+α^{110}x^{19}+α^{190}x^{18}+α^{195}x^{17}+α^{147}x^{16}+α^{205}x^{15}+α^{27}x^{14}+ \\α^{232}x^{13}+
α^{201}x^{12}+α^{21}x^{11}+α^{43}x^{10}+α^{245}x^{9}+α^{87}x^{8}+α^{42}x^{7}+ \\
α^{195}x^{6}+α^{212}x^{5}+
α^{119}x^{4} +α^{242}x^{3}+α^{37}x^{2}+α^{9}x +α^{123}

The pressure is still strong, but it's pretty refreshing.

By the way, how do you find the remainder for a polynomial? I feel like I did it around Number II-B when I was in high school. As a reminder, let's find the remainder of the function m (x) = x ^{2 </ sup> + 3x + 1 divided by g (x) = x-1.}

First, put the formula on the side to be broken.

x^2 + 3x + 1

Then, match the order and coefficient of the formula on the dividing side to the side to be divided.

\begin{align}
  & x^2 + 3x + 1 \\
-)& x^2 -  x     \hspace{2pc} ←xg(x)
\end{align}

And you'll subtract. Erases the highest degree term.

4x + 1

And in the same way,

\begin{align}
  & 4x + 1 \\
-)& 4x - 4     \hspace{2pc} ←4g(x)
\end{align}

The remaining ones are below the order of the dividing side, so it ends here. Therefore, the remainder is 5. When the coefficient of the maximum order of g (x) is 1, it is easy to do like this.

You can get P (x) in exactly the same way. Now, let's try to actually divide M (x) by G (x) only at the beginning (sorry, but it's too long to write).

First, check each other's maximum degree terms. M (x) is α ^{7 </ sup> x 43 </ sup>, and G (x) is α 0 </ sup> x 28 </ sup>. So multiply G (x) by α 7 </ sup> x 15 </ sup> to get the same value.}

\begin{align}
& α^{7}x^{43}+α^{219}x^{42}+α^{148}x^{41}+... \\
& α^{7}α^{0}x^{43}+α^{7}α^{168}x^{42}+α^{7}α^{223}x^{41}+... \hspace{2pc} ←α^7x^{15}G(x)
\end{align}

Here we use equation (3). The multiplication of the powers of α is the addition of the exponents, so if you organize it

\begin{align}
  & α^{7}x^{43}+α^{219}x^{42}+α^{148}x^{41}+... \\
-)& α^{7}x^{43}+α^{175}x^{42}+α^{230}x^{41}+... \hspace{2pc} ←α^7x^{15}G(x)
\end{align}

Equation (4) is used for this subtraction. Subtraction between powers takes an 8-bit XOR, right? For α ^{219 </ sup> --α 175 </ sup>, α (01010110 xor 11111111) </ sup> = α 10101001 </ sup> = α 135 </ sup> That's right. α 148 </ sup> --α 230 </ sup> = α 01010010 xor 11110100 </ sup> = α 10100110 </ sup> = α 207 </ sup > .... Be sure to refer to the table when converting from ʻe expression(exponential value) tob expression (decimal number) and from b expression to ʻe expression (decimal number <as is). -> Do not convert to decimal number)}

All you have to do now is repeat the process of erasing the highest degree terms. As a caveat, if the exponent becomes 255 or more after using equation (3), use α ^{255 </ sup> = 1 to correct the exponent to be less than 255. ..}

It ends when the side to be finally divided falls below x ^{28 </ sup>, and R (x) is calculated as follows.}

R(x) = α^{248}x^{27}+α^{159}x^{26}+α^{237}x^{25}+α^{105}x^{24}+α^{12}x^{23}+α^{215}x^{22} \\
+α^{172}x^{21}+α^{102}x^{20}+α^{113}x^{19}+α^{149}x^{18}+α^{233}x^{17}+α^{135}x^{16}\\ 
+α^{51}x^{15}+α^{42}x^{14}+α^{233}x^{13}+α^{7}x^{12}+α^{44}x^{11}+α^{236}x^{10}+α^{216}x^{9} \\
+α^{159}x^{8}+α^{64}x^{7}+α^{70}x^{6}+α^{11}x^{5}+α^{0}x^{4}+α^{51}x^{3}+α^{5}x^{2}+a^{60}x^{1}+a^{168}

What I wanted (RS code) is the exponential value of each coefficient part of this R (x). Therefore

248 159 237 105 12 215 172 102 113 149 233 135 51 42 233 7 44 236 216 159 64 70 11 0 51 5 60 168

It's done. It was tough.

Place data and error correction code in the square

So far, it's about 60-70%. It's a little more.

Arrange the created data and error correction symbols bit by bit according to the image numbers. Since the data is 16 bytes and the error correction symbol is 28 bytes, 44 * 8 = 352 bits. Fill up to 351 in the figure.

I will add color (0 or 1) to the rest The white part is called the bright module, and bit 0 is inserted. The black part is called the dark module, and bit 1 is inserted. The green part is called the residual bit, which is a fractional part, so insert bit 0. I will fill in the purple part at the end, but ** I did not know what value to enter at this time, so I will temporarily enter the value TBD. Please let me know if you are familiar with it **. (The standard (P.45) says that it must be emptied temporarily, but what is it?)

Only the purple part in the figure is temporarily placed, but the figure is completed.

Choosing the right mask (hard)

The QR code has a function called "mask" to prevent the contents of the data from generating patterns that are extremely difficult to read. The purpose is to partially invert the arranged black and white patterns using eight different patterns, and finally generate the most readable pattern.

Therefore, in the software (encoder) that creates the QR code, you have to try all eight masks and select the best one.

Mask type

There are eight types of masks below. (Calculation formula omitted. For details, see P.49 of the standard)

Part to be included in the mask target

--Data part --Error correction code

Parts not included in the mask target (other than those listed above)

--Functional pattern (position detection, timing, alignment) --Format information --Remaining bits

Evaluation

After applying each mask, the score will be evaluated according to four types of evaluation criteria. The evaluation is a deduction method, and the one with the fewest points will be actually used.

The evaluation target is the entire QR code. (However, there is a part where the color has not been decided yet, so it is unclear what to do with it ...)

The evaluation criteria are as follows (Table 11 on page 53 of the standard).

The explanation here is very rough, so please refer to the standard for the exact contents.

• 1 Points will always be deducted (-36 points in total) for the black 3x3 dark module pattern inside the position detection pattern in the three corners. However, since no mask is applied to this part, points are deducted equally in the evaluation of all eight masks, so there is no effect on the mask selection result.
• 2 Refers to the large position detection pattern at the three corners.

When actually evaluated, only evaluations 1 and 2 were deducted, and evaluations 3 and 4 were not deducted in all eight masks. ** For evaluation 3, the evaluation stopped working at all because I put a value such as value TBD in the format information part, but what about this ... ** After all, the Ming module Is it appropriate to put in ...?

The mask pattern 111 (bottom right of the image above) was selected with the least goals this time. Then actually apply the selected mask.

Calculate format information

Fill in the last remaining part. What remains is the part called "formal information".

The following two are included in the format information.

--Error correction level (2bit) 10 --Selected mask pattern number (3bit) 111

The error correction level is 10 because'H'was selected this time. For other levels, refer to the standard (P.54, Table 12).

BCH code is calculated based on this 5-bit information 10111. This is also a type of error correction code similar to the RS code. You might think, "Is it math again?", But it's okay because it's the same process flow and it's pretty easy.

BCH code

In this case as well, the functions I (x) and G (x) are defined, and the following problems are solved.

N = 15, K=5 \\
I(x) = 1x^4 + 0x^3 + 1x^2 + 1x + 1 \\
G(x) = x^{10} + x^8 + x^5 + x^4 + x^2 + x + 1 \\
In\\
P(x) = x^{N-K}I(x) \quad mod \quad G(X) \\
Ask for

Each coefficient of I (x) is an array of error correction level and mask number bits. Thankfully this time, all the coefficients are 0 or 1, so it's very easy to calculate.

If you write only the result, you will get 0000101001. This is connected after the existing 5bit and XORed with the specified mask 101010000010010 to complete.

\begin{array}{c}
\begin{align}
  & 101110000101001 \\
\oplus & 101010000010010 \\
\hline
& 000100000111011
\end{align}
\end{array}

The correct values are listed on page 76, Table C.1 of the standard, but they are in good agreement. Was good.

Place format information in a cell

Finally, write the 15 bits of the format information you just obtained to the still empty part.

You need to write the same thing in two different places.

Make a QR code image

Finally, make an image and you're done. It's easiest to create an image at the same size and enlarge it without interpolation. Don't forget to add at least 4 squares of quiet zone (white margin) around it.

Complete! !! It was a long way to go!

Operation check

By the way, can you read what you made?

** It's done **.

I tried it on an iPad, Android tablet, and Free software for Windows, but all of them read without problems. .. I didn't expect it to go so smoothly.

By the way, I forgot to mask the format information at first and output it as it is, but it still read it properly. Is the decoder side doing its best to do something about it?

Impressions

By experiencing the process of actually making a QR code, the article "Reading a QR code manually" that I once read and tilted my head is also "Ah, I was able to feel that I could do it somehow. "

I hope you read this article and think that QR codes are surprisingly easy to create.

The source code (language is Python) created this time has become a little long, so it is on an external site (Github). Please boil or bake. (I think it would be nice to put the QR code on a business card, like P) QR code generator that displays "Izumi Oishi"

Reference link

I'll put up a reference site and a link that I recommend reading in connection with this article.

QR code in general

Try to make a QR code : The site that I referred to most this time QR Code.com : Denso's site that developed the QR code. I can roughly understand the QR code QR code Deep Dive-data coding and error correction- : The page I found when I almost finished writing this article (lighthouse darkness). I should have searched for the article in Qiita before writing, but I don't understand why I missed it. Creating a QR Code step by step : (English) A great site that illustrates the process of creating a QR code step by step with detailed information.

RS code related

Galois field and extension field : Easy-to-understand article about Galois body 1 Galois Body Course : Easy-to-understand article about Galois body 2 [Wikipedia-Reed-Solomon Code](https://ja.wikipedia.org/wiki/%E3%83%AA%E3%83%BC%E3%83%89%E3%83%BB%E3%82% BD% E3% 83% AD% E3% 83% A2% E3% 83% B3% E7% AC% A6% E5% 8F% B7 #% E7% AC% A6% E5% 8F% B7% E5% 8C% 96 ) : The formula used in the explanation example is the same as the one used in the QR code, so it is very helpful. Reed–Solomon codes for coders : Although it is in English, it is explained in general, so if you can read it, please do

Other

CRC-32 : This is an explanation slide about CRC-32. CRC, which is often used to check data corruption, is also a technology that uses Galois fields. If you read it together, you will deepen your understanding, maybe. What is Oishi Izumi (Delicious Izumi) [Pixiv Encyclopedia] : For those who are Izumi Oishi