Search code examples
qr-codereed-solomon

Reed Solomon error correction for QR-Code


As a QR-Code uses Reed-Solomon for error correction, am I right, that with certain levels of corruption, a QR-Code reader could theoretically return wrong results?

If yes, are there other levels of integrity checks (checksums etc.) that would prevent that?


Solution

  • You can do a web search for "QR Code ISO", to find a pdf version of the document. I found one here:

    https://www.swisseduc.ch/informatik/theoretische_informatik/qr_codes/docs/qr_standard.pdf

    There are multiple strengths of error correction in the standard, and to avoid mis-correction, in some cases, some of the "parity" bytes are only used for error detection, and not for error correction. This is shown in table 13 in the pdf file linked to above. The ones marked with a "b" are cases where some of the parity bytes are used only for error detection. For example, the very first entry in table 13 shows (26,19,2)b, which means 26 total bytes, 19 data bytes, and 2 byte correction, which means of the 26-19 = 7 parity bytes, 4 are used for correction (each corrected byte requires 2 parity bytes unless hardware can flag "erasures"), and 3 are used for detection only.

    If the error correction calculates an invalid location (one that is "outside" the range of valid locations), that will be flagged as a detected error. If the number of unique calculated locations is less than than the number of assumed errors used to calculate those locations (duplicate or non-existing root) that will be flagged as a detected error. For higher levels of error correction, the odds of all the calculated locations being valid for bad data is so small that none of the parity bytes are used for error detection only. These cases don't have the "b" in their table 13 entries.

    The choices made for the various levels of error correction result in a very small chance of a bad result, but it's always possible.

    are there other levels of integrity checks (checksums etc.) that would prevent that?

    A QR-Code reader could flags bytes where any of the bits were not clearly 0 or 1 (like a shade of grey on a black / white code) as potential "erasures", which would lower the odds of a bad result. I don't know if this is done.

    When generating a QR-Code, a mask is chosen to even out the ratio of light and dark areas in a code, and after correction, if there is evidence that the wrong mask was chosen, that could be flagged as a detected error, but I'm not sure if the "best" mask is always chosen when a code is printed, so I don't know if a check for "best" mask is used.