QR Code Demystified – Part 5

Now that we’ve got the data and error correction sorted out, we’re almost ready to place it in the symbol. As seen in Part 2, the data and error correction modules basically go everywhere that isn’t taken up by something else. The reason we’re not quite ready to place it is that we haven’t established the locations of the alignment patterns.

Table 9 indicates the placement of the alignment patterns for each symbol version. The numbers represent the X and Y positions of the center of the alignment patterns, where the top-left is point (0,0). To save space, I’ve listed each number only once, but they should form a grid. Alignment patterns that would overlap a finder pattern are ignored. For example, version 7 has alignment patterns centered on (22,6), (6,22), (22,22), (38,22), (22,38), and (38,38). Each version (except 1, which has no alignment patterns) has an alignment pattern in the bottom-right corner, with the center 6 modules away from the bottom and right edges. Versions 7 and up (those with more than one alignment pattern) have at least one positioned on each of the timing patterns, also being 6 modules away from the edge.

Table 9 – Alignment patterns

For the sake of the length of the post, we’ll cover version information next week. We can’t place the format information anyway, because we haven’t selected a mask yet. So for now, just remember that those things are there and don’t place any data/error correction modules where they go, but we’ll have to fill them in later.

Now we’re finally ready to start placing the data/error correction modules. First, we divide the entire symbol into columns 2 modules wide, ignoring the vertical timing pattern (column 6.) Then, starting in the bottom right corner, we traverse these columns going up, then down, then up, then down, etc. In each row of each 2-wide column, we place a bit (black for 1, white for 0) in the right side if available, then the left if available. Then we move up or down, depending on which way we’re going at the time, and do it again. Once we reach the top or bottom of the column, we shift left to the next column and reverse whether we’re going up or down. The image below illustrates the order of bits for a version 1 symbol, with blue lines to clearly indicate the separation of the columns.

Remember of course that a version 1 symbol doesn’t have version info or alignment patterns to worry about, though the orange area is reserved for format data. As you increase versions it gets more complicated. This should serve to explain the concept well enough though. It’s very important to remember to alternate up and down. See how 0-23 goes up, and 24-47 goes down, etc. Also remember that you always try the right side of the column first.

One of the last issues we have is masking. Masking toggles certain modules from black to white or vice versa, so as to prevent artifacts that confuse the reading software. In theory, each type of mask is to be applied to the symbol in turn, and the one with the fewest undesirable artifacts should be used. In practice, this can be rather processor intensive, and many generators simply select a mask at random or always use the same one. I’ll explain the rules in case you want to do it by the book.

Each mask has a particular rule. For each data/error correction module (not any of the other modules) check the X and Y locations against the rule to determine whether to invert that module. Table 10 describes these rules – perform the calculation shown, and if the result is 0, invert the module. Mod means modulus division, which is to divide the number on the left by the number on the right, and get the remainder. When using regular division (represented with the forward slash /) round the quotient down to the nearest whole number (integer division). The left column indicates the decimal value of the mask, and also the binary representation (we’ll need that in Part 6).

Table 10 – Masking rules

So we know what each mask does, now we just need to know how to choose one. Like I said before, some people choose at random or use a fixed choice, but the official way is more complicated. It uses a points system to determine which is the most ideal, readable version. You run a series of tests on the symbol with each mask applied. The results of these tests may add “points” to that mask. The mask with the fewest points at the end is the most readable, and should be used. For each test, there may be multiple instances of the artifact. Add the points together for every instance.

Here are the tests. If a symbol contains at least 5 modules in a straight line (horizontally or vertically) that are either all white or all black, add a number of points equal to the length minus 2 (so the minimum is 3 for a line of 5). Each time the symbol contains a 2×2 square of white or black, add 3 points. If a symbol contains the pattern black, white, black, black, black, white, black, either horizontally or vertically, add a whopping 40 points. Finally, determine the percentage of black and white modules. If the ratio is less even than 55% to 45%, add 10 points per additional percentage of variation. For example, 58% black to 42% white would be (58-55 = 3) * 10 = 30 points.

We’ve covered a lot in this post. Next time we’ll wrap up. We’ve still got to cover the format information, version information, and some miscellany. If you haven’t already, don’t forget to check out the previous parts of this lesson – Part 1, Part 2, Part 3, Part 4. Next week I’ll cover the last you need to know to generate QR Codes, and reveal the QR Code generator I made that inspired this lesson series.