- Transformée de walsh
-
Transformée de Walsh
En mathématiques, et plus précisément en analyse harmonique la transformée de Walsh est l'analogue de la Transformée de Fourier discrète.
Elle opère sur un corps fini de l'arithmétique modulaire à la place des nombres complexes.
Elle est utilisée en théorie de l'information à la fois pour les codes linéaires et la cryptographie.
Sommaire
Définition
Soit G un groupe abélien fini d'ordre g et d'exposant une puissance nième d'un nombre premier p, Fpn le corps fini de cardinal p n, χ un caractère à valeur dans Fpn et f une fonction de G dans Fpn.
-
- La transformée de Walsh est une fonction, souvent noté de l'ensemble des caractères de G dans le corps Fpn définie par :
Analyse harmonique sur un groupe abélien fini
Article détaillé : Analyse harmonique sur un groupe abélien fini.Le contexte est identique à celui de l'analyse harmonique classique d'un groupe abélien fini. La forme bilinéaire associée à l'algèbre du groupe est alors la suivante :
L'ensemble des résultats de la théorie de l'analyse harmonique s'applique, on dispose ainsi de l'égalité de Parseval, du théorème de Plancherel, d'un produit de convolution, de la dualité de Pontryagin ou encore de la formule sommatoire de Poisson.
Cas d'un espace vectoriel fini
Article détaillé : Analyse harmonique sur un espace vectoriel fini.Il existe un cas particulier, celui ou le groupe G est le groupe additif d'un espace vectoriel fini. Un cas particulier est celui ou G est un corps.
La transformation discrète de Fourier est donnée par
La transformation théorique de nombre opère sur une suite de n nombres, modulo un nombre premier p de la forme , où peut être tout nombre entier positif.
Le nombre est remplacé par un nombre où est une « racine primitive » de p, un nombre où le plus petit nombre entier positif où est . Il devrait y avoir une quantité d' qui collent à cette condition. Les deux nombres et élevé à la puissance n sont égaux à 1 (mod p), toutes les puissances inférieures différentes de 1.
La transformation théorique de nombre est donnée par
Contexte
La transformation théorique de nombre inverse est donnée par
- , l'inverse de , et , l'inverse de n. (mod p)
L'inverse est vrai, car est n pour z=1 et 0 pour tous les autres z où . Une démonstration de ceci (devrait marcher pour toute algèbre de division) est
- (soustrayant )
- si (divisant les deux cotés)
Si z=1 alors nous pouvions voir de manière triviale que . Si alors le coté droit doit être faux pour éviter une contradiction.
Nous pouvons maintenant compléter la démonstration. Nous prenons la transformation inverse de la transformation.
- (puisque )
Voir aussi
Lien externe
- Portail des mathématiques
Catégories : Page à recycler (mathématiques) | Arithmétique modulaire | Analyse harmonique discrète | Transformée -
Wikimedia Foundation. 2010.