The Error-Correcting Abilities of QR Codes
M.E.J. Koolen (TU Delft - Electrical Engineering, Mathematics and Computer Science)
J.H. Weber – Mentor (TU Delft - Electrical Engineering, Mathematics and Computer Science)
J.A.M. de Groot – Graduation committee member (TU Delft - Electrical Engineering, Mathematics and Computer Science)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
QR codes have become incredibly widespread in the last few years, appearing everywhere around us, but apart from being easy to use, they are also quite prone to damage. To protect the data in a QR code, several error-correcting codes are used. Specifically, BCH codes, Reed-Solomon codes, and Golay codes are used, in different sections of the QR code, together with other protection strategies, such as interleaving and duplication of codewords. In this thesis, the error-correcting codes behind three sections of QR code versions 2 and 5, and the four sections of QR code version 7 are investigated to find the error-correcting abilities of QR codes.
First, the general theory behind error-correcting codes is described, as well as the theory behind BCH codes, Reed-Solomon codes and Golay codes. Then, the specifics of the codes used in the different sections of the QR codes are described, before looking into the error-correcting abilities of each code. Through the characteristics of the error-correcting codes, the way they are used, and manually editing the QR code and scanning it, conditions are found for each section that need to be met by a QR code and its errors for it to be readable. For the first section, in all QR codes, the Function Patterns, the Finder Patterns need to be visible, whereas the Timing and Alignment Patterns can be covered. For the second section, the data section, included in all QR codes, each data block corresponding to a Reed-Solomon codeword needs to have its number of errors and erasures comply to a certain formula. The third section, which is the Format Information, also in all QR codes, needs the Format Information string closest to the correct codeword to be closer to that correct codeword, than the other Format Information string is to an incorrect codeword, and at most at distance 3 from the correct codeword. Lastly, the fourth section, only for QR code versions 7 and up, needs to have at least one Version Information area at distance at most 3 to the correct Version Information. Once all these conditions are met, a QR code is guaranteed to be readable.