CODES BARRES

Figure 1 : Code barres EAN 13 et code barres EAN 8




Auteurs : Yoan WAUCAMPT, Nicolas NGAUV, Mehdi BEKHTAOUI




Les codes barres jouent de nos jours un rôle fondamental.
Destinés à automatiser l'acquisition d'une information généralement numérique, ils trouvent leurs applications dans des domaines aussi variés que la gestion des prêts d'une bibliothèque, les caisses enregistreuses à lecture optique, ou le contrôle de la production dans l'industrie...
Ils permettent d’encoder des informations de manière compacte, et avec une redondance qui permet une correction automatique de l’information
lue en cas d’erreurs (dans une certaine limite).

Petite précision avant de débuter...
Il existe plusieurs normes pour les codes barres (EAN, UPC, etc.) : ici nous parlerons dans cet article des codes barres EAN, c'est-à-dire des codes barres reconnus dans les pays de l'Union Européenne (et compatible avec les codes UPC utilisés en Amérique du Nord, le code EAN étant dérivé de ce dernier).

Les codes barres sont principalement utilisés pour la gestion et la vente de produits. Leur décodage nécessite un lecteur spécifique.
Le premier code barres a été breveté le 7 octobre 1952 par les Américains Norman Woodland et Bernard Silver. Au lieu des barres verticales actuelles, ils avaient imaginé des cercles concentriques (première apparition à Ohio en 1974)

Première version du code barre


Dans un premier temps, nous verrons en quoi consiste le codage graphique de l'information (quel motif correspond à quel chiffre/symbole) et quel est l'intérêt d'un codage d'un chiffre sur 7 bits.
Cette description sera suivie d'une démonstration d'un programme ayant pour but de générer un code barres étant donnée une information à coder.
Et finalement, nous calculerons la probabilité qu'une erreur soit détectée et corrigée avec ces codes.




Codage graphique de l'information et intérêt du codage d'un chiffre sur 7 bits

Il existe plusieurs normes pour les codes barres (EAN, UPC, etc.) : nous parlerons dans cet article des codes barres EAN, c'est-à-dire des codes barres reconnus dans les pays de l'Union Européenne (et compatible avec les codes UPC utilisés en Amérique du Nord, le code EAN étant dérivé de ce dernier).

Il existe des codes EAN 8 et EAN 13 (respectivement constitué de 8 et 13 caractères, répartis entre trois zones) :
- les codes EAN 8 pour l'usage sur des produits de petite taille (paquets de chewing gum par exemple)
- les codes EAN 13

En lisant de gauche à droite, on trouve :
- un code composé de 2 caractères indiquant l'origine du code (code pays)
- la "zone utile de codage" : 10 caractères (4 pour le fabriquant et 6 pour l'article) pour un codage sur 13 chiffres, et 5 caractères (les 5 étant utilisés uniquement pour le codage de l'article) pour un codage sur 8 chiffres
- le "code de contrôle", vérifiant la validité du code à l'aide d'un unique caractère (calculé à l'aide d'un algorithme).


Figure 2 : La norme EAN 8





Figure 2 bis : La norme EAN 13




Les caractères sont représentés par la concaténation de 2 barres de base de 0,5 mm (une telle barre est dite de largeur élémentaire) :
- une barre noire, qui représente le 1 binaire
- une barre blanche, qui représente le 0 binaire.
Chaque caractère étant codé à l'aide de 7 barres, il s'agit donc d'un codage sur 7 bits.

Les largeurs des barres sont toutes des multiples de la largeur élémentaire :
- une barre de largeur 1 correspond à une seule barre élémentaire,
- une barre de largeur 2 correspond à deux barres élémentaires de même couleur
- une barre de largeur 3 correspond à trois barres élémentaires de même couleur
- une barre de largeur 4 correspond à quatre barres élémentaires de même couleur

Les codes barres doivent pouvoir être lus à des distances différentes, et donc les lecteurs ne mesurent pas la largeur réelle des barres, mais leurs largeurs relatives, c'est-à-dire par rapport aux autres barres du code.
Cela impose de fortes contraintes sur le codage, car ces lecteurs n’ont au départ aucune donnée sur la largeur élémentaire utilisée dans le codage. Ils doivent donc la déduire de ce qu’ils captent, et être en mesure de décider si ce qu’ils ont détecté correspond à la réalité du codage initial.

Un séparateur divise le code en deux parties. On trouve 0101 entre les parties gauche et droite du code, et 101 aux extrémités (les barres qui représentent ces séparateurs sont plus longues que les barres qu'ils encadrent).
De plus, chacun des chiffres composant l'EAN peut, selon sa position dans le code, avoir 3 représentations distinctes nommées élément (ou jeu) 1, élément (ou jeu) 2 ou élément (ou jeu) 3.
Les jeux A et B sont uniquement situés à gauche du milieu du code barres (et seulement le jeu A à gauche pour le code EAN 8), tandis que le jeu C se trouve uniquement à droite.

Figure 3 :
Les codes des jeux A et B commencent tous par 0 et finissent tous par 1.
Inversement, les codes du jeu C commencent tous par 1 et finissent par 0.
Remarquons que le codage d'un même chiffre comme élément C est toujours le complément de son codage comme élément A (les 1 et les 0 sont permutés) .





Remarques :

La structure du code permet d'identifier le type d'un élément grâce sa parité (à savoir si le nombre de 1 est pair ou impair) et par son premier ou son dernier bit :

  • paire, commence par 0, se termine par 1 → élément B
  • paire, commence par 1, se termine par 0 → élément C
  • impaire, commence par 0, se termine par 1 → élément A
  • impaire, commence par 1, se termine par 0 → élément incorrect

Le codage d'un même chiffre (situés ci-dessus sur la même ligne du tableau de la Figure 3) comme élément B est toujours le symétrique de son codage comme élément C.

  • Lu à l'envers (par exemple de droite à gauche), un élément de type B apparaît donc comme un élément de type C (lu de gauche à droite) et inversement.
  • Par contre un élément de type A lu à l'envers est incorrect.
    Il est donc nécessaire d'avoir au moins un élément de type A dans le code afin de déterminer le sens de lecture : tous les éléments de gauche pour le code EAN-8, et pour le code EAN-13, le deuxième élément est toujours de type A (c'est ce qui permet de lire le code barre d'un objet qu'on tient dans n'importe quelle position, par exemple lorsque l'on fait ses courses).

Les codages A et C d'un même chiffre (situés ci-dessus sur la même ligne du tableau de la Figure 3) sont toujours complémentaires l'un par rapport à l'autre (les 1 et les 0 sont permutées).

  • Il en résulte que si un élément qui devrait être de type A est de type C, c'est que les couleurs sont inversées : blanc → 1 et noir → 0 (c'est ce qui permet de lire le code barres, qu'il soit blanc sur fond noir ou noir sur fond blanc par exemple).

On en déduit donc que le codage EAN rend possible la lecture du code :

  • quel que soit le sens de lecture
  • quelle que soit la couleur d'impression du code barres.



Détaillons maintenant le calcul du caractère de contrôle (le dernier caractère codé du code barres) :

Le dernier chiffre détermine si le code barre ne contient pas d'erreurs.
On prend le code EAN puis on multiplie chaque caractère en alternant une multiplication par 1 puis par 3 (en commencent une multiplication par 1) puis on additionne tout les résultats et on divise par 10. On note le reste de la division.
Puis on fait :
10 - reste = caractère de contrôle
On peut ensuite vérifier si le code barre a été erroné ou non.

Ci-dessous un exemple de calcul du caractère de contrôle d'un code EAN 13. Pour un code EAN 8, la procédure est la même, il y a seulement moins de chiffres à prendre en compte.


Code EAN2 047650 00081X
Chiffres2|0 | 4 | 7 | 6| 5| 0 | 0 | 0| 0| 8 | 1
Multiplier par1 | 3 | 1 | 3 | 1 | 3 | 1 | 3 | 1 | 3 | 1 | 3
Résultat2|0 | 4 |21| 6| 15| 0| 0 | 0| 0 | 8 | 3
Somme2 + 0 + 4 + 21 + 6 + 15 + 0 + 0 + 0 + 0 + 8 + 3 = 59
Division par 1059 / 10 = 5, et reste = 9
Caractère de contrôle10 - reste = 1
(Si le reste de la division vaut 0,
alors le caractère de contrôle vaut
également 0).

Le code EAN final est donc dans ce cas 2 047650 000811 .



Voyons maintenant l'intérêt du codage sur 7 bits :

Pour rappel, chaque caractère est codé à l'aide de 7 bits (chaque bit étant soit un 0, soit un 1).
Les éléments A, B et C peuvent aussi être représentés sous la forme équivalente suivante où seules les largeurs des quatre barres successives (décrites de gauche à droite) sont indiquées (les éléments A et C se distinguent uniquement par la couleur de la première barre) :

chiffre élément A ou C élément B
0 3211 1123
1 2221 1222
2 2122 2212
3 1411 1141
4 1132 2311
5 1231 1321
6 1114 4111
7 1312 2131
8 1213 3121
9 3112 2113

Figure 4 : Récapitulatif des chiffres codés sous la forme où seules les largeurs des quatre barres successives sont indiquées







Le codage EAN peut permettre de distinguer 10 caractères différents (les chiffres de 0 à 9), mais c'est tout (donc pas de lettre par exemple, mais cela n'a aucune importance puisque les chiffres de 0 à 9 suffisent amplement pour coder l'information) !
En effet les 20 ensembles de 4 chiffres figurant dans le tableau ci-dessus représentent exactement l'ensemble des 20 permutations possibles de 4 chiffres non nuls telles que la somme de ces chiffres soit égale à 7 : il n'y a donc plus aucune combinaisons disponibles permettant le codage d'un quelconque caractère supplémentaire.
Ceci est lié à p4(7).

Pour continuer l'explication, introduisons d'abord la fonction de partage d'un entier.
Le symbole pk(n) correspondant à la fonction "partage d'un entier" ou "partition d'un entier" :
pk(n) = x veut dire "on ne peut écrire n sous la forme d'une somme de k entiers strictement positifs que de x manières différentes" .
Ainsi, p4(7) = 3 et l'on a :
7 = 4 + 1 + 1 + 1 = 3 + 2 + 1 + 1 = 2 + 2 + 2 + 1
"on ne peut écrire 7 sous la forme d'une somme de 4 entiers strictement positifs que de 3 manières différentes"

Ces 3 "façons" générant respectivement, par permutation de leurs 4 chiffres, les 4 + 12 + 4 variantes suivantes :

1) 4+1+1+1 = 1+4+1+1 = 1+1+4+1 = 1+1+1+4

2) 3+2+1+1 = 3+1+2+1 = 3+1+1+2 = 2+3+1+1 = 2+1+3+1 = 2+1+1+3 = 1+3+2+1 = 1+2+3+1 = 1+1+3+2 = 1+1+2+3 = 1+2+1+3 = 1+3+1+2

3) 2+2+2+1 = 2+2+1+2 = 2+1+2+2 = 1+2+2+2


Pour résumer :
Le codage sur 7 bits est le codage sur le plus petit nombre de bits (et c'est ce qu'on veut lorsqu'on a pour but d'avoir un code le plus petit et compact possible !), permettant de différencier 10 caractères distincts (les chiffres de 0 à 9) codés en bits (0 ou 1), tout en respectant les critères stricts (vus précédemment) du codage graphique de l'information qu'est le code barres EAN.






Programme Codes Barres


Programme écrit en java. Implémentation de l'encodage EAN8 avec la structure nécessaire pour encodage EAN13.

Il s'agit de modifier la valeur "lecode" dans la classe "TestJFrame" pour voir les différents codes barres s'afficher lors de l'execution.

Détection d'erreurs et correction

Comme nous l'avons précédemment cité, Le code-barres de nombreux produits est constitué de 13 chiffres. Les 12 premiers chiffres permettent d'identifier le produit. Le 13ème chiffre est une clé de contrôle qui permet de détecter une éventuelle erreur dans les 12 chiffres d'identification.
Pour calculer la clé de contrôle, il faut
a) Additionner les chiffres de rang impair en partant de la gauche sans compter le dernier chiffre de contrôle.
b) Ajouter à ce résultat trois fois la somme des chiffres de rang pair toujours en partant de la gauche.
On obtient un chiffre K.
la clé de contrôle est le chiffre (entre 0 et 9) qui ajouté à K va donner un multiple de 10.

On peut vérifier si un code est correct de cette manière :
On utilise tous les caractères ; et le chiffre K qu'on a calculé juste avant et on lui rajoute le dernier chiffre de contrôle avec la même règle.
Pour que le code soit correct, le chiffre obtenu doit impérativement être un multiple de 10.
Exemple sur le code : 5 0 1 0 3 5 6 8 2 3 3 5 7

On a ici :
( 5 + 1 + 3 + 6 + 2 + 3 + 7) + 3 (0 + 0 + 5 + 8 +3 + 5) = 90.
90 est bien un multiple de 10, le code est correct.

Un exemple de correction de code est la théorie de Reed Solomon, qui reprend le principe du reste de la division.

Le code de Reed Solomon est un code correcteur basé sur les corps finis dont le principe est de construire un polynôme formel à partir des symboles à transmettre et de l’échantillonner. Le résultat est alors envoyé, au lieu des symboles originaux. La redondance de cet échantillonnage permet au récepteur du message encodé de reconstruire le polynôme même s'il y a eu des erreurs pendant la lecture du code qui crée le code barre lui-même.
Donc, en plus des opérations traditionnelles (additions et multiplications) nous utiliserons le calcul d'exposant et de "XOR".

Bibliographie

Informations :
https://www.aurel32.net/elec/codes_barres.php
https://fr.wikipedia.org/wiki/Code-barres_EAN
https://fr.wikipedia.org/wiki/Code-barres
http://au3plus.free.fr/pages/tutoriel4.html
https://fr.wikipedia.org/wiki/Code_universel_des_produits
https://fr.wikipedia.org/wiki/Partition_d%27un_entier
https://www.pedagogie.ac-aix-marseille.fr/upload/docs/application/pdf/2013-06/orme2013_-_code_barres_et_qr_code.pdf

Illustrations :
Figure 1 : http://www.transbar.fr/choisir/choisir_ean.html?lg=fr
Figure 2 et 2bis : https://www.aurel32.net/elec/codes_barres.php
Figure 3 : http://au3plus.free.fr/pages/tutoriel4.html
Figure 4 : https://fr.wikipedia.org/wiki/Code-barres_EAN




Afin de traiter ce sujet au mieux, voici pour l'instant la répartition provisoire des tâches au sein du groupe :

- Description du codage graphique de l'information et intérêt du codage d'un chiffre sur 7 bits = Yoan WAUCAMPT, Nicolas NGAUV, Mehdi BEKHTAOUI

- Programme générant un code barre à partir d'une information à coder = Yoan WAUCAMPT, Nicolas NGAUV, Mehdi BEKHTAOUI

- Détection d'erreurs et correction = Yoan WAUCAMPT, Nicolas NGAUV, Mehdi BEKHTAOUI

6 Cliquer pour recommander cet article