Technology

History

Barcode Types

Barcode Printer

Inventory Management

Application

Software

Label Paper

Barcode Scanner

AI Barcode QRCode

Barcodes B

Barcodes C

Barcodes D

Barcodes E

Barcodes F

Robot Tech

Electronic

New Tech A

New Tech B

Psychology at Work

QR codes use error correction to ensure that the data encoded can be accurately read even if the code is partially damaged or obscured.

The error correction is based on the Reed-Solomon code, which is widely used in digital communications and storage systems for error detection and correction.

Reed-Solomon Code

Reed-Solomon codes are a group of error-correcting codes that can detect and correct multiple symbol errors. A symbol in the context of Reed-Solomon codes is a group of bits. For QR codes, these symbols are elements of the finite field F256\mathbb{F}_{256}F256, meaning each symbol is an 8-bit byte.

QR Code Error Correction Process

1.Encoding Data: The original data to be encoded is divided into blocks. Each block is then processed separately for error correction.

2.Generating Polynomials: For each block, a generator polynomial is used to create error correction codes. The degree nnn of the polynomial determines the number of error correction bytes. In this example, the degree is 7, meaning there are 7 error correction bytes.

3.Appending Error Correction Bytes: These error correction bytes are appended to the original data bytes to form the final codeword (block).

4.Data and Error Correction Byte Relationship:

The number of data bytes and error correction bytes within each block varies based on the version of the QR code (which affects the side length) and the error correction level chosen.

Higher error correction levels result in more error correction bytes, reducing the number of data bytes that can be stored.

QR Code Error Correction Levels

QR codes support four levels of error correction, each providing a different balance between storage capacity and robustness to damage:

1.Level L (Low): 7% of data bytes can be restored.

2.Level M (Medium): 15% of data bytes can be restored.

3.Level Q (Quartile): 25% of data bytes can be restored.

4.Level H (High): 30% of data bytes can be restored.

Codewords and Blocks in QR Codes

In the context of QR codes:

Codeword: Refers to the elements of F256\mathbb{F}_{256}F256 (the symbols in Reed-Solomon terminology).

Block: Refers to what is traditionally called a codeword in Reed-Solomon terminology, which includes both data and error correction bytes.

Example

To illustrate, let's consider a simple QR code encoding example:

Assume a QR code version that allows for 50 data bytes.

Using Level H error correction (30% recovery capability), approximately 15 bytes (30% of 50) will be used for error correction, leaving 35 bytes for actual data.

For a Reed-Solomon code with a polynomial of degree 7, the steps are:

1.Data Division: Data is split into 35-byte blocks.

2.Generate Error Correction: For each 35-byte block, 7 error correction bytes are generated.

3.Form Codeword: Each block then has 42 bytes (35 data + 7 error correction).

Practical Impact

The choice of error correction level impacts the QR code's capacity and robustness:

Higher Error Correction (Level H): Less data capacity, higher resilience.

Lower Error Correction (Level L): More data capacity, lower resilience.

This system ensures that even if parts of the QR code are damaged or obscured, the encoded data can still be reliably reconstructed, maintaining the QR code's effectiveness in real-world applications.