QR-Codes Schritt für Schritt erzeugen

 (nayuki.io)
5 Punkte von GN⁺ 2024-11-19 | 1 Kommentare | Auf WhatsApp teilen
  • Verfolgt den internen Prozess, bei dem Text in einen QR-Code umgewandelt wird, anhand einer Visualisierung der Schritte 0 bis 9 und zeigt, wie die Nayuki QR Code generator library funktioniert
  • Die Beispieleingabe Hello, world! 123 wird als 17 Unicode-Codepoints analysiert und im Byte-Modus codiert, da sie weder Numeric, Alphanumeric noch Kanji ist
  • Durch Aneinanderhängen von Modusbits, Zeichenanzahl, Segmentdaten und Terminator-Bits entstehen 19 Daten-Codewords, die in die Kapazität von Version 1 mit ECC L passen
  • Ein QR-Code der Version 1 hängt in einem Block an 19 Daten-Codewords 7 Reed–Solomon-ECC-Codewords an und platziert anschließend feste Muster und Datenmodule
  • Durch Vergleich der Penalties der 8 Masken wird das Mask pattern 3 mit der niedrigsten Gesamtpunktzahl ausgewählt; das Endergebnis entsteht also nicht nur durch einfache Codierung, sondern auch durch Qualitätsbewertung

Ziel der Demo und Verarbeitung der Eingabe

  • Diese Webanwendung visualisiert Schritt für Schritt, wie eine Textzeichenfolge als QR-Code codiert wird
  • Die Seite zeigt den Codierungsprozess detailliert, um die interne Funktionsweise der QR Code generator library nachvollziehbar zu machen
  • Die Benutzereingaben bestehen aus Textzeichenfolge, Fehlerkorrekturstufe, erzwungener Mindest-Version und erzwungenem Maskenmuster

Schritt 0: Analyse der Unicode-Zeichen

  • Die Beispielzeichenfolge lautet Hello, world! 123; die Anzahl der Codepoints im Eingabetext beträgt 17
  • Für jedes Zeichen wird geprüft, ob es in den Modi Numeric, Alphanumeric, Byte oder Kanji codiert werden kann
  • Die Codierbarkeit der gesamten Zeichenfolge nach Modus ist wie folgt
    • Numeric: nicht möglich
    • Alphanumeric: nicht möglich
    • Byte: möglich
    • Kanji: nicht möglich
  • Der gewählte Segmentmodus, um alle Zeichen aufzunehmen, ist Byte

Schritt 1: Datensegment erzeugen

  • Jedes Zeichen wird in eine Bitfolge umgewandelt
  • In den Modi Numeric und Alphanumeric werden aufeinanderfolgende Zeichen gruppiert und codiert
  • Im Byte-Modus erzeugt ein Zeichen 8, 16, 24 oder 32 Bit
  • Im Beispiel wird der Hexadezimalwert jedes Zeichens in 8 Bit umgewandelt
    • H: 48 → 01001000
    • e: 65 → 01100101
    • 1: 31 → 00110001
    • 2: 32 → 00110010
    • 3: 33 → 00110011
  • Das Demoprogramm erzeugt zur Vereinfachung immer ein einzelnes Segment
  • Eine optimale Aufteilung zur Reduzierung der gesamten Bitlänge wird separat unter optimal text segmentation for QR codes behandelt

Schritt 2: Versionsnummer anpassen

  • Die gesamte Bitlänge, die zur Darstellung der Segmentliste benötigt wird, hängt vom Versionsbereich ab
    • Version 1–9: 148 Bit, 19 Codewords
    • Version 10–26: 156 Bit, 20 Codewords
    • Version 27–40: 156 Bit, 20 Codewords
  • Ein Codeword ist als 8 Bit, also 1 Byte, definiert
  • Die Kapazität eines QR-Codes für Daten-Codewords hängt von Version und Fehlerkorrekturstufe ab
  • Die Beispieleingabe passt bei der gewählten Fehlerkorrekturstufe in Version 1
  • Die endgültig gewählte Versionsnummer ist 1

Schritt 3: Segmente verbinden, Padding, Codewords erzeugen

  • Mehrere Bitstrings werden aneinandergehängt, um den Daten-Bitstrom zu bilden
    • Segment 0 mode: 0100, 4 Bit
    • Segment 0 count: 00010001, 8 Bit
    • Segment 0 data: 136 Bit
    • Terminator: 0000, 4 Bit
  • Die kumulierte Bitanzahl beträgt 152 Bit
  • In diesem Beispiel haben sowohl Bit-Padding als auch Byte-Padding 0 Bit
  • Die gesamten Daten-Codeword-Bytes werden in 8-Bit-Einheiten aufgeteilt und hexadezimal dargestellt
    • 41 14 86 56 C6 C6 F2 C2 07 76 F7 26 C6 42 12 03 13 23 30

Schritt 4: Blockaufteilung, ECC hinzufügen, Interleaving

  • Die Blockstatistik des Beispiels ist wie folgt
    • Anzahl der Daten-Codewords: 19
    • Anzahl der Blöcke: 1
    • Daten-Codewords pro kurzem Block: 19
    • Daten-Codewords pro langem Block: nicht zutreffend
    • ECC-Codewords pro Block: 7
    • Anzahl kurzer Blöcke: 1
    • Anzahl langer Blöcke: 0
  • Die Daten-Codeword-Sequenz wird in kurze und lange Blöcke aufgeteilt; am Ende jedes Blocks werden ECC-Codewords berechnet und angehängt
  • Der mathematische Ablauf der Berechnung der Reed–Solomon-Fehlerkorrekturcodes wird ausgelassen, weil er lang, mühsam und wenig interessant ist
  • Die endgültige Codeword-Sequenz besteht aus ineinander verschachtelten Daten- und ECC-Codewords
    • 41 14 86 56 C6 C6 F2 C2 07 76 F7 26 C6 42 12 03 13 23 30 85 A9 5E 07 0A 36 C9
  • Auch der endgültige Bitstrom, der im Zickzack-Scan gezeichnet wird, wird aus dieser Codeword-Sequenz erzeugt

Schritte 5–6: Feste Muster und Codeword-Platzierung

  • Im Schritt für feste Muster wird in Zeile 6 und Spalte 6 das timing pattern gezeichnet
  • In den drei Ecken wird jeweils ein 8×8 finder pattern einschließlich Separator platziert
  • Um die Finder herum werden vorläufige dummy format bits eingefügt
  • Im Schritt der Codeword-Platzierung wird ein Zickzack-Scan berechnet, der in der rechten unteren Ecke beginnt
  • Der Zickzack-Scan überspringt Funktionsmodule (function modules) und besucht Module, die noch nicht gefüllt sind
  • Daten-, ECC- und Remainder-Module werden entsprechend den endgültigen Codeword-Bitwerten und der Zickzack-Reihenfolge gezeichnet
  • Als Beispiel ist das hexadezimale Codeword C5 binär 11000101 und erzeugt die Modulsequenz [dark, dark, light, light, light, dark, light, dark]

Schritte 7–9: Maske anwenden und Penalty berechnen

  • Jedes Maskenmuster wirkt sich nur auf Nicht-Funktionsmodule (non-function modules) aus
  • Die Maske wird per XOR auf Daten-, ECC- und Remainder-Module angewendet
  • Die tatsächlichen format bits werden rund um die Finder gezeichnet
  • Die Penalty-Suche prüft folgende Elemente
    • horizontale Runs von 5 oder mehr Modulen derselben Farbe
    • vertikale Runs von 5 oder mehr Modulen derselben Farbe
    • 2×2-Boxen derselben Farbe
    • horizontale finder-like pattern
    • vertikale finder-like pattern
    • Gleichgewicht zwischen dunklen und hellen Modulen
  • Größe und Farbverhältnis des Beispiel-QR-Codes sind wie folgt
    • Seitenlänge: 21
    • Gesamtzahl der Module: 441
    • Helle Module: 221
    • Dunkle Module: 220
    • Anteil dunkler Module: 49,887 %
    • Abweichung von der Hälfte: −0,113 %
  • Die gesamten Penalties der 8 Masken sind wie folgt
    • Mask 0: 1204
    • Mask 1: 1134
    • Mask 2: 1084
    • Mask 3: 1081
    • Mask 4: 1121
    • Mask 5: 1100
    • Mask 6: 1189
    • Mask 7: 1137
  • Die Maske mit der niedrigsten Gesamt-Penalty ist Mask pattern 3

Quellcode

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-11-19
Hacker-News-Kommentare
  • Schade, dass Erklärungen zu QR-Codes online anscheinend überall die Reed-Solomon-Fehlerkorrekturberechnung auslassen
    Auch hier sagt der Autor, sie sei „lang, langweilig und nicht besonders interessant“, aber weil alle so denken, ist sie inzwischen ziemlich schwer zu finden
    • Ich habe im Graduiertenstudium eine Vorlesung über Codierungstheorie besucht; sie war die strengste meiner Kurse und für alle 5 Teilnehmenden schwierig, aber ich bin froh, sie gehört zu haben
      Reed-Solomon kam etwas nach der Mitte des Semesters dran, und der Kern ist, dass es auf Polynomen basiert. Wenn man genügend Punkte hat, ist das Polynom eindeutig bestimmt; fügt man also zusätzliche Punkte hinzu, kann man es rekonstruieren, selbst wenn einige verloren gehen
      Der Rest ist die Frage, wie man das auf Binärdaten anwendet, also der Teil mit endlichen Körpern. Mathematisch schön, aber ziemlich komplex
    • Die Fehlerkorrekturberechnung wird in diesen beiden Tutorials erklärt
      https://www.thonky.com/qr-code-tutorial/error-correction-cod...
      https://dev.to/maxart2501/let-s-develop-a-qr-code-generator-...
    • https://www.quaxio.com/an_artisanal_qr_code.html und PagedOut! Issue #2 enthalten eine Anleitung, wie man einen QR-Code von Grund auf erstellt, einschließlich der Fehlerkorrekturberechnung per langer Division
    • Lang und langweilig, aber tatsächlich der interessanteste Teil des Ganzen
    • Es gibt einen passenden Wikipedia-Artikel dazu
  • Das neuere Veritasium-Video I used to hate QR codes. But they're actually genius behandelt dieses Thema ebenfalls
    https://www.youtube.com/watch?v=w5ebcowAJD8
  • Die Sammlung des Feedbacks, das der Autor bekommen hat, ist ziemlich unterhaltsam: https://www.nayuki.io/page/poor-feedback-from-readers
    • Sich über Leute mit schlechtem Englisch lustig zu machen und Kommentare zu schreiben, die ein ganzes Land herabsetzen, als wären die E-Mail-Schreiber repräsentative Beispiele dieses Landes, sagt mehr über den Blogbetreiber aus als über die Absender
      In den Kommentaren ist ein stark elitärer Ton zu spüren. Beim flüchtigen Durchsehen des Blogs bittet er um Bitcoin-Spenden und schlägt 3 $ vor, scheint aber nicht zu berücksichtigen, dass ein erheblicher Teil davon durch Gebühren verschwinden kann
    • Auch wenn man Nachrichten bekommt, die einem nicht gefallen, ist es besser, Beschwerden nicht mit leichtem Rassismus und Kritik an den Englischkenntnissen des Verfassers zu vermischen
    • Sich über schlechtes Englisch lustig zu machen, ist immer ein Zeichen von Dummheit. Auch kluge Menschen können sich dumm verhalten
    • Tut mir leid, aber der Blogautor wirkt wie ein ziemlich unsympathischer Mensch
      Es klingt etwa wie: „Nein, du darfst den Code aus meinem GitHub-Repository nicht für deinen Uni-Projekt-Chatbot verwenden. Deine Coding-Standards genügen meinen nicht. Und dein Englisch ist auch miserabel“
    • Ich kann nachvollziehen, wie anstrengend es sein kann, einen persönlichen Blog zu betreiben. Man muss mit allen möglichen Leuten umgehen
      Zum Glück teilt er auch gutes Feedback separat: https://www.nayuki.io/page/decent-feedback-from-readers
  • Ziemlich gut. Ich würde gern auf dieselbe Weise auch einen Decoder sehen
    • Vielleicht gefällt dir auch der Guide von Piko und blinry darüber, wie man QR-Codes ohne Computer liest: https://qr.blinry.org/
    • Stimme zu. Ich bin immer wieder erstaunt, wie schnell ein Handy QR-Codes dekodiert, die dunkel und verschwommen sind und zu etwa einem Viertel außerhalb des Bildschirms liegen
    • Ich suche immer noch nach einem Guide, der einen QR-Reader von Grund auf implementiert
      Ich will nichts in der Art, wie man es bei Google findet: „Einfach diese Computer-Vision-Bibliothek einbinden, ein Bild hineinwerfen, und das Ergebnis kommt heraus“
      Ich suche einen Guide, der davon ausgeht, dass bereits dekodierte Rohbilddaten vorliegen, und dann alle nötigen Algorithmen implementiert
  • Gut, dass es eine Erklärung gibt. Persönlich wollte ich einfach nur schnell einen erstellen, aber bei der Suche fand ich werbeüberladene Seiten oder Seiten, die erst nach Registrierung nutzbar waren
    Auf GitHub habe ich auch ein paar gefunden, aber die hatten andere Probleme, also habe ich mit einer gut designten Bibliothek, die ich schon einmal genutzt hatte, schnell selbst etwas gebaut; es dauerte etwa 15 Minuten
    https://greggman.github.io/qr-code/
    Man könnte noch mehr Optionen hinzufügen, aber ich glaube, die meisten Nutzer brauchen solche Optionen eigentlich nicht
    • Freut mich, dass es nützlich war. Ich wollte auch schon länger selbst eine Implementierung schreiben, aber alles, was ich finden konnte, waren fertige Pakete für Python oder Golang
      Falls jemand hilfreiche Ressourcen kennt, aus denen man den Fehlerkorrekturteil bei QR-Codes lernen kann, wüsste ich gern davon
  • Ich habe früher eine Rust-Implementierung erstellt
    https://github.com/aabiji/qr
  • Wenn der Beitrag nicht aus dem aktuellen Jahr stammt, ist es gute Praxis, das Jahr des Beitrags im Titel anzugeben, hier also 2018
    • Stimme zu. Im Originallink gab es, soweit ich sehen konnte, kein Datum, und jetzt kann ich es nicht mehr ändern
  • Gut. Zu lernen, wie QR-Codes funktionieren, stand schon lange auf meiner To-do-Liste, und das war ein guter Einstiegsartikel
  • Jetzt, da ich weiß, wie es funktioniert, kann ich es auch in SQL-Queries verwenden: https://github.com/Florents-Tselai/pgQR