Une création mathématique puissante : le code-barres

Introduction

Qu'est-ce qu'un code-barres et à quoi sert-il ?

Les codes-barres, aussi discrets soient-ils, sont fondamentalement indispensables dans le fonctionnement de nos sociétés. Il y a 50 ans, avant sa démocratisation dans le commerce et l'industrie en 1974, le seul moyen de gérer les stocks était de fermer la boutique, et compter à la main, rayon par rayon les stocks de chaque article, et ce chaque mois. Aujourd'hui les codes-barres font ce travail à notre place, on les retrouve là où il faut faire de la gestion de stocks : prêts et retours dans une bibliothèque, stocks dans un hypermarché, quantité de production dans une usine...

On estime même à plus de 10 milliards le nombre de codes-barres scannés par jour.

Essayons de comprendre plus en détail ce qu'est un code-barres.

C'est tout simplement une alternance de 0 et de 1 représentée en noir et blanc formant une image qui permet d'encoder une information. En effet cette alternance de 0 et de 1 forme un code binaire qu'on peut associer à une séquence de chiffres, de lettres ou de symboles.

Quelques types de codes-barres

Le code-barres EAN/UCP

EAN-13, GTIN-13 :: Numéro d'article européen :: Numéro d'article sur le  commerce mondial (Global Trade Item Number) description de symbology de code  à barres

Le code-barres EAN (European Article Numbering)(dont UCP est l'équivalent aux Etats-Unis) est celui utilisé dans les magasins pour gérer les stocks. Il en existe plusieurs types :

  • EAN 13 : le code-barres le plus classique utilisé dans tous les supermarchés attribue de manière unique et universel 13 chiffres à un produit. De cette façon le produit peut être identifié avec un scanner de n'importe quel pays du monde car les 13 chiffres du produit sont dans une base de données.
  • EAN 128 : son nom vient de sa capacité à stocker 48 caractères des 128 caractères disponibles dans le code ASCII, il dépasse ainsi les limites de l'EAN 13 qui pouvait stocker uniquement 12 chiffres (le treizième étant la clé de contrôle) et aucune lettre.

La DataMatrix

Datamatrix — Wikipédia

L'idée derrière ce code-barres était de passer d'une dimension à deux dimensions pour augmenter la quantité d'informations stockable dedans. Le DataMatrix est reconnaissable grâce à ses deux barres pleines en bas et à gauche .

Cela permet de tracer un objet, soit lors de sa fabrication, soit lors de la livraison. On en voit notamment dans les cartons de colis et les boîtes de médicament.

Il contient la référence de l'objet, et chaque fois qu'il est flashé, on sait alors qu'il a franchi une étape. C'est grâce à cela qu'on peut suivre l'état d'un colis, on voit simplement chaque fois qu'il a été flashé.

Le QR Code

QR Codes - Dizziweb - Agence web digitale

Le QR Code est un DataMatrix amélioré, il peut contenir 7000 chiffres. Son principal avantage est la redondance de l'information stockée dedans. Cette redondance le rend moins sensible à la casse. En effet là où un code-barres EAN (le code-barres classique) peut être rendu inutilisable en un coup de crayon, le QR restera parfaitement lisible. C'est d'ailleurs pour cette raison qu'il est possible sur certains site de créer un QR Code avec un logo au milieu.

Avec un QR Code on peut ainsi encoder une carte de visite, un numéro de téléphone, un envoi d'email ou de sms, une carte de restaurant, un réseau wifi...

Il en existe pleins d'autres, que je vous invite à découvrir en cliquant sur ce bouton :


Nous allons maintenant nous intéresser plus particulièrement au fonctionnement des codes-barres EAN.

Codage graphique de l'information

Code-barres EAN (European article numbering):

Le numéro EAN identifie des articles ou des unités logistiques de façon unique
il peut être composé de 8, 13 ou 128 chiffres représentés sous forme de séquences de barres noires et blanches formant un code-barres.

EAN 8

les codes EAN 8 sont réservés pour des objets de petites tailles, et se composent de la façon suivante:

  • 2-3 premiers chiffres : pays où est référencée l'entreprise
  • 2-3 chiffres : identificateur de l'entreprise
  • 2 chiffres : identificateur de l'article
  • dernier chiffre : clé de contrôle

EAN 13

Les codes EAN 13 sont utilisés dans la plupart des pays du monde sur les produits de grandes consommation , ils se composent d'une série de 13 chiffres comme suit :

  • 2-3 premiers chiffres : pays où est référencée l'entreprise
  • 4-5 chiffres : identificateur de l'entreprise
  • 5-6 chiffres : identificateur de l'article
  • dernier chiffre : clé de contrôle

Calcul de la clé de contrôle

Comme vu juste avant, le dernier chiffre d'un code EAN est une clé de contrôle, qu'on calcule avec une formule :

Méthode générale

Soit C la clé de contrôle, on va attribuer un poids de 1 pour les rangs impair et de 3 pour les rangs pair.

S = ( somme des chiffres de rang pair) + 3*(somme des chiffres de rang impair)

On calcule R = S modulo 10
Alors on obtient : C= 10-R si R>0, 0 si non.

Exemple

Essayons de retrouver avec la formule le chiffre 2 qui correspond à la clé de contrôle sur l'image ci-dessus :

On a la séquence de 12 chiffres : 4 070071 96707

S = (4+7+0+1+6+0) + 3*(0+0+7+9+7+7) = 108
R = 108 modulo 10 = 8
C = 10-R = 10-2 = 2
On retrouve bien la clé de contrôle qui vaut 2.

Calculateur de clé de contrôle

Quelques codes de pays

Pour vous faire une idée, voici une liste (non exhaustive) des principaux codes de pays, en tant que consommateur cela peut notamment permettre de connaître la provenance des produits achetés.

ChiffresSignification
000 - 019Etats-Unis
300 - 379France
400 - 440Allemagne
450 - 459, 490 - 499Japon
460 - 469Russie
471Taïwan
480Philippines
489Hong Kong
500 - 509Grande-Bretagne
540 - 549Belgique, Luxembourg
690 - 695Chine
700 - 709Norvège
730 - 739Suède
740 - 750Amérique Centrale
754 - 755Canada
800 - 839Italie
840 - 849Espagne
885Thaïlande
893Vietnam
978Livres
3 premiers chiffres d'un code-barre correspondant aux pays

Interprétation graphique des codes-barres selon la norme EAN

Système d'encodage

Pour passer du numéro EAN a un codage en barre et espace ,chaque chiffre du code est associé a une représentation graphique selon des critères bien définis :
(la barre est symbolisé ici avec 1 et l'espace avec 0)

  • la largeur d'une barre/espace est appelé module, chaque chiffre est représenté sur 7 modules.
  • chaque suite de 7 modules forme deux blocs de 1 et deux blocs de 0
  • La marque de début et la même que la marque de fin est : "101"
  • Une marque de séparation (plus longue que les autres barres) est placée au milieu (après le 7eme chiffre pour EAN 13) est : "01010"
  • Chacun des chiffres composant le numéro EAN peut avoir trois représentations différentes selon les tables A,B et C ci-dessus :
chiffre Table ATable BTable C
0000110101001111110010
1001100101100111100110
2001001100110111101100
30111101010001100010
4010001100111011011100
5011000101110011001110
6010111100001011010000
7011101100100011000100
8011011100010011001000
9000101100101111110100
Représentation des chiffres selon la table utilisée

Le choix de la table à utiliser pour les chiffres de 2 à 7 est défini selon le premier chiffre du code-barres de la façon suivante :

Valeur du chiffre 1chiffre 2 chiffre 3 chiffre 4chiffre 5chiffre 6chiffre 7
0AAAAAA
1AABABB
2AABBAB
3AABBBA
4ABAABB
5ABBAAB
6ABBBAA
7ABABAB
8ABABBA
9ABBABA
Table à choisir en fonction du premier chiffre

Pour les chiffres de 8 à 13 , on utilisera la table C.


Nous allons maintenant nous intéresser à la détection et la correction d'erreur lors de la numérisation d'un code-barres.

Détection et correction d'une erreur dans un code EAN 13

Dans cette partie nous allons nous intéresser au cas du code-barres EAN 13, mais le raisonnement présenté ci-dessous pourrait être appliqué à tous les codes-barres EAN.

Pourquoi s'intéresser à la correction et la détection d'erreurs

Avec la quantité de code-barres scannés dans le monde, on comprend légitimement l'importance de réduire au maximum les erreurs. Si un code-barres est mal lu cela peut vous faire payer deux fois le prix d'un article passé en caisse, mais peut être plus embêtant si cela vous arrive avec votre ticket d'avion, votre carte de crédit ou bien votre numéro de sécurité sociale.

Beaucoup de ces codes fonctionnent avec la clé de contrôle décrite précédemment, elle permet une certaine redondance de l'information, puisque le scanner a accès au treizième chiffre, ainsi qu'au calcul lui permettant de trouver ce treizième chiffre.

L'idée naïve pour palier ce problème serait de transmettre deux fois le code. Bien que cette méthode détecterait une erreur, on ne pourrait pas savoir quel code transmit était le bon, et il n'y aurait aucun moyen de corriger cette erreur.

La solution implémentée dans les codes-barres est celle que nous avons vu, la clé de contrôle, nous allons maintenant découvrir sa puissance, ainsi que ses limites.

Unicité de la clé de contrôle

Une propriété essentielle pour détecter une erreur de manière efficace à l'aide de la clé de contrôle est l'unicité de celle-ci. Evidemment si une séquence pouvait avoir deux clés de contrôle, celle-ci ne servirait plus à rien.

Montrons cette unicité :
Si l'on note a1, a2, …, a13 les 13 chiffres d'un code-barres, la clé a13 est déterminée de façon à ce que l'entier S = 3(a2+a4+a6+a8+a10+a12)+a1+a3+a5+a7+a9+a11 soit un multiple de 10.

Démontrer que la clé correspondante a une séquence a1,a2,...,a12 est unique revient a démontrer l'implication suivante :

Si c1 et c2 deux entiers satisfaisant la définition de la clé pour la séquence a1,a2,...,a12 alors c1=c2.

Soit l'équation suivante :

3(a2+a4+a6+a8+a10+a12)+a1+a3+a5+a7+a9+a11 =q*10+r donc a13=r et comme le reste de la division euclidienne est unique alors 13 est unique est il est forcément inférieur strictement a 10 donc encodé sur un seul chiffre entre 0 et 9.

Plusieurs séquences peuvent correspondre a une clé c donnée

Bien sûr la réciproque n'est pas vraie. Si l'on prend une clé de contrôle, il existe un certain nombre de séquence a1, a2, ..., a12 qui auront la même clé. Par exemple si l'on prend une séquence a1, a2, a3, ..., a12 et qu'on permute deux éléments de rangs pair ou deux éléments de rangs impair, alors la somme des chiffres ne changera pas. Dans ce cas-ci la clé de contrôle ne changera pas, donc si le scanner lit un code-barres en intervertissant deux chiffres de même parité de rang, cette erreur ne sera jamais détectée.

Néanmoins cette erreur n'est pas vraiment considérée puisqu'il est peu probable qu'un scanner lise une séquence de cette façon.

Quels types d'erreurs peuvent donc apparaître ?

Comme le scanner va lire le code-barres de gauche à droite les erreurs possibles sont les suivants

  • Oublier un nombre
  • Ajouter un nombre
  • Lire un nombre incorrect
  • Intervertir deux chiffres adjacents

Dans le cas d'un oubli ou un ajout de nombre, il va détecter directement le problème de la taille de la séquence. Il reste donc "lire un nombre incorrect" ou "intervertir deux chiffres adjacents".

Lire un nombre incorrect

On suppose qu'on a fait une erreur sur le chiffre a2 en entrant un code-barres dans une base de données (et aucune autre erreur). Notons b2 le chiffre qui s'est substitué à a2 et :S'= 3*(b2+a4+a6+a8+a10+a12)+a1+a3+a5+a7+a9+a11.

un encadrement de la différence a2-b2: on sais que S-S'=3(a_2-b_2) et

-9=<a2-b2=<9 donc -27=<S-S' <=27

si S-S' était un multiple de 10 non nul ce serait donc -20,-10,10 ou 20
on aurait donc
3(a_2-b_2)\ ({-20,-10,10,20})ce qui est impossible car 3 ne divise ni 10 ni 20 donc S-S' n'est pas un multiple de 10
donc si S est un multiple de 10 S' n'est pas multiple de 10

Ce raisonnement montre que la présence d'une erreur unique sur un chiffre de rang pair ou impair ne pose pas problème, et va être détectée.

Intervertir deux chiffres adjacents

Pour ce qui est de la transposition de deux éléments successifs, on a deux chiffres adjacents a suivit de b et on imagine que le scanner récupère les éléments dans le mauvais ordre, i.e b suivit de a. Quel est la probabilité que cette erreur soit détectée ?

Supposons a de poids 3 et b de poids 1, la différence obtenue lors du calcul de la clé de contrôle sera 3c+d -(3d+c) = 2(c-d). Alors l'unique façon que cette erreur ne soit pas détectée est que 2(c-d) modulo 10 = 0, dans tous les autres cas cette différence modifiera la clé de contrôle. Il faut donc trouver quand est-ce que 2(c-d) = 0 modulo 10.

Cela arrive uniquement lorsque la différence c-d vaut 5, i.e lorsque :

  • l'un vaut 0 et l'autre 5
  • l'un vaut 1 et l'autre 6
  • l'un vaut 2 et l'autre 7
  • l'un vaut 3 et l'autre 8
  • l'un vaut 4 et l'autre 9

Ce qui nous donne 5 possibilités. Mais en réalité ces cas correspondent aux transpositions 0 <-> 5, 1 <-> 6, 2 <->7, 3<->8, 4<->9 et on peut donc les intervertir, ce qui donne 10 possibilités, soit 10 transpositions indétectables.

Or pour 2 chiffres, le nombre de probabilités est de 10*10 = 100 (les deux nombres sont entre 0 et 9).

Distinguons aussi le cas où a et b sont égaux, par exemple a et b valent 3, ou valent 6. Dans ce cas précis, l'erreur ne sera pas détectée mais cela ne posera pas problème car le code-barres restera inchangé, ce qui correspond a 10 transpositions.

On a donc 90 transpositions de deux chiffres successifs qui nous intéresse, et parmi elles 10 qui ne seront pas détectées. Donc la probabilité de détecter ce type d'erreur est 80/90.

Remarque : nous avons raisonné pour a de poids 3 et b de poids 1, mais le raisonnement est la conclusion sont strictement les même si on avait prit a de poids 1 et b de poids 3.

Un exemple d'erreur qui n'est jamais détectée

Un cas impossible à détecter avec ce système est la transposition entre deux chiffres avec un autre entre les deux. Par exemple 204 et 402.

Ces deux nombres, ici "2" et "4" seront toujours multipliés par le même montant, soit 1 soit 3. Si dans notre exemple "2" et "4" sont de rang pair, le résultat de la somme sera :

(a1+a3+...+a11)+3*(2+4+...+a12) ou bien

(a1+a3+...+a11) + 3*(4+2+...+a12)

La somme sera identique, la clé de contrôle aussi, donc cette erreur ne sera jamais détectée.

Intérêt du codage d'un chiffre sur 7 bits

Comme expliqué plus haut , chaque caractère d'un code EAN 13 est composé de :
7 éléments (digit) qui forment 2 blocs espace et 2 blocs barre, chaque caractère est donc représenté avec 4 blocs.

On peut par conséquent les écrire avec une forme équivalente ou seule les largeurs de ces blocs sont représentées, de la façon suivante a0a1a2a3 tel que
a0+a1+a2+a3=7
Sachant que :
7 s’écrit sous la forme de 4 entiers positifs non nuls de seulement 3 façon

  • 7 = 4 + 1 + 1 + 1
  • 7= 3 + 2 + 1 + 1
  • 7= 2 + 2 + 2 + 1

Par permutation des 4 chiffres de chacune de ces trois façons on obtient donc 4+12+4 =20 suites différentes.

Cette méthode permet donc de différencier 20 codes distincts : la représentation des chiffres de 0 à 9 selon la table A et la table B .
(La table C contient les même éléments de A transcrit de manière négative )

Donc le codage sur 7 bits est optimal pour représenter tous les éléments des tables A,B et C.

Conclusion

Les codes-barres EAN ont leurs limites en terme de détection et de correction d'erreurs. Il restent néanmoins relativement robuste à la casse et extrêmement puissants pour l'utilisation qu'on en fait.

Bien sûr pour des utilisations plus poussées où il n'est pas permis de laisser une erreur, il existe des codes plus sophistiqués qu'une simple clé de contrôle, tels que les codes Hamming ou les codes reposant sur l'arithmétique polynomiale.

Le blog du cours de mathématiques discrètes du L3 Informatique , Université de Paris

Bibliographie:

https://grandzebu.net/informatique/codbar/ean13.html
https://www.techno-science.net/glossaire-definition/Code-barres-EAN.html
https://fr.wikipedia.org/wiki/Code-barres_EAN#Les_codes_EAN_13
https://www.laintimes.com/explication-et-construction-des-codes-barres-suivant-la-norme-ean-13/

https://fr.wikipedia.org/wiki/Code-barres_EAN#:~:text=Le%20num%C3%A9ro%20EAN%20constitue%20la,formant%20un%20code%20%C3%A0%20barres.

https://www.open.edu/openlearn/science-maths-technology/exploring-communications-technology/content-section-2.1

https://plus.maths.org/content/take-break

0 Cliquer pour recommander cet article