Seit der weltweiten Verbreitung von Smartphones mit integrierter Bilderkennung sind die quadratischen Punktmuster aus dem Alltag nicht mehr wegzudenken. Doch welche mathematischen und optischen Prinzipien stecken hinter dem Quick Response Code?
Der anatomische Aufbau eines QR-Codes
Ein QR-Code besteht aus mehreren festgelegten Funktionsbereichen, die für Scanner unverzichtbar sind:
- Finder Patterns (Positionsmuster): Die drei markanten quadratischen Schachteln in den oberen Ecken und der linken unteren Ecke. Sie ermöglichen es dem Kamerasensor, die Ausrichtung und Drehung des Codes im Raum in 360 Grad sofort zu erkennen.
- Timing Patterns (Taktreihen): Eine abwechselnde Reihe von schwarzen und weißen Modulen, die die drei Suchmuster miteinander verbinden. Sie definieren das Gitter und die Koordinaten jedes einzelnen Moduls.
- Alignment Patterns (Ausrichtungsmuster): Kleinere Quadrate in größeren QR-Codes (ab Version 2), die Verzerrungen auf unebenen oder gewölbten Oberflächen (z.B. Flaschen oder Dosen) rechnerisch ausgleichen.
- Format- und Versionsinformationen: Codieren das verwendete Fehlerkorrekturlevel und die verwendete Maskenmatrix.
- Daten- und Fehlerkorrekturmodule: Der eigentliche Nutzinhalt, komprimiert in binären Datenströmen.
Die Reed-Solomon-Fehlerkorrektur
Das Geheimnis der Robustheit von QR-Codes liegt in der mathematischen Reed-Solomon-Codierung. Dabei werden den eigentlichen Nutzdaten redundante Prüfpolynome hinzugefügt.
Wird ein QR-Code beispielsweise auf Level H generiert, können bis zu 30% der Module mit einem schwarzen Marker übermalt, abgerissen oder mit einem Firmenlogo versehen werden, ohne dass die Lesbarkeit beeinträchtigt wird. Die Software berechnet die fehlenden Bits aus den erhaltenen Polynomen in Echtzeit wieder zurück.