Skip to content

QR Code Generation Algorithm

Jump to bottom
Binary-Eater edited this page Jan 2, 2018 · 2 revisions

Generation procedure

The process (and high-level algorithm) for generating a QR Code symbol is as follows:

  1. Choose the text (Unicode string) or binary data (byte string) to encode.
  2. Choose one of the 4 error correction levels (ECL). A higher ECC level will yield a barcode that tolerates more damaged parts while preserving the payload data, but will tend to increase the version number (i.e. more modules in width and height).
  3. Encode the text into a sequence of zero or more segments. A segment in byte mode can encode any data, but using alphanumeric or numeric mode is more compact if the text falls into these subsets.
  4. Based on the segments to be encoded and the ECL, choose a suitable QR Code version to contain the data, preferably the smallest one.
  5. Concatenate the segments (which have headers and payload) and add a terminator. The result is a sequence of bits.
  6. Add padding bits and bytes to fill the remaining data space (based on the version and ECL).
  7. Reinterpret the bitstream as a sequence of bytes, then divide it into blocks. Compute and append error correction bytes to each block. Interleave bytes from each block to form the final sequence of 8-bit codewords to be drawn.
  8. Initialize a blank square grid based on the version number.
  9. Draw the function patterns (finders, alignment, timing, version info, etc.) onto the appropriate modules. This is formatting overhead to support the QR Code standard, and does not encode any user data.
  10. Draw the sequence of (data + error correction) codewords onto the QR Code symbol, starting from the bottom right. Two columns at a time are used, and the scanning process zigzags going upward and downward. Any module that was drawn for a function pattern is skipped over in this step.
  11. Either manually or automatically choose a mask pattern to apply to the data modules. If masking automatically, then all 8 possibilities are tested and the one with the lowest penalty score is accepted. Note that the format information is redrawn to reflect the mask chosen.
  12. We are now finished the algorithmic parts of QR Code generation. The remaining work is to render the newly generated barcode symbol as a picture on screen, or save it as an image file on disk.

Note that my QR Code generator library provides the logic to perform steps 3 through 11. The other steps must be performed by the user of the library.

Source: https://www.nayuki.io/page/qr-code-generator-library

Clone this wiki locally