Specifications | Spécification du Data Matrix
Samedi 27 mai 2017
Google

CODE BARRES DATA MATRIX

Format du DATA MATRIX

Longueur Type Système de correction d'erreur
de 1 à 3116 caractères (variable) numérique, alphanumérique
ou byte
oui (Reed-Solomon)

La taille du symbole, représentation graphique, est déterminée selon la nature et le nombre de données à encoder.

Une structure intermédiaire de 8 bits est utilisée pour enregistrer chaque donnée : le codeword.

Le symbole est composé de 3 groupes de codewords, placés les uns après les autres :

L'encodage se déroule en deux étapes :

Représentation graphique du code barres Data Matrix

Le symbole est composé de petits carrés noirs et blancs juxtaposés, appelés modules.

Un module représente un bit : généralement en noir pour le 1 et en blanc pour le 0.

Le Data Matrix peut être de forme carrée (la plus utilisée) ou rectangulaire.

On peut décomposer le symbole en trois parties :

Lorsque le symbole dépasse une certaine limite de taille, le symbole est divisé en plusieurs zones de données, les régions, qui sont délimités par des motifs de repérage internes. Quatre types de division en régions existent : 3 pour la forme carrée et 1 pour la forme rectangulaire.

Encodage de haut niveau

Six modes d'encodage coexistent : ASCII, Text, C40, X12, EDIFACT et Base 256. L'encodage ASCII est l'encodage par défaut et le plus utilisé. Il sera le seul présenté ici.

L'ensemble des valeurs des codewords du mode ASCII sont visibles dans le tableau suivant :

Valeur du Codeword Correspondance
1 - 128 Caractères ASCII (valeur ASCII + 1)
129 Premier caractère de remplissage
130 - 229 Nombres entre 00 et 99 (valeur numérique + 130)
230 Caractère d'enclenchement du mode C40
231 Caractère d'enclenchement du mode base 256
232 Caractère FNC1
233 Caractère "Structured Append"
234 Caractère "Reader Programming"
235 Upper Shift (passage à l'ASCII étendu)
236 - 237 05 Macro - 06 Macro
238 Caractère d'enclenchement du mode X12
239 Caractère d'enclenchement du mode Text
240 Caractère d'enclenchement du mode EDIFACT
241 Caractère ECI
242 - 255 Pas utilisés dans le mode ASCII

Certaines valeurs ne sont pas explicitées car non utilisées.

Dans le mode ASCII, les données sont encodées selon 3 possibilités :

Lorsque le nombre de codewords de données ne peut remplir complètement la partie « données » de la plus petite taille de symbole possible, des codewords de remplissage sont ajoutés. Le premier de ces codewords, qui indique la fin des données dans ce cas, vaut toujours « 129 ». La suite est calculée grâce à l'algorithme 253-state suivant :


Calcul des codewords de correction


Les codes de Reed-Solomon sont utilisés comme système de correction d'erreurs. Ceux-ci ont une capacité de détection et de correction d'erreurs définie à l'avance, dépendant de la taille de la matrice de données.

Un corps C est un ensemble d'éléments fermé et muni de deux opérations binaires appelées addition et multiplication. Le fait d'être fermé implique que le résultat de chaque opération sur deux éléments de l'ensemble donnera toujours un élément de l'ensemble.

Il existe de nombreux corps, finis et infinis. Il s'avère que pour tout entier premier p et pour tout entier n (>=1), il existe un corps fini unique avec np éléments, que l'on note GF(np). Ces corps sont appelés Corps de Galois.

On peut représenter les éléments de GF(np) à l'aide des éléments de base a : 0, 1, a, a2, a3, ..., a(n-1). Prenons un exemple :

Les éléments peuvent également être représentés sous différentes formes : en binaire, en décimal ou même sous la forme d'un polynôme. Pour le même exemple, sous la forme :

Pour chaque corps de Galois, il existe au moins un polynôme primitif, noté p(x), qui permet de construire le corps. Les Data Matrix stockant les données sur 8 bits (dans des codewords), ils travaillent donc dans le corps de Galois GF(28). Ils utilisent le polynôme primitif x8+x5+x3+x2+1, qui correspond à la valeur 301.

L'addition et la soustraction de deux éléments consiste en la fonction XOR (OU exclusif) entre ces deux éléments. La multiplication et la division sont calculés en multipliant les polynômes correspondant. Cette opération étant relativement coûteuse en temps de calcul, un algorithme est utilisé. Sachant que tous les éléments sont une puissance du polynôme primitif p, il faut donc chercher pour chaque élément c la puissance i telle que :

A partir de là, on peut calculer pour deux éléments c et d :

On peut obtenir le tableau des antilogs e grâce à cet algorithme :

Un code de Reed-Solomon de taille n avec k données est noté RS(n,k). Il y a donc n-k = 2t symboles de contrôle et ce code permet de corriger jusqu'à t symboles erronés. Le nombre de symboles de contrôle est défini par la taille du Data Matrix.

L'équation clé pour le codage d'un code RS(n,k) est :

avec

Les 2t symboles de contrôle sont calculés à partir d'un polynôme générateur de puissance 2t, composé de 2t + 1 termes, qui est de la forme suivante :

Il y a 16 longueurs de bloc de Reed-Solomon possible (voir tableau récapitulatif). Les coefficients des polynômes générateurs peuvent être calculés grâce à l'algorithme suivant :

Le polynôme générateur étant calculé, il suffit de suivre l'équation afin d'obtenir le polynôme de contrôle : il s'agit du reste de la division entre le polynôme de données et le polynôme générateur. Les coefficients correspondent aux codewords de contrôle.

Pour les symboles Data Matrix contenant un total de moins de 255 codewords (tous les symboles rectangulaires et les carrés de tailles inférieures à 48x48), les codewords de correction sont calculés directement à partir des codewords de données. Pour les autres symboles, les codewords de correction sont calculés en suivant une procédure d'entrelacement : on divise les codewords de données en plusieurs blocs de tailles identiques et les codewords de correction sont calculés bloc par bloc. Chaque codeword c fait parti du groupe :

avec n le nombre de blocs pour le symbole

Pour simplifier, pour n blocs, le premier groupe est formé des codewords de données 1, n+1, 2n+1, 3n+1, ... le second est formé des codewords de données 2, n+2, 2n+2, 3n+2, ...

Un exemple d'entrelacement peut être visualisé ci-après :

Encodage de bas niveau

Chaque codeword est représenté dans la matrice de données par un carré partiel de 8 modules, correspondant à 8 bits. Le module 1 possède la valeur du bit le plus signifiant (valeur 128) alors que le module 8 possède la valeur du bit le plus insignifiant (valeur 1).

Il se peut cependant qu'un codeword ne peut être contenu entièrement dans la matrice à un certain emplacement. Ceux-ci peuvent alors être séparés en plusieurs parties (2 ou 3) afin d'être continué de l'autre côté du symbole.

De plus, dans quatre cas particuliers, les codewords placés dans les coins peuvent être également placé de façon différente.

Le placement dans la matrice suit un certain ordre. Les premiers codewords sont toujours placés comme ceci :

Les codewords sont ensuite emboîtés les uns dans les autres, en suivant des lignes obliques (45°) parallèles. Le sens des obliques est identique une fois sur deux.

Il se peut, selon la taille du symbole, que les quatres modules du coin inférieur droit soient vides. Les symboles 12x12 par exemple, dont la matrice de données est de 10x10, donnent 100 modules dans lesquels 12 codewords peuvent être insérés. Sachant qu'un codeword rempli 8 modules, un total de 96 modules seront occupés et les 4 derniers seront donc vides. Pour les remplir, on utilise des modules noirs et blancs alternés comme présenté ci-dessous :

Il faudra ensuite ajouter le finder pattern principal et éventuellement les finder pattern internes si le nombre de régions est supérieur à 1.

Exemple d'encodage

Supposons que l'on veuille encoder « ENC01 ». Les valeurs ascii des différents caractères sont :

E N C 0 1
69 78 67 48 49

Selon le mode ASCII, les valeurs des codewords seront :

Codeword Méthode Evaluation Valeur mode ASCII Equivalent binaire
C1 Valeur ASCII + 1 69 + 1 70 0100 0110
C2 Valeur ASCII + 1 78 + 1 79 0100 1111
C3 Valeur ASCII + 1 67 + 1 68 0100 0100
C4 Valeur numérique + 130 1 + 130 131 1000 0011

La valeur des codewords 1, 2 et 3 ont été calculés simplement en utilisant la « valeur ASCII + 1 », alors que le codeword 4 encode deux chiffres successifs en utilisant « valeur numérique + 130 ».

On a donc 4 codewords à encoder, on choisit dès lors, la taille minimale de symbole permettant de les encoder : il s'agit du symbole de taille 12x12, proposant une matrice de données de taille 10x10 et permettant d'encoder 12 codewords composés de 5 codewords de données et de 7 codewords de correction. Sachant que 5 codewords de données sont nécessaires et que nous n'en possédons que 4, un codeword de remplissage va être ajouté : il s'agit du codeword de valeur « 129 », qui est toujours le premier afin d'indiquer la fin des données. Il n'est pas nécessaire d'en calculer d'autres à l'aide de l'algorithme 253-state.

Codeword Valeur mode ASCII Equivalent binaire
C5 129 1000 0001

Par rapport à ce qu'on a vu précédemment, on sait que :

Pour rappel, les opérations se passent dans GF(28). Grâce aux algorithmes présentés précédemment, le polynôme générateur a été calculé :

Le calcul du polynôme représentant les codewords de correction est effectué comme ceci :

Les codewords de correction, correspondant aux coefficients de ce polynôme sont les suivants :

Codeword Valeur mode ASCII Equivalent binaire
C6 4 0000 0100
C7 133 1000 0101
C8 98 0110 0010
C9 49 0011 0001
C10 253 1111 1101
C11 53 0011 0101
C12 182 1011 0110

Il faut ensuite placer ces différents codewords dans la matrice de données en suivant l'algorithme adéquat. L'ordre de placement est le suivant :

Tableau récapitulatif des données des Data Matrix

Générateur de code barres Data Matrix en ligne

Veuillez saisir le code :