Algoritme-architectuur

Zo werkt foutcorrectie in QR-codes: de wiskunde van Reed-Solomon uitgelegd

Heb je je ooit afgevraagd hoe een QR-code nog foutloos scant als hij gescheurd is, een koffievlek heeft, deels besmeurd is of in het midden bedekt is door een bedrijfslogo? Het geheim zit in de polynomiale foutcorrectie van Reed-Solomon.

Vier QR-codes van hetzelfde adres op foutcorrectieniveaus L, M, Q en H, elk met 7, 15, 25 of 30 procent van het oppervlak zwartgemaakt om te tonen hoeveel schade het niveau kan opvangen

1. Wat is Reed-Solomon-foutcorrectie?

Reed-Solomon-foutcorrectie (RS), in 1960 bedacht door de wiskundigen Irving S. Reed en Gustave Solomon, is een niet-binair, cyclisch foutcorrigerend algoritme dat veel wordt gebruikt in ruimtetelecommunicatie (NASA Voyager), optische schijven (cd/dvd), satelliettelevisie en de ISO/IEC 18004-standaard voor QR-codes.

In plaats van fouten alleen te detecteren (zoals een eenvoudige pariteitsbit of CRC-controlesom), maakt Reed-Solomon-code redundante wiskundige pariteitsblokken die precies kunnen aanwijzen waar beschadigde bytemodules zitten en de oorspronkelijke gegevens kunnen reconstrueren, zonder de overdracht opnieuw op te vragen.

2. De 4 foutcorrectieniveaus van QR-codes

De ISO/IEC 18004-standaard definieert vier selecteerbare foutcorrectieniveaus (ECC, Error Correction Code). Elk niveau staat voor het percentage van alle codewoorden dat vernietigd of bedekt kan zijn voordat de code onleesbaar wordt:

ECC-niveau Herstelcapaciteit Moduledichtheid Aanbevolen toepassing
Niveau L (laag) ~7% van de gegevens Minst dicht (minste vierkantjes) Digitale schermen, veel gegevens waarbij de QR-code klein moet blijven.
Niveau M (gemiddeld) ~15% van de gegevens Evenwichtige standaard Standaard voor gewone URL's, verpakkingen, flyers en marketingdrukwerk.
Niveau Q (kwartiel) ~25% van de gegevens Matig dicht Het beste voor eigen logo's, tafelstandaards en plekken met veel slijtage.
Niveau H (hoog) ~30% van de gegevens Hoogste dichtheid (meeste vierkantjes) Reclameborden buiten, industriële labels, omgevingen met zware fysieke belasting.

3. Hoe een ingevoegd logo gebruikmaakt van foutcorrectie

Als je een logo of icoon in het midden van een QR-code plaatst, ziet de optische sensor van de scanner het logo als fysieke beschadiging of ontbrekende modules.

Omdat foutcorrectieniveau Q tot 25% van de beschadigde gegevens kan herstellen en niveau H tot 30%, berekent de wiskundige Reed-Solomon-decoder de ontbrekende modules onder het logo en reconstrueert hij de oorspronkelijke URL in milliseconden.

De gouden regels voor QR-codes met logo:

  • Maximaal oppervlak: laat een logo nooit meer dan 20% tot 25% van het totale oppervlak van de QR-code innemen.
  • Bescherm de 3 hoekmarkeringen: laat je logo nooit de drie grote vierkante ogen linksboven, rechtsboven en linksonder bedekken of raken.
  • Gebruik witte marges: zet altijd een effen witte beschermrand rond je logo, zodat de omliggende QR-modules niet in de afbeelding van het logo overlopen.
  • Automatisch naar niveau Q of H: qr-code.love verhoogt je foutcorrectieniveau automatisch naar niveau Q of H zodra je een eigen logo uploadt.

4. De wiskundige stappen in het Galoisveld GF(256)

De encoder die in je browser draait, rekent in een eindig veld met 256 elementen, geschreven als GF(28) of GF(256). Elke byte is een element van het veld, en vermenigvuldigen is gedefinieerd modulo deze primitieve veelterm:

P(x) = x8 + x4 + x3 + x2 + 1   (0x11D hexadecimaal)

De databytes worden behandeld als de coëfficiënten van een veelterm D(x). De engine vermenigvuldigt die met xE, waarbij E het aantal foutcorrectiecodewoorden is dat het niveau vraagt, en deelt het resultaat door een vaste generatorveelterm G(x) voor dat niveau. De rest van die deling is de pariteit: E bytes die na de gegevens in het symbool worden geplaatst.

5. De 8 ISO-maskerpatronen & de strafpunten

Zijn de foutcorrectiecodewoorden berekend, dan kan het plaatsen van ruwe binaire bytes in een raster per ongeluk grote vlakken met alleen zwarte of alleen witte modules opleveren, of valse "hoekmarkeringen" die optische camerasensoren in de war brengen.

Om dat op te lossen past de ISO/IEC 18004-standaard 8 kandidaat-maskerpatronen (wiskundige XOR) toe op het raster. De engine beoordeelt elke gemaskeerde kandidaat met een strikte strafpuntenformule:

  • Straf 1 (reeksen aangrenzende modules): een aaneengesloten reeks van 5 of meer modules in dezelfde kleur levert 3 punten op, plus 1 voor elke module boven de vijf.
  • Straf 2 (blokken van 2x2 modules): elk effen vierkant van 2x2 levert 3 strafpunten op.
  • Straf 3 (valse hoekmarkeringen): elke modulereeks die overeenkomt met 1:1:3:1:1 levert 40 strafpunten op.
  • Straf 4 (onevenwicht donker/licht): afwijking van een 50/50-verhouding levert evenredig strafpunten op.

Het maskerpatroon met de laagste totale strafscore wordt gekozen en vastgelegd in de formaatinformatiebits rond de hoekmarkeringen.

6. Bestand tegen slijtage in de praktijk

Het juiste foutcorrectieniveau kiezen is cruciaal voor fysieke materialen die blootstaan aan weer en slijtage:

Omgeving Aanbevolen ECC Typisch risico op schade
Reclameborden buiten & metalen borden Niveau H (30%) Verbleking door uv, regenstrepen, roest en vogelpoep.
Tafelstandaards & menukaarten in restaurants Niveau Q (25%) Gemorst eten, duimvegen en desinfectiemiddel op alcoholbasis.
Productverpakkingen & etiketten Niveau M (15%) Lichte wrijving en schaafplekken door hantering.
Digitale schermen & tv-uitzendingen Niveau L (7%) Geen fysieke slijtage; zo min mogelijk pixels heeft voorrang.

7. Data- en foutcorrectiecodewoorden per versie

Elke versie heeft een vast aantal codewoorden van elk acht bits, en het niveau bepaalt hoeveel daarvan je gegevens dragen en hoeveel herstelgegevens. De eerste drie versies zien er zo uit.

VersieTotaalL (data + EC)MQH
12619 + 716 + 1013 + 139 + 17
24434 + 1028 + 1622 + 2216 + 28
37055 + 1544 + 2634 + 3626 + 44

Niet alle datacodewoorden zijn inhoud. De eerste bits bevatten de modusindicator en het aantal tekens; in bytemodus nemen die twaalf bits in tot en met versie 9 en twintig vanaf versie 10. Daarom bevat een symbool van versie 1 op niveau L 17 bytes van jouw gegevens en niet 19.

Op niveau H zijn de herstelgegevens al vanaf versie 1 groter dan de inhoud. Dat is de afweging die de logo-optie maakt als hij het niveau verhoogt: minder ruimte in bytes, in ruil voor een symbool dat nog leesbaar is als er een deel overheen is getekend.

Bronnen & verder lezen

Maak QR-codes met foutcorrectie

Kies je Reed-Solomon-niveau (L, M, Q, H) en voeg je merklogo toe, zonder dat er iets op een server wordt vastgelegd.

Open de alles-in-één-generator