Demande d’aide aux matheux et aux devs, code reed solomon

Pause Café
#1

Bonjour.
J’essaye de faire un générateur de code barre 2D datamatrix ECC200 en python.
Mais je me heurte à un problème. Il faut générer les mots clés de correction d’erreur, pour cela on utilise le code reed solomon , et la je sèche :017 (mon niveau d’étude (et mon petit cerveau)ne me permet pas de comprendre ce …] machin)
Voici le site qui ma déjà permis de faire une générateur de code barre (code 128) dans le passé.
grandzebu.net
La page qui traite du datamatrix
grandzebu.net/index.php?page=/in … matrix.htm

[quote=“grandzebu”]• Le système de correction est basé sur les codes de "Reed Solomon"qui font la joie des matheux et la terreur des autres …
• Le nombre de MCs de correction dépend de la taille de la matrice. (Voir tableau ), plus exactement il dépend de la taille des blocs.
• Les codes de Reed Solomon font appel à un polynome dans lequel la puissance de x est le nombre de MCs de correction d’erreur utilisé. Par exemple avec la matrice de 8 x 8 nous utilisons une équation comme ceci : x5 + ax4 + bx3 + cx2 + dx + e. Les nombres a, b, c, d et e sont les facteurs de l’équation polynomiale.
• Pour information l’équation est : (x - 2)(x - 22)(x - 23)…(x - 2k) Nous développons l’équation polynomiale avec l’arithmetique de Galois sur chaque facteur…
Il y a 16 tailles de bloc de code de Reed Solomon (Voir tableau ) : 5, 7, 10, 11, 12, 14, 18, 20, 24, 28, 36, 42, 48, 56, 62, 68. Les facteurs de ces 16 équations polynomiales ont étés précalculés. Vous pouvez voir le fichier des facteurs.
• Plutôt que de dessiner l’algorithme de calcul des MC de correction, je préfére vous le fournir en Basic.
Soit k le nombre de MC de correction, a le tableau des coefficients, m le nombre de MC de données, d le tableau des MC de données et c le tableau des MC de correction. Nous utiliserons aussi une variable temporaire t.
Les c et t sont initialisés à 0. Et c’est parti pour le tripatouillage mathématique :

For i = 0 To m - 1 t = (d(i) Xor c(k - 1)) For j = k - 1 To 0 Step -1 If t = 0 Then c(j) = 0 Else c(j) = Mult(t, a(j)) End If If j > 0 Then c(j) = c(j - 1) Xor c(j) Next Next
Mult est la multiplication spéciale dans les champs de Galois.
Opérations arithmétiques dans un champ de Galois de caractéristique 2.
La somme et la différence sont la même fonction : la fonction OU exclusif.
A + B = A - B = A Xor B
La multiplication est plus compliquée; d’abord nous devons créer 2 tableaux contenant les Logs et Antilogs du champ :

Log(0) = -255 Alog(0) = 1 For i = 1 To 255 Alog(i) = Alog(i - 1) * 2 If (Alog(i) >= 256) Then Alog(i) = Alog(i) Xor 301 Log(Alog(i)) = i Next
Maintenant nous pouvons calculer Mult = Alog((Log(a) + Log(b)) Mod 255)

[/quote]
:006

#2

Il faut s’inscrire pour voir les pages que tu as mis en lien.

Je n’ai bien sûr pas tout compris aux explications, mais l’algo ne semble pas monstrueux quel est ton problème exactement et de manière très terre à terre ?

L’implémentation de l’algo n’a pas l’aire complexe après je ne sais pas comment il interviens dans la création du code barre. De plus il semble qu’il y a un paramètre à indiquer (le nombre de MC) et enfin il y a les entrées à donner à ton algo.

J’avoue que j’aurais mieux pu t’aider avec des CRC :unamused:

#3

Merci de bien vouloir me répondre
Les liens fonctionnent sans inscription, il faut dire que le design de son site est bizarre, il ne doit pas marcher avec tout les navigateurs essaye de cliquer sur les "<<<"
Ce qui me trouble déjà, ce sont les deux où exclusifs “Xor” et le "Mult"
Comment A peut être égal a B où C ?
Mult c’est bien une fonction ? si oui ou vont les paramètres t et a ? que retourne la fonction ?

#4

En fait tu as des polynômes du genre aX^2+bX^1+cX+d. Ce qui est intéressant dans ces polynômes c’est les valeurs de a, b, c et d. Chacun d’entre eux est un entier entre 0 et 1. Donc on peut les représenter avec un entier où chaque bit de l’entier représente un coefficient.

L’addition entre deux polynômes consiste à additionner modulo 2 deux à deux les facteurs. La soustraction c’est l’inverse. Du coup c’est équivalent à un xor (sauf que le xorg c’est une seul instruction processeur).

Alors bien sûr c’est extrêmement mal expliqué par un étudiant en info qui n’a pas touché à Galois depuis trop longtemps, mais c’est à peut près ça.

Mult est bien une fonction oui. Le pseudo code qu’il donne pour la fonction Mult est une étape préliminaire qui est à faire une fois pour toute. En dessus il parle de la formule (qui est toute simple) avec log^-1(log(a)+log(b)) = a*b

Je pris les matheux de ne pas vous moquer de mes explication pas terrible, je fais vraiment ce que je peux (et c’est dur).

#5

Je suis désolé je n’ai pas compris grand-chose mais je vais essayer mettre mes neurones en marche
Pour le Xor on fait un ou exclusif comme en binaire ?
1 = 1 xor 0
1 = 0 xor 1
0 = 1 xor 1
0 = 0 xor 0

Donc 6 xor 21 = 19
Puisque :

Rang__ 1 0 xor 1 = 1
Rang__ 2 1 xor 0 = 1
Rang__ 4 1 xor 1 = 0
Rang__ 8 0 xor 0 = 0
Rang_ 16 0 xor 1 = 1
Rang_ 32 0 xor 0 = 0
Rang_ 64 0 xor 0 = 0
Rang 128 0 xor 0 = 0

#6

Je viens de trouver comment on fait un xor avec python

a = 6 ^ 21 print a 19
par contre je bug sur Mult :119 :030