View
3
Download
0
Category
Preview:
Citation preview
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
Recommended