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.
P
a
g
e
d
O
u
t
!
Padding
Error correcting code
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.