Skip to Content
CDaten & InformationBuchstaben & QR-Codes

Lernziele

  • Sie können mit der ASCII-Tabelle eine Nachricht binär in einem QR-Code speichern.
  • Sie wissen, welche drei Schritte anschliessend noch nötig wären, damit der QR-Code komplett und scanbar ist.
  • Sie kennen den Namen des Error-Correction-Codes, der bei QR-Codes angewandt wird.
  • Sie können den Einfluss des Error-Correction-Levels auf die Menge der Daten, die abgespeichert werden können, erklären. (Sie müssen die EC-Levels nicht auswendig können!)

Buchstaben binär speichern

Es wird Sie kaum überraschen, dass Texte in Computern letztlich eine Serie von Binärzahlen sind. Die Kodierung ist letztlich einfach eine Tabelle, die jeder Zahl einen Buchstaben zuordnet.

Heute verwenden wir dafür weiterhin die sogenannte ASCII-Tabelle, die in den 1960ern standardisiert wurde. Dieser Zeichensatz wurde für die Übertragung so klein wie möglich gehalten, nämlich 7 Bit oder 128 Zeichen.

svg alt tag

Beispiel:

  • A hat den ASCII-Code 65.
  • a hat den ASCII-Code 97.

ASCII deckt hauptsächlich die englische Sprache ab und hat somit Einschränkungen für andere Sprachen und Symbole (z.B. € — © ™ ∆ Ω 你好 Привіт 😊 🎉)

Als Reaktion auf die Beschränkungen von ASCII wurde Unicode entwickelt, um alle Schriftzeichen aller Sprachen darzustellen. Unicode kann über 1 Million Zeichen kodieren, von denen bisher über 143’000 definiert sind.

Zusatz: Binäre Kodierung von Unicode

Binär nutzt Unicode den Umstand, dass die ASCII-Tabelle nur 7 Bit benötigt, also dass ein “normales” ASCII-Byte mit 0 beginnen würde. Unicode sagt nun: Wir signalisieren mit 1 am Anfang des ersten Byte, wie viele Bytes wir nutzen, und mit 10 am Anfang der weiteren Bytes, dass sie teil des gleichen Symbols sind.

  • 1 Byte (für Zeichen von U+0000 bis U+007F):
    • Format: 0xxxxxxx
    • Beispiel: A (U+0041) -> 01000001
  • 2 Bytes (für Zeichen von U+0080 bis U+07FF):
    • Format: 110xxxxx 10xxxxxx
    • Beispiel: é (U+00E9) -> 11000011 10101001
  • 3 Bytes (für Zeichen von U+0800 bis U+FFFF):
    • Format: 1110xxxx 10xxxxxx 10xxxxxx
    • Beispiel: 你 (U+4F60) -> 11100100 10111101 10100000
  • 4 Bytes (für Zeichen von U+10000 bis U+10FFFF):
    • Format: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
    • Beispiel: 𐍈 (U+10348) -> 11110000 10010000 10001101 10001000

QR-Codes

Nun zeichnen Sie den Beginn Ihres eigenen QR-Codes. Wir haben im Video gesehen: Wir können binäre Bytes in einen QR-Code schreiben. Standardmässig werden Binärdaten von Lesern als ASCII-Charaktere interpretiert.

Bilder und Audio auf QR-Codes speichern? Und wieso verwenden wir nicht “alphanumerisch”?

Ja, Sie könnten theoretisch Binärdaten jedweder Art speichern – also auch Bilder, Audio oder ganze Programme. Das Problem: Woher soll der Leser wissen, um was für Daten es sich handelt? QR-Codes speichern sehr wenig Meta-Daten – das sind “Daten über Daten”, wie z. B. die Kodierung oder den Dateityp. Wir haben bloss auf den ersten vier Bits die Möglichkeit zu sagen, dass es sich um Binärdaten handelt. Aber darüber hinaus gibt es keine festgelegte Struktur.

Das bedeutet, dass der Empfänger entweder vorher wissen muss, was für eine Art von Datei sich im QR-Code befindet, oder man muss eine eigene Konvention festlegen, z. B. indem man am Anfang der Daten eine kleine Kennung speichert (etwa "PNG" für ein Bild oder "MP3" für eine Audiodatei). In der Praxis werden daher oft URLs verwendet, die auf eine Datei im Internet verweisen – so kann der Browser oder das Betriebssystem automatisch das richtige Programm zum Öffnen wählen.

Im Übrigen wählen wir Binärdaten, damit Sie die ASCII-Tabelle verwenden können, die überall in der Informatik vorkommt. Alphanumerische QR-Codes könnten Buchstaben, Zahlen und einige wenige Symbole kompakter speichern, aber dann müssten Sie eine spezielle Kodierung verwenden, die Ihnen anderweitig wenig bringt.

  1. Beginnen Sie, den QR-Code von unten rechts aufzufüllen. Am Anfang kommen 12 Bits Metadaten - also “Daten über Daten”.
  2. Die ersten vier Bits definieren welche von Daten im QR-Code stecken. Es gibt vier Optionen:
    • 0001 für numerische Daten
    • 0010 für alphanumerische Daten
    • 0100 für Binärdaten
    • 1000 für japanisches Kanji Wir wählen Binärdaten, damit wir die ASCII-Tabelle nutzen können.
  3. Wählen Sie eine Nachricht aus, die Sie auf Ihrem QR-Codes kodieren wollen. Als Beispiel nehmen ich hier den String: “www.informatikgarten.ch ”
  4. Zählen Sie die Anzahl Charaktere in der Nachricht. Da es sich um normale ASCII-Charakter handelt, ist jeder Charakter ein Byte lang. Im Beispiel also 2310, was 0001’01112 entspricht.
  5. Füllen Sie die Anzahl Charaketere als ein ganzes Byte ab, wie im Bild gezeigt. Hängen Sie also vorne an Ihre Binärzahl Nullen an, bis Sie acht Stellen haben.
  6. Ab diesem Punkt füllen Sie jeden Charakter als ein volles Byte auf den QR-Code ab.

04-qrcode-bytegrenzen.excalidraw.light.svg

Ein Turtle-Programm, das QR-Code-Bilder erstellt

Folgendes Turtle-Programm können Sie gebrauchen, um Ihren QR-Code zu überprüfen. Ändern Sie dazu die Inputwerte auf den Zeilen 500 bis 510 ab.

Loading...
Run


Drei finale Schritte


Mit dem Abfüllen der Daten ist Ihr QR-Code noch nicht fertig. Es fehlen noch drei Schritte:


    

  • Es werden aus Ihren Daten noch Fehlerbehebungsdaten berechnet und hinzugefügt - ähnlich der Prüfziffer beim Barcode, aber besser!
    • 

  • Dann werden viele Bits gemäss einer von acht möglichen Masken invertiert, um den QR-Code so gut scanbar zu machen wie möglich.
    • 

  • Welches Fehlerbehebungsniveau und welche Maske gewählt wurde, wird in den (bei uns orangen) Formatstrips gespeichert.
    • 



svg alt tag


Wir schauen uns die Fehlerbehebung noch genauer an.


Error Correction im QR-Code


QR-Codes sind erstaunlich robust – selbst wenn ein Teil des Codes beschädigt oder unleserlich ist, kann er oft noch korrekt gelesen werden. Die Fehlerkorrektur in QR-Codes basiert auf dem Reed-Solomon-Code, einer mathematischen Technik aus der Informationstheorie. Im Prinzip löst der Reed-Solomon-Code das gleiche Problem wie die Prüfziffer bei EAN-13-Barcodes: Wir speichern nicht nur die eigentlichen Daten, sondern auch zusätzliche Prüfwerte, die helfen, Fehler zu erkennen. Aber der Reed-Solomon-Code kann Fehler nicht nur erkennen, sondern sogar auch noch korrigieren!


Der Reed-Solomon-Code wird zum Beispiel verwendet um: bei CDs, DVDs und Bluerays Kratzer auszugleichen, oder um die gesendeten Daten der Voyager-Raumsonden abzusichern - die am weitesten von der Erde entfernten Objekte, die je von Menschen gebaut wurden.


04-qrcode-voyager.png


Wie viele Fehler erkannt und korrigiert werden können, hängt davon ab, wie viel Platz für die Fehlerkorrekturdaten eingeplant wird. QR-Codes haben deshalb verschiedene Fehlerkorrekturstufen, die mehr oder weniger Platz gebrauchen und entsprechend weniger oder mehr Daten speichern können:


    

  • Level L (Low) kann nur bis zu 7% der Daten wiederherstellen, dafür aber 34 Bytes speichern.
    • 

  • Level M (Medium) kann bis zu 15% der Daten wiederherstellen und 28 Bytes speichern.
    • 

  • Level Q (Quartile) kann bis zu 25% der Daten wiederherstellen und 22 Bytes speichern.
    • 

  • Level H (High) kann zwar bis zu 30% der Daten wiederherstellen, dafür aber nur 16 Bytes speichern.
    • 



(Als Kontext: Wir reden hier immer von unserem QR-Code der Version 2 mit 25x25 Feldern. Mit grösseren QR-Codes können Sie natürlich viel mehr speichern!)


Die mathematischen Grundlagen von Reed-Solomon würden den Rahmen dieses Fachs sprengen, da sie recht recht anspruchsvoll sind und auf Polynomdivision in endlichen Körpern basieren. Wichtig zu verstehen ist aber, dass diese Methode QR-Codes sehr widerstandsfähig macht. Selbst wenn ein Stück fehlt oder durch einen Fleck verdeckt ist, kann der Code oft noch vollständig rekonstruiert werden. Eine sehr wertvolle Eigenschaft für den praktischen Einsatz - den Firmen dafür nutzen, Ihre Logos mitten auf den QR-Code zu pflanzen.


“…und er scannt doch!”


svg alt tag
Last updated on 
Hexadezimale ZahlenFarben