# Réalisation d'un QR Code :page_with_curl: ###### Armand VANEL, Renaud VISIOLI, Sébastien LUONG ###### ESIEE PARIS E2 ## Introduction Dans ce rapport, nous allons expliquer comment réaliser un QR Code ``version 1`` de A à Z. Pour ce faire, nous choisirons de coder le message suivant : **LOVEMATHEMATIQUES**. Nous allons suivre ces 6 étapes : 1. Analyser les données à encoder et paramétrer le niveau du code correcteur. 2. Convertir les caractéristiques de données dans un flux de bits. 3. Implémenter la correction des erreurs. 4. Insérer les données avec le code correcteur dans la matrice. 5. Générer la matrice et évaluer le résultat retourné. 6. Générer le QR Code au format image. --- ## Etape 1 : Analyse des données Avant de commencer, il faut savoir qu'il y a quatre principaux modes d'encodage de texte : * Numérique * Alphanumérique * Octet * Kanji Tous ces modes d'encodage transforment notre message en une chaîne de bits : 1 et 0. Néanmoins, chacun utilise une méthode différente de conversion. Quelque soit le mode, le but est d'obtenir la plus petite chaîne de bits possible. En effet, chaque version a une capacité maximale en fonction de l'encodage utilisé. De plus, le niveau de correction d'erreur restreint davantage la capacité. Dans notre cas : ![](https://i.imgur.com/tHJkivB.png) Comme notre message **LOVEMATHEMATIQUES** contient 17 caractères, nous décidons de l'encoder en `binaire` (octet) avec un niveau de correction d'erreur `LOW`. --- ## Etape 2 : Codage des données Maintenant que nous avons choisi le mode d'encodage approprié, il est temps d'encoder notre texte. Nous nous retrouvons finalement avec une chaîne de 19 octets. Mais avant d'arriver à ce résultat, il faut suivre quelques étapes : ### 1. Ajout d'un indicateur de mode Chaque mode d'encodage est identifié par un indicateur de mode à quatre bits. Les données codées doivent commencer par cet indicateur qui spécifiera le mode utilisé. ![](https://i.imgur.com/dDtytPk.png) Rappel : nous encodons en `binaire`. Nous aurons donc : :::success **0100** ::: ### 2. Ajout de l'indicateur de nombre de caractères Nous devons ensuite spécifier la longueur du message à encoder, dont le nombre de bits dépend de la version du QR-Code. Cet indicateur de nombre de caractères doit être placé après l'indicateur de mode. Ci-dessous, nous retrouvons la variation de ce dernier pour chaque mode et version : ![](https://i.imgur.com/cVhSq8k.png) Notre message est composé de 17 caractères. Compte tenu de la version de notre QR Code et de son mode d'encodage, l'expression binaire équivalente est **10001**. Les données codées sont sur 8 bits, or nous n'en avons que 5. Il suffit alors d'ajouter trois zéros en `MSB`. Nous obtenons : :::success **00010001** ::: ### 3. Encodage du message Il nous faut par la suite convertir notre message en `binaire` sous forme d'octet. Nous avons utilisé l'outil suivant : [Cyberchef](https://gchq.github.io/CyberChef/#recipe=To_Binary('Space')&input=TE9WRU1BVEhFTUFUSVFVRVM), et obtenons alors : | Lettre | Octet (binaire) | | ------ | --------------- | | L | 01001100 | | O | 01001111 | | V | 01010110 | | E | 01000101 | | M | 01001101 | | A | 01000001 | | T | 01010100 | | H | 01001000 | | E | 01000101 | | M | 01001101 | | A | 01000001 | | T | 01010100 | | I | 01001001 | | Q | 01010001 | | U | 01010101 | | E | 01000101 | | S | 01010011 | Soit : :::success **01001100 01001111 01010110 01000101 01001101 01000001 01010100 01001000 01000101 01001101 01000001 01010100 01001001 01010001 01010101 01000101 01010011** ::: ### 4. Division en octet (et ajout d'octets de remplissage si nécessaire) Notre chaîne de bits est présentement composée de l'indicateur de mode, de l'indicateur de nombre de caractères et des bits de données. Mais il faut que ces données binaires soient découpées par octets, soit 8 par 8. Ces chaînes de 8 bits sont appelées ``codewords``. #### a. Détermination du nombre de bits requis pour notre QR-Code Pour cela nous nous reportons au tableau suivant : ![](https://i.imgur.com/IfZ4wKJ.png) Rappelez-vous : nous avons choisi de réaliser un QR Code de ``version 1`` encodé en ``binaire``. Par conséquent, le nombre total de bits requis est 152, soit 19 octets. #### b. Ajout d'un Terminator Un Terminator de quatre 0 maximum doit être ajouté à la fin de notre chaîne. > Si le nombre de 0 pour atteindre le nombre de bits requis est inférieur à 4, ajoutez uniquement les 0 nécessaires. A partir de notre exemple : | Indicateur de mode | Indicateur de nombre de caractère | Données encodées | Terminator | | ------------------ | --------------------------------- |:------------------------------------------------------------------------------------------------------------------------------------------------------------:| ---------- | | **0100** | **00010001** | **01001100 01001111 01010110 01000101 01001101 01000001 01010100 01001000 01000101 01001101 01000001 01010100 01001001 01010001 01010101 01000101 01010011** | **0000** | Nous procédons ensuite à la découpe en ``MSB`` de notre code pour n'obtenir que des octets. Ceux-ci seront nos ``codewords``: :::success **01000001 00010100 11000100 11110101 01100100 01010100 11010100 00010101 01000100 10000100 01010100 11010100 00010101 01000100 10010101 00010101 01010100 01010101 00110000** ::: Nous pouvons voir que nous avons bien nos 152 bits, soit les 19 octets que nous voulions. >Si ce n'était pas le cas, il aurait fallu remplir nos octets manquants pour atteindre la longueur optimale. Pour cela, il existe deux octets spécifiques : **11101100** (Code ASCII 236) et **00010001** (Code ASCII 17) que nous rajoutons alternativement jusqu'à ce que nous complétions les bits requis. Comme ce n'est pas notre cas, nous pouvons donc passer à l'étape suivante. --- ## Etape 3 : Implémentation de la correction des erreurs Nous devons maintenant calculer les ``codewords`` de correction d’erreurs. En effet, l'un des points forts du QR Code est son système de correction d’erreurs reposant sur le code de Reed-Solomon. > Il permet une bonne lecture du QR Code même si celui-ci est endommagé : rayures, graffiti, page pliée, etc. Comme chaque version et niveau de correction d'erreurs ont leur propre nombre de ``codewords`` à générer, nous nous référons au tableau suivant : ![](https://i.imgur.com/IfZ4wKJ.png) Dans notre cas, il faut donc calculer 7 octets de ``codewords`` de correction d'erreurs. Pour cela, il nous faut : * Un polynôme générateur * Un polynôme message Il faut comprendre que le processus de Reed-Solomon consiste à effectuer une division polynomiale longue, autrement dit, diviser un polynôme par un autre polynôme. ### 1. Le polynome générateur Nous obtenons le polynôme générateur en effectuant : **(x - α^0^ ) * ... * (x - α^n-1^ )**, où ``n`` est le nombre de mots du code de correction d'erreurs devant être généré et où ``α (alpha)`` est égal à 2. > Nous travaillons avec l'arithmétique modulo 2, cela signifie que nous utilisons GF(256) . Finalement, le polynôme générateur est : :::info **g(x) = α^0^x^7^ + α^87^x^6^ + α^229^x^5^ + α^146^x^4^ + α^149^x^3^ + α^238^x^2^ + α^102^x + α^21^.** ::: > Le détail de nos calculs **[ici](/bRl7fiInRDuZ0enn25Jitg)**. ### 2. Le polynome message Ici c'est très simple, il suffit de convertir nos 19 octets obtenus précédemment en décimal. Nous utilisons une nouvelle fois notre ami [Cyberchef](https://gchq.github.io/CyberChef/#recipe=From_Binary('Space')To_Decimal('Space',false)&input=MDEwMDAwMDEgMDAwMTAxMDAgMTEwMDAxMDAgMTExMTAxMDEgMDExMDAxMDAgMDEwMTAxMDAgMTEwMTAxMDAgMDAwMTAxMDEgMDEwMDAxMDAgMTAwMDAxMDAgMDEwMTAxMDAgMTEwMTAxMDAgMDAwMTAxMDEgMDEwMDAxMDAgMTAwMTAxMDEgMDAwMTAxMDEgMDEwMTAxMDAgMDEwMTAxMDEgMDAxMTAwMDA). Le résultat est : **65 20 196 245 100 84 212 21 68 132 84 212 21 68 149 21 84 85 48** Ces nombres correspondent en fait aux coefficient du polynôme grafittis, message. Donc celui-ci est : :::info **65x^18^ + 20x^17^ + 196x^16^ + 245x^15^ + 100x^14^ + 84x^13^ + 212x^12^ + 21x^11^ + 68x^10^ + 132x^9^ + 84x^8^ + 212x^7^ + 21x^6^ + 68x^5^ + 149x^4^ + 21x^3^ + 84x^2^ + 85x^1^ + 48** ::: ### 3. Place à la division Il est maintenant temps de diviser le polynôme message par le polynôme générateur. Voici les étapes de division en prenant en compte l'arithmétique GF(256) : 1) La première étape consiste à multiplier le polynôme générateur par le terme principal du polynôme message. Le but étant de supprimer le terme de plus haut degré du polynôme message 2) La deuxième, est de XORé le résultat par le polynôme message. 3) Répéter ces deux étapes le même nombre de fois qu’il y a de ``codeword`` dans le polynôme message (dans notre cas, nous le faisons donc 19 fois). Nous avons écrit cet [algorithme](/SsOgNytOTX6Uiq_ELzkXfA), on l'éxecute et on obtient dans un fichier les résultats suivants : [résultats](/Dr95UqWbSDOr36akYQzW5g). On obtient : **3 20 171 38 8 33 134**, il ne reste plus qu'à faire la conversion de ces nombres en binaire (toujours grâce à [Cyberchef](https://gchq.github.io/CyberChef/#recipe=From_Decimal('Space',false)To_Binary('Space')&input=MyAyMCAxNzEgMzggOCAzMyAxMzQ)) : :::success La conversion en binaire nous donne : **00000011 00010100 10101011 00100110 00001000 00100001 10000110** ::: Les ``codewords`` de correction d'erreur ont maintenant été générés. > Nous avons également fait un algorithme qui réalise les trois prmières étapes. Vous pouver y acceder [ici](/ZPf0LtJOSbazTNaqE4ExSQ). --- ## Etape 4 : Insertion des données avec le code correcteur dans la matrice Avant de placer nos données dans notre matrice, il faut se renseigner sur la structure d'un QR-Code. Commençons tout d'abord par placer les éléments obligatoires. >Pour rappel : nous réalisons un QR-Code de ``version 1``, c'est-à-dire de taille 21x21 modules. Il est logique que les insertions de données diffèrent selon les versions de QR-Code. ### 1. Motifs de positionnement (finder patterns) Un QR-Code contient trois motifs de positionnement identiques disposés aux deux coins supérieurs et en bas à gauche. Chaque motif est composé de trois carrés concentriques superposés : * Le plus grand de 7 x 7 modules en noir * Le second de 5 x 5 modules en blanc * Le dernier de 3 x 3 modules en noir ### 2. Les séparateurs : Les séparateurs sont constitués de modules blancs uniquement, ils servent à distinguer les motifs de positionnement de la zone d’encodage. ### 3. Les timing paterns : Les timing paterns sont composés de modules blancs et noirs en alternance (le premier et le dernier module sont toujours en noir). Il y a deux timing paterns : * un horizontal (en haut à partir de la colonne 6). * un vertical (à gauche à partir de la ligne 6). Ils permettent au lecteur de percevoir le contraste entre les modules blans et les modules noirs. ### 4. Un simple module noir C'est un module noir unique qui est toujours placé au même endroit (voir image ci-dessous). ### 5. Motifs d'alignement (alignment paterns) Ces motifs sont formés de la même manière que les motifs de positionnement. Cependant, ils sont plus petits (5 x 5 noirs, 3 x 3 blancs, 1 x 1 noir). Leur nombre et leur emplacement dépendent de la version du QR-Code. > Ils servent notamment à lire le QR-Code même si celui-ci est déformé, par exemple sur un objet 3D ou sur une feuille courbée. > Comme nous travaillons sur une ``version 1``, pas besoin d'en placer. Voici l'allure général de notre QR-Code : ![](https://i.imgur.com/8t9LPe6.png) ### 6. Placement des ``codewords`` L’espace restant doit maintenant contenir toutes les données. Mais il y a un sens de lecture précis qui dépend de la version du QR-Code. Dans notre cas, voici la manière dont les données sont placées : ![](https://i.imgur.com/Ubw1HbO.png) #### A. Octets de données Pour rappel, voici ce que nous avions obtenus à l'étape 2 (Codage des données) : :::info **01000001 00010100 11000100 11110101 01100100 01010100 11010100 00010101 01000100 10000100 01010100 11010100 00010101 01000100 10010101 00010101 01010100 01010101 00110000** ::: Il est possible d'aller plus loin dans la description de ces données : * Les 4 premiers bits représentent notre type d'encodage. * Les 8 suivants représentent la taille de notre message. * Les 132 qui suivent correspondent aux lettres de notre message encodés en binaire sur huit bits. * Et enfin les 4 derniers représentent le terminator. #### B. Octets de correction d'erreurs Pour rappel, voici ce que nous avions obtenus à l'étape 3 (Implémenter la correction des erreurs) : :::warning **00010101 01000100 10010101 00010101 01010100 01010101 00110000** ::: #### C. Informations Les informations sont constituées d’une séquence de 15 bits comprenant 5 bits de données et 10 bits de correction d’erreur. Les deux premiers bits indiquent le niveau de correction d’erreurs suivant ce tableau : | Niveau de correction d’erreur | L | M | Q | H | | -------- | -------- | --- | --- | -------| | **Indicateur binaire** | **01** | **00** | **11** |**10** | Les 3 bits suivants contiennent la référence du motif de masquage des données : ![](https://i.imgur.com/IkxxOL1.png) Pour calcluer ces 15 bits d'information il faut utiliser le code BCH. > Le code BCH (reprenant les initiales de ses inventeurs : Bose, Ray-Chaudhuri et Hocquenghem1) est un code correcteur utilisé pour corriger des erreurs aléatoires. Nous avons écrit cet [algorithme](/X1xrft9tQW-0L31BJPdYKA), voici les [résultats](/8ntYUabAQXGbUhfMOvNiSQ) de notre code. Grâce à notre code nous obtenons 15 bits d'information avec le masque n°0 : :::danger **111011111000100** ::: Il reste une dernière étape pour les informations : leurs emplacements. Il faut placer ce que nous avons obtenu ci-dessus en ``LSB`` : ![](https://i.imgur.com/vjiSZFa.png) ### 7. Place au résultat brut de notre matrice Après avoir compris comment insérer nos données et comment était construit un QR-Code de ``version 1`` de niveau ``LOW`` de correction avec le masque 0, voici à quoi ressemble notre matrice : ![](https://i.imgur.com/B65nV95.png) --- ## Etape 5 : Masquage des données Maintenant que les données ont été placées dans la matrice, il faut determiner le motif de masquage le plus adapté. Le but de cette étape est de rendre la lecture du QR-Code plus facile ; il ne faut pas avoir des modules noirs ou blancs juxtaposés sur une trop grande zone. Comme vous vous en doutez, il existe huit types de masques que nous avons eu l'occasion de voir durant l'étape précédente. Voici à quoi ressemble les motifs de masquage de données : ![](https://i.imgur.com/CgKSNea.png) Pour appliquer un masque on peut suivre les formules de chaqun d'entre eux, ou bien XORer la matrice brute avec un masquage de donnés. Une fois qu’un modèle de masque a été appliqué (il ne doit être appliqué qu’aux modules de données) à notre matrice, il reçoit un score de pénalité basé sur quatre conditions d’évaluation : 1. La première règle donne au QR-Code une pénalité pour chaque groupe de cinq modules consécutifs de même couleur ou plus. 2. La deuxième règle donne au QR-Code une pénalité pour chaque zone 2x2 de modules de même couleur dans la matrice. 3. La troisième règle donne au QR-Code une pénalité importante s’il y a des modèles qui ressemblent aux modèles de finder (voir ci-après). 4. La quatrième règle donne au QR-Code une pénalité si plus de la moitié des modules sont noirs ou blanc, la pénalité augmente avec la différence. Ensuite c'est le modèle qui a le plus petit score qui est utilisé pour la sortie finale. Prenons exemple, en appliquant le masque n°0, sur notre matrice : ### 1. Application de la première condition Reprenons cette règle : *une pénalité est attribuée pour chaque groupe de cinq modules de même couleur ou plus d’affilée (ou colonne).* Nous attribuons une pénalité de **3pts** s'il y a cinq modules consécutifs de la même couleur. Si les modules de même couleur continuent après les cinq premiers, il faut ajouter **1pts** de pénalité pour chaque module supplémentaire. Regardons sur notre matrice, nous appliquons cette première conditons verticlament et horizontalement : ![](https://i.imgur.com/PxvoDt2.png) :::info Nous obtenons un total de : **129 + 86 = 215pts** de pénalités ::: ### 2. Application de la deuxième condition Reprenons cette règle : *une pénalité est attribuée pour chaque zone 2x2 de modules de même couleur dans la matrice.* Nous attribuons une pénalité de **3x(l-1)x(L-1)pts**, dès qu'il y au moins une zone de 2x2 de modules de même couleur. Par exemple si nous avions une zone de 3x3 module de même couleur, la pénalité serait calculée de la façon suivante : **3x(3-1)x(3-1) = 12pts**. Regardons sur notre matrice comment s'applique cette règle : ![](https://i.imgur.com/6dG8cMb.png) :::info Nous obtenons un total de : **114pts** de pénalités. ::: ### 3. Application de la troisième condition Reprenons la troisième règle : *une pénalité est attribuée s’il y a des modèles qui ressemblent aux modèles de finder* Nous attribuons une pénalité de **40pts** à chaque fois que nous trouvons les motifs suivants : ![](https://i.imgur.com/HMDwkNL.png) Regardons sur notre matrice comment s'applique cette règle : ![](https://i.imgur.com/m6O7L6S.png) :::info Nous obtenons un total de : **3 x 40 = 120ts** de pénalités. ::: ### 4. Application de la quatrième condition Reprenons la dernière règle : *une pénalité est attribuée si plus de la moitié des modules est noir ou blanc, avec une pénalité plus importante pour une différence plus grande.* Cette étape est simple, elle est basée sur le rapport entre les modules noirs et blancs. Mais il faut suivre quelques étapes pour comprendre comment attribuer les points de pénalités : * Compter le nombre de module total : **21x21 = 441** * Compter le nombre de modules noirs : **226** * Calculer le pourcentage de modules noirs **(226/441)x100 = 51.24** * Déterminer les multiples de 5 qui précedent et qui suivent le pourcentage : **50 et 55** * Soustraire 50 aux multiples trouvés : **|50-50| = 0 et |55-50| = 5** * Diviser les résultats trouvés par 5 : **0/5 = 0 et 5/5 = 1** * Enfin prenez le plus petit des deux résultats trouvés précédemment et multipliyez-le par 10 : **0x10 = 0** :::info Par consquent nous attribuons **0pts** de pénalité. ::: :::success Le score du masque 0 est alors de : **215+114+120+0 = 449pts** ::: Comme vous l'avez sans doute compris, il faut réaliser ce que nous venons de faire huit fois, pour faciliter ce travail nous avons écrit un [algorithme](/qNXC0_IBT7qZR5iLYPXpog). On obtient alors les [résultats](/Nn3xrA87Q2inGu5GpF7T2g) suivants : ![](https://media.discordapp.net/attachments/435131061492776972/789867109521293343/unknown.png) Une fois les 4 pénalités appliquées sur chacun de nos QR-Code avec des masques différents, nous nous retrouvons avec des écarts assez distincts pour les résultats finaux. Comme on peut l'observer, ci-dessus le masque qui a obtenu le plus petit score et donc le plus optimal est le suivant : **Le masque 1** avec un score de 303. :::success On garde le **Masque n°1.** ::: --- ## :checkered_flag:Etape 6 : Générer le QR Code au format image. En appliquant tout ce que nous avons calculé, c'est-à-dire la conversion de nos données en flux de bytes, le calcul et l'implémentation de nos codes correcteurs ainsi que l'application du masque le plus optimale ; on obtient le **QR-Code** suivant : ![](https://media.discordapp.net/attachments/435131061492776972/788728373718417488/unknown.png) Nous venons donc de réaliser ensemble un QR-Code de ``version 1`` et de niveau de correction ``LOW``, en encodant le message **LOVEMATHEMATIQUES** en mode binaire. ## Sources Pour réaliser ce rapport nous nous sommes aidés des sources suivantes : ### Les sites : https://www.thonky.com/qr-code-tutorial/introduction https://sitelec.org/cours/abati/qrcode/solomon.html https://sitelec.org/cours/abati/qrcode/bch.html http://cerig.pagora.grenoble-inp.fr/memoire/2012/codes-2D.htm ### Les pdf : **Polycopié du cours de Maths Discrètes ESIEE PARIS E2** https://sitelec.org/download_page.php?filename=cours/abati/qrcode/qr_code.pdf http://remy-manu.no-ip.biz/C++/PDF/QRCode.pdf ### Vidéos : https://www.youtube.com/watch?v=142TGhaTMtI https://www.youtube.com/watch?v=N2Wz1T4drsg https://www.youtube.com/watch?v=KA8hDldvfv0&t=689s