Répondre à la discussion
Affichage des résultats 1 à 6 sur 6

Corps de Galois pour algorithme de Reed-Solomon



  1. #1
    supernico999

    Post Corps de Galois pour algorithme de Reed-Solomon


    ------

    Salut tout le monde
    Voilà je suis en mpsi et je bosse mon tipe. J'ai choisi de m'intéresser à l'algorithme de Reed-Solomon utilisé pour la réparation de données informatiques dans les systèmes RAID (pour la petit histoire, c'est ce qui est utilisé dans les fichiers PAR qui sont très utiles pour réparer des bouts de divx corrompus sur les newsgroups lol).

    Bon j'utilise surtout ce document:
    http://www.cs.utk.edu/~plank/plank/papers/CS-96-332.pdf

    Il est assez complet, ça me permet de piger à peu près tout grâce à mon cours...
    Mais ce qui me manque pour que mon tipe tienne debout, c'est des infos sur les corps de Galois. Vu que les "mots", c'est-à-dire les données dont on veut assurer la protection, sont de taille fixée, on doit utiliser un corps fini (ainsi les combinaisons linéaires des mots, qui permettent de retrouver des données perdues, sont aussi de la même taille). C'est pourquoi les corps de Galois entrent en jeu.
    J'ai cherché un peu sur google (en anglais) et j'ai cru comprendre que pour une puissance donnée r d'un nombre premier p, il existe un unique corps de Galois. J'ai également à peu près compris la définition des deux lois (ça utilise des polynomes de degrés inférieurs à r, à coefficients entre 0 et p-1).
    Mais ce qu'il manque cruellement dans ce document, c'est la raison profonde pour laquelle cela forme un corps; pourquoi les axiomes des corps sont vérifiés? (par exemple la distributivité de * sur +).
    J'ai cru aussi comprendre que ça utilise des groupes cycliques...

    Enfin bref, j'aimerais bien avoir des infos précises à ce sujet (que ce soit grâce à votre incroyable culture mathématique, ou grâce à un site). J'ai beau chercher et je tombe à chaque fois sur des articles qui partent dans des délires qui me dépassent lol

    Merci d'avance

    -----

  2. Publicité
  3. #2
    martini_bird

    Re : Corps de Galois pour algorithme de Reed-Solomon

    Salut,

    je ne vais pas détailler la théorie de Galois proprement dite, car elle ne te servirais pas vraiment de toute façon.

    Je vais plutôt te montrer comment construire un corps qui en contient un autre. Je suppose que tu connais les corps Z/pZ (p premier) et la notion d'ensemble quotient.

    Un premier exemple: construction de C

    Tu as déjà vu que C peut être construit en rajoutant une solution i de l'équation x²+1=0.
    Une autre construction un peu plus algébrique est la suivante (mais celà revient quasiment au même):
    dans R[X], X²+1 est un polynôme irréductible. Soit I l'ensemble de tous les multiples de X²+1: . On dit que I est l'idéal engendré par X²+1 et on le note (X²+1).
    Ce qui est intéressant c'est que l'on va pouvoir quotienter R[X] par I: la relation d'équivalence est donnée par P~Q ssi P-Q I. Tu obtiens alors un ensemble sur lequel tu peux facilement récupérer la structure d'anneau. C'est l'ensemble des polynômes modulo X²+1. Il se trouve que c'est un corps, car X²+1 est irréductible sur R (c'est le théorème essentiel). Et il n'est pas difficile de montrer que cette ensemble est isomorphe à R[i]=C.

    Construction de Fq

    Pour construire un sur-corps de Fp=Z/pZ, il suffit d'appliquer la même méthode: se donner un polynôme P irréductible sur Fp (en utilisant par exemple le critère d'Eisenstein).
    On forme le quotient Fp[X]/(P) et bingo, on obtient un corps. De plus, le théorème de l'élément primitif permet d'affirmer que le corps obtenu est isomorphe à Fp(a) où a est une racine de l'équation P(x)=0. Enfin, si le degré de P est r, l'extension Fp[X]/(P)=Fq contient pr éléments et est unique à isomorphisme près.

    Voili, je tâche de te trouver une doc sur les extensions de corps.

    Cordialement.

    PS: j'ai peut-être omis certains points de détail, mais le squelette général est celui-là.

  4. #3
    martini_bird

    Re : Corps de Galois pour algorithme de Reed-Solomon

    Une disussion sur la construction de F4.

  5. #4
    martini_bird

    Re : Corps de Galois pour algorithme de Reed-Solomon

    ... et un cours sur le sujet.

  6. #5
    supernico999

    Re : Corps de Galois pour algorithme de Reed-Solomon

    OK merci beaucoup, ça m'éclaire.
    Maintenant, j'ai juste deux questions précises:

    1) Pourquoi lorsque Q€R[X] est irréductible l'ensemble R[X]/Q est un corps ? (ce que tu appelles théorème essentiel)
    enfin pour mon cas c'est pas R mais juste {0,1} vu que les opérations sont faites sur les bits.

    2) Je note CG(2^w) le corps de galois à 2^w éléments muni de ses deux lois. On a CG(2)={0,1}
    On définit CG(2^w) en l'identifiant à CG(2)[X]/Q où Q est un polynome irréductible dans CG(2)[X].
    L'article dont j'ai donné l'adresse dit ensuite que X est générateur de CG(2^w), et qu'on peut donc écrire la liste ses éléments en calculant X^i mod Q, pour i allant de 0 à (2^w)-1.
    Ouais bah là je pige pas pourquoi X est générateur...

    Merci

  7. A voir en vidéo sur Futura
  8. #6
    martini_bird

    Re : Corps de Galois pour algorithme de Reed-Solomon

    Citation Envoyé par supernico999
    1) Pourquoi lorsque Q€R[X] est irréductible l'ensemble R[X]/Q est un corps ? (ce que tu appelles théorème essentiel)
    enfin pour mon cas c'est pas R mais juste {0,1} vu que les opérations sont faites sur les bits.
    Soit K un corps.
    Clairement si Q=R.S avec R et S non constants, K[X]/(Q) ne peut être un corps, du fait de la présence de diviseurs de zéro. En effet, si R' (resp S') sont les classes de R et S modulo Q, on a R'.S'=0 (mod Q). Le fait que Q soit irréductible est donc nécessaire.

    Supposons maintenant que Q soit irréductible et soit P K[X]/(Q): soit P' K[X] un représentant de P tel que deg(P)<deg(Q) (c'est bien entendu toujours possible, par division euclidienne). Puisque P' et Q sont premiers entre eux, d'après le théorème de Bézout, il existe U et V K[X] tels que UP'+VQ=1 et P admet donc un inverse modulo Q.

  9. Publicité

Sur le même thème :

Discussions similaires

  1. besoin d'aide pour un algorithme
    Par manianga dans le forum Internet - Réseau - Sécurité générale
    Réponses: 4
    Dernier message: 27/11/2006, 18h02
  2. algorithme pour le calcul numerique
    Par Ksilver dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 11/12/2005, 12h56
  3. Algorithme pour la division euclidienne
    Par jdh dans le forum Mathématiques du supérieur
    Réponses: 12
    Dernier message: 28/09/2005, 16h52
  4. Algorithme pour nombres premiers.
    Par Antikhippe dans le forum Mathématiques du supérieur
    Réponses: 26
    Dernier message: 22/05/2005, 23h28
  5. Algorithme pour trouver X exp Y
    Par lthithhi dans le forum Mathématiques du collège et du lycée
    Réponses: 7
    Dernier message: 15/01/2004, 00h05