How do QR Codes work, exactly?

Have you ever wondered what exactly the single pixels of a QR code mean? How you could generate your own QR code by hand?

In this post, we will decode by hand the QR Code on the right, which links to https://jbirnick.github.io/ and was created with some online generator.

Overview

The pixels of a QR code can be grouped into the following 4 (or 5) categories:

• function patterns
• format information
• version information
• data codewords & error correction codewords, modulo mask
• (blank, modulo mask)

Of course, in the end, we are interested in the data codewords. The error correction codewords help to reconstruct the data codewords in case a few pixels are lost or erroneous. A mask is applied there to avoid e.g. big areas of white pixels (which are hard to scan) that might come from the data. The version information contains the size of the QR code. The format information contains the level of error correction and the ID of the used mask. And the function patterns are just there to help the camera find and scan the QR code.

Function Patterns

Each QR code has three corners with the same 7px times 7px finder pattern. Towards the inner side of the QR code, they have a white 1px wide separator. This helps the camera to locate the QR code (boundaries).

But QR codes can become quite large, as they come in 40 different sizes, called “versions”. Version 1 has a sidelength of 21px, version 40 has sidelength 177px, and inbetween it goes in steps of 4px. Our QR code has a sidelength of 25px, so it’s of version 2.

So there are additional patterns to help the camera read the pixels. Between the finder patterns are 1px wide alternating timing patterns. Furthermore, there are 5px times 5px alignment patterns distributed across the QR code. Their quantity and position depend on the version; in our case, there is only one.

Format Information

You can see that I marked 30 bits as format information. Actually, there are only 15 bits, which are printed twice as in the picture below, and the pixel above the lower 7th pixel is (always) black.

Of those 15 bits, in turn, only the first 5 are relevant; the latter 10 are just for error correction. These first 5 bits shall be XORed with 10101, and can then be decoded as follows.

The first 2 bits indicate the error correction level (see later) according to this table:

The last 3 bits indicate the mask which is applied to the data & error correction codewords. Let’s analyze it in our case. The raw first 5 bits are 11010, so after the obligatory XOR with 10101 we obtain 01111.

This means we have error correction level L and mask 111 (which you’ll see later).

Version Information

Our QR code doesn’t contain version information, because this is only included in version 7 and larger. It would just contain the version number (i.e. size) of the QR code (and, as the format information, some error correction bits). Similar to the format information, two copies are placed into the QR code: one above the bottom left finder pattern, and another to the left of the top right finder pattern.

Data & Error Correction Codewords

The rest of the space is (finally!) taken for codewords. But first, recall that we need to apply mask 111.

You can see it on the left. Applied to our QR code, except for function patterns and format info and version info, it yields the second picture on the right.

Now in which order should we read the bits? We go:

• in columns of width 2 from right to left in an up-down-up-down-… pattern
• within a column, always first right then left
• function patterns are skipped

There is one little exception: The timing pattern between the two finding patterns on the left is “completely skipped”. Please see the first picture below to grasp what I mean.

Now these bits are divided into codewords of 8 bits each. Since we have 359 bits (check!), we can put 44 codewords and need to leave 7 bits blank.

The allocation of the codewords and the numbering of the bits within them is shown below.

Our codewords are:

01: 0b01110001 = 0x71
02: 0b10100100 = 0xA4
03: 0b00011011 = 0x1B
04: 0b01101000 = 0x68
05: 0b01110100 = 0x74
06: 0b01110100 = 0x74
07: 0b01110000 = 0x70
08: 0b01110011 = 0x73
09: 0b00111010 = 0x3A
10: 0b00101111 = 0x2F
11: 0b00101111 = 0x2F
12: 0b01101010 = 0x6A
13: 0b01100010 = 0x62
14: 0b01101001 = 0x69
15: 0b01110010 = 0x72
16: 0b01101110 = 0x6E
17: 0b01101001 = 0x69
18: 0b01100011 = 0x63
19: 0b01101011 = 0x6B
20: 0b00101110 = 0x2E
21: 0b01100111 = 0x67
22: 0b01101001 = 0x69
23: 0b01110100 = 0x74
24: 0b01101000 = 0x68
25: 0b01110101 = 0x75
26: 0b01100010 = 0x62
27: 0b00101110 = 0x2E
28: 0b01101001 = 0x69
29: 0b01101111 = 0x6F
30: 0b00101111 = 0x2F
31: 0b00000000 = 0x00
32: 0b11101100 = 0xEC
33: 0b00010001 = 0x11
34: 0b11101100 = 0xEC
35: 0b00010101 = 0x15
36: 0b00100011 = 0x23
37: 0b01010010 = 0x52
38: 0b01110010 = 0x72
39: 0b00100111 = 0x27
40: 0b01100000 = 0x60
41: 0b10110010 = 0xB2
42: 0b00011001 = 0x19
43: 0b11100111 = 0xE7
44: 0b10100011 = 0xA3

You can see that I highlighted the codewords in two different colors. This is because we have error correction level L, which means that of our 44 codewords, (the first) 34 contain the data and 10 are for error correction.

Before we decode the data, let’s check how the error correction is constructed.

Error Correction

For error correction, each codeword is interpreted as an element of $$\F_2[t]/(t^8 + t^4 + t^3 + t^2 + 1) \cong: \F_{2^8} = \F_2(\alpha)$$ with $\alpha := \bar{t}$. Namely, the codeword $b_7 b_6 \cdots b_0$ is interpreted as $b_7 \alpha^7 + \dots + b_0$.

(For non-mathematicians: $\F_q$ is the finite field with $q$ elements.)

Now we form a polynomial $D \in \F_{2^8}[X]$ whose coefficients are the data codewords (interpreted as elements of $\F_{2^8}$). The first data codeword is the coefficient of $X^{33}$ and the 34th (i.e. last) data codeword is the constant coefficient.

Hence the whole data (and nothing more) is captured in the polynomial $D$.

Now we compute $D \cdot X^{10}$ modulo $g$ where $g \in \F_{2^8}[X]$ is the polynomial

of degree 10. This yields a polynomial $E \in \F_{2^8}[X]$ of degree 9. Similar to how we constructed the data polynomial $D$, this is in turn used to construct the error correction codewords. The coefficient of $X^9$ in $E$ will form the first error correction codeword (so codeword 35), and the constant coefficient of $E$ will form the last error correction codeword (codeword 44).

This can be considered a BCH variant of Reed-Solomon error correction. I might explain in a later series how to actually correct errors with this (and what this means).

But let’s check that in our QR code this is what actually happened. We have

$D = (\alpha^{6} + \alpha^{5} + \alpha^{4} + 1) X^{33} + (\alpha^{7} + \alpha^{5} + \alpha^{2}) X^{32} + (\alpha^{4} + \alpha^{3} + \alpha + 1) X^{31} + (\alpha^{6} + \alpha^{5} + \alpha^{3}) X^{30} + (\alpha^{6} + \alpha^{5} + \alpha^{4} + \alpha^{2}) X^{29} + (\alpha^{6} + \alpha^{5} + \alpha^{4} + \alpha^{2}) X^{28} + (\alpha^{6} + \alpha^{5} + \alpha^{4}) X^{27} + (\alpha^{6} + \alpha^{5} + \alpha^{4} + \alpha + 1) X^{26} + (\alpha^{5} + \alpha^{4} + \alpha^{3} + \alpha) X^{25} + (\alpha^{5} + \alpha^{3} + \alpha^{2} + \alpha + 1) X^{24} + (\alpha^{5} + \alpha^{3} + \alpha^{2} + \alpha + 1) X^{23} + (\alpha^{6} + \alpha^{5} + \alpha^{3} + \alpha) X^{22} + (\alpha^{6} + \alpha^{5} + \alpha) X^{21} + (\alpha^{6} + \alpha^{5} + \alpha^{3} + 1) X^{20} + (\alpha^{6} + \alpha^{5} + \alpha^{4} + \alpha) X^{19} + (\alpha^{6} + \alpha^{5} + \alpha^{3} + \alpha^{2} + \alpha) X^{18} + (\alpha^{6} + \alpha^{5} + \alpha^{3} + 1) X^{17} + (\alpha^{6} + \alpha^{5} + \alpha + 1) X^{16} + (\alpha^{6} + \alpha^{5} + \alpha^{3} + \alpha + 1) X^{15} + (\alpha^{5} + \alpha^{3} + \alpha^{2} + \alpha) X^{14} + (\alpha^{6} + \alpha^{5} + \alpha^{2} + \alpha + 1) X^{13} + (\alpha^{6} + \alpha^{5} + \alpha^{3} + 1) X^{12} + (\alpha^{6} + \alpha^{5} + \alpha^{4} + \alpha^{2}) X^{11} + (\alpha^{6} + \alpha^{5} + \alpha^{3}) X^{10} + (\alpha^{6} + \alpha^{5} + \alpha^{4} + \alpha^{2} + 1) X^{9} + (\alpha^{6} + \alpha^{5} + \alpha) X^{8} + (\alpha^{5} + \alpha^{3} + \alpha^{2} + \alpha) X^{7} + (\alpha^{6} + \alpha^{5} + \alpha^{3} + 1) X^{6} + (\alpha^{6} + \alpha^{5} + \alpha^{3} + \alpha^{2} + \alpha + 1) X^{5} + (\alpha^{5} + \alpha^{3} + \alpha^{2} + \alpha + 1) X^{4} + (\alpha^{7} + \alpha^{6} + \alpha^{5} + \alpha^{3} + \alpha^{2}) X^{2} + (\alpha^{4} + 1) X + \alpha^{7} + \alpha^{6} + \alpha^{5} + \alpha^{3} + \alpha^{2}$

and so $D \cdot X^{10}$ modulo $g$ gives:

$E = (\alpha^4 + \alpha^2 + 1) X^9 + (\alpha^5 + \alpha + 1) X^8 + (\alpha^6 + \alpha^4 + \alpha) X^7 + (\alpha^6 + \alpha^5 + \alpha^4 + \alpha) X^6 + (\alpha^5 + \alpha^2 + \alpha + 1) X^5 + (\alpha^6 + \alpha^5) X^4 + (\alpha^7 + \alpha^5 + \alpha^4 + \alpha) X^3 + (\alpha^4 + \alpha^3 + 1) X^2 + (\alpha^7 + \alpha^6 + \alpha^5 + \alpha^2 + \alpha + 1) X + \alpha^7 + \alpha^5 + \alpha + 1$

You can check that this actually agrees with the error correction codewordes above.

Data Decoding

Finally, let’s decode the data codewords.

The first 4 bits indicate the mode (Numeric, Alphanumeric, Byte, Kanji, …). We have 0111, which means ECI (Extended Channel Interpretation) mode. The next 8 bits (i.e. the last 4 bits of codeword 1 and the first 4 bits of codeword 2) contain the ECI Designator 0x1A, which means that UTF-8 encoding is used.

The 4 bits after this (i.e. the last 4 bits of codeword 2) contain the mode in which the data is encoded. In our case, 0100, this means we use byte mode. (This is kinda the default, we just read the bytes and nothing more. Other modes exist as shortcuts to often-used byte ranges.) Codeword 3 contains the character count, namely 27.

Codewords 4 to 30 then encode the string https://jbirnick.github.io/ in UTF-8. In this case, each character takes only one codeword.

Codeword 31 is 00000000, the terminator.

We still have three free codewords. They are filled up by alternately adding the pad codewords 11101100 and 00010001.