Division euclidienne dans F2
Répondre à la discussion
Affichage des résultats 1 à 13 sur 13

Division euclidienne dans F2



  1. #1
    christophe_de_Berlin

    Division euclidienne dans F2


    ------

    Bonjour, j´étudie les codes correcteurs et dans ce contexte (code binaire de Hamming de longueur 7) il est écrit dans mon cours:

    "Le polynôme générateur g = 1 + X + X^3

    et

    g divise X^7 - 1 puisque X^7 - 1 = ( 1 + X + X^3)(1 + X + X^2 + X^4)"

    C´est là que je m´aperçois qu´une division euclidienne dans F2 n´est pas claire dans ma tête. J´ai essayé la chose suivante:

    J´ai fait la division euclidienne "classique", c´est à dire à coefficients dans Z de X^7 - 1 par g, et j´ai obtenu:

    X^7 - 1 = (X^3 + X + 1)(X^4 - X^2 - X - 1)

    Et dans le deuxième facteur de ma division, j´ai tout simplement remplacé les - par des +, vu que dans F2 -1 = +1. Ainsi j´obtiens le même résultat que dans mon cours.

    Mais est-ce la bonne méthode? Y-a-t-il une méthode plus rationnelle ou plus directe?

    merci d´avance

    Christophe

    -----

  2. #2
    invite8b04eba7

    Re : Divisin euclidienne dans F2

    Citation Envoyé par christophe_de_Berlin Voir le message
    Mais est-ce la bonne méthode? Y-a-t-il une méthode plus rationnelle ou plus directe?
    Comment calcules-tu dans F2 ? Simplement en calculant dans Z puis en effectuant les modulo 2. Pour la division euclidienne, c'est pareil : tu fais tout dans Z puis tu passes au modulo 2 (tu peux meme le faire a chaque etape). Ca te donne le bon resultat a cause de l'unicite de cette division : une relation A = BQ + R avec deg(R) < deg(B) reste de la meme forme modulo 2.

  3. #3
    christophe_de_Berlin

    Re : Divisin euclidienne dans F2

    Super merci, c´est exactement la confirmation dont j´avais besoin.

    Mais dans ce (presque) même chapitre, j´ai une autre question: Il s´agit cette fois d´opérations dans des corps finis Fp. Si p est premier, c´est simple, il suffit comme tu l´expliques de calculer dans Z (addition ou multiplication, peu importe) puis de faire modulo p.

    Par contre sur Fn, n n´était pas premier, je ne sais pas comment m´y prendre. Pour être plus concret, j´ai trouvé un sîte d´exercices d´arithmétique, où il s´agit, entre autre, d´opérations sur F4. Naivement j´ai essayé de faire les calculs exactement comme si 4 était premier, et logiquement, j´ai tout faux...

    Voilà le sîte:

    http://wims.auto.u-psud.fr/wims/wims...bra%2Foefff.fr
    OEF corps finis

    Comment faut-il s´y prendre?

    merci d´avance

  4. #4
    invité576543
    Invité

    Re : Divisin euclidienne dans F2

    Attention, ça ne marche que dans certains cas! On peut très bien avoir un produit dans P(F2) qui ne correspond à rien pour les polynômes sur Z.

    Par exemple X²+1 est divisible par X+1 dans P(F2), et la méthode consistant à travailler dans Z ne risque pas de donner la bonne division!

    Pour faire une division euclidienne entre polynômes de F2, faut faire comme pour des polynomes sur Z, mais en faisant les additions et soustractions dans Z/2Z, à chaque opération élémentaire.

    Cordialement,

  5. A voir en vidéo sur Futura
  6. #5
    invité576543
    Invité

    Re : Divisin euclidienne dans F2

    Citation Envoyé par christophe_de_Berlin Voir le message
    Super merci, c´est exactement la confirmation dont j´avais besoin.

    Mais dans ce (presque) même chapitre, j´ai une autre question: Il s´agit cette fois d´opérations dans des corps finis Fp. Si p est premier, c´est simple, il suffit comme tu l´expliques de calculer dans Z (addition ou multiplication, peu importe) puis de faire modulo p.

    Par contre sur Fn, n n´était pas premier, je ne sais pas comment m´y prendre. Pour être plus concret, j´ai trouvé un sîte d´exercices d´arithmétique, où il s´agit, entre autre, d´opérations sur F4. Naivement j´ai essayé de faire les calculs exactement comme si 4 était premier, et logiquement, j´ai tout faux...

    Voilà le sîte:

    http://wims.auto.u-psud.fr/wims/wims...bra%2Foefff.fr
    OEF corps finis

    Comment faut-il s´y prendre?

    merci d´avance
    PEux-tu préciser et présenter un exemple?

    Les calculs dans Z/nZ se font de la même manière pour n premier ou pas, ce qui change est le fait que certains nombres non nuls n'ont pas d'inverse, et que ab=0 n'implique pas que a=0 ou b=0.

    Cordialement,

  7. #6
    Gwyddon

    Re : Divisin euclidienne dans F2

    Pour les corps fini Fp avec p non premier, on peut peut-être se ramener à un corps isomorphe particulier dans lequel effectuer l'opération non ?

    Bon ok calculer dans un corps de rupture de polynôme, ce n'est pas folichon
    A quitté FuturaSciences. Merci de ne PAS me contacter par MP.

  8. #7
    christophe_de_Berlin

    Re : Divisin euclidienne dans F2

    Ben oui, justement, c´est ça le problème dans cette série d´exos: Ils parlent de F4, donc du corps à 4 éléments {0,1,2,3}, mais justement il ne s´agit pas de Z/4Z vu que Z/4Z n´est pas un corps. Donc comment faire des opérations dans F4, vu que ce sont exactement les mêmes éléments, mais pas les mêmes opérations.

    D´une façon générale, quand on parle de Fn, il s´agit du corps à n éléments 0 à (n-1). Donc si n est premier, Z/nZ étant alors un corps, on a Fn = Z/nZ. Mais si n n´est pas premier, alors Z/nZ n´est pas un corps, donc Fn <> Z/nZ. Du moins c´est ce que je crois avoir compris. Quelqu´un peut-il me le confirmer?

  9. #8
    Gwyddon

    Re : Divisin euclidienne dans F2

    Tu as raison, d'ailleurs une discussion récente citait des exemples de corps à 4 éléments (des corps de rupture, comme je te le disais).
    A quitté FuturaSciences. Merci de ne PAS me contacter par MP.

  10. #9
    christophe_de_Berlin

    Re : Divisin euclidienne dans F2

    Donc euh... personne sait faire ces exos dans F4 dans ce sîte?

  11. #10
    invite8b04eba7

    Re : Divisin euclidienne dans F2

    Citation Envoyé par mmy Voir le message
    Attention, ça ne marche que dans certains cas! On peut très bien avoir un produit dans P(F2) qui ne correspond à rien pour les polynômes sur Z.
    On est d'accord, mais ça n'empeche pas la division euclidienne de marcher (le reste dans Z[X] peut etre nul dans Z/2Z[X]).

  12. #11
    invite8b04eba7

    Re : Divisin euclidienne dans F2

    Citation Envoyé par christophe_de_Berlin Voir le message
    Donc euh... personne sait faire ces exos dans F4 dans ce sîte?
    Il suffit de comprendre ce qu'est F4 : une division euclidienne ça ne requiert que des additions, des multiplications et peut-être une division.

  13. #12
    christophe_de_Berlin

    Re : Divisin euclidienne dans F2

    Bon ben entretemps j´ai trouvé une réponse (pragmatique, car sans explication) à ma question au sujet de F4: un texte dans Internet, avec une table de multiplication et une d´addition dans F4:


    http://www.math.u-bordeaux.fr/~lasjauni/page_fr_8.htm
    Page 8 sur 10

    Par contre je ne m´explique toujours pas comment ils en arrivent à ce résultat.

  14. #13
    invite8b04eba7

    Re : Divisin euclidienne dans F2

    Salut !

    Il me semble t'avoir déjà répondu à cette question : le groupe multiplicatif de F4 est cyclique de cardinal 3, engendré par un élément w. Si tu rajoutes 0 (qui annule tous les autres) tu obtiens ta loi de multiplication.

    Pour la loi d'addition, le nombres 0 et 1 se comportent très bien entre eux. La seule relation non triviale est 1 + w +w^2 = 0 (ça n'est pas difficile de voir que 1+w est différent de 0,1 et w). Toutes les autres se déduisent de celle là et du fait que le corps est de caractéristique 2.

Discussions similaires

  1. Division euclidienne
    Par inviteb150b6f0 dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 01/12/2007, 14h43
  2. division euclidienne
    Par invite4f4507a2 dans le forum Mathématiques du collège et du lycée
    Réponses: 2
    Dernier message: 24/11/2007, 19h20
  3. division euclidienne
    Par invitede8a3ed2 dans le forum Mathématiques du collège et du lycée
    Réponses: 12
    Dernier message: 16/09/2006, 15h34
  4. division euclidienne
    Par christophe_de_Berlin dans le forum Mathématiques du supérieur
    Réponses: 10
    Dernier message: 13/06/2006, 13h58
  5. Division euclidienne
    Par invitee240f783 dans le forum Mathématiques du supérieur
    Réponses: 7
    Dernier message: 13/10/2005, 19h13