Forum : algèbre :
[TIPË] Codes linéaires

Bonjour

Il serait temps que je commence mon TIPE, je passe lundi

J'aurai au fur et à mesure des questions d'algèbres à poser à propos de cet article

citation :
Si est une puissance non nulle d'un nombre premier, on sait qu'il existe à isomorphisme près un unique corps fini de cardinal . Choisissons comme ensemble des messages. L'ensemble devient maintenant un espace vectoriel de dimension sur , et il est naturel de ne considérer que les fonctions d'encodage linéaires. Le code est alors structuré en sous-espace vectoriel de (page 10)

On peut m'expliquer ?

Merci !

Salut vieux,

Hé j'ai fait mon TIPE sur la crypto sur les corps finis. C'était marrant.

Voici ce que j'ai compris:

Tu munis E d'une structure de F_q espace vectoriel, rien de plus naturel. f va permettre de coder, ie de passer d'éléments de E à Q (enfin, c'est comme ça qu'ils l'appellent dans le pdf). Ce qu'il entend par encodage linéaire, c'est que tout bêtement, l'application qui à un élément de E associe le "c" est linéaire...

Salut vieux

Le principe du codage je l'ai capté, c'est le décor mathématique où c'est moins clair, mais ça c'est ta branche tu vas pouvoir m'aider

citation :
Tu munis E d'une structure de F_q espace vectoriel, rien de plus naturel

Pas si naturel pour moi

Fq c'est bien Z/qZ avec q premier ?

Comment on confère à E une structure d'espace vectoriel alors ?

Merci !

Non, c'est le piège classique.

Ca c'est vrai uniquement quand p es premier, ce qui n'est pas le cas ici (pas a priori du moins). Pour q non premier, Fq ne peut plus se visualiser comme un corps de nombre. Au mieux, on peut le voir comme une sorte de "corps de polynômes".
Sais-tu ce qu'est un corps de rupture? (ou de décomposition)? Je pourrai pas aller plus loin dans mon analogie sinon...

J'ai pas compris, dis moi c'est quoi le corps fini Fq

citation :
Sais-tu ce qu'est un corps de rupture? (ou de décomposition)? Je pourrai pas aller plus loin dans mon analogie sinon...

On en a besoin pour montrer que E est un ev ?

Faut vraiment que j'aille à l'essentiel j'ai très peu de temps pour boucler le TIPE

Bonjour Kevin

Pour faire simple (!!) Pour tout p premier et tout k>0 il existe un corps ayant q=p^k éléments. Si tu n'as pas trop de temps, admets simplement son existence (et son unicité à isomorphisme près). Pour k=1, c'est bien Z/pZ. Par exemple, F₄ a 4 éléments: 0,1, et 1+. L'addition est donnée par le fait que x+x=0 pour chaque x.Pour la multiplication, il suffit de savoir que ²=1+.

Ensuite, tu oublies, et tu travailles avec les applications linéaires comme d'habitude...

Camélia >> Oui, mais il va avoir du mal à faire du calcul dedans s'il n'a pas une vision un peu plus pratique des choses.

Kéké >> Je vais essayer d'aller à l'essentiel. Tu te rappelles de la construction de Z/pZ? Je vais essayer de faire pareil là.
Tu prends un corps fini de type F_p (p premier) et un polynôme irréductible sur F_p (de degré k) T.
On considère l'ensemble des polynômes de F_p[X] de degré strictement inférieur à k. On le note K.
L'addition est définie trivialement.
Pour la multiplication, tu prends 2 polynômes de K, disons P et Q. Leur produit est défini comme le reste de P*Q dans la division euclidienne par T.
L'irréductibilité permet de justifier l'existence de l'inverse (cf Bezout).
K est donc un corps, c'est le corps à p^k éléments. C'est assez utile pour faire des calculs.

D'accord merci à vous deux

Et les codes correcteurs de Hamming vous connaissez ? Parce que dans le lien ils définissent la matrice génératrice mais ils ne disent pas comment on l'obtient..

Arf plus loin ils donnent des polynômes générateurs mais j'aurais pas le temps d'aborder toutes les notions d'algèbre qui sont derrière, j'me réserve ça pour cet été, lundi j'admettrai les résultats tant pis

Le code de Hamming... ouais j'ai vaguement vu ça en SI... ça permet de repérer une erreur (pas plus) et ça la corrige même pas. Enfin, c'est ce qu'on avait vu. On l'améliore peut être dans le pdf, je sais pas. J'y suis pas arrivé.
Bon courage en tous cas.

citation :
ça permet de repérer une erreur (pas plus) et ça la corrige même pas. Enfin, c'est ce qu'on avait vu

Une seule erreur effectivement, mais ça la corrige !

Au temps pour moi.

On parle de codes dans deux cas très différents :
- lorsque qu'on veut envoyer un message crypté (cryptographie RSA par ex)
- lorsque qu'on envoie une information qui se trouve perturbée par la transmission et qu'il faut reconstituer à l'arrivée. c'est un code correcteur d'erreurs.
Parmi ces codes correcteurs, il y en a qui sont basés sur l'algèbre linéaire sur les corps finis et particulièrement sur le corps   qui a l'avantage de contenir deux éléments 0 et 1 et de ce fait d'être proche de la modélisation informatique (code de Hamming). Le code est constitué de vecteurs (liste de 0 et 1) et n'utilise que de l'algèbre linéaire élémentaire (licence1).

Des codes plus perfectionnés utilisent davantage la structure des corps à q éléments addition et multiplication et le fait que le groupe multiplicatif soit cyclique. Ce sont les codes BCH. Pour bien comprendre leur fonctionnement il faut bien connaître les corps finis. c'est un peu trop difficile en prépa c'est plutôt niveau licence 3 ou niveau master.

Un code correcteur peut corriger plusieurs erreurs mais le nombre maximum d'erreurs corrigeables est fixé à l'avance selon la fiabilité du système de transmission utilisé : nombre de bits contenus dans un paquet, cable ou sattelite etc. Certains codes peuvent seulement détecter un nombre d'erreurs (également fixé à l'avance) sans les corriger.
Pour en savoir plus un document sur le sujet se trouve ici dans les documents pédagogiques sous la rubrique compléments, codes correcteurs.
Il ne faut pas tout lire, car le niveau est sans doute trop élevé le début peut t'éclairer sur les codes de Hamming et il y a à la fin une bibliographie mais c'est plutôt niveau master sauf le Child qui donne des exemples très concrets mais ne se lit pas tout de même en trois jours ! Plutôt une lecture pour l'été.

[Dem] M. Demazure, Cours d'alg`ebre, Cassini 1997. niveau master
[Esc] J-P. Escofier, Th ́eorie de Galois, Dunod 1997. niveau master
[Chi] L. Childs, A Concrete Introduction to Higher Algebra, Springer Verlag. plus concret mais en anglais
[Gan] F.R. Gantmacher, Th ́eorie des matrices, tome 1, Dunod. niveau master
[PW] O. Papini et J. Wolfman, Alg`ebre discr`ete et codes correcteurs, Springer Verlag. niveau master peut être plus abordable