[PYTHON] Erstellen Sie einen QR-Code, der durch Kratzen "Izumi Oishi" anzeigt

Adventskalender "Izumi Oishi" Ich werde für den 5. Tag verantwortlich sein. Ich nehme zum ersten Mal am Adventskalender teil. Ich bin aufgeregt.

Dieses Mal werde ich das Verfahren zum Erstellen von QR-Code von Grund auf neu vorstellen, ohne auf die vorhandene Bibliothek angewiesen zu sein. Es ist jetzt nicht besonders nützlich, da die vorhandenen Bibliotheken umfangreich sind, aber bitte sehen Sie es als Lesematerial, das Ihnen das Gefühl gibt, dass QR-Code so erstellt wurde.

Über den Inhalt dieses Artikels

Wir werden einen QR-Code erstellen, der den Text "Izumi Oishi" als Daten speichert, und erklären, wie man ihn mit einem vorhandenen QR-Code-Leser liest. Die QR-Code-Spezifikationen werden erläutert und konzentrieren sich nur auf die erforderlichen Teile.

Referenzierte Site

Erstens ist dieser Artikel nicht das Original, sondern eine Folgeherausforderung, die auf Informationen zu Websites basiert, die ähnliche Dinge im Web tun.

Erstellen Sie einen QR-Code (http://www.swetake.com/qrcode/qr1.html)

In diesem Artikel werde ich mich auf das konzentrieren, was steckt, während ich mich darauf beziehe.

Darüber hinaus sind JIS-Informationen, die ein Standard sind, für die Implementierung von QR-Codes unverzichtbar. Sie können den Standard auf der JIS-Site lesen (Drucken ist nicht möglich). Da Sie die URL nicht direkt zum Fliegen bringen können, durchsuchen Sie die Datenbank bitte mit "JIS X 0510". Die referenzierte Version ist "X0510: 2018" und wurde 2018 aktualisiert.

Ich habe Informationen von vielen anderen Websites erhalten, daher werde ich sie am Ende dieses Artikels vorstellen.

Entscheiden Sie den Typ des QR-Codes

Obwohl es sich um einen QR-Code handelt, gibt es tatsächlich viele Typen. Es gibt über 40 Versionen, von kompakten und großen Quadraten bis zu wahnsinnig großen und feinkörnigen.

Was sich unterscheidet, sind grundsätzlich zwei Punkte, Kapazität und Stärke der Fehlerkorrektur. Die Kapazität beträgt 5 Byte bis etwa 3700 Byte, und die Fehlerkorrektur stellt 7% bis 30% der Gesamtkapazität wieder her, selbst wenn ein Teil nicht gelesen werden kann.

Dieses Mal möchte ich einen einfachen Code erstellen, der nur den Text "Izumi Oishi" enthält, also werde ich einen kleinen auswählen. Insbesondere handelt es sich um einen QR-Code mit 25 Quadraten auf jeder Seite, der als Version 2-H bezeichnet wird. Die Kapazität beträgt 16 Byte (Tabelle 7 auf Seite 31 des Standards). Zusätzlich haben wir die mit der höchsten Fehlerkorrekturleistung von 30% ausgewählt. Für Kanji und Hiragana können 9 Zeichen eingegeben werden. "Anastasia Suki" ist sicher. "Eve Santa Claus mag" ist leider nicht enthalten.

Die Gesamtdatenstruktur für diese Version ist wie folgt. Es sieht aus wie das.

Die großen auffälligen Muster in den drei Ecken sind das "Positionserkennungsmuster" (und das angrenzende weiße "Trennmuster"). Das Muster wie eine Kreuzung, die sie verbindet, ist das "Timing-Muster", und der kleine Augapfel unten rechts ist das "Ausrichtungsmuster". Diese werden als "Funktionsmuster" bezeichnet und sind immer farbig.

Andererseits ändert sich der codierte Bereich in Abhängigkeit von den gespeicherten Daten. Es gibt drei Arten unten.

Andere Arten von QR-Codes haben andere "Modellnummerninformationen", aber ich werde sie weglassen, da dies nicht in dieser Zeit der Fall ist. Darüber hinaus gibt es die folgenden Teile.

Wenn Sie diese erstellen können, ist der QR-Code vollständig. Es ist ein langer Weg, aber bitte bleiben Sie in Kontakt.

Bereiten Sie Daten vor, die in QR enthalten sein können

Die detaillierte Struktur des Datenabschnitts ist wie folgt.

Modustyp

Da die Kapazität des QR-Codes wertvoll ist, gibt es mehrere Modi, die auf die Art der einzugebenden Daten spezialisiert sind. Wählen Sie dieses Mal den auf Kanji spezialisierten Kanji-Modus. Es können nur die im Shift-JIS-Zeichencode enthaltenen Zeichen verwendet werden, diesmal ist dies jedoch ausreichend. Der Identifikationscode für den Kanji-Modus lautet "1000" (binär). Wenn Sie einen anderen Modus verwenden, können Sie Unicode-Zeichenfolgen verwenden.

Wortzahl

Im Kanji-Modus wird die Länge der Zeichenfolge in 8 Bit gespeichert. In anderen Modi unterscheidet es sich von 9-Bit oder 10-Bit. Diesmal sind es 5 Zeichen, also "00000101".

Zeichendaten

Der Zielzeichentyp hängt von Shift-JIS ab (UTF-8 ist heutzutage so beliebt, dass es nicht viel verwendet wird ...). In Shift-JIS wird ein Zeichen durch 16 Bits dargestellt, aber da es insgesamt etwas mehr als 7.000 Zeichen sind, kann es durch 13 Bits dargestellt werden (2 13 = 8096). Führen Sie die folgenden Schritte aus, um den Shift-JIS-Zeichencode in einen dedizierten 13-Bit-Code zu konvertieren.

Die Verarbeitung ist in zwei Typen unterteilt, da Shift-JIS selbst grob in zwei Abschnitte unterteilt ist (streng vier). (Referenz) (oder Standard S.89)

Infolgedessen wird "Oishi Izumisuki" wie folgt konvertiert.

Kündigungsmuster

Informationen, die darauf hinweisen, dass dies das Ende der Daten ist. Mit 4 Bit auf 0000 behoben. Wenn die verbleibende Kapazität jedoch 3 Bit oder weniger beträgt, schneiden Sie einen Teil oder die gesamte Kapazität so ab, dass sie nicht hervorsteht.

Vergrabenes Grasstückchen

~~ Es wächst Gras. ~~ Wenn die Gesamtzahl der Bits bis zu diesem Punkt kein Vielfaches von 8 ist, füllen Sie sie mit Füllbits = "Bit 0", bis sie ein Vielfaches von 8 wird. Diesmal sind 4 + 8 + 13 * 5 + 4 = 81, also füllen Sie 7 Bits aus. 0000000

Vergrabener Grasbiss

Wenn bis zu diesem Zeitpunkt noch Platz im Prozess vorhanden ist, werden "11101100" und "00010001" abwechselnd gefüllt, bis die Kapazität voll ist.

Schließlich

Um den bisherigen Inhalt zusammenzufassen

1000 00000101 0110010100101 0101111001110 0101111110010 0000100110111 0000100101011 0000 0000000 11101100 00010001 11101100 00010001 11101100

Wenn Sie nach 8 Bits organisieren
10000000 01010110 01010010 10101111 00111001 01111110 01000001 00110111 00001001 01011000 00000000 11101100 00010001 11101100 00010001 11101100

In Dezimalzahl konvertieren
128 86 82 175 57 126 65 55 9 88 0 236 17 236 17 236

Es ist fertig.

Fehlerkorrekturcode berechnen (sehr schwer)

Dies war die schwierigste Aufgabe. In dem QR-Code wird ein Fehlerkorrekturcode durch ein Verfahren hinzugefügt, das als Read Solomon Code (im Folgenden RS Code) bezeichnet wird, so dass die Daten korrekt decodiert werden können, selbst wenn ein Teil der Daten (dh schwarz oder weiß) nicht korrekt gelesen werden kann. Diese Berechnungsmethode ist sehr schwierig für diejenigen, die nicht gut in Mathematik sind.

Es ist ein sehr langer Abschnitt, daher ist es möglicherweise eine gute Idee, zuerst hier zu überspringen und bis zum Ende zu lesen.

Problem

Kurz gesagt, die Probleme, die hier gelöst werden müssen, sind folgende.

Primitive Polypolyse x^8+x^4+x^3+x^2+1 wurde verwendet\\Vergrößerte Galois GF(2^8)Im\\
N = 44, K = 16 \\
I(x) = d_1x^{15}+d_2x^{14}+d_3x^{13}+d_4x^{12}+d_5x^{11}+d_6x^{10}+d_7x^9+d_8x^8 + \\ d_9x^7+d_{10}x^6+d_{11}x^5+d_{12}x^4+d_{13}x^3+d_{14}x^2+d_{15}x+d_{16}
\\
G(x) =
x^{28}+α^{168}x^{27}+α^{223}x^{26}+α^{200}x^{25}+α^{104}x^{24}+α^{224}x^{23}+α^{234}x^{22}+α^{108}x^{21}+ \\
α^{180}x^{20}+α^{110}x^{19}+α^{190}x^{18}+α^{195}x^{17}+α^{147}x^{16}+α^{205}x^{15}+α^{27}x^{14}+ \\α^{232}x^{13}+
α^{201}x^{12}+α^{21}x^{11}+α^{43}x^{10}+α^{245}x^{9}+α^{87}x^{8}+α^{42}x^{7}+ \\
α^{195}x^{6}+α^{212}x^{5}+
α^{119}x^{4} +α^{242}x^{3}+α^{37}x^{2}+α^{9}x +α^{123}
\\Wann\\
P(x) = x^{N-K} I(x) \quad mod \quad G(x) 
\\ 
Nachfragen

...

...

...
** Was? ** Ich weiß nicht was es bedeutet?

Es ist verlockend, wegzulaufen, während man "Murry" schreit, wenn man ein Polypoly höherer Ordnung wie einen Narren sieht, aber es soll natürlich gelöst werden. Ich möchte fortfahren und eins nach dem anderen erklären.

Über GF2

Bevor ich mich dem Problem zuwende, halte ich es für notwendig, das Konzept der Mathematik namens GF (2) zu erläutern. Ich kann es nicht erklären, weil ich mich gerade daran erinnert habe, aber kurz gesagt bedeutet es "eine Welt mit speziellen Berechnungsregeln, die nur zwei Arten von Zahlen hat, 0 und 1." In dieser Welt gelten folgende Regeln für Addition und Subtraktion.

Zusatz

Subtraktion

Ja, Addition und Subtraktion haben genau das gleiche Ergebnis. Wie Sie diesem Ergebnis entnehmen können, entspricht dies auch der XOR (exklusive logische Summe) der Bits. Hier gibt es etwas Bequemes für den Computer. Durch die stetige Erweiterung werden verschiedene Anwendungen möglich sein.

GF ist übrigens eine Abkürzung für Galois Field und wird auf Japanisch Galois-Form oder endliche Form genannt.

Über primitive Polynome und GF (2 8)

Primitive Polynome sind spezielle Polynome, die zum Erweitern und Anwenden von GF verwendet werden (p m). Es wird auch verwendet, um GF (2) zu verlängern (p = 2, m = 1).

GF (2 8) ist eine Erweiterung von GF (2), die auch spezielle Berechnungsregeln enthält. GF (2) enthielt nur zwei Zahlen, 0 und 1, während GF (2 8 </ sup>) 2 8 = 256 Zahlen enthielt. .. Dies scheint häufig verwendet zu werden, da es für 8-Bit-Arithmetik sehr praktisch ist.

Wenn wir GF (2) auf GF (2 8 </ sup>) erweitern, verwenden wir primitive Polynome, aber es gibt verschiedene Arten von primitiven Polynomen, und wenn wir den RS-Code berechnen, welche Da sich das Berechnungsergebnis je nach Verwendung ändert, wird beim Erstellen des QR-Codes x 8 </ sup> + x <4> </ sup> + x <3> </ sup> + x <verwendet Sie werden eindeutig angewiesen, sup> 2 </ sup> + 1 zu verwenden.

Was ist α?

Das "α", das in der Funktion G (x) erscheint, ist das primitive Polypoly F (x) = x 8 + x + 4 + x 3 3 Die Wurzel von + x 2 </ sup> + 1, dh die Lösung, wenn F (x) = 0 ist. Und es ist eine sehr wichtige Existenz, die die 256 numerischen Werte (in technischen Begriffen auch als Original bezeichnet) zusammensetzt, die in GF (2 8) enthalten sind. Da die Eigenschaften von α zur Lösung dieses Problems benötigt werden, werde ich es noch lange ausführlich erläutern.

Da α F (α) = 0 erfüllt, gilt die folgende Gleichung.

α^8+α^4+α^3+α^2+1 = 0 \tag{1}

Zu diesem Zeitpunkt gehören alle Koeffizienten jedes Terms zur Welt von GF (2). Das heißt, es werden nur zwei Werte verwendet, 0 und 1, und das Ergebnis der Addition und Subtraktion ist gleich XOR. Basierend darauf wird (1) transformiert.

α^8 = α^4+α^3+α^2+1 \tag{2}

Sie denken vielleicht "Hmm?", Aber es ist kein Fehler, dass es beim Übertragen kein Minus gibt. Da Addition und Subtraktion gleich sind, kann man mit Sicherheit sagen, dass es in dieser Welt keinen Unterschied zwischen +/- gibt (α 8 = 1 α 8 = (0-1) α. 8 </ sup> = -α 8 </ sup>).

Finden Sie die Kraft von α

Die Kraft von α hat eine sehr wichtige Eigenschaft. Um darüber zu sprechen, berechnen wir zuerst ein ^{e </ sup> (e ist eine ganze Zahl größer oder gleich 0). & agr; 8 </ sup> ist gleich & agr; 4 </ sup> + & agr; 3 </ sup> + & agr; 2 + / 1, also & agr; 9 </ sup>, α10, α1111}

α^9 = α^5 + α^4 + α^3 + α \\
α^{10} = α^6 + α^5 + α^4 + α^2 \\
α^{11} = α^7 + α^6 + α^5 + α^3 \\

Es wird sein. In α1212

\begin{align}
α^{12} &= α^8 + α^7 + α^6 + α^4 \\
       &= (a^4 + a^3 + a^2 + 1) + a^7 + a^6 + a^4 \\
       &= a^7 + a^6 + (1+1)a^4 + a^3 + a^2 + 1 \\
       &= a^7 + a^6 + a^3 + a^2 + 1
\end{align}

In der dritten Zeile gilt 1 + 1 = 0 für den α-Koeffizienten, so dass der Term α4 </ sup> verschwindet. Wie Sie sehen können, werden dank des Ersetzens von & agr; 8 </ sup>, egal wie hoch die Ordnung von & agr; ist, höchstens 8 Terme unter & agr; 7 </ sup> liegen. Kann ersetzt werden.

α^e = b_1α^7 + b_2α^6 + b_3α^5 + b_4α^4 + b_5α^3 + b_6α^2 + b_7α + b_8

b _{1 </ sub> ~ b 8 </ sub> ist eine Zahl (0 oder 1), die zu GF (2) gehört. Sie können die Bitberechnung fühlen.}

Und wenn Sie die Ordnung von α weiter erhöhen,

α^{255} = 1

Kann erhalten werden. Da α 0 = 1 ist, durchläuft α e Schleifen in 255 Zyklen.

Es ist lange her, aber hier ist das Wichtigste.

*** Über αe </ sup> In dem Bereich, in dem e 0 bis 254 ist, werden die Koeffizienten b1 ~ b ~ 8 8 eindeutig bestimmt ** * *

Mit anderen Worten, e und b 1 ~ b ~ 8 können jeweils eine 1: 1-Entsprechung haben. Es sollte wie in der folgenden Tabelle aussehen.

Alle sind zu lang, daher werden nur einige aufgelistet. Hier und [Hier (Link Tabelle 4)](http: / /www.swetake.com/qrcode/qr3.html).

Im Folgenden finden Sie den Code zum Generieren der Tabelle. Nur wer es sehen will.

#   e     0, 1, 2, 3, 4, 5, 6, 7, 8
buffer = [1, 0, 0, 0, 0, 0, 0, 0, 0]
print('e  b1 b2 b3 b4 b5 b6 b7 b8 d10')
for e in range(1, 255):
    #Verschieben Sie den Puffer nach rechts
    buffer = [0] + buffer[0:8]
    if buffer[8]:
        buffer[8] = 0
        # a^8 ist aufgetreten, also a^4+a^3+a^2+a^Durch 0 ersetzen
        added = [1, 0, 1, 1, 1]
        for i in range(len(added)):
            # GF(2)In ist die Addition von Ziffern gleich XOR(Und es gibt keinen Fortschritt)
            buffer[i] = buffer[i] ^ added[i]
    n = sum([buffer[i] * (2 ** i) for i in range(8)])
    print(e, list(reversed(buffer[:8])), n)

load("gf")$
gf_set_data(2, x^8+x^4+x^3+x^2+1)$
binmap(n) := makelist(coeff(gf_exp(x, n), x^k), k, 7, 0, -1)$
exp2num(n) := lreduce(lambda([x,y],2*x+y), binmap(n))$
for n : 0 thru 254 do print(n, binmap(n), exp2num(n));

Für αe </ sup> fand ich, dass der gleiche Wert auf zwei Arten ausgedrückt werden kann, e oder b1 </ sub> bis b8 </ sub>. In dem Artikel werden wir sie als "e Ausdruck" bzw. "b Ausdruck" bezeichnen. Der Schlüssel ist, wie diese beiden Ausdrücke richtig verwendet werden.

Über die Berechnung der Potenzen von α

Ich werde das Berechnungsgesetz zwischen den Potenzen von α erklären.

Erstens ist die Multiplikation.

Beim Multiplizieren der beiden Werte α i i und α j j

α^iα^j = α^{i+j} \tag{3}

Es wird sein. Ich denke, das ist kein Problem, weil es ein Bereich ist, der sogar in der Mathematik der High School gelernt werden kann. Ich werde es später verwenden.

Als nächstes folgt Addition und Subtraktion.

α^i + α^j = ? \\
α^i - α^j = ?

Diese Berechnung kann nicht mit der "e-Darstellung" durchgeführt werden. Aber Sie können es mit b Ausdruck tun.

α^i = b_{i1}α^7+b_{i2}α^6+b_{i3}α^5+b_{i4}α^4+b_{i5}α^3+b_{i6}α^2+b_{i7}α+b_{i8} \\
α^j = b_{j1}α^7+b_{j2}α^6+b_{j3}α^5+b_{j4}α^4+b_{j5}α^3+b_{j6}α^2+b_{j7}α+b_{j8} \\
Wenn du gehst\\
\begin{align}
α^i + α^j = α^i - α^j &= (b_{i1} \oplus b_{j1})α^7 + (b_{i2} \oplus b_{j2})α^6 + (b_{i3} \oplus b_{j3})α^5 \\
&+ (b_{i4} \oplus b_{j4})α^4 + (b_{i5} \oplus b_{j5})α^3 + (b_{i6} \oplus b_{j6})α^2 \tag{4} \\ &+ (b_{i7} \oplus b_{j7})α + (b_{i8} \oplus b_{j8}) 
\end{align}

• In 〇 steht ein Symbol für XOR (exklusive logische Summe). Dies bedeutet, dass die Addition und Subtraktion im "e-Ausdruck" für jeden Koeffizienten im "b-Ausdruck" gleich dem XOR ist. Einfacher ist es gleich "XOR" zwischen 8 Bits in einer Tabelle.

Die erforderlichen Werkzeuge stehen gemäß den Gleichungen (3) und (4) zur Verfügung.

Was ist d?

Als nächstes wird der Koeffizient d erklärt, der in der Funktion I (x) erscheint.

Ich werde ich (x) wieder schreiben.

I(x) = d_1x^{15}+d_2x^{14}+d_3x^{13}+d_4x^{12}+d_5x^{11}+d_6x^{10}+d_7x^9+d_8x^8 + \\ d_9x^7+d_{10}x^6+d_{11}x^5+d_{12}x^4+d_{13}x^3+d_{14}x^2+d_{15}x+d_{16}

d _{1 </ sub> ~ d 16 </ sub> enthält die Daten, die durch den RS-Code geschützt werden sollen, dh die 16 zuvor erhaltenen Datenbytes, von denen jedes 8 Bits entspricht. Es ist ein Ausdruck höherer Ordnung der Variablen α, die Informationen enthält. Die Definition ist wie folgt.}

d = b_1α^7 + b_2α^6 + b_3α^5 + b_4α^4 + b_5α^3 + b_6α^2 + b_7α^1 + b_8

Ja, es ist dasselbe wie der "b-Ausdruck", der αe </ sup> entspricht. Daher können die Eingabedaten alle 8 Bits in die Form von d = αe </ sup> konvertiert werden. Lass es uns für einen Moment tun.

Die ersten 4 Datenbytes waren "10000000" 01010110 "01010010" 10101111 ". Wenn Sie versuchen, dies zu konvertieren, während Sie die Korrespondenztabelle betrachten (finden Sie den Wert von e von rechts nach links),

d_1 = α^7 \\
d_2 = α^{219} \\
d_3 = α^{148} \\
d_4 = α^{97}

(Entschuldigung, d _{3 </ sub> und d 4 </ sub> werden aufgrund des Weglassens der Tabelle nicht aufgelistet.)}

Es werden alle Daten auf die gleiche Weise konvertiert. Nur ein Punkt braucht Aufmerksamkeit. Es gibt kein e, das α ^{e </ sup> = 0 nur dann macht, wenn die Daten "00000000" sind, also habe ich es aufgegeben, dies in Form von α e </ sup> und dem Begriff selbst auszudrücken. Ich werde es schneiden.}

Infolgedessen sieht I (x) folgendermaßen aus:

I(x) = α^{7}x^{15}+α^{219}x^{14}+α^{148}x^{13}+α^{97}x^{12}+α^{154}x^{11}+α^{167}x^{10}+α^{191}x^9+α^{185}x^8 + \\ α^{223}x^7+α^{241}x^6+0x^5+α^{122}x^4+α^{100}x^3+α^{122}x^2+α^{100}x+α^{122}

Die Daten, die d11 </ sub> entsprechen, waren "00000000", so dass der Abschnitt x5 </ sup> verschwand.

Finde den Rest P (x)

Erinnern Sie sich an die Funktion P (x), die Sie hier finden möchten.

\begin{align}
P(x) &= x^{N-K} I(x) \quad mod \quad G(x) \\
     &= x^{28} I(x) \quad mod \quad G(x)
\end{align}

Ersetzen Sie also x 28 (/) I (x) durch eine andere Funktion.

M(x) = x^{28}I(x) \\
= α^{7}x^{43}+α^{219}x^{42}+α^{148}x^{41}+α^{97}x^{40}+α^{154}x^{39}+α^{167}x^{38}+α^{191}x^{37}+α^{185}x^{36} + \\ α^{223}x^{35}+α^{241}x^{34}+0x^{33}+α^{122}x^{32}+α^{100}x^{31}+α^{122}x^{30}+α^{100}x^{29}+α^{122}x^{28}

Wenn Sie dann erneut G (x) schreiben,

G(x) =
α^{0}x^{28}+α^{168}x^{27}+α^{223}x^{26}+α^{200}x^{25}+α^{104}x^{24}+α^{224}x^{23}+α^{234}x^{22}+α^{108}x^{21}+ \\
α^{180}x^{20}+α^{110}x^{19}+α^{190}x^{18}+α^{195}x^{17}+α^{147}x^{16}+α^{205}x^{15}+α^{27}x^{14}+ \\α^{232}x^{13}+
α^{201}x^{12}+α^{21}x^{11}+α^{43}x^{10}+α^{245}x^{9}+α^{87}x^{8}+α^{42}x^{7}+ \\
α^{195}x^{6}+α^{212}x^{5}+
α^{119}x^{4} +α^{242}x^{3}+α^{37}x^{2}+α^{9}x +α^{123}

Der Druck ist immer noch stark, aber es ist ziemlich erfrischend.

Wie finden Sie übrigens den Rest für ein Polynom? Ich habe das Gefühl, dass ich es mit Nummer II-B gemacht habe, als ich in der High School war. Zur Erinnerung, lassen Sie uns den Rest der Funktion m (x) = x 2 + 3x + 1 geteilt durch g (x) = x-1 finden.

Legen Sie zuerst die Formel auf die Seite, die gebrochen werden soll.

x^2 + 3x + 1

Passen Sie dann die Reihenfolge und den Koeffizienten der Formel auf der Teilungsseite an die zu teilende Seite an.

\begin{align}
  & x^2 + 3x + 1 \\
-)& x^2 -  x     \hspace{2pc} ←xg(x)
\end{align}

Und du wirst subtrahieren. Löscht den Term höchster Ordnung.

4x + 1

Und auf die gleiche Weise

\begin{align}
  & 4x + 1 \\
-)& 4x - 4     \hspace{2pc} ←4g(x)
\end{align}

Die restlichen liegen unterhalb der Reihenfolge der geteilten Seite, daher endet sie hier. Daher beträgt der Rest 5. Wenn der Koeffizient der maximalen Ordnung von g (x) 1 ist, ist dies einfach möglich.

Sie können P (x) genauso erhalten. Versuchen wir nun, M (x) erst am Anfang durch G (x) zu teilen (sorry, aber alles ist zu lang zum Schreiben).

Überprüfen Sie zunächst die maximalen Bestellbedingungen des anderen. M (x) ist α 7 x 43 und G (x) ist α 28 x 28. Multiplizieren Sie daher G (x) mit α 7 x 15, um den gleichen Wert zu erhalten.

\begin{align}
& α^{7}x^{43}+α^{219}x^{42}+α^{148}x^{41}+... \\
& α^{7}α^{0}x^{43}+α^{7}α^{168}x^{42}+α^{7}α^{223}x^{41}+... \hspace{2pc} ←α^7x^{15}G(x)
\end{align}

Hier verwenden wir Gleichung (3). Das Multiplizieren der Potenzen von α ist das Hinzufügen von Exponenten, wenn Sie es also organisieren

\begin{align}
  & α^{7}x^{43}+α^{219}x^{42}+α^{148}x^{41}+... \\
-)& α^{7}x^{43}+α^{175}x^{42}+α^{230}x^{41}+... \hspace{2pc} ←α^7x^{15}G(x)
\end{align}

Gleichung (4) wird für diese Subtraktion verwendet. Die Subtraktion zwischen Potenzen erfordert ein 8-Bit-XOR. Für & agr; 219 </ sup> - & agr; 175 </ sup> ist & agr; (01010110 xor 11111111) </ sup> = & agr; 10101001 </ sup> = & agr; 135 </ sup> Das stimmt. α 148 - α 230 230 01010010 xor 11110100 = α 10100110 = α 207 </ sup > .... Achten Sie beim Konvertieren von "e Ausdruck" (Exponentialwert) in "b Ausdruck" (binär) und beim Konvertieren von "b Ausdruck" in "e Ausdruck" (wie es ist, Dezimalzahl <) auf die Tabelle -> Nicht in Binärzahl konvertieren)

Jetzt müssen Sie nur noch den Vorgang des Löschens der Begriffe höchster Ordnung wiederholen. Wenn der Exponent nach Verwendung von Gleichung (3) 255 oder mehr wird, verwenden Sie als Einschränkung α 255 </ sup> = 1, um den Exponenten auf weniger als 255 zu korrigieren. ..

Sie endet, wenn die endgültig zu teilende Seite unter x 28 fällt und R (x) wie folgt berechnet wird.

R(x) = α^{248}x^{27}+α^{159}x^{26}+α^{237}x^{25}+α^{105}x^{24}+α^{12}x^{23}+α^{215}x^{22} \\
+α^{172}x^{21}+α^{102}x^{20}+α^{113}x^{19}+α^{149}x^{18}+α^{233}x^{17}+α^{135}x^{16}\\ 
+α^{51}x^{15}+α^{42}x^{14}+α^{233}x^{13}+α^{7}x^{12}+α^{44}x^{11}+α^{236}x^{10}+α^{216}x^{9} \\
+α^{159}x^{8}+α^{64}x^{7}+α^{70}x^{6}+α^{11}x^{5}+α^{0}x^{4}+α^{51}x^{3}+α^{5}x^{2}+a^{60}x^{1}+a^{168}

Was ich wollte (RS-Code), ist der Exponentialwert jedes Koeffiziententeils dieses R (x). Deshalb

248 159 237 105 12 215 172 102 113 149 233 135 51 42 233 7 44 236 216 159 64 70 11 0 51 5 60 168

Es ist fertig. Es war hart.

Platzieren Sie Daten und Fehlerkorrekturcode in der Masse

Bisher sind es ungefähr 60-70%. Es ist ein bisschen mehr.

Ordnen Sie die erstellten Daten und Fehlerkorrektursymbole Stück für Stück entsprechend den Zahlen im Bild an. Da die Daten 16 Bytes und das Fehlerkorrektursymbol 28 Bytes sind, sind 44 * 8 = 352 Bits. Füllen Sie die Abbildung mit bis zu 351 aus.

Ich werde dem Rest Farbe (0 oder 1) hinzufügen Der weiße Teil wird als helles Modul bezeichnet, und "Bit 0" wird eingefügt. Der schwarze Teil wird als dunkles Modul bezeichnet und "Bit 1" wird eingefügt. Der grüne Teil wird als Restbit bezeichnet, das ein Bruchteil ist. Fügen Sie also "Bit 0" ein. Ich werde den lila Teil am Ende ausfüllen, aber ** Ich wusste zu diesem Zeitpunkt nicht, welchen Wert ich eingeben soll, daher werde ich vorübergehend den Wert TBD eingeben. Bitte lassen Sie mich wissen, wenn Sie damit vertraut sind **. (Der Standard (S.45) besagt, dass es vorübergehend geleert werden muss, aber was ist das?)

Nur der lila Teil in der Figur wird vorübergehend platziert, aber die Figur ist fertig.

Auswahl der richtigen Maske (schwer)

Der QR-Code hat eine Funktion namens "Maske", um zu verhindern, dass der Inhalt der Daten Muster erzeugt, die extrem schwer zu lesen sind. Der Zweck besteht darin, die angeordneten Schwarz-Weiß-Muster unter Verwendung von acht verschiedenen Mustern teilweise zu invertieren und schließlich das am besten lesbare Muster zu erzeugen.

Daher müssen Sie in der Software (Encoder), die QR-Codes erstellt, alle acht Masken ausprobieren und die beste auswählen.

Maskentyp

Es gibt acht Arten von Masken unten. (Berechnungsformel weggelassen. Einzelheiten siehe S.49 des Standards)

Teil, der in das Maskenziel aufgenommen werden soll

--Datenteil

• Fehlerkorrekturcode

Teile, die nicht im Maskenziel enthalten sind (außer den oben aufgeführten)

• Funktionsmuster (Positionserkennung, Timing, Ausrichtung) --Formatinformationen
• Verbleibende Bits

Auswertung

Nach dem Anwenden jeder Maske wird die Bewertung anhand von vier Arten von Bewertungskriterien bewertet. Die Bewertung ist eine Abzugsmethode, und die mit den wenigsten Punkten wird tatsächlich verwendet.

Das Bewertungsziel ist der gesamte QR-Code. (Es gibt jedoch einen Teil, in dem die Farbe noch nicht festgelegt wurde, sodass unklar ist, was damit zu tun ist ...)

Die Bewertungskriterien lauten wie folgt (Tabelle 11 auf Seite 53 der Norm).

Die Erklärung hier ist sehr grob. Den genauen Inhalt entnehmen Sie bitte der Norm.

• Für das schwarze 3x3-Dunkelmodulmuster innerhalb des Positionserkennungsmusters in den drei Ecken werden immer 1 Punkte abgezogen (insgesamt -36 Punkte). Da auf diesen Teil jedoch keine Maske angewendet wird, werden Punkte bei der Bewertung aller acht Masken gleichermaßen abgezogen, sodass das Ergebnis der Maskenauswahl nicht beeinflusst wird.
• 2 Bezieht sich auf das große Positionserkennungsmuster an den drei Ecken.

Bei der tatsächlichen Bewertung wurden nur die Bewertungen 1 und 2 abgezogen, und die Bewertungen 3 und 4 wurden nicht in allen acht Masken abgezogen. ** Für Auswertung 3 hat die Auswertung überhaupt nicht mehr funktioniert, weil ich einen Wert wie "Wert TBD" in den Formatinformationsteil eingefügt habe, aber was ist damit ... ** Immerhin das helle Modul Ist es angebracht, ... einzutragen?

Das Maskenmuster "111" (unten rechts im Bild oben) wurde diesmal mit den geringsten Zielen ausgewählt. Wenden Sie dann tatsächlich die ausgewählte Maske an.

Formatinformationen berechnen

Füllen Sie den letzten verbleibenden Teil aus. Was bleibt, ist der Teil "formale Information".

Die folgenden beiden sind in den Formatinformationen enthalten.

• Fehlerkorrekturpegel (2 Bit) 10
• Ausgewählte Maskenmusternummer (3 Bit) 111

Die Fehlerkorrekturstufe ist "10", weil ich "H" dieses Mal ausgewählt habe. Für andere Stufen siehe Standard (S.54, Tabelle 12).

Der BCH-Code wird basierend auf dieser 5-Bit-Information "10111" berechnet. Dies ist auch eine Art Fehlerkorrekturcode, der dem RS-Code ähnlich ist. Sie könnten denken: "Ist es wieder Mathematik?", Aber es ist in Ordnung, weil es der gleiche Prozessablauf ist und es ziemlich einfach ist.

BCH-Code

Auch in diesem Fall werden die Funktionen I (x) und G (x) definiert und die folgenden Probleme gelöst.

N = 15, K=5 \\
I(x) = 1x^4 + 0x^3 + 1x^2 + 1x + 1 \\
G(x) = x^{10} + x^8 + x^5 + x^4 + x^2 + x + 1 \\
Im\\
P(x) = x^{N-K}I(x) \quad mod \quad G(X) \\
Nachfragen

Jeder Koeffizient von I (x) ist ein Array von Fehlerkorrekturpegel- und Maskenzahlbits. Zum Glück sind diesmal alle Koeffizienten 0 oder 1, daher ist die Berechnung sehr einfach.

Wenn Sie nur das Ergebnis schreiben, erhalten Sie 0000101001. Verbinden Sie dies nach dem vorhandenen 5-Bit und nehmen Sie das XOR mit der angegebenen Maske "101010000010010", um abzuschließen.

\begin{array}{c}
\begin{align}
  & 101110000101001 \\
\oplus & 101010000010010 \\
\hline
& 000100000111011
\end{align}
\end{array}

Die korrekten Werte sind auf Seite 76, Tabelle C.1 des Standards aufgeführt, stimmen jedoch gut überein. War gut.

Platzieren Sie Formatinformationen in der Masse

Schreiben Sie abschließend die 15 Bits der soeben erhaltenen Formatinformationen in den noch leeren Teil.

Sie müssen dasselbe an zwei verschiedenen Stellen schreiben.

Machen Sie ein QR-Code-Bild

Machen Sie zum Schluss ein Bild und Sie sind fertig. Es ist am einfachsten, ein Bild in derselben Größe zu erstellen und es ohne Interpolation zu vergrößern. Vergessen Sie nicht, mindestens 4 Quadrate der Ruhezone (weißer Rand) darum herum hinzuzufügen.

Komplett! !! Es war ein langer Weg!

Funktionsprüfung

Kannst du übrigens lesen, was du gemacht hast?

** Es ist fertig **.

Ich habe es auf iPad, Android-Tablet und Freie Software für Windows versucht, aber alle haben problemlos gelesen. .. Ich hatte nicht erwartet, dass es so reibungslos läuft.

Übrigens habe ich zunächst vergessen, die Formatinformationen zu maskieren und so auszugeben, wie sie sind, aber sie wurden trotzdem richtig gelesen. Tut die Decoderseite ihr Bestes, um etwas dagegen zu unternehmen?

Impressionen

Wenn ich den Prozess des tatsächlichen Erstellens eines QR-Codes erlebe, lautet der Artikel "QR-Code manuell lesen", den ich einmal gelesen und meinen Kopf geneigt habe, auch "Ah, Ich konnte fühlen, dass ich es irgendwie schaffen konnte.

Ich hoffe, Sie lesen diesen Artikel und denken, dass QR-Code überraschend einfach zu erstellen ist.

Der diesmal erstellte Quellcode (Sprache ist Python) ist etwas lang geworden, sodass er sich auf einer externen Site (Github) befindet. Bitte kochen oder backen. (Ich denke, es wäre schön, den QR-Code auf eine Visitenkarte wie P zu schreiben.) QR-Code-Generator, der "Izumi Oishi" anzeigt

Referenzlink

Ich werde die Websites veröffentlichen, auf die ich verwiesen habe, und die Links, die ich im Zusammenhang mit diesem Artikel lesen möchte.

QR-Code im Allgemeinen

Versuchen Sie, einen QR-Code zu erstellen : Die Seite, auf die ich mich dieses Mal am meisten bezogen habe QR Code.com : Densos Website, die den QR-Code entwickelt hat. Ich kann den QR-Code ungefähr verstehen QR-Code Deep Dive-Datencodierung oder Fehlerkorrektur- : Die Seite, die ich gefunden habe, als ich diesen Artikel fast fertig geschrieben habe (Leuchtturmdunkelheit). Ich hätte vor dem Schreiben in Qiita nach dem Artikel suchen sollen, aber ich verstehe nicht, warum ich ihn verpasst habe. Creating a QR Code step by step : (Englisch) Eine großartige Website, die den Prozess der schrittweisen Erstellung eines QR-Codes mit detaillierten Informationen veranschaulicht.

RS-Code bezogen

Galoa und vergrößert : Leicht verständlicher Artikel über Galois Körper 1 Galoa Body Course : Leicht verständlicher Artikel über Galois Körper 2 [Wikipedia-Lead Solomon Code](https://ja.wikipedia.org/wiki/%E3%83%AA%E3%83%BC%E3%83%89%E3%83%BB%E3%82% BD% E3% 83% AD% E3% 83% A2% E3% 83% B3% E7% AC% A6% E5% 8F% B7 #% E7% AC% A6% E5% 8F% B7% E5% 8C% 96 ) : Die im Erklärungsbeispiel verwendete Formel ist die gleiche wie die im QR-Code verwendete, daher ist sie sehr hilfreich. Reed–Solomon codes for coders : Obwohl es auf Englisch ist, wird es allgemein erklärt. Wenn Sie es also lesen können, tun Sie es bitte

Andere

CRC-32 : Dies ist eine Erklärungsfolie zu CRC-32. CRC, das häufig zur Überprüfung auf Datenkorruption verwendet wird, ist ebenfalls eine Technologie, die Galois verwendet. Wenn Sie es zusammen lesen, werden Sie vielleicht Ihr Verständnis vertiefen. Was ist Oishi Izumi (Delicious Izumi) [Pixiv Encyclopedia] : Für diejenigen, die Izumi Oishi sind