MathemaTeX.net

[gronaze]

Bonjour,

Je souhaite utiliser les codes correcteurs d'erreur de Reed Solomon, j'ai implémenté la partie codage et je suis actuellement dans la partie décodage.
Ma chaîne de décodage est constitué des fonctions suivantes:
1) calcul du syndrome
2) calcul du polynôme de localisations d'erreurs ET calcul du polynôme d'amplitude des erreurs par la méthode d'Euclide
3) Avec la méthode du Chien search je calcul le polynôme d'amplitude des erreurs évalué pour tous les éléments de GF(256) ainsi que la dérivée du polynôme de localisation des erreurs évaluée pour tous les éléments de GF(256)
4) application de l'algorithme de Forney pour calculer la division entre le polynôme d'amplitude et la dérivée du polynôme de localisations des erreurs
5) enfin la correction des erreurs qui nous fournie le mot de code reconstitué

Voici l'adresse de la documentation sur laquelle je m'appuie:
http://www.sweegy.ch/documents/reports/Projet_Diplome_2005%20v1.1-dietler%20.pdf

Ma fonction 2) est fausse parce que lorsque j'introduis 2 erreurs je ne retrouve pas deux zéros dans le polynôme localisateur d'erreurs; en faite mon nombre de zéros dans le poly localisateur d'erreur dépend des valeurs introduites comme erreur or cela devrait être indépendant:
Si pour data[5] je mets 4 j'obtiens trois zéros dans le poly localisateur d'erreur, et pour data[5] je mets 6 je n'obtiens plus de zéro dans le poly localisateur d'erreur!!!

Je pense que mon problème provient de mes calculs dans le corps de Galois:
ATTENTION j'utilise un code RS(39,22)
On a donc 2t = 39-22 = 17

Soit K(x) un polynôme tel que l'addition et la multiplication sont définies comme le + et le * traditionnel. Exemple : K(x) = 7x^2 + 5
Soit L(alpha^i) un polynôme évalué pour tous les éléments de GF(256) c’est à dire i compris entre 1 et 256. L(x) = 2x^2 + x
On a donc L(alpha^1) = 2( (alpha^1) ^2) + (alpha^1)
L(alpha^2) = 2( (alpha^2) ^2) + (alpha^2)
…
L(alpha^256) = 2( (alpha^256) ^2) + (alpha^256)
ATTENTION puisqu’on est dans le corps de Galois l’addition a+b est définie par : a XOR b avec le résultat défini comme un polynôme
et dans le corps de Galois la multiplication a*b est définie par GFI( GF(a) + GF(b) MOD 255 ) avec le résultat défini comme un polynôme

On passe d’un polynôme L(x) = 2x^2 + x à un polynôme évalué L(alpha^i) en prenant :
L(alpha^i) = 2*GF(2) XOR GF(1) = 2( (alpha^i) ^2) XOR (alpha^i)
Avec ( (alpha^i) ^2) = alpha^((i+2) MOD 255)
Donc L(alpha^i) = 2(alpha^((i+2) MOD 255) XOR (alpha^i)
On doit aussi transformer 2 en GF
Alors L(alpha^i) = { ( GF(2) + (alpha^((i+2) MOD 255) ) MOD 255 } XOR (alpha^i)

Mes étapes de calculs sont-elles correctes?


Désolé mais je sais pas comment on fait pour se servir de Latex…

[la main gauche]

Une chose me paraît très étrange dans ce que tu as écrit, le polynôme L que tu veux évaluer est L = 2x^2 + x, à coefficients dans le corps GF(256) qui est de caracteristique 2, on y a donc L = x, ce qui ne pose pas de problèmle particulier pour l'évaluation. Il faudrait que tu expliques un peu plus ce que sont GFI et GF dans

dans le corps de Galois la multiplication a*b est définie par GFI( GF(a) + GF(b) MOD 255 )

A tout hasard, on peut se souvenir que: GF(256) est un GF(2) espace vectoriel de dimension 16 (2^16=256), ce qui valide ta formule pour l'addition.

Dans GF(256) il y a deux sortes d'éléments, 0 et les 255 éléments non nuls qui forment un groupe multiplicatif cyclique, c'est à dire qu'il existe une bijection A de GF(256) privé de 0 vers les nombres entre 0 et 254, dinverse B et telle que a*b = B(A(a) + A(b) mod 255). Pour faire des calculs explicites il faut construire A, et il y a certainement des explications dans le rapport que tu indiques, l'auteur explique comment représenter et manipuler GF(16) (16=2^4) avec Matlab.

Il faudrait que tu sois un peu moins flou dans ce que tu racontes: même s'il y a ici beaucoup de gens de bonne volonté, il vaut mieux que tu expliques ton problème de façon indépendante (autonome) du rapport que tu cites, même si la citation est utile.

[gronaze]

Je tiens d'abord à préciser que je ne comprends pas tous les raisonnements concernant les corps de Galois... Mais je vais essayer de me faire comprendre en étant un peu plus précis.

le polynôme L que tu veux évaluer est L = 2x^2 + x, à coefficients dans le corps GF(256) qui est de caracteristique 2, on y a donc L = x

Les codes de Reed-Solomon RS(k,t) sont formés de n symboles, avec n=q-1 au maximum, q=2^k. Chaque symbole appartenant à GF(q) qui est le corps de Galois à q éléments, k représente donc le nombre de bits par symboles. Le nombre t représente de symboles d'erreurs que ce code sera capable de corriger.

Les symboles peuvent être binaires (codes BCH) où non (codes de Reed Solomon): F est un corps fini de caractéristique 2, F={0,1}

voici un extrait d'un document dont je me sers (je préfère le mettre tel quel parce que j'ai peur de faire une mauvaise interprétation):

Corps de Galois

La notation pour la suite, sera la suivante :

- F représente un corps fini (Field).
- Fp représente le corps fini à p éléments.
- F* représente le groupe multiplicatif du corps F.

2.1 Propriétés d’un corps fini

On rappelle ici, quelques propriétés utiles des corps finis. Soit F un corps fini de caractéristique p ayant q éléments. Alors,

a) F est un Fp-espace vectoriel de dimension k, avec q = pk.
b) Le groupe additif de F est isomorphe au groupe (Z/pZ,+)k.
c) F* est cyclique d’ordre q - 1 = pk - 1.
d) Tout élément x de F* vérifie xq-1 = 1.

Commentaire : Le point c) nous affirme qu’il existe un élément a, dit primitif, qui engendre le groupe multiplicatif F*. Le point a) nous dit que F est un espace vectoriel de dimension k sur le corps Fp, le choix d’une base sera généralement les puissance entière de l’élément primitif, soit 1,a , a2, a3, ..., ak-1. Un élément c de F s’écrira alors de la manière suivante :

c = ck-1 . ak-1 + ... + c1 . a1 + c0 . 1
avec ci appartenant à Fp pour i = 0,..,k-1.

2.2 Construction d’un corps fini

La construction d’un corps fini est basée sur le théorème suivant :

Théorème : Soit a un nombre algébrique sur F. Soit k le degré de son polynôme irréductible sur F. L’espace vectoriel engendré sur F par 1,a , a2, ..., ak-1 est alors un corps, et la dimension de cet espace vectoriel est k.

Ce théorème nous donne une méthode pour construire un corps avec une base donnée, mais ne nous donne pas de méthode pour trouver un élément primitif, a n’est pas forcément un élément primitif.

2.2.1 Représentation des éléments

Il existe principalement deux méthodes pour représenter les éléments d’un corps fini, soit :

i) Fq est un Fp-espace vectoriel de dimension k, on choisit une certaine base {b1,...,bk} de cet espace et on repère chaque élément de Fq par ses composantes sur cette base.

ii) On prend un élément a de F* qui engendre ce groupe et tout élément non nul de Fq s’écrit d’une manière, et d’une seule, sous la forme am, avec m = 0,...,q-1.

Pour décrire un élément du corps, on utilisera exclusivement la première représentation, car elle permet d’associer un nombre à chaque élément du corps. Mais on prendra soin de tabuler ces deux représentations, la raison en est que la représentation i) se prête très bien pour l’addition et que la représentation ii) est bien adaptée pour la multiplication. Comme on a besoin de ces deux opérations, on travaillera avec ces deux représentations qui seront tabulées une fois pour toute.

On choisit un polynôme primitif ou irréductible dans 2^8,
P(x) = x^8 + x^5 + x^3 + x^2 + 1 qui se note en binaire:
100101101 soit a racine de P(x)
on a donc P(a) = 0 ce qui donne a^8 = a^5 + a^3 +a^2 + 1

On peut calculer deux tables de logarithme et d'antilogarithme:
(ce que j'ai noté GF et GFI dans

GFI( GF(a) + GF(b) MOD 255 )

)

On peut calculer deux tables de logarithme et d'antilogarithme:
Je ne sais pas vraiment pourquoi mais on construit GFi de la manière suivante :
GFFi(0) = 0

Gfi(1) == 0*x^7 + 0*x^6 + 0*x^5 + 0*x^4 + 0*x^3 + 0*x^2 + 0*x^1 + 1*1 = 1
Gfi(2) == 0*x^7 + 0*x^6 + 0*x^5 + 0*x^4 + 0*x^3 + 0*x^2 + 1*x^1 + 0*1 = 2
Gfi(3) == 0*x^7 + 0*x^6 + 0*x^5 + 0*x^4 + 0*x^3 + 1*x^2 + 0*x^1 + 0*1 = 4
…
Gfi(7) == 1*x^7 + 1*x^6 + 1*x^5 + 1*x^4 + 1*x^3 + 1*x^2 + 1*x^1 + 1 = 128
Gfi(8) == (la valeur des monômes non nul de P(x)) = 1*x^5 + 1*x^3 + 1*x^2 + 1 = 45
Gfi(9) = (la valeur +1 des monômes non nul de P(x)) = 1*x^6 + 1*x^4 + 1*x^3 + 2 = 90
Gfi(10) = (la valeur +2 des monômes non nul de P(x)) = 1*x^7 + 1*x^5 + 1*x^4 + 2^4 = 180
Comme le prochain est supérieur à 256
Gfi(11) == (la valeur des monômes non nul de P(x) + le premier monôme nul de plus bas degré dans P(x)) = 1*x^5 + 1*x^3 + 1*x^2 + 1 + 1*x^4 = 69
Et ainsi de suite…

Pour construire GF on se sert de GF(Gfi(k)) = k

Ouf…
Maintenant que GF(log) et Gfi(log) sont construit on a tout pour faire les calculs

[gronaze]

texte très intéressant et rigoureux sur le corps de Galois:
http://www.math.jussieu.fr/%7Ealp/GF2_9.pdf

voila tout devrait être clair maintenant