QR Code Demystified – Part 3

Now we’ll cover how the data is encoded. There are several steps involved. First, the encoding method is chosen, then the raw data is converted to binary based on the encoding method, then the error correction algorithm is applied, and then the data is placed in the symbol. Finally a mask is selected and applied.

For now I’ll cover the encoding methods, and conversion to binary, and save the rest for later.

Before I go any further, I want to point out that an understanding of dealing with the binary number system will be needed. Because it’s very easy to get an explanation of it, and many programmers are already familiar with it, I’m going to assume this understanding. If you need an explanation or refresher course, try Wikipedia or a Google search. Further, I’m going to refer to adding bits to your data. Think of this as a stream of bits that will later be placed in the correct order on the symbol. I’ll explain exactly how that’s done later, but for now, just imagine that you’re creating a chain of 1s and 0s. I might add spaces between some of the bits to make them more readable, but they’re not part of the binary data.

The encoding methods are Numeric, Alphanumeric, Binary, and Kanji. Numeric only supports the digits 0-9, but can store 3 of them in only 10 bits. Alphanumeric supports letters A-Z (upper-case only), digits 0-9, and the special characters $%*+-./: and space. It’s good for encoding URLs and simple text. It takes 11 bits to store 2 alphanumeric characters. Binary data is stored 8 bits per character, and supports the 256 characters in the extended ASCII table. Kanji takes 11 bits for a single character. I won’t go into detail on the Kanji, because I’m guessing that very few people reading this tutorial will need to encode Japanese. So if you do, you’ll have to settle for Romaji or find the details elsewhere.

In order to encode data with one of these methods, we first indicate which method we’re using, and how much data we’re storing. We indicate the method with four bits – Numeric is 0001, Alphanumeric is 0010, Binary is 0100, and Kanji is 1000. The encoding method determines how many bits we use to indicate the data length. Details are in Table 1 below. As an example, if we’re encoding 5 binary characters to a Version 1 symbol, the binary data we start with will be 0100 00000101. (0100 to indicate binary, and 00000101 is the 8-bit representation of 5, to indicate the data length.) It is also possible to use different methods, by appending a new method/size indicator after the previous data, followed by the new data. (In other words, Method1, Size1, Data1, Method2, Size2, Data2)

Table 1 – Bits used to indicate data length

Once we’ve indicated what we’re storing, now it’s time to actually add the data. Binary is the easiest – simply take the 8-bit representation of the character and add it to your data. For the numeric data, you take sets of three digits. For each set of three you encode them directly to their 10-bit binary representations, so you encode “123456” as one-hundred twenty-three followed by four-hundred fifty-six. (0001111011 0111001000) If at the end of your data you have 1 digit left, encode it to four bits, and if you have 2 digits left, encode it into seven bits. Alphanumeric data is a little trickier. You have to convert each character to its numerical value – see Table 2. Then you take pairs of characters, multiply the first numerical value by 45, and add the second numerical value. Then convert the pair to 11-bit binary. If you end up with one character left over at the end of your data, encode its value to 6-bits. For example, ABC would be (A=10*45=450) + (B=11) = 461 and C=12. 461 in 11-bit binary is 00111001101 and 12 in 6-bit is 001100, so 00111001101001100.

Table 2 – Character values in alphanumeric mode

After you’ve encoded all your data, if there’s any space left over, you need to add some padding. First, add 0000. Then, if the number of bits in your data isn’t divisible by 8, add 0s until it is. Then alternately add “11101100” and “00010001” until you’ve reached the limit for your version and error correction mode (Table 3). If you’ve reached your limit just from your actual data, none of this is necessary.

Table 3 – Maximum bits for data

The error correction is quite complicated, so we’ll cover that next time. For now, I’ll say that QR Codes use the Reed-Solomon error correction algorithm. You can read about it at Wikipedia. After that, I’ll cover the placement order of the modules and the masking system. If you haven’t already, you’ll definitely want to check out the previous parts of this tutorial – Part 1 and Part 2.