Maths and Computing:

The Key Stages in Creating a QR Code

This is a step by step overview of the processes involved in creating a QR code containing a given series of characters.

For more information, select the title button for a given stage.

• An encoding mode is chosen to determine how the characters will be encoded.
• Binary data can contain 7-bit ASCII characters or unicode characters that are encoded as multibyte characters using the UTF-8 encoding.
• Numeric data takes the least space, followed by alphanumeric and then binary
• If the data can be encoded in more that one way, then the one that takes the least space is chosen

• An error level determines the number of bytes that can be corrupted, detected and correntec.
• The four error levels are high, quartile, medium and low.
• The high error level requires the most space followed by quartile, medium and then low.
• The error level is determined accoring to whether it is more important to be able to correct data or to keep the size of the QR code low.

• With the input data, the encoding and the error level, the number of data bytes can be calculated..
• The number of data bytes determines the minimum QR code version that can be used..
• The QR Code grid can then be set up with the number of module based on the verison
• The static elements of the QR code are the positioning patterns, the timing patterns and the spacing. These can be added to the grid.

• There are eight different mask patterns.
• Any of these mask patterns can be applied to the data to create a valid QR code.
• Certain mask patterns create a better result with fewer blocks of white and black data.
• The result when each pattern is applied is rated, and the mask with the lowest ranking is chosen and applied to the data.

• The format information consists of fifteen bits.
• Two bits are used for the error level and three for the mask pattern. The rest are error correction bits.
• A mask is applied to the bits and the resulting bits are added to the QR code.
• The information bits are placed near to the two left positioning pattern
• A copy of the fifteen bits is also added to the QR code.

Terminology

Components of a QR Code

A QR code consists of a number of static elements that help determine the orientation and size of a QR code when it is being scanned.

The rest of the QR code is used to store the data relating to the information that is encoded within it.

• This QR code structure is for a version 1 QR code.
• The information in the QR code relates to Hello World with Binary encoding, Low error level and mask pattern 0.

Data Position in the QR Code

A version 1 QR code allows for 208 bits of data. This data is entered into the data area of the QR code

• The first bit is placed in the bottom right of the QR code.
• The last bit is placed on the far right just above the bottom left positioning pattern.
• The data goes up and down in a two module width columns, as shown below.
• If the data sequence reaches a point where it cannot continue, it jumps to the bottom right of the unused data space.

Table showing how data is positioned within the QR code

Data bits

The encoded data is then made up of:

1. The mode indicator for the encoding (4 bits)
2. The character count indicator block (The number of bits used depends on the encoding and the QR version)
3. The encoded data blocks
4. Padding data to complete any unused bytes.
5. Error Codes

QR Code Encoding

Encoding describes the method by which the characters are converted into bits of data that can be store in the QR code

• There are four standard encoding modes used by QR codes: numeric, alphanumeric, binary and kanji.
• This tool demonstrates numeric, alphanumeric and binary encoding.
• All characters can be encoded using binary encoding although this may not be the most efficient selection.
• The selected encoding is stored as a 4-bit mode indicator at the beginning of the data.

Table of encoding types for a QR code

Numeric Encoding

Numeric encoding can be used if the data is made up entirely of the characters 0, 1, 2, 3, 4, 5, 6, 7, 8 or 9

To encode the numeric characters:

• The digits are placed into groups of three from left to right to create values between 0 and 999.
• The 3-digit values are coverted to 10-bit binary numbers.
• If there is one remaining digit, it is multiplied by 16 and converted to an 8-bit binary number
• If there are two remaining digits, 2-digit value is multiplied by 2. The result is converted to an 8-bit binary number

Alphanumeric Encoding

Alphanumeric encoding can be used if the data is made up entirely of the following:

• Numeric digits
• Upper case letters
• Space
• The characters $ % * + - , / .

To encode the alphanumeric characters:

• Look up the value of each alphanumeric character.
• The values are taken in pairs.
• The first value of each pair is multiplied by 45 and added to the second value to form a value between 1 and 2024.
• This value is then converted to an 11-bit binary number.
• If there is one remaining character, its value is multiplied by 4 and converted to an 8-bit binary number.

Binary Encoding

Binary encoding can be used for any character that has a unicode value and is stored using one of more bytes using UTF-8 encoding.

For values between 0 and 127, one byte of data is used and the character is encoded using it's ASCII value.

Multi-Byte Characters

For character with unicode values greater than 127, UTF-8 encoding is used and each character is encoded using two or more bytes of data.

The table below shows examples of such characters and the UTF-8 encoded byte values store in the QR code

Error Levels

QR codes may be corrupted through incorrect formatting, damage or issues with scanning. The error level determines the percentage of the data that can be corrupted and then corrected in the QR Code data.

• There are four error levels: High, Quartile, Medium and Low.
• The error level value is stored in the first two digits of the information string.
• High error levels are able to correct more data errors but require more data bytes to be used for error correction codes.
• Low error levels requires fewer data bytes to be used as error codes but correct fewer errors.

Error Levels for a Version 1 QR Code

The table below gives information relating to the maximum number of characters that can be encoded for a particular error level and the maximum percentage of the data that can be corrected for a Version 1 QR code.

Padding Blocks

The number of bytes allocated to the encoded data depends on the error level. If the space used to store the indicator modes and the encoded characters is less that the that available, extra padding blocks are added to to fill up the data.

• The first padding block is made up of four 0 bits and is always included to indicate the end of the data blocks..
• Additional padding blocks standardly use the byte values 0xEC and 0x11, alternating, until less than eight bits of data are left.
• Any final padding block with less that eight bits can take a value of 0

Example: "Version 1" encoded using binary mode

• A version 1 QR code has capacity for 26 bytes.
• The indicator data and extra 0 bits take up two bytes.
• Binary encoded "Version 1" takes up nine bytes (One byte per character).
• This leaves fifteen bytes for the error codes and the padding bytes

Error Codes

Reed-Solomon error correction codes are added to the data to allow for a level of error detection and correction,

• The error level determines the number of error correction codes that can be created.
• The current data is split into byte size values, and these are used to generate the error codes
• If the data is corrupted, an algorithm is run on all of the bytes to determinine where the errors occured and how to correct it
• The error level determines at what point there is too much corruption of the data for the damage to be repaired

Generating the Reed-Solomon Error Codes

Generating the Reed-Soloman error codes from the existing data requires the maths of Galois Fields and Polynomial Division.

• The data is split into k bytes
• If the capacity of the QR code is n bytes, then n-k bytes are used as error codes
• The data bytes are used as the coefficients of a polynomial or order k
• The polynomial is then multiplied by x^n-k and divided by a given generator polynomial using Galois Field multiplication over eight elements.
• The coefficients of the remainder are used as the error codes

The "Error Codes"/"Calculation" tab shows the full calculation for any data input when a QR code is generated.

Masking

A mask is applied to the data area of the QR Code to optimise the ability for a scanner to read it.

• There are eight different mask patterns.
• All eight masks produce valid QR codes that can be scanned in.
• QR code generation tools select the one with the lowest penalty as that is considered visibly the best.
• The best masks optimise the distribution of black and white modules.

Mask Patterns

The list of mask patterns show the conditional statement and the result of applying it to a 24 by 24 area of white modules

Rating Masks

To determine which is the best mask to use for a QR code, each mask is applied and then rated using a penalty point system.

• The mask with the lowest penalty points is chosen by default.
• Any mask value can be chosen although it may not be visibly the best.

Penalty Points

Penalty points are determined using the following factors

Calculation 1: Horizontal and vertical runs of five or more modules of the same colour

Each run of five or more modules of the same colour has a penalty of 3 points plus 1 for each additional pixel

Calculation 2: Block of the same colour greater than two by two modules.

Each two by two block of the same colour has a penalty of 3 points.

Calculation 3: Hoizontal and vertical runs matching the value "10111010000".

Each run matching the following has a penalty of 40 points.

Calculation 4: The ratio of black to white modules

Penalty calculated from the percentage of black modules. Ten penality points for each multiple of 5% from 50%

Format Information

The format information is a 15-bit sequence containing the error level and mask pattern.

• The essential information is made up of five bits.
• The first two bits represent the error level.
• The next three bits represent the mask pattern.

Example: Low Error Level and Mask Pattern 0

Mapping for each Error Level and Mask Combination