Corps fini - Codes lineaires

[invite6754323456711]

Bonjour,

Si q est une puissance d'un nombre premier il existe un et un seul corps fini de cardinal q à isomorphisme prés. Ce corps est noté F_q. L'ensemble des messages E = F_q ^k est maintenant structuré en espace vectoriel de dimension k sur F_q

Cela signifie t'il que si q n'est pas une puissance d'un nombre premier alors il peut exister plusieurs corps fini (distinct) de cardinal q ?


Quel est l'intérêt de cette propriété dans les codes linéaires http://fr.wikipedia.org/wiki/Code_lin%C3%A9aire ?

Merci
Patrick
-----

[invitebe0cd90e]

Non, ca n'est pas tres clair dans ce que tu cites, mais en fait le cardinal d'un corps fini est forcement une puissance d'un nombre premier, qui accessoirement est sa caracteristique.

[invite6754323456711]

Non, ca n'est pas tres clair dans ce que tu cites, mais en fait le cardinal d'un corps fini est forcement une puissance d'un nombre premier, qui accessoirement est sa caracteristique.

Merci. Je ne dois pas bien comprendre ce qu'est un corps fini.

un corps fini est entièrement déterminé par son cardinal qui est toujours de la forme pⁿ, une puissance d'un nombre premier.

Pourquoi une telle définition ? Quelles sont les propriété remarquables d'un corps fini ?

Le plus petit corps fini est (F₂, +, .).

(F₃₆₀, +,.) n'est donc pas un corps fini car 360 = 2³ x 3² x 5 ?

Patrick

[invite986312212]

Merci. Je ne dois pas bien comprendre ce qu'est un corps fini.

c'est tout bêtement un corps qui a un nombre fini d'éléments. Alors qu'il y a des groupes de tous ordres, et même en général plusieurs groupes non isomorphes d'ordre donné, ce n'est pas le cas pour les corps: le cardinal doit être une puissance d'un nombre premier et il n'y a qu'un corps de cardinal (fini) donné. Le Cours d'Arithmétique de Serre donne une preuve de ce fait.

[A voir en vidéo sur Futura]

[invitebe0cd90e]

Pourquoi une telle définition ? Quelles sont les propriété remarquables d'un corps fini ?

Bah c'est un corps, et il est fini La phrase que tu donnes n'est absolument pas une definition, mais une propriété remarquable. Elle dit que si un corps possede un nombre fini d'element alors ce nombre d'element est forcement une puissance d'un nombre premier.

Peut etre en fait que tu ne sais pas ce qu'est un corps au sens mathématique ?

[invite6754323456711]

Peut etre en fait que tu ne sais pas ce qu'est un corps au sens mathématique ?

Surement quelque chose m'échappe.

Je comprend (http://fr.wikipedia.org/wiki/Corps_(math%C3%A9matiques) : Un corps est un ensemble K muni de deux lois internes notées en général + et × vérifiant :

(K, +) forme un groupe commutatif dont l'élément neutre est noté 0
(K \ {0}, ×) forme un groupe multiplicatif.
a multiplication est distributive pour l'addition (à gauche comme à droite) c’est-à-dire que.

Ce qui me trouble c'est :

Elle dit que si un corps possède un nombre fini d'element alors ce nombre d'élément est forcement une puissance d'un nombre premier.

Par exemple l'ensemble ensemble ayant un cardinal de 360 (= 2³ x 3² x 5) a bien un nombre fini d'élément. Il n'est pas dit se décompose en produit de facteurs premiers car tout nombre naturel n non nul peut s'écrire de manière unique comme le produit fini de nombres premiers à une puissance adéquate.


Patrick

[invite57a1e779]

Par exemple l'ensemble ensemble ayant un cardinal de 360 (= 2³ x 3² x 5) a bien un nombre fini d'élément. Il n'est pas dit se décompose en produit de facteurs premiers car tout nombre naturel n non nul peut s'écrire de manière unique comme le produit fini de nombres premiers à une puissance adéquate.

Tout simplement, sur un ensemble fini de cardinal 360, on ne peut pas définir une addition et une multiplication en satisfaisant les axiomes des corps.

[invitebe0cd90e]

Surement quelque chose m'échappe.

Je comprend (http://fr.wikipedia.org/wiki/Corps_(math%C3%A9matiques) : Un corps est un ensemble K muni de deux lois internes notées en général + et × vérifiant :

Voila. Moralement, un corps c'est un ensemble avec deux trucs qui ressemblent a une addition et une multiplication, et tel que tout element non nul est inversible pour la multiplication, et tout element est inversible pour l'addition.

Ce qui me trouble c'est :



Par exemple l'ensemble ensemble ayant un cardinal de 360 (= 2³ x 3² x 5) a bien un nombre fini d'élément. Il n'est pas dit se décompose en produit de facteurs premiers car tout nombre naturel n non nul peut s'écrire de manière unique comme le produit fini de nombres premiers à une puissance adéquate.


Patrick

La je crois que tu n'as pas compris. Un corps fini n'est pas "un ensemble a tant d'element" !!! C'est un ensemble AVEC des operations qui verifient certaines propriétés. Donc parler ici de "l'ensemble a 360 element" n'a simplement pas de sens, ou si tu preferes il n'existe pas de corps ayant 360 elements.

[invite6754323456711]

Bonjour,

Merci pour vos réponses.

Donc un base 360 ne peut donc être un corps comme l'est une base 2 {0,1} ?

Quels sont les axiomes des corps qui ne peuvent être satisfait ?

Patrick

[invitebe0cd90e]

Donc un base 360 ne peut donc être un corps comme l'est une base 2 {0,1} ?

Le terme "une base" n'est pas vraiment correct ici, attention au sens des mots en maths. Disons qu'un ensemble possedant 360 elements ne peut pas etre muni d'une structure de corps

Quels sont les axiomes des corps qui ne peuvent être satisfait ?

Essentiellement c'est celui qui distingue un corps d'un anneau, puisque il existe par contre des anneaux ayant 360 elements (Z/360Z par exemple), cad le fait que tout element non nul soit inversible pour la multiplication.

Par exemple et sauf erreur de ma part, 5 n'est pas inversible dans Z/360Z puisque c'est ce qu'on appelle un "diviseur de 0" (car 5*72=0 dans cet anneau)

[invite6754323456711]

Essentiellement c'est celui qui distingue un corps d'un anneau, puisque il existe par contre des anneaux ayant 360 elements (Z/360Z par exemple), cad le fait que tout element non nul soit inversible pour la multiplication.

Par exemple et sauf erreur de ma part, 5 n'est pas inversible dans Z/360Z puisque c'est ce qu'on appelle un "diviseur de 0" (car 5*72=0 dans cet anneau)

Nous avons bien ? :
- Un corps (commutatif) K est un anneau tel que tout élément non nul soit inversible pour la multiplication.

- Z/360Z est l'ensemble des classes d'équivalence pour la congruence modulo 360. Il comporte 360 classes d'équivalence.

- Inversible signifie bien : Tout élément a appartenant à Z/360Z qui admettent un symétrique pour la seconde loi * de l'anneau.

- x a un inverse x' pour la multiplication si x * x' = x' * x = 1 (classe d'équivalence 1)

Maintenant pour Z/16Z on a bien aussi 4* 4 = 4 * 8 = 4 * 12 = 0 de plus il n'existe pas de classe d'équivalence x tel que 4 * x = 1 (http://homeomath.imingo.net/opeznz.htm). Pourtant 16 = 2⁴ et 2 est bien premier ?

Il y a donc encore quelque chose que je ne maitrise pas.

Patrick

[invite769a1844]

Salut,

comme tu dis Z/16Z n'est pas un corps, c'est seulement un anneau,
bien que 16=2^4. Tu aurais pu prendre un exemple similaire plus simple: Z/4Z.

Les seuls corps du type Z/nZ, sont les Z/pZ (de cardinal p) avec p premier.

Après on peut fabriquer des corps finis de cardinal (avec p premier et n entier naturel quelconque), mais ce ne sera pas si n>1.

En particulier il existe un corps a quatre éléments (qui n'est pas Z/4Z), et un corps a 16 éléments (qui n'est pas Z/16Z).

[invite6754323456711]

Bonjour,

En fait je m'intéresse au "Codage Réseau" (Network Coding) qui est une méthode de transmission de données multipoint. L’idée de base consiste à demander aux routeurs de "combiner" les flux qu’il reçoivent et à rediriger ces combinaisons vers les différentes routes. Ces combinaisons de flux sont des combinaisons linéaires où les flux sont considérés comme des suites d’éléments de corps finis. Certains travaux récents ont montré que cette technique permet d’optimiser l’utilisation des liens et d’améliorer la tolérance aux fautes du système.

Voir définition code linéaire (http://fr.wikipedia.org/wiki/Code_lin%C3%A9aire) ou il est question de corps fini mais aussi de base.

Soit p un nombre premier, d une puissance de p, n un entier strictement positif et k un entier plus petit que n. Un code linéaire C de dimension k et de longueur n est un sous-espace vectoriel de F^d_n de dimension k. Si d est égal à deux, le code est dit binaire sinon on parle de code linéaire de base d.

Patrick

[invite769a1844]

oui il est question de base d'espace vectoriel (vu qu'on considère que des -espaces vectoriel de dimension finie.

ce sont les bases d'espace vectoriel, à ne pas confondre avce le terme "base" que tu as utilisé dans ton message de 20h07.

[invitebe0cd90e]

Maintenant pour Z/16Z on a bien aussi 4* 4 = 4 * 8 = 4 * 12 = 0 de plus il n'existe pas de classe d'équivalence x tel que 4 * x = 1 (http://homeomath.imingo.net/opeznz.htm). Pourtant 16 = 2⁴ et 2 est bien premier ?

Attention ! Tout corps fini a pour cardinal une puissance d'un nombre premier, mais ca ne veut evidemment pas dire que tout anneau dont le cardinal est une puissance d'un nombre premier est forcement un corps !

l'unique corps de cardinal 16 est (Z/2Z)^4, qui n'est pas isomorphe a Z/16Z, sauf erreur de ma part (il est deja tard )

[invite6754323456711]

oui il est question de base d'espace vectoriel (vu qu'on considère que des -espaces vectoriel de dimension finie.

ce sont les bases d'espace vectoriel, à ne pas confondre avce le terme "base" que tu as utilisé dans ton message de 20h07.

En fait d est un alphabet par exemple {0,1} et est un espace vectoriel de dimension n.

Avec 16 symboles on aurait toujours qui est un espace vectoriel de dimension n.

Il me semble que le d de s'interprète bien comme une base (pas celle de l'espace vectoriel)


Maintenant effectivement il faut lire la propriété A ==> B (Tout corps fini a pour cardinal une puissance d'un nombre premier) mais pas l'inverse.

Merci
Patrick

[invite986312212]

salut,

il faut bien comprendre la chose suivante: un anneau Z_n (on note aussi Z/nZ) n'est un corps que si n est premier. Si tu considères un corps fini à p^n éléments avec n>1, il n'est donc pas isomorphe à Z_(p^n) et en particulier son groupe additif n'est certainement pas cyclique. En revanche, le groupe multiplicatif d'un corps fini est toujours cyclique.
par exemple le corps à 4 éléments, noté F_4, a pour groupe additif le vierergruppe de Klein, et pas le groupe additif de Z_4.

[invitebe0cd90e]

Ca n'est pas totalement faux, effectivement tu peux identifier F_2^n a l'ensemble des nombre binaires compris entre 0 et 2^n-1, donc comme des nombres écrits en base 2, et c'est probablment ce qu'on fait dans le contexte des codes lineaires.

Donc a la limite je comprends que tu aies envie de dire "F_10^n c'est l'ensemble des nombres en base 10 entre 0 et 10^n-1", et de poser ca comme definition. Sauf que F_10 ne veut rien dire puisque il n'existe pas de corps a 10 elements, et donc f_10^n n'est pas un espace vectoriel, etc... Mais je comprends que tu aie cette idée.

Donc du strict point de vue "ecrire des nombres dans une certaine base", ca se tient. Sauf que dans ces histoires de codes linéaires, de codes correcteurs, etc.. on est amené evidemment a faire des operations sur les éléments de F_q^n. Et il est probable qu'en general, pour que ces operations aient un sens il est crucial d'avoir un espace vectoriel, et donc un corps en dessous.

[invite6754323456711]

Et il est probable qu'en general, pour que ces operations aient un sens il est crucial d'avoir un espace vectoriel, et donc un corps en dessous.

L'objectif est bien d'avoir une structure algébrique pour faire des opérations qui ont sens.

C'est bien l'étude des codes linéaires sur un corps fini . Ma vision de base n'est surement pas la bonne compréhension qu'il faut avoir.

Peut on résumer ainsi :

Si p est un nombre premier, il existe un unique (à isomorphisme prés) corps fini à p éléments qui est muni des opérations usuelles.

Maintenant pour un entier q quelconque, il existe un corps fini à q éléments si et seulement si q est une puissance d’un nombre premier p (q=p^r). Dans ce cas il est unique (à isomorphisme prés), il contient un unique sous-corps isomorphe sur lequel il est un espace vectoriel de dimension r.

Patrick

[invitebe0cd90e]

C'est ca, et du coup si q=p^r, on peut voir F_q comme (F_p)^r

Donc au final tu as des espaces vectoriels sur F_q, qui est lui meme un espace vectoriel sur F_p.

Et pour completer ma derniere reponse : tu as donc raison, du point de vue des codes lineaires, de parler de q comme une base au sens "ecrire un entier en base q".

S'il s'agissait uniquement d'encoder des entiers dans une certaine base, un q quelqconque conviendrait. Mais comme derriere tu veux effectuer des operations sur ces codes, tu as besoin d'avoir un espace vectoriel, donc un corps, donc que q soit une puissance d'un nombre premier.

Tout ceci etant finalement un peu abstrait dans la mesure ou in fine j'imagine qu'on parle de binaire, et donc tout se passe sur le corps F_2, donc la question ne se pose pas vraiment.

[invite6754323456711]

Tout ceci etant finalement un peu abstrait dans la mesure ou in fine j'imagine qu'on parle de binaire, et donc tout se passe sur le corps F_2, donc la question ne se pose pas vraiment.

Pour amélioration les vitesses de codage et de décodage il est définit des codes sur le corps fini F₂¹⁶. Les éléments de ce corps pouvant être vus comme des entiers codés sur 16 bits, les processeurs classiques les manipulent plus facilement.

http://www.laas.fr/~juanole/seminair...lides/lacan.pd

Patrick

[invite6754323456711]

Pour amélioration les vitesses de codage et de décodage il est définit des codes sur le corps fini F₂¹⁶. Les éléments de ce corps pouvant être vus comme des entiers codés sur 16 bits, les processeurs classiques les manipulent plus facilement.

http://www.laas.fr/~juanole/seminair...lides/lacan.pd

Patrick

erreur url
http://www.laas.fr/~juanole/seminair...ides/lacan.pdf

Patrick

[invité576543]

Pour amélioration les vitesses de codage et de décodage il est définit des codes sur le corps fini F₂¹⁶. Les éléments de ce corps pouvant être vus comme des entiers codés sur 16 bits, les processeurs classiques les manipulent plus facilement.

Ce n'est pas vraiment les voir comme des entiers qui aide (au contraire). C'est juste que le code porte sur des symboles dont la représentation naturelle est une chaîne de 16 bits, et une taille de 16 bits qui est adapté à la mémoire et aux registres.

Quand on travaille avec les codes linéaires de ce genre, les opérations ne sont pas celles sur des nombres entiers. L'addition est le ou exclusif bit à bit, et la multiplication une suite de décalages et de ou exclusif. Rien à voir avec l'arithmétique des nombres codés en positionnel binaire.

Cordialement,

[invitebe0cd90e]

Pour amélioration les vitesses de codage et de décodage il est définit des codes sur le corps fini F₂¹⁶. Les éléments de ce corps pouvant être vus comme des entiers codés sur 16 bits, les processeurs classiques les manipulent plus facilement.

http://www.laas.fr/~juanole/seminair...lides/lacan.pd

Patrick

Oui, bien sur, mais c'est toujours sur F_2, c'est toujours des puissances de 2 qu'on manipule puisque l'un dans l'autre on est toujours sur des architectures qui reposent sur du binaire, c'est ca que je voulais dire.

[invite6754323456711]

Quand on travaille avec les codes linéaires de ce genre, les opérations ne sont pas celles sur des nombres entiers. L'addition est le ou exclusif bit à bit, et la multiplication une suite de décalages et de ou exclusif. Rien à voir avec l'arithmétique des nombres codés en positionnel binaire.

Oui.

Mon intérêt est de comprendre le formalisme mathématiques sur lequel s'appuie l'utilisation des codes linéaires dans le domaine des réseaux. Le codage réseau (unifie les concepts réseaux à la théorie de l'information et du codage) est par exemple une technologie émergente s'intéressant à l'optimisation de la capacité du réseau.


Patrick