QR-code foutcorrectie: hoeveel mag er kapot?
Een QR-code op een verweerde poster of met een logo in het midden scant vaak gewoon. Elke QR-code draagt foutcorrectie mee: extra bytes waarmee je telefoon kapotte stukken zelf terugrekent. Hoeveel er kapot mag, kies je bij het maken van de code.
Ik heb het nagemeten: ik maakte QR-codes voor https://wallieweb.nl op alle vier de foutcorrectieniveaus, beschadigde ze stap voor stap in Python en liet een decoder (zxing-cpp) kijken wanneer hij het opgaf. Onderweg haalde ik één code uit elkaar tot op de bytes.
Vier niveaus van QR-foutcorrectie
DENSO WAVE, het bedrijf dat de QR-code bedacht, noemt vier niveaus: L herstelt ongeveer 7 procent, M 15, Q 25 en H 30 procent. M wordt volgens DENSO het vaakst gekozen. Q of H is bedoeld voor een fabriek waar codes vuil worden, L voor een schone omgeving met veel data.
Meer foutcorrectie kost ruimte. Een QR-code bestaat in 40 versies, van 21 bij 21 modules (de zwarte en witte vakjes) tot 177 bij 177, met steeds 4 modules extra per zijde. In de grootste versie passen 2953 bytes op niveau L en nog maar 1273 op niveau H. Bij mijn korte URL zag je dat direct: op L, M en Q werd het versie 2 (25 bij 25 modules), op H versie 3 (29 bij 29).
Van tekst naar codewords
Een QR-code rekent in codewords van 8 bits. Versie 2 heeft er 44. Op niveau M zijn 28 daarvan data en 16 foutcorrectie. De databytes van mijn code zagen er zo uit:
41 46 87 47 47 07 33 a2 f2 f7 76 16 c6 c6 96 57 76 56 22 e6 e6 c0 00 ec 11 ec 11 ec
De eerste vier bits (0100) zeggen "nu volgen gewone bytes", de volgende acht (0001 0100, oftewel 20) geven de lengte, en dan komen de twintig tekens van de URL, een halve byte verschoven. Daarna is het bericht op, maar de 28 databytes moeten vol. Na een paar nulbits als afsluiter vult de norm de rest aan met de vaste opvulbytes ec en 11, om en om. Die zie je aan het eind staan.
Reed-Solomon: rekenen met kapotte bytes
De 16 foutcorrectiebytes zijn een Reed-Solomon-code, dezelfde familie die DENSO ook bij muziek-cd's noemt en die volgens hen oorspronkelijk tegen ruis bij satellieten en ruimtesondes is ontwikkeld. Op wallieweb kwam hij al eerder langs bij kabelinternet, waar elk blok van 188 bytes er 16 controlebytes bij krijgt.
Het idee: de databytes worden behandeld als coëfficiënten van een polynoom, en de extra bytes zijn zo gekozen dat het geheel deelbaar is door een vaste generatorpolynoom. Raakt er iets beschadigd, dan gaat die deling niet meer op. Uit de manier waarop het niet klopt, kan de decoder afleiden waar de fout zit en wat er had moeten staan.
DENSO zegt het zo: Reed-Solomon heeft twee foutcorrectiebytes nodig voor elke byte die hersteld moet worden. Met 16 bytes kun je dus 8 kapotte bytes repareren. Ik rekende het na met de Python-bibliotheek reedsolo, ingesteld op de rekenregels van QR (een eindig lichaam van 256 elementen). Zijn foutcorrectiebytes waren byte voor byte gelijk aan die in de QR-code. Daarna maakte ik willekeurige bytes kapot:
8 fouten: hersteld
9 fouten: Too many errors to correct
16 uitwissingen met bekende plek: hersteld
17 uitwissingen: Too many erasures to correct
Die factor twee is de prijs van niet weten waar de fout zit. Weet de decoder al welke bytes onbetrouwbaar zijn, dan kost elke herstelde byte maar één foutcorrectiebyte en lukt het met 16.
De grens precies gemeten
In de echte QR-code zocht ik uit welke modules bij welk codeword horen en keerde ik steeds meer willekeurige codewords om, 40 pogingen per stap:
| Niveau | Codewords (data + correctie) | Nog leesbaar tot | Eerste onleesbare |
|---|---|---|---|
| 2-L | 34 + 10 | 5 kapot | 6 kapot |
| 2-M | 28 + 16 | 8 kapot | 9 kapot |
| 2-Q | 22 + 22 | 11 kapot | 12 kapot |
| 3-H | 2 × (13 + 22) | zie hieronder |
Precies de helft van het aantal correctiebytes, elke keer. Rekenkundig is 5 van 44 ruim 11 procent, meer dan de 7 procent die DENSO voor L noemt. Ik rekende het voor alle 40 versies uit met de tabellen in de encoder: L komt uit op 9,7 tot 11,5 procent, M op 17,9 tot 19,2, Q op 23,1 tot 28,0 en H op 30,8 tot 33,2. De percentages van DENSO zijn dus afgeronde richtgetallen, geen exacte grens per code.
Blokken en vlechtwerk
Niveau H in versie 3 is in twee blokken van 35 codewords verdeeld, elk met een eigen Reed-Solomon-code die 11 fouten aankan. Bij 16 willekeurige kapotte codewords bleef die code 40 van de 40 keer leesbaar. Bij 17 werd het 39 van de 40, bij 19 nog 31. Zodra één blok 12 fouten heeft, is het voorbij.
Grote codes hebben veel blokken: versie 40 op H telt er 81. Om te voorkomen dat een kras één blok helemaal opeet, worden de blokken bij het plaatsen in elkaar gevlochten: eerst byte 1 van elk blok, dan byte 2 van elk blok, enzovoort. De bits gaan daarna in kolommen van twee modules breed, zigzaggend van rechts naar links, de code in. Een codeword is daardoor meestal een rechthoekje van 2 bij 4 modules.
Waarom 30 procent niet 30 procent van het oppervlak is
Dat rechthoekje verklaart iets wat me verraste. Ik maakte een wit vierkant in het midden van de code steeds groter, uitgelijnd op de modules:
| Niveau | Grootste wit vlak dat nog werkt | Codewords geraakt |
|---|---|---|
| 2-L en 2-M | 5×5 modules, 4,0% | 6 |
| 2-Q | 7×7 modules, 7,8% | 10 |
| 3-H | 11×11 modules, 14,4% | 21 |
Bij 3-H ging het mis bij 13×13 modules, 20,1 procent van het oppervlak. Een vlak raakt veel codewords maar half, en een half codeword is ook kapot. Daarnaast is een flink deel van de code helemaal geen data: van de 841 modules in versie 3 dragen er 560 codewords, bij versie 2 zijn het er 352 van de 625.
Een kras is nog lastiger. Een lijn van één module hoog over de hele breedte maakte L, M en Q onleesbaar. H overleefde een lijn van twee modules hoog, bij drie was het voorbij.
Wat niet kapot mag
Reed-Solomon beschermt alleen de codewords. De drie grote vierkanten in de hoeken, de finder patterns, vertellen de scanner waar de code ligt en hoe hij gedraaid is. Ik maakte er één wit, zelfs alleen het zwarte kerntje van 3 bij 3: ook op niveau H vond zxing-cpp niets meer.
Het niveau en het maskerpatroon staan in 15 bits formaatinformatie naast de finder patterns. Dat zijn 5 bits inhoud (32 combinaties) en 10 controlebits, en het geheel staat er twee keer in. Het masker is een van acht vaste patronen dat over de data wordt gelegd. De encoder kiest het patroon met de laagste strafscore: lange rijen van één kleur, grote egale blokken en reeksen die op een finder pattern lijken kosten punten. Eén kopie van de formaatinformatie volledig wit of zwart: leesbaar. Beide kopieën: niet.
Zelf proberen
Installeer de bibliotheken in een virtuele omgeving:
python3 -m venv qrenv
qrenv/bin/pip install segno zxing-cpp pillow
Dit script maakt de code op elk niveau en legt er een groeiend wit vlak overheen, als percentage van de code zonder witte rand:
import segno, zxingcpp
from PIL import Image, ImageDraw
url = "https://wallieweb.nl"
for lvl in "LMQH":
qr = segno.make(url, error=lvl, boost_error=False)
qr.save(f"qr-{lvl}.png", scale=10, border=4)
w = Image.open(f"qr-{lvl}.png").width
for pct in (4, 8, 12, 16, 20):
img = Image.open(f"qr-{lvl}.png").convert("L")
sym = w - 80 # zonder de witte rand van 4 modules
s = int(sym * (pct / 100) ** 0.5) # vierkant met pct% van de code
x = (w - s) // 2
ImageDraw.Draw(img).rectangle([x, x, x + s, x + s], fill=255)
ok = bool(zxingcpp.read_barcodes(img))
print(f"{qr.designator:5} wit vlak {pct:2}%: {'leesbaar' if ok else 'onleesbaar'}")
Mijn uitvoer, ingekort:
2-L wit vlak 4%: leesbaar
2-L wit vlak 8%: onleesbaar
2-Q wit vlak 8%: leesbaar
2-Q wit vlak 12%: onleesbaar
3-H wit vlak 16%: leesbaar
3-H wit vlak 20%: onleesbaar
boost_error=False is belangrijk: zonder die optie kiest segno zelf een hoger niveau als dat in dezelfde versie past.
Tot slot
Ik had verwacht dat niveau H een logo van bijna een derde van de code zou slikken. In mijn meting ging het tussen 16 en 20 procent van het oppervlak al mis, omdat de schade in codewords telt en niet in vierkante millimeters. Wie een logo in een QR-code zet, kiest dus H, houdt het logo klein en test met een paar telefoons voordat de code op een poster gaat.