CODE BARRES ET QR CODE

Rencontre de l’Orme 2013 - Marseille

Jean-Baptiste CIVET

Code Barres et QR Code

Au départ

Un QR Code floral….

2

Code Barres et QR Code

Oui mais voilà…

3

Code Barres et QR Code

Avant de comprendre la 2D, petit détour par la 1D

4

Le code barres se décode facilement mais ne résiste pas à la dégradation

Code Barres et QR Code

Exemple : le code barre 39

5

Il s’agit d’un code alphanumérique.

Nous pouvons coder 26 lettres majuscules et 10 chiffres.

L’ensemble est complété de 8 caractères spéciaux.

Pour ce code-barres, il n’y a pas de limite de longueur de

chaîne de caractères.

Code Barres et QR Code

Exemple : le code barre 39

6

_ chaque caractère est composé de 9 bits. Parmi ces 9 bits, 3

et uniquement 3 sont toujours égaux à 1.

_ Un bit est représenté alternativement par une barre noire ou

un espace blanc. Le 1er bit est une barre noire, le 2e un

espace, le 3e une barre etc.

_ S’il s’agit d’un bit à 1, on le représentera par une barre ou

un espace large. Inversement s’il s’agit d’un bit à 0, on le

représentera par une barre ou un espace étroit

_ Une barre large est deux fois plus grande qu’une barre

étroite. Selon la précision souhaitée, on peut aller jusqu’à une

largeur trois fois plus importante.

Code Barres et QR Code

Exemple : le code barre 39

7

La lettre A est codée selon la série de bits suivante :

100001001

Chacune des caractéristiques précédentes est respectée :

_ on démarre par une barre noire.

_ elle est large puisqu’il s’agit d’un bit à 1.

_ le bit suivant est donc un espace.

_ il est étroit puisqu’égal à 0

On remarquera qu’il y a bien seulement 3 éléments larges dans ce dessin.

Du fait de l’utilisation de 9 bits, chaque caractère démarre et finit par une

barre noire.

Code Barres et QR Code

Exemple : le code barre 39

8

Finalement, on se rend compte qu’on peut facilement coder un générateur de code barres

_ il nous faut connaitre l’alphabet du CB39

_ il faut savoir que toute chaine doit démarrer et finir par « * »

_ il faut avoir dessiner des rectangles avec la GDI de son logiciel de programmation

Code Barres et QR Code

Et les QR Codes dans tout ça ?

9

Une référence : la norme ISO 18004 – 120 pages – en Anglais – 70 variations

Version 1 à 21 modules

Des marqueurs de reconnaissance

Des timers

Des zones d’informations

Code Barres et QR Code

Et les Mathématiques dans tout ça ?

10

Un carré de 21 modules de côté,

Théoriquement, 441 bits, c'est-à-dire 55 octets.

La version 70, un carré de 177 modules de côté.

Marqueurs de reconnaissance 202 modules.

Modules réservés pour la transcription d’information de Format et Version, soit 31 modules

supplémentaires.

Pour l’instant, nous avons donc 441 – 202 – 31 modules soit 208 modules de disponibles c'est-

à-dire 208 bits c'est-à-dire en réalité 26 octets (contre 55 au départ).

Code Barres et QR Code

Et les Mathématiques dans tout ça ?

11

Le choix d’un alphabet 8 bits (c'est-à-dire 1 octet) permet de coder 256 caractères différents.

En revanche, l’usage d’un alphabet « alphanumérique » à 30 symboles permet de coder

davantage de caractères sur un même nombre de bits que l’alphabet ASCII.

Exemple :

pour coder 2 caractères avec l’alphabet ASCII, 16 bits seront nécessaires

pour coder 2 caractères avec l’alphabet Alphanumérique, 11 bits seront nécessaires

Rappelons que nous ne disposons que de 208 bits c'est-à-dire 26 octets pour coder notre

message.

Code Barres et QR Code

Et les Mathématiques dans tout ça ?

12

Dernier point et non des moindres, le niveau de résistance à la dégradation de notre

QRCode !

Il y a 4 niveaux de correction d’erreur possibles, décrits dans la norme des QRCodes,

répertorié sous les initiales L, M, Q, H (pour s’en souvenir : Low quality, Médium quality,

Quality, High quality).

Nous allons opté pour la plus haute norme de correction d’erreurs disponible, à savoir la

norme H. Ainsi sur les 26 octets disponibles, 9 octets seront dédiés au message à coder et 17

octets seront dédiés à la correction d’erreur.

A ce stade de notre balade, nous savons que

Le QR Code est donc en version 1-H, soit 9 octets pour le codage

L’alphabet retenu est l’alphabet ASCII sur 8 bits (1 octet par caractère)

Code Barres et QR Code

Dans le calcul des blocs d’erreur…

13

Vous avez probablement déjà abordé en classe le principe de la clé de contrôle du numéro

INSEE, clé qui est issue dela différence de 97 et du reste de la division euclidienne par 97du

numéro INSEE à 13 chiffres.

Exemple :

si le n°INSEE suivant existait, 1234567891011, sa clé de contrôle vaudrait 93

En effet 1234567891011 = 12727504031 * 97 + 4 et 97 – 4 = 93

Pour notre projet, le système de code d’erreur reprend le principe du reste de la division sauf

que les nombres entiers sont remplacés par des polynômes dont les coefficients seront tous

compris entre 0 et 255. Nos opérations ne seront donc pas tout à fait l’addition et la

multiplication que vous connaissez. Plutôt un travail de calcul d’exposant et de « XOR ». Il

existe une règle de base dans cet univers : a^255 = 1. C’est ce que l’on appelle le code

d’erreur Reed Solomon.

Code Barres et QR Code

Dans le calcul des blocs d’erreur…

14

Initialisation

G(x) =

x^17+a^43*x^16+a^139*x^15+a^206*x14+a^78*x^13+a^43*x^12+a^239*x^11+a^1

23*x^10+a^206*x^9+a^214*x^8+a^147*x^7+a^24*x^6+a^99*x^5+a^150*x^4+a^39*

x^3+a^243*x^2+a^163*x+a^136

Ce polynôme nous est donné par la théorie Reed Solomon et la norme ISO qui décrit le

fonctionnement des QR Codes où a est tel que a^255 = 1

F(x) est un polynôme de degré 25 dont les coefficients f25 à f17 sont nos 9 octets exprimés en

décimal du message que nous souhaitons codé. Voir chapitre 1.

Nous allons chercher R(x) le reste de la division de F(x) par G(x)

Code Barres et QR Code

Un algorithme simple à mettre en oeuvre

15

for index=1,9 do

if coeff_f1[index] ~= 0 then

exposant = table_entier[coeff_f1[index]] --conversion du coefficient en exposant

for k=1,degre_g+1 do

coeff_f2[k+index-1] = table_exposant[(exposant+exposant_g[k]) % 255 + 1]

end

for k=1,26 do

coeff_f2[k]=XOR(coeff_f1[k],coeff_f2[k])

end

for k=1,26 do

coeff_f1[k] = coeff_f2[k]

end

end

end --end for index

Code Barres et QR Code

On y est presque…ou pas

16

A ce stade, on a 9 octets de message et 17 octets issus du code RS

On va placer des entêtes dans notre QR Code

L : 01, M : 00, Q : 11 et H : 10

Le n° de masque parmi 8 possibles (sur 3 bits)

Correction d’erreur BCH de paramètres (15,5)

Code Barres et QR Code

On y est presque…ou pas

17

Qualité H (10) et Masque 3 (011)

Message de départ : 10 011

Polynôme de départ :f(x) = x^14+x^11+x^10

Polynôme de référence, imposé : g(x) = x^10+x^8+x^5+x^4+x^2+x+1

Polynôme restant en divisant f(x) par g(x) : r(x) = x^8+x^7+x^6+x

Code BCH correspondant : 0111000010

Message de Format avant masquage (on concatene) : 10 011 0111000010

XOR binaire, imposé : 10 011 0111000010 XOR 101010000010010

Message à recopier dans la zone grisée : 001100111010000

Code Barres et QR Code

Ca y est, on dessine….matriciellement

18

Code Barres et QR Code

Ca y est, on dessine….matriciellement

19

Code Barres et QR Code

La nature a horreur du vide !

20

Code Barres et QR Code

XOR à la rescousse !

21

XOR

ENTREE 1 ENTREE 2 SORTIE

0 0 0

0 1 1

1 0 1

1 1 0

Message Non Masqué XOR Masque = Message Masqué

Message Masqué XOR Masque = Message Non Masqué

Code Barres et QR Code

Rappel et exemple !

22

Le 1er module en haut à gauche a pour coordonnées (1,1).

(1+ 1) mod 2 est effectivement égale à 0 donc on renvoie 1 donc

on noircit le module sur le masque.

Code Barres et QR Code

XOR à la rescousse ! Le retour !

23

XOR =

XOR =

Code Barres et QR Code

Quelques exemples de masques…

24

Code Barres et QR Code

Quelques exemples de masques…

25

Code Barres et QR Code

Finalement…

26

Code Barres et QR Code

Merci…

27