Error correction

QR codes use Reed–Solomon error correction[1] over the finite field[2] , the elements of which are encoded as bytes of 8 bits[3]; the byte with a standard numerical value encodes the field element where is taken to be a primitive element satisfying . The Reed–Solomon code uses one of 37 different polynomials over , with degrees ranging from 7 to 68, depending on how many error correction bytes the code adds. It is implied by the form of Reed–Solomon used (systematic BCH view)[4] that these polynomials are all on the form , however the rules for selecting the degree are specific to the QR standard.

When discussing the Reed–Solomon code phase there is some risk for confusion, in that the QR ISO/IEC standard uses the term codeword for the elements of , which with respect to the Reed–Solomon code are symbols, whereas it uses the term block for what with respect to the Reed–Solomon code are the codewords. The number of data versus error correction bytes within each block depends on (i) the version (side length) of the QR symbol and (ii) the error correction level, of which there are four. The higher the error correction level, the less storage capacity. The following table lists the approximate error correction capability at each of the four levels:

Level L (Low) 7% of data bytes can be restored.
Level M (Medium) 15% of data bytes can be restored.
Level Q (Quartile)[5] 25% of data bytes can be restored.
Level H (High) 30% of data bytes can be restored.

damaged qr code
Figure 1 - Damaged but still decodable QR code

In larger QR symbols, the message is broken up into several Reed–Solomon code blocks. The block size is chosen so that no attempt is made at correcting more than 15 errors per block; this limits the complexity of the decoding algorithm. The code blocks are then interleaved together, making it less likely that localized damage to a QR symbol will overwhelm the capacity of any single block.

Due to error correction, it is possible to create artistic QR codes with embellishments to make them more readable or attractive to the human eye, and to incorporate colors, logos, and other features into the QR code block; the embellishments are treated as errors, but the codes still scan correctly.[6][7]

It is also possible to design artistic QR codes without reducing the error correction capacity by manipulating the underlying mathematical constructs.[8][9] Image processing algorithms are also used to reduce errors in QR-code.[10]

artistic embellishment
Figure 2 - Example of a QR code with artistic embellishment that will still scan correctly thanks to error correction

Sources:

[1] https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction
[2] https://en.wikipedia.org/wiki/Finite_field
[3] https://en.wikipedia.org/wiki/Octet_(computing)
[4] https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction#The_BCH_view:_The_codeword_as_a_sequence_of_coefficients
[5] https://archive.ph/20120915040144/http://www.tec-it.com/de/support/knowbase/symbologies/qrcode/Default.aspx
[6] https://washingtonindependent.com/w/functionality-and-form-of-qr-codes/
[7] https://archive.ph/20120710063050/http://mashable.com/2011/04/18/qr-code-design-tips/
[8] https://web.archive.org/web/20150321031237/http://research.swtch.com/qart
[9] https://research.swtch.com/qr/draw/
[10] https://www.researchgate.net/publication/323676167_Extending_the_Storage_Capacity_And_Noise_Reduction_of_a_Faster_QR-Code

Source: Wikipedia.com

More information