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.
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 1, Part 2, Part 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.