Sunday, September 11, 2016

Business Card

When I just started freelancing, I wanted to design my own business card. It had to have QR code, of course. At first I tried one of these online QR code generators and got something like this:

That contains all the Information I want to share about myself. Unfortunately, this is a very dense QR code, and therefore it’s harder to scan properly with a smartphone, especially when printed on a card. It seemed like no matter how much Information I removed from it, it was still the dense kind of QR code. So I started reading about the structure of QR codes to understand what are the limits of the nice smartphone friendly type.
Apparently there are classes of QR codes called versions, where “Ver1” is the most friendly, but contains the least amount of data, while the one above is of version 7. Therefore, I was aiming for version 5 at most.
During my research (when I say research I mean reading the Wikipedia page for QR code), I came across this picture that explains the structure of QR codes:

Source: Wikipedia
After I saw that sample, I knew exactly how my Business card should look like. My skill is “Reverse Engineering”, I take things apart to understand how they work. The Picture reflected that very well. I wanted to deconstruct the QR into elements of data on the card. The idea I had in mind was something like:

The colors of a box reflect the data it encodes. Of course, this is just a sample I made by hand, in which the colors have very little to do with the data.

My plan was to:

  • Find a Python library for encoding QR codes
  • Find a way to encode the information in the version 5 QR code
  • Write a new feature for the library to add colors to the data

I started with the Python QR code library from:

But it seemed like it wasn’t optimized enough, this is what I got the first time I used it:

Which is a level 8 QR code, while for the same data I already got a level 7 QR code. At first I assumed it had to do with the amount of error correction used in the encoding, but investigating further, I found that both of them were set for M (Medium) error correction mode.
By investigating the code I found that I can get a better result by using the library a bit differently, but still it wasn't the most optimized encoding.
QR code has 4 different kinds of data encodings:

  • Numbers only (0-9), for which every 3 characters are encoded by 10 bits
  • Number + capital alphabet + “ $%*+-./:”, in which every 2 characters are encoded by 11 bits
  • 8 bit char for each every character takes 8 bits
  • Kanji for Chinese characters encoding

The problem is that moving from one mode to another cost about 15 bits. For example: to encode the string “a111a” you can use either:

  • 15 to set to mode 3
  • Encode “a”
  • 15 bits to move to mode 1
  • Encode “111” with 10 bits
  • Move back to mode 3 = 15 more bits
  • Encode “a”

In total: 15 + 8 + 15 + 10 + 15 + 8 = 63 bits
Another option is to:

  • Move to mode 3 for 15
  • Encode everything “a111a” with 8 * 5 bits

In total: 15 + 40 = 55bits
Therefore, it’s hard to know when it’s really worth changing encoding mode.
To solve the problem with 100% certainty of the best encoding, I used a flow graph. In that graph I made a node for “start” and edge to each encoding mode that can encode the next character. For the data In the example above the graph would look something like:

Once I created the graph, searching the shortest path from “start” to “end” using “Dijkstra” gave me the very best encoding for my data.

This work brought me back the level 7 QR code, which is still not the level I was aiming. Meanwhile, I found out that UPPER CASE letters are encoded much better than lower case. So by playing with the data a little I got:

This is a level 6 QR code, just one more level to go ;)
The last encoding improvement I got by reducing error correction from M to L (Low). Here it is:

This is a level 5 QR code, big success!

All that I was left to do is take care of the colors. To adjust the colors I simply attached an RGB value to every data piece that I added, and percolated it throw the different functions. For the error correction I used two different modes, one uses a different color (see example below) and one that reflects the data colors in a vague way. Here is the result:

FN:Assaf Nativ
  • Probs
  • Timing pattern
  • Error Correction

One more fun twist: Squares -> Circles:

Cheer, Assaf

P.S. The definition of the QR Code standard is ISO/IEC 18004:2015, which cost about 300 USD. If you liked this post, any help in getting the PDF would be very appreciated.