Article published in PagedOut! issue #2.

Encoding of "PagedOut!" results in 16 bytes of data:

binary: mode|length |P |a |g |e |d |O |u |t |! |padding 0100 0000 1001 0101 0000 0110 0001 0110 0111 0110 0101 0110 0100 0100 1111 0111 0101 0111 0100 0010 0001 0000 1110 1100 0001 0001 1110 1100 0001 0001 1110 1100 hex: 0x40 0x95 0x6 0x16 0x76 0x56 0x44 0xf7 0x57 0x42 0x10 0xec 0x11 0xec 0x11 0xec dec: 64,149,6,22,118,86,68,247,87,66,16,236,17,236,17,236

The article contains a JavaScript snippet to compute the Reed-Solomon ECC. Here, we can see the same calculation being performed using middle school style long division. We use xor instead of substraction. It is feasible to perform these calculations using just pen and paper.

We are going to divide by [1,216,194,159,111,199,94,95,113,157,193] (the divisor can be computed or we can look up appendix A in the standard and use a log table).

note: the powers of x have been omitted — the notation 1, 2, 3, ... is actually 1*x^25 + 2*x^24 + 3*x^23...

--------------------------------------------------------------------------------------------------------- 1,216,194,159,111,199,94,95,113,157,193 | 64,149, 6, 22,118, 86, 68,247, 87, 66, 16,236, 17,236, 17,236, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ^ 64, 4,202, 20,194,151, 30, 94, 17,148, 10 <= if computing by hand, the multiplication of the divisor ------------------------------------------- is easiest to compute with log/antilog tables. 145,204, 2,180,193, 90,169, 70,214, 26,236 ^ 145,209,247,178, 72, 24,235,122, 16,141, 89 ------------------------------------------- 29,245, 6,137, 66, 66, 60,198,151,181, 17 ^ 29, 16, 15, 80, 47,102,120,101, 68,106, 40 ------------------------------------------- 229, 9,217,109, 36, 68,163,211,223, 57,236 ^ 229,145,203,239,244,157, 22,243, 29, 56,249 ------------------------------------------- 152, 18,130,208,217,181, 32,194, 1, 21, 17 ^ 152,135,107,161,120,169,127,231,206,140,222 ------------------------------------------- 149,233,113,161, 28, 95, 37,207,153,207,236 ^ 149,150,216,244,233, 35,142, 27,201,195,122 ------------------------------------------- 127,169, 85,245,124,171,212, 80, 12,150, 0 ^ 127,187, 57,109, 82,167,213,170, 49,147,184 ------------------------------------------- 18,108,152, 46, 12, 1,250, 61, 5,184, 0 ^ 18,172, 37, 38, 96,127, 53, 39,161, 2, 19 ------------------------------------------- 192,189, 8,108,126,207, 26,164,186, 19, 0 ^ 192, 12, 67, 60, 91,164, 34,226, 51,161, 30 ------------------------------------------- 177, 75, 80, 37,107, 56, 70,137,178, 30, 0 ^ 177,211,146,184, 41,221,228, 85,150,199, 92 ------------------------------------------- 152,194,157, 66,229,162,220, 36,217, 92, 0 ^ 152,135,107,161,120,169,127,231,206,140,222 ------------------------------------------- 69,246,227,157, 11,163,195, 23,208,222, 0 ^ 69,155, 39,205, 12,107, 37, 96,185, 71,232 ------------------------------------------- 109,196, 80, 7,200,230,119,105,153,232, 0 ^ 109, 23, 28, 75, 50,216,224,141,144,145,171 ------------------------------------------- 211, 76, 76,250, 62,151,228, 9,121,171, 0 ^ 211,120,164,133, 84, 28, 73,154,227, 62,204 ------------------------------------------- 52,232,127,106,139,173,147,154,149,204, 0 ^ 52, 68,246, 73,126, 18,227,215, 28, 33,170 ------------------------------------------- 172,137, 35,245,191,112, 77,137,237,170, 0 ^ 172,195,157,232, 6,187,156, 48,210,173,116 ------------------------------------------- 74,190, 29,185,203,209,185, 63, 7,116 <= our error correcting code

Note: these multiplications and divisions using xor are basic Galois Field operations. If you understand these, you can perform AES encryption or decryption by hand — AES requires similar operations in addition to swapping bytes around using predefined tables.

Similarly to above, we can use long division with xor to calculate the BCH correcting code.

data = 00101 divisor = 10100110111 mask = 101010000010010 ----------------- 10100110111 | 001010000000000 ^ 10100110111 ----------- 0000011011100 <= remainder data + remainder = 001010011011100 ^ 101010000010010 (xor with mask) --------------- 100000011001110 <= format info

See the "PagedOut!" QR code drawn step-by-step.

Choose the size and amount of error correcting code.

QR codes come in various sizes. The smallest is 21x21 cells and the largest is 177x177. For each size, the data can be encoded in different ways and with different levels of error correction.

Error correction helps read the data even if the QR code is slightly damaged.

The combination of size, encoding and error correction determines the total amount of data we can store.

A 21x21 QR code can store 14 bytes with an error correcting level M, which works for us.

Position patterns.

Three of the four corners of the QR code contain a position pattern. This is distinctive mark used by the decoder to locate QR codes. The pattern also provides orientation and scale information.

Timming pattern.

The three corners are connected with alternating colors. This provides alignment information to the decoder for each row and column.

Error correction level and mask.

The error correction level (00b) and the mask (101b) are encoded horizontally. Encoders should pick the mask which minimizes large clusters of identical color.

Error correction level and mask.

The same data is repeated in the other direction for redundancy purpose.

Mode

The actual data is layed out from bottom-right in a drunken-snake like pattern.

Data in the QR code can be encoded in several ways. We use binary (0100b). Other modes include numeric, alphanumeric and Kanji.

Length.

The next 8 cells are the actual data's length. In our case, we have
9 characters, which is 0000 1001b.

P

Binary mode is the simplest mode to encode. Each letter is simply
encoded using its ASCII value. P is encoded as 80 (0101 0000b).

a

In a similar way, a is 97 (0110 0001b).

g

g is 103 (0110 0111b).

e

e is 101 (0110 0101b).

d

d is 100 (0110 0100b).

O

O is 79 (0100 1111b).

u

u is 117 (0111 0101b).

t

t is 116 (0111 0100b).

!

! is 33 (0010 0001b).

Padding

At the end, we need to put some padding: 0000b followed by 0xec (1110 1100b) 0x11 (0001 0001b) 0xec 0x11 0xec.

Error correcting code

Finally, we lay the error correcting code we computed above.

That's it!

The final step is to apply the right mask. Each QR code is XORed with one of 8 different masks. The encoder tries each mask and computes a score which takes into account how many consecutive cells are the same color.

The mask with the most number of alternating cells is chosen as it leads to better scannability.

- The ISO/IEC 18004 standard is useful. Specifically, the tables in the appendix are useful for validation purpose.
- qrcode.js is a library written in JavaScript. Being browser-based makes it easy to set breakpoints, inspect, hack, etc. Keep in mind that this library seems no longer maintained — some bugs were reported many years ago and never fixed.
- An online long division calculator. The Log/Antilog table on the same site is useful as well as all the other information related to QR codes.
- Wikipedia page about Reed Solomon.
- Wikipedia page about QR code.
- Wikipedia page about Finite field artihmetic.
- QR Code Basics.
- Information capacity and versions tables.
- Finite field question on StackExchange.

- qrquine: a QR code based quine.
- The word "QR Code" is registered trademark of DENSO WAVE INCORPORATED (http://www.denso-wave.com/qrcode/)