Discussion :

[Titomdu69]

Bonjour à tous,
Tout d’abord je vous avoue que c’est mon premier message dans le forum. (Donc désolé si je me suis trompé de catégorie.)
En faite je suis en train de travailler sur un projet : Le datamatrix. Le principe affiché un code sur un écran pour économiser du papier et faire du bien à la planète ^^.
J’aurais 900 caractères alphanumérique à envoyer donc l’utilisation de code sur 96x96 pixels (mais j’en suis pas encore là)
Dans un premier temps je travaille avec un code 10x10 pixels, pour déjà voir si mon lecteur le lit sur mon écran et OUI . Le problème maintenant c’est que je vais devoir connaitre la composition du code pour le refaire dans mon écran.
Donc il y a deux points : les data et les check.
Les data j’ai compris mais les check font appel au code reed solomon qui d’ailleurs au passage m’a mis une claque dans mon timing … J’utilise et comprend assez bien les polynômes sauf que là je ne comprends même pas le départ …
Prenons un exemple déjà tout fait :
Codage de 1 2 3 4 5 6
Donc pour les data :
12 + 130 = 142
34 + 130 = 164
56 + 130 = 186
Jusque là tout va bien, mais après pour les check, c’est une autre histoire.

En faite mon code à la fin doit donner : 142 164 186 114 25 5 88 102
Avec 114 25 5 88 102 comme check
Mais bon il me manque l’étape de calcul des check, et là, malgré avoir fait pas mal de site et essayer aussi bien des divisions euclidiennes de polynômes que de calcul logique je suis jamais arrivé au bon résultat…
Donc si quelqu’un connait ce code et peu juste me montrer le passage entre les data de l’exemple et les check

[pseudocode]

Mais bon il me manque l’étape de calcul des check, et là, malgré avoir fait pas mal de site et essayer aussi bien des divisions euclidiennes de polynômes que de calcul logique je suis jamais arrivé au bon résultat…
Donc si quelqu’un connait ce code et peu juste me montrer le passage entre les data de l’exemple et les check

Le mieux est encore de lire le document de référence "Reed-Solomon Error Correction" de C.K.P. Clarke. Il y a les explications ainsi qu'un exemple de calcul "à la main".

En fait, il s'agit de trouver le polynome R(x) tel que

M(x) = Q(x)*G(x) + R(x)

G(x) : le polynome générateur, dans ton cas de degré 5 (car tu veux un code de taille 5)
M(x) : le polynome représentant ton message, de degré 8 (message de taille 3 + code de taille 5)
Q(x) : le quotient de la division
R(x) : le reste de la division = le polynome représentant le code

Attention ! Les calculs se font dans un corps de Galois !!!!

[Titomdu69]

Merci pour ces renseignements.

Je regarde ça aujourd'hui, je vous tiens au courant

[Titomdu69]

Bonjour,

Voila le tableau que j'obtiens pour coder 1 2 3 4 5 6
12 + 130 =142
34 + 130 =164
56 + 130 =186





Donc L1 correspond à mon polynomes (142x^2 + 164^x + 186)*x^5
L2 correspond à 142x^2 *( G(x) )
G(x) : Polynome générateur : x^5 + 62x^4 + 111x^3 + 15 x^2 + 48x + 228
Enfin j'utilise bien le tableau GF(256)
L3 : L1 XOR L2

Et je répète la manip
Par contre je devrais obtenir 114 25 5 88 102 et j'obtiens : 58 19 124 14 114

Donc si quelqu'un voit une erreur n'hésitez pas ^^

[pseudocode]

L2 correspond à 142x^2 *( G(x) )

142.x^2 * G(x)
= [142*1].x^7 + [142*62].x^6 + [142*111].x^5 + [142*15].x^4 + [142*48].x^3 + [142*228].x^2
= 142.x^7 + 85.x^6 + 176.x^5 + 25.x^4 + 194.x^3 + 122.x^2

Donc je pense qu'il y a un problème dans ton tableau GF(256).

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// primitive polynomial for DATAMATRIX : x^8+x^5+x^3+x^2+1
int PP = 301; // = 100101101 (binary)
 
// sequence of A^i in GF(256)
int[] A = new int[256];
A[0]=1;
for (int i = 1; i < 256; i++) { 
	A[i] = A[i-1] << 1; 
	if (A[i]>255) A[i]^=PP; 
}
 
// Multiplication table : A^i * A^j = A^(i+j)
int[][] mul = new int[256][256];
for (int j = 0; j < 256; j++)
	for (int i = 0; i < 256; i++)
		mul[A[i]][A[j]] = A[(i+j) % 255];

[Titomdu69]

Slt

Pour mon tableau de GF(256), j'ai pris ce site :

http://wcours.gel.ulaval.ca/2010/h/G...Galois_256.pdf

primitive polynomial for DATAMATRIX : x^8+x^5+x^3+x^2+1

Eux, ils utilisent le polynome : x^8+x^4+x^3+x^2+1

Donc c'est vrai que l'on trouve pas le même tableau ^^

Je vais essayer avec le tien on verra bien ^^


Edit : Voici un autre pdf qui donne le meme polynome primitif que moi :
http://www.sweegy.ch/documents/repor...dietler%20.pdf
(Page6)

[jacosado]

Pouvez-vous m'expliquer la manière avec laquelle vous trouvez la ligne L2 ?
Merci par avance.

Bonjour,

Voila le tableau que j'obtiens pour coder 1 2 3 4 5 6
12 + 130 =142
34 + 130 =164
56 + 130 =186





Donc L1 correspond à mon polynomes (142x^2 + 164^x + 186)*x^5
L2 correspond à 142x^2 *( G(x) )
G(x) : Polynome générateur : x^5 + 62x^4 + 111x^3 + 15 x^2 + 48x + 228
Enfin j'utilise bien le tableau GF(256)
L3 : L1 XOR L2

Et je répète la manip
Par contre je devrais obtenir 114 25 5 88 102 et j'obtiens : 58 19 124 14 114

Donc si quelqu'un voit une erreur n'hésitez pas ^^

[pseudocode]

Pouvez-vous m'expliquer la manière avec laquelle vous trouvez la ligne L2 ?
Merci par avance.

Le tableau représente une division de polynome

Polynome | Generateur
         |------------
         |
   reste | Quotient
         |
         |

Pour le cas qui nous intéresse, c'est le polynome (142,164,186,0,0,0,0,0) qui doit être divisé par (1,62,111,15,48,228). Le premier résultat du quotient est donc 142.

(142,164,186,0,0,0,0,0) | (1,62,111,15,48,228)
                        |----------------------
                 Reste  | 142
                        |  
                        |  
                        |  
                        |  

Et donc on a:

Reste = (142,164,186,0,0,0,0,0) - 142*(1,62,111,15,48,228)

La ligne L2 représente l'opération 142*(1,62,111,15,48,228)