[PYTHON] Créez un code QR qui affiche "Izumi Oishi" en grattant

#   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):
    #Déplacez le tampon vers la droite
    buffer = [0] + buffer[0:8]
    if buffer[8]:
        buffer[8] = 0
        # a^8 s'est produit, donc un^4+a^3+a^2+a^Remplacer par 0
        added = [1, 0, 1, 1, 1]
        for i in range(len(added)):
            # GF(2)Dans, l'ajout de chiffres est égal à XOR(Et il n'y a pas d'avance)
            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));

Pour α ^{e </ sup>, j'ai trouvé que la même valeur peut être exprimée de deux manières, e ou b _{1 </ sub> à b 8 </ sub>. Dans l'article, nous les appellerons respectivement «e expression» et «b expression». La clé est de savoir comment utiliser correctement ces deux expressions.}}

A propos du calcul des puissances de α

J'expliquerai la loi de calcul entre les puissances de α.

Le premier est la multiplication.

Lors de la multiplication des deux valeurs α ^{i </ sup> et α j </ sup>}

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

Ce sera. Je pense que ce n'est pas un problème parce que c'est une gamme qui peut être apprise même en mathématiques au secondaire. Je l'utiliserai plus tard.

Viennent ensuite l'addition et la soustraction.

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

Ce calcul ne peut pas être fait avec l '«expression e». Mais vous pouvez le faire avec b expression.

α^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} \\
Si tu pars\\
\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 〇 est un symbole représentant XOR (somme logique exclusive). Cela signifie que l'addition et la soustraction dans «l'expression e» sont égales au XOR pour chaque coefficient de «l'expression b». Plus simplement, il est égal à "XOR" entre 8 bits dans une table.

Les outils nécessaires sont disponibles selon les équations (3) et (4).

Qu'est-ce que d?

Ensuite, le coefficient d qui apparaît dans la fonction I (x) sera expliqué.

J'écrirai à nouveau I (x).

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> contient les données à protéger par le code RS, c'est-à-dire les 16 octets de données obtenus à l'avance, dont chacun équivaut à 8 bits. C'est une expression d'ordre supérieur de la variable α qui contient des informations. La définition est la suivante.}

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

Oui, c'est la même chose que l'expression «b» correspondant à α ^{e </ sup>. Par conséquent, les données d'entrée peuvent être converties sous la forme d = α e </ sup> tous les 8 bits. Faisons-le un instant.}

Les 4 premiers octets de données étaient «10000000» 01010110 »« 01010010 »10101111». Si vous essayez de convertir cela en regardant la table de correspondance (trouvez la valeur de e du côté droit vers le côté gauche),

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

(Désolé, d _{3 </ sub> et d 4 </ sub> ne sont pas répertoriés en raison de l'omission du tableau.)}

Il convertira toutes les données de la même manière. Un seul point mérite attention. Puisqu'il n'y a pas de e qui rend α ^{e </ sup> = 0 uniquement lorsque les données sont «00000000», je renonce à l'exprimer sous la forme de α e </ sup> et du terme lui-même. Je vais le couper.}

En conséquence, je (x) ressemble à ceci:

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}

La donnée correspondant à d _{11 </ sub> était "00000000", donc la section x ^{5 </ sup> a disparu.}}

Trouvez le reste P (x)

Rappelez la fonction P (x) que vous souhaitez trouver ici.

\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}

Remplacez donc x ^{28 </ sup> I (x) par une autre fonction.}

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}

Ensuite, si vous écrivez à nouveau G (x),

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}

La pression est toujours forte, mais c'est plutôt rafraîchissant.

Au fait, comment trouvez-vous le reste d'un polynôme? J'ai l'impression de l'avoir fait autour du numéro II-B quand j'étais au lycée. Pour rappel, trouvons le reste de la fonction m (x) = x ^{2 </ sup> + 3x + 1 divisé par g (x) = x-1.}

Tout d'abord, mettez la formule du côté à casser.

x^2 + 3x + 1

Ensuite, faites correspondre l'ordre et le coefficient de la formule du côté de division au côté à diviser.

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

Et vous soustrayez. Efface le terme d'ordre le plus élevé.

4x + 1

Et de la même manière,

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

Les autres sont en dessous de l'ordre du côté divisé, donc cela se termine ici. Par conséquent, le reste est de 5. Lorsque le coefficient de l'ordre maximum de g (x) est 1, c'est facile de faire comme ça.

Vous pouvez obtenir P (x) exactement de la même manière. Maintenant, essayons de diviser M (x) par G (x) seulement au début (désolé, mais tout est trop long à écrire).

Tout d'abord, vérifiez les conditions de commande maximales de chacun. M (x) est α ^{7 </ sup> x 43 </ sup>, et G (x) est α 0 </ sup> x 28 </ sup>. Par conséquent, multipliez G (x) par α 7 </ sup> x 15 </ sup> pour faire correspondre la même valeur.}

\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}

Ici, nous utilisons l'équation (3). Multiplier les puissances de α est l'addition d'exposants, donc si vous l'organisez

\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}

L'équation (4) est utilisée pour cette soustraction. La soustraction entre les puissances prend un XOR 8 bits. Pour α ^{219 </ sup> --α 175 </ sup>, α (01010110 xor 11111111) </ sup> = α 10101001 </ sup> = α 135 </ sup> C'est vrai. α 148 </ sup> --α 230 </ sup> = α 01010010 xor 11110100 </ sup> = α 10100110 </ sup> = α 207 </ sup > .... Assurez-vous de vous référer au tableau lors de la conversion de «e expression» (valeur exponentielle) en «b expression» (binaire), et lors de la conversion de «b expression» en «e expression» (tel quel, nombre décimal < -> Ne pas convertir en nombre binaire)}

Il ne vous reste plus qu'à répéter le processus d'effacement des termes d'ordre le plus élevé. En guise de mise en garde, si l'exposant devient 255 ou plus après avoir utilisé l'équation (3), utilisez α ^{255 </ sup> = 1 pour corriger l'exposant pour qu'il soit inférieur à 255. ..}

Il se termine lorsque le côté à diviser finalement tombe en dessous de x ^{28 </ sup>, et R (x) est calculé comme suit.}

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}

Ce que je voulais (code RS), c'est la valeur exponentielle de chaque partie de coefficient de ce R (x). Donc

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

C'est fait. C'était dur.

Placer les données et le code de correction d'erreur dans la masse

Jusqu'à présent, c'est environ 60 à 70%. C'est un peu plus.

Organisez les données créées et les symboles de correction d'erreur bit par bit en fonction des nombres de l'image. Étant donné que les données sont de 16 octets et que le symbole de correction d'erreur est de 28 octets, 44 * 8 = 352 bits. Remplissez jusqu'à 351 dans la figure.

J'ajouterai de la couleur (0 ou 1) au reste La partie blanche est appelée module lumineux et le "bit 0" est inséré. La partie noire est appelée le module sombre et le "bit 1" est inséré. La partie verte est appelée le bit résiduel, qui est une partie fractionnaire, insérez donc «bit 0». Je remplirai la partie violette à la fin, mais ** je ne savais pas quelle valeur entrer pour le moment, donc je vais temporairement entrer la `valeur à déterminer '. S'il vous plaît laissez-moi savoir si vous le connaissez **. (La norme (P.45) dit qu'il doit être vidé temporairement, mais qu'est-ce que c'est?)

Seule la partie violette de la figure est temporairement placée, mais la figure est terminée.

Choisir le bon masque (difficile)

Le code QR a une fonction appelée «masque» pour éviter que le contenu des données ne génère des motifs extrêmement difficiles à lire. Le but est d'inverser partiellement les motifs en noir et blanc disposés en utilisant huit motifs différents, et enfin de générer le motif le plus lisible.

Par conséquent, dans le logiciel (encodeur) qui crée des codes QR, vous devez essayer les huit masques et sélectionner le meilleur.

Type de masque

Il existe huit types de masques ci-dessous. (Formule de calcul omise. Pour plus de détails, voir P.49 de la norme)

Pièce à inclure dans la cible du masque

--Partie de données --Code de correction d'erreur

Pièces non incluses dans la cible du masque (autres que celles énumérées ci-dessus)

• Modèle fonctionnel (détection de position, synchronisation, alignement)
• Informations sur le format --Bits restants

Évaluation

Après application de chaque masque, le score sera évalué selon quatre types de critères d'évaluation. L'évaluation est une méthode de déduction, et celle avec le moins de points sera effectivement utilisée.

La cible de l'évaluation est le code QR complet. (Cependant, il y a une partie où la couleur n'a pas encore été décidée, donc on ne sait pas quoi en faire ...)

Les critères d'évaluation sont les suivants (Tableau 11 à la page 53 de la norme).

L'explication ici est très approximative, veuillez donc vous référer à la norme pour le contenu exact.

• 1 Des points seront toujours déduits (-36 points au total) pour le motif de module noir 3x3 sombre à l'intérieur du motif de détection de position dans les trois coins. Cependant, comme aucun masque n'est appliqué à cette partie, les points seront déduits de manière égale dans l'évaluation des huit masques, de sorte que le résultat de la sélection du masque ne sera pas affecté.
• 2 Fait référence au grand motif de détection de position aux trois coins.

Lorsqu'elles ont été réellement évaluées, seules les évaluations 1 et 2 ont été déduites, et les évaluations 3 et 4 n'ont pas été déduites dans les huit masques. ** Pour l'évaluation 3, j'ai mis une valeur telle que `valeur à déterminer 'dans la partie informations de format, donc l'évaluation a cessé de fonctionner du tout, mais qu'en est-il de cela ... ** Après tout, le module lumineux Est-il approprié de mettre ...?

Le motif de masque "111" (en bas à droite de l'image ci-dessus) a été sélectionné avec le moins de buts cette fois. Ensuite, appliquez réellement le masque sélectionné.

Calculer les informations de format

Remplissez la dernière partie restante. Reste la partie appelée «information formelle».

Les deux suivants sont inclus dans les informations de format.

• Niveau de correction d'erreur (2 bits) 10
• Numéro de modèle de masque sélectionné (3 bits) 111

Le niveau de correction d'erreur est «10» car j'ai sélectionné «H» cette fois. Pour les autres niveaux, reportez-vous à la norme (P.54, Tableau 12).

Le code BCH est calculé sur la base de ces informations à 5 bits «10111». Il s'agit également d'un type de code de correction d'erreur similaire au code RS. Vous pourriez penser: "Est-ce encore des mathématiques?", Mais ce n'est pas grave parce que c'est le même flux de processus et c'est assez facile.

Code BCH

Dans ce cas également, les fonctions I (x) et G (x) sont définies et les problèmes suivants sont résolus.

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 \\
Dans\\
P(x) = x^{N-K}I(x) \quad mod \quad G(X) \\
Demander

Chaque coefficient de I (x) est un tableau de bits de niveau de correction d'erreur et de numéro de masque. Heureusement cette fois, tous les coefficients sont 0 ou 1, donc c'est très facile à calculer.

Si vous n'écrivez que le résultat, vous obtiendrez «0000101001». Connectez-le après le 5 bits existant et prenez le XOR avec le masque spécifié 101010000010010 pour terminer.

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

Les valeurs correctes sont répertoriées à la page 76, tableau C.1 de la norme, mais elles sont en bon accord. C'était bien.

Placer les informations de format dans la masse

Enfin, écrivez les 15 bits des informations de format que vous venez d'obtenir dans la partie encore vide.

Vous devez écrire la même chose à deux endroits différents.

Créer une image de code QR

Enfin, créez une image et vous avez terminé. Il est plus simple de créer une image de même taille et de l'agrandir sans interpolation. N'oubliez pas d'ajouter au moins 4 carrés de zone tranquille (marge blanche) autour d'elle.

Achevée! !! C'était un long chemin à parcourir!

Contrôle de fonctionnement

Au fait, pouvez-vous lire ce que vous avez fait?

** C'est fait **.

Je l'ai essayé sur iPad, tablette Android et Logiciel gratuit pour Windows, mais ils ont tous lu sans problème. .. Je ne m'attendais pas à ce que ça se passe si bien.

Au fait, j'ai oublié de masquer les informations de format au début et de les sortir telles quelles, mais elles les lisent toujours correctement. Le côté décodeur fait-il de son mieux pour y remédier?

Impressions

En expérimentant le processus de création d'un code QR, l'article "Lire le code QR manuellement" que j'ai lu une fois et j'ai incliné la tête disait également "Ah, J'ai pu sentir que je pouvais le faire d'une manière ou d'une autre.

J'espère que vous avez lu cet article et que vous pensez que le code QR est étonnamment facile à créer.

Le code source (le langage est Python) créé cette fois-ci est devenu un peu long, il se trouve donc sur un site externe (Github). Veuillez faire bouillir ou cuire au four. (Je pense que ce serait bien de mettre le code QR sur une carte de visite, comme P) Générateur de code QR qui affiche "Izumi Oishi"

Lien de référence

Je publierai les sites auxquels j'ai fait référence et les liens que je recommande de lire en relation avec cet article.

Code QR en général

Essayez de créer un code QR : Le site auquel j'ai le plus fait référence cette fois QR Code.com : Site de Denso qui a développé le code QR. Je peux à peu près comprendre le code QR Code QR Deep Dive-data coding or error correction- : La page que j'ai trouvée quand j'ai presque fini d'écrire cet article (l'obscurité des phares). J'aurais dû chercher l'article dans Qiita avant d'écrire, mais je ne comprends pas pourquoi je l'ai manqué. Creating a QR Code step by step : (Anglais) Un excellent site qui illustre le processus de création d'un code QR étape par étape avec des informations détaillées.

Code RS lié

Galoa et élargi : Article facile à comprendre sur le corps Galois 1 Cours corporel Galoa : Article facile à comprendre sur le corps Galois 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 ) : La formule utilisée dans l'exemple d'explication est la même que celle utilisée dans le code QR, elle est donc très utile. Reed–Solomon codes for coders : Bien qu'il soit en anglais, il est expliqué en général, donc si vous pouvez le lire, veuillez le faire

Autre

CRC-32 : Ceci est une diapositive d'explication sur CRC-32. Le CRC, qui est souvent utilisé pour vérifier la corruption des données, est également une technologie qui utilise Galois. Si vous le lisez ensemble, vous approfondirez peut-être votre compréhension. Qu'est-ce que Oishi Izumi (Delicious Izumi) [Encyclopédie Pixiv] : Pour ceux qui sont Izumi Oishi