Close

QR Code Demystified – Part 4

Tuesday, June 14th, 2011

QR Code Demystified Part 4

I had planned on holding off the error correction until later, but it really fits better right here. Before error correction is done, the data that we’ve generated must be broken down into “code words”, which are just 8-bit bytes.

All we have to do is take our “bit stream” from the last tutorial, and break it into 8-bit sections. Each one is represented by a number in the range 0 to 255.

The Reed-Solomon algorithm uses a Galois Field to calculate the data. Since we’re dealing with 8 bits per word, we need a Galois Field of length 256. This can be calculated manually, but using a simple array is much easier. Values of αx can be found in Table 4, and the reverse can be found in Table 5.

Table 4 – Exponents of α to Values

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 2 4 8 16 32 64 128 29 58 116 232 205 135 19 38
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
76 152 45 90 180 117 234 201 143 3 6 12 24 48 96 192
32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
157 39 78 156 37 74 148 53 106 212 181 119 238 193 159 35
48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
70 140 5 10 20 40 80 160 93 186 105 210 185 111 222 161
64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79
95 190 97 194 153 47 94 188 101 202 137 15 30 60 120 240
80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95
253 231 211 187 107 214 177 127 254 225 223 163 91 182 113 226
96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111
217 175 67 134 17 34 68 136 13 26 52 104 208 189 103 206
112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127
129 31 62 124 248 237 199 147 59 118 236 197 151 51 102 204
128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143
133 23 46 92 184 109 218 169 79 158 33 66 132 21 42 84
144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159
168 77 154 41 82 164 85 170 73 146 57 114 228 213 183 115
160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175
230 209 191 99 198 145 63 126 252 229 215 179 123 246 241 255
176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191
227 219 171 75 150 49 98 196 149 55 110 220 165 87 174 65
192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207
130 25 50 100 200 141 7 14 28 56 112 224 221 167 83 166
208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223
81 162 89 178 121 242 249 239 195 155 43 86 172 69 138 9
224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239
18 36 72 144 61 122 244 245 247 243 251 235 203 139 11 22
240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255
44 88 176 125 250 233 207 131 27 54 108 216 173 71 142 1

Table 5 – Values to Exponents of α

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 1 25 2 50 26 198 3 223 51 238 27 104 199 75
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
4 100 224 14 52 141 239 129 28 193 105 248 200 8 76 113
32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
5 138 101 47 225 36 15 33 53 147 142 218 240 18 130 69
48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
29 181 194 125 106 39 249 185 201 154 9 120 77 228 114 166
64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79
6 191 139 98 102 221 48 253 226 152 37 179 16 145 34 136
80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95
54 208 148 206 143 150 219 189 241 210 19 92 131 56 70 64
96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111
30 66 182 163 195 72 126 110 107 58 40 84 250 133 186 61
112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127
202 94 155 159 10 21 121 43 78 212 229 172 115 243 167 87
128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143
7 112 192 247 140 128 99 13 103 74 222 237 49 197 254 24
144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159
227 165 153 119 38 184 180 124 17 68 146 217 35 32 137 46
160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175
55 63 209 91 149 188 207 205 144 135 151 178 220 252 190 97
176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191
242 86 211 171 20 42 93 158 132 60 57 83 71 109 65 162
192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207
31 45 67 216 183 123 164 118 196 23 73 236 127 12 111 246
208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223
108 161 59 82 41 157 85 170 251 96 134 177 187 204 62 90
224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239
203 89 95 176 156 169 160 81 11 245 22 235 122 117 44 215
240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255
79 174 213 233 230 231 173 232 116 214 244 234 168 80 88 175

These values will be important as we run the calculations required to generate the error correction data. Next, let’s get into the actual process. First, we figure out how many error correction code words are in each block using Table 6. Then we cross-reference that on Table 7 to get our generator values. The comma-separated list we get as a result represents exponents of α. To see the breakdown of blocks, see Table 8 at the bottom of the page. The numbers shown are the total code word counts per block, and the number of blocks. For example, a Version 10 Error Correction L symbol has 2 blocks of 86 code words, and 2 of 87 code words. Table 6 indicates the number of those code words that are for error correction, and the remainder are for data.

Basically we start with an array of values – the values of the data codewords, followed by a number of 0 values equal to the number of error correction codewords. For example, for a Version 1 block with M Error Correction, there are 16 data words and 10 ECC words. So we start with an array of length 26, where the first 16 values are the data words, and the next 10 are set to 0.

Table 6 – Error Correction codewords per block

1 2 3 4 5 6 7 8 9 10
L 7 10 15 20 26 18 20 24 30 18
M 10 16 26 18 24 16 18 22 22 26
Q 13 22 18 26 18 24 18 22 20 24
H 17 28 22 16 22 28 26 26 24 28
11 12 13 14 15 16 17 18 19 20
L 20 24 26 30 22 24 28 30 28 28
M 30 22 22 24 24 28 28 26 26 26
Q 28 26 24 20 30 24 28 28 26 30
H 24 28 22 24 24 30 28 28 26 28
21 22 23 24 25 26 27 28 29 30
L 28 28 30 30 26 28 30 30 30 30
M 26 28 28 28 28 28 28 28 28 28
Q 28 30 30 30 30 28 30 30 30 30
H 30 24 30 30 30 30 30 30 30 30
31 32 33 34 35 36 37 38 39 40
L 30 30 30 30 30 30 30 30 30 30
M 28 28 28 28 28 28 28 28 28 28
Q 30 30 30 30 30 30 30 30 30 30
H 30 30 30 30 30 30 30 30 30 30

Table 7 – Generator Polynomials

ECC Codewords Generator exponents of α
7 87, 229, 146, 149, 238, 102, 21
10 251, 67, 46, 61, 118, 70, 64, 94, 32, 45
13 74, 152, 176, 100, 86, 100, 106, 104, 130, 218, 206, 140, 78
15 8, 183, 61, 91, 202, 37, 51, 58, 58, 237, 140, 124, 5, 99, 105
16 120, 104, 107, 109, 102, 161, 76, 3, 91, 191, 147, 169, 182, 194, 225, 120
17 43, 139, 206, 78, 43, 239, 123, 206, 214, 147, 24, 99, 150, 39, 243, 163, 136
18 215, 234, 158, 94, 184, 97, 118, 170, 79, 187, 152, 148, 252, 179, 5, 98, 96, 153
20 17, 60, 79, 50, 61, 163, 26, 187, 202, 180, 221, 225, 83, 239, 156, 164, 212, 212, 188, 190
22 210, 171, 247, 242, 93, 230, 14, 109, 221, 53, 200, 74, 8, 172, 98, 80, 219, 134, 160, 105, 165, 231
24 229, 121, 135, 48, 211, 117, 251, 126, 159, 180, 169, 152, 192, 226, 228, 218, 111, 0, 117, 232, 87, 96, 227, 21
26 173, 125, 158, 2, 103, 182, 118, 17, 145, 201, 111, 28, 165, 53, 161, 21, 245, 142, 13, 102, 48, 227, 153, 145, 218, 70
28 168, 223, 200, 104, 224, 234, 108, 180, 110, 190, 195, 147, 205, 27, 232, 201, 21, 43, 245, 87, 42, 195, 212, 119, 242, 37, 9, 123
30 41, 173, 145, 152, 216, 31, 179, 182, 50, 48, 110, 86, 239, 96, 222, 125, 42, 173, 226, 193, 224, 130, 156, 37, 251, 216, 238, 40, 192, 180

Now there’s a process we’ll undertake a number of times equal to the number of data codewords in this block. We remove the first element from the array, we’ll call it A, and find its corresponding α exponent on Table 5, which we’ll refer to as B. For the next C elements of the array, where C is the length of the generator, we add the generator numbers, in turn, to B. We’ll call this sum D. If D is greater than 255, divide it by 255 and use the remainder. Finally we find the value of αD on Table 4, and do a bitwise XOR against the current value of the given element of the array. Confused? Me too. Let’s look at an example.

Let’s say we have a Version 1 QR Code with H Error Correction. Looking at Table 6, we see that we’ll have 17 ECC Codewords. Looking at Table 7, we see that means our generator is [43, 139, 206, 78, 43, 239, 123, 206, 214, 147, 24, 99, 150, 39, 243, 163, 136]. Let’s pretend our data, which for a Version 1 with H Error Correction will be 9 words long, is [32, 65, 205, 69, 41, 220, 46, 128, 236]. So our staring array looks like this:

32 65 205 69 41 220 46 128 236 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

We remove the first element of the array, and if we look up the first value on Table 5, we see that 32 is the 5th exponent of α. Therefore, we add 5 to our ECC numbers and get:

48 144 211 83 48 244 128 211 219 152 29 104 155 44 248 168 141

Now we convert all these numbers from exponents of α to integer values, using Table 4. Then we use bitwise XOR on each set of values. The table below shows the original values (after we removed the first element,) then the integer values of the immediately preceding list (the generator numbers + 5,) and finally the result of the XOR mask.

65 205 69 41 220 46 128 236 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
70 168 178 187 70 250 133 178 86 73 48 13 114 238 27 252 21
7 101 247 146 154 212 5 94 86 73 48 13 114 238 27 252 21

So the third row in the above table is our new value array. We see on Table 5 that 7 converts to 198, so we remove the first element (7) from our new value array, and add 198 to each element in our original generator of [43, 139, 206, 78, 43, 239, 123, 206, 214, 147, 24, 99, 150, 39, 243, 163, 136]. Then we convert these to integer values again, and apply another XOR series. Once we’ve done this 9 times (for our 9 data code words) we’ll have a value array that’s 17 elements long – and these are our error correction code words. In this case, our final values are as follows:

42 159 74 221 244 169 239 150 138 70 237 85 224 96 74 219 61

EDIT: Thanks to Erik for pointing out the special case that if the first element is 0, the bitmask is all 0s. In other words, the operation is simply to remove the first element (0) and do nothing else.

Table 8 – Blocks and Codewords

1 2 3 4 5
L 26 44 70 100 134
M 26 44 70 50(x2) 67(x2)
Q 26 44 35(x2) 50(x2) 33(x2), 34(x2)
H 26 44 35(x2) 25(x4) 33(x2), 34(x2)
6 7 8 9 10
L 86(x2) 98(x2) 121(x2) 146(x2) 86(x2), 87(x2)
M 43(x4) 49(x4) 60(x2), 61(x2) 58(x3), 59(x2) 69(x4), 70
Q 43(x4) 32(x2), 33(x4) 40(x4), 41(x2) 36(x4), 37(x4) 43(x6), 44(x2)
H 43(x4) 39(x4), 40 40(x4), 41(x2) 36(x4), 37(x4) 43(x6), 44(x2)
11 12 13 14 15
L 101(x4) 116(x2), 117(x2) 133(x4) 145(x3), 146 109(x5), 110
M 80, 81(x4) 58(x6), 59(x2) 59(x8), 60 64(x4), 65(x5) 65(x5), 66(x5)
Q 50(x4), 51(x4) 46(x4), 47(x6) 44(x8), 45(x4) 36(x11), 37(x5) 54(x5), 55(x7)
H 36(x3), 37(x8) 42(x7), 43(x4) 33(x12), 34(x4) 36(x11), 37(x5) 36(x11), 37(x7)
16 17 18 19 20
L 122(x5), 123 135, 136(x5) 150(x5), 151 141(x3), 142(x4) 135(x3), 136(x5)
M 73(x7), 74(x3) 74(x10), 75 69(x9), 70(x4) 70(x3), 71(x11) 67(x3), 68(x13)
Q 43(x15), 44(x2) 50, 51(x15) 50(x17), 51 47(x17), 48(x4) 54(x15), 55(x5)
H 45(x3), 46(x13) 42(x2), 43(x17) 42(x2), 43(x19) 39(x9), 40(x16) 43(x15), 44(x10)
21 22 23 24 25
L 144(x4), 145(x4) 139(x2), 140(x7) 151(x4), 152(x5) 147(x6), 148(x4) 132(x8), 133(x4)
M 68(x17) 74(x17) 75(x4), 76(x14) 73(x6), 74(x14) 75(x8), 76(x13)
Q 50(x17), 51(x6) 54(x7), 55(x16) 54(x11), 55(x14) 54(x11), 55(x16) 54(x7), 55(x22)
H 46(x19), 47(x6) 37(x34) 45(x16), 46(x14) 46(x30), 47(x2) 45(x22), 46(x13)
26 27 28 29 30
L 142(x10), 143(x2) 152(x8), 153(x4) 147(x3), 148(x10) 146(x7), 147(x7) 145(x5), 146(x10)
M 74(x19), 75(x4) 73(x22), 74(x3) 73(x3), 74(x23) 73(x21), 74(x7) 75(x19), 76(x10)
Q 50(x28), 51(x6) 53(x8), 54(x26) 54(x4), 55(x31) 53, 54(x37) 54(x15), 55(x25)
H 46(x33), 47(x4) 45(x12), 46(x28) 45(x11), 46(x31) 45(x19), 46(x26) 45(x23), 46(x25)
31 32 33 34 35
L 145(x13), 146(x3) 145(x17) 145(x17), 146 145(x13), 146(x6) 151(x12), 152(x7)
M 74(x2), 75(x29) 74(x10), 75(x23) 74(x14), 75(x21) 74(x14), 75(x23) 75(x12), 76(x26)
Q 54(x42), 55 54(x10), 55(x35) 54(x29), 55(x19) 54(x44), 55(x7) 54(x39), 55(x14)
H 45(x23), 46(x28) 45(x19), 46(x35) 45(x11), 46(x46) 46(x59), 47 45(x22), 46(x41)
36 37 38 39 40
L 151(x6), 152(x14) 152(x17), 153(x4) 152(x4), 153(x18) 147(x20), 148(x4) 148(x19), 149(x6)
M 75(x6), 76(x34) 74(x29), 75(x14) 74(x13), 75(x32) 75(x40), 76(x7) 75(x18), 76(x31)
Q 54(x46), 55(x10) 54(x49), 55(x10) 54(x48), 55(x14) 54(x43), 55(x22) 54(x34), 55(x34)
H 45(x2), 46(x64) 45(x24), 46(x46) 45(x42), 46(x32) 45(x10), 46(x67) 45(x20), 46(x61)

EDIT: I forgot to explain something that’s very important. Each block consists of the data code words followed by the error correction code words. So for the example above, the one and only block for our 1H would be our data: [32, 65, 205, 69, 41, 220, 46, 128, 236], followed by our error correction: [42, 159, 74, 221, 244, 169, 239, 150, 138, 70, 237, 85, 224, 96, 74, 219, 61]. Since this symbol only has one block, we directly encode these 26 bytes into binary and place them according to the rules in the next section. However, for symbols with more blocks, we actually encode the first code word of each block in order, then the second, and so on. So the encoding for two blocks goes like block 1 code word 1, block 2 code word 1, block 1 code word 2, block 2 code word 2, etc. In many cases, not all the blocks have exactly the same number of code words. That’s okay, you’ll just have some that are one code word longer than some others. After some of them run out, just skip over them and continue the process with the others.

Error correction is by far the most complicated portion of a QR Code, and the easiest to mess up. If I haven’t explained something fully, please leave a comment and I’ll try to address it. Next week we’ll start placing data in the symbol, and applying masks. Be sure to read through the previous posts if you haven’t already – Part 1Part 2Part 3.

About Matcha Design

Matcha Design is a full-service creative B2B agency with decades of experience executing its client’s visions. The award-winning company specializes in web design, logo design, branding, marketing campaign, print, UX/UI, video production, commercial photography, advertising, and more. Matcha Design upholds the highest personal standards for excellence and can see things from a unique perspective due to its multicultural background.  The company consistently delivers custom, high-quality, innovative solutions to its clients using technical savvy and endless creativity. For more information, visit MatchaDesign.com.

Related Tags

You Might Also Like