Transformée de Walsh 210026 31288120 2008-07-04T09:27:51Z Valvino 116222 /* Lien externe */ [[Catégorie:Transformée]] {{à recycler (mathématiques)}} En [[mathématiques]], et plus précisément en [[analyse harmonique sur un groupe abélien fini|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 [[nombre complexe|nombres complexes]]. Elle est utilisée en [[théorie de l'information]] à la fois pour les [[code linéaire|codes linéaires]] et la [[cryptographie]]. == Définition == Soit ''G'' un [[groupe abélien fini]] d'ordre ''g'' et d'[[exposant d'un groupe|exposant]] une puissance n<sup>ième</sup> d'un [[nombre premier]] ''p'', ''F''<sub>p<sup>n</sup></sub> le [[corps fini]] de cardinal ''p'' <sup>n</sup>, χ un [[caractère d'un groupe fini|caractère]] à valeur dans ''F''<sub>p<sup>n</sup></sub> et ''f'' une fonction de ''G'' dans ''F''<sub>p<sup>n</sup></sub>. :* La '''transformée de Walsh''' est une fonction, souvent noté <math>\widehat f</math> de l'ensemble des caractères de ''G'' dans le corps ''F''<sub>p<sup>n</sup></sub> définie par : <center><math>\widehat f (\chi) \ = \frac 1g \sum_{s \in G} f(s)\chi^{-1}(s)</math></center> == 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 d'un groupe fini|algèbre du groupe]] est alors la suivante : <center><math>\forall f,h \in \mathbb F_{p^n}^G <f|h>=\frac 1g \sum_{s \in G} f(s)^{-1}.\,h(s) \;</math></center> 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 :<math>f_j=\sum_{k=0}^{n-1}x_k\left(e^{-\frac{2\pi i}{n}}\right)^{jk}\quad\quad j=0,\dots,n-1</math> La transformation théorique de nombre opère sur une suite de ''n'' nombres, modulo un [[nombre premier]] ''p'' de la forme <math>p = \xi n + 1\,</math>, où <math>\xi\,</math> peut être tout nombre entier positif. Le nombre <math>e^{-\frac{2\pi i}{n}}\,</math> est remplacé par un nombre <math>\omega^{\xi}\,</math> où <math>\omega\,</math> est une « [[racine primitive]] » de ''p'', un nombre où le plus petit nombre entier positif <math>\alpha\,</math> où <math>\omega^{\alpha} = 1\,</math> est <math>\alpha = p - 1\,</math>. Il devrait y avoir une quantité d'<math>\omega\,</math> qui collent à cette condition. Les deux nombres <math>e^{-\frac{2\pi i}{n}}\,</math> et <math>\omega^{\xi}\,</math> é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 :<math>f(x)_j=\sum_{k=0}^{n-1}x_k(\omega^\xi)^{jk}\mod p\quad\quad j=0,\dots,n-1</math> == Contexte == La transformation théorique de nombre inverse est donnée par :<math>f^{-1}(x)_h=n^{p-2}\sum_{j=0}^{n-1}x_j(\omega^{p-1-\xi})^{hj}\mod p\quad\quad h=0,\dots,n-1</math> :<math>\omega^{(p-1-\xi)} = \omega^{-\xi}\,</math>, l'inverse de <math>\omega^{\xi}\,</math>, et <math>n^{p-2} = n^{-1}\,</math>, l'inverse de ''n''. (mod p) L'inverse est vrai, car <math>\sum_{k=0}^{n-1}z^k</math> est ''n'' pour z=1 et 0 pour tous les autres ''z'' où <math>z^n = 1\,</math>. Une démonstration de ceci (devrait marcher pour toute [[algèbre de division]]) est :<math>z\left(\sum_{k=0}^{n-1}z^k\right)+1=\sum_{k=0}^nz^k</math> :<math>z\sum_{k=0}^{n-1}z^k=\sum_{k=0}^{n-1}z^k</math> (soustrayant <math>z^n = 1\,</math>) :<math>z=1\,</math> si <math>\sum_{k=0}^{n-1}z^k\ne 0</math> (divisant les deux cotés) Si ''z''=1 alors nous pouvions voir de manière triviale que <math>\sum_{k=0}^{n-1}z^k=\sum_{k=0}^{n-1}1=n</math>. Si <math>z \ne 1\,</math> 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. :<math>f^{-1}(f(x))_h=n^{p-2}\sum_{j=0}^{n-1}\left(\sum_{k=0}^{n-1}x_k\left(\omega^\xi\right)^{jk}\right)(\omega^{p-1-\xi})^{hj}\mod p</math> :<math>f^{-1}(f(x))_h=n^{p-2}\sum_{j=0}^{n-1}\sum_{k=0}^{n-1}x_k(\omega^\xi)^{jk-hj}\mod p</math> :<math>f^{-1}(f(x))_h=n^{p-2}\sum_{k=0}^{n-1}x_k\sum_{j=0}^{n-1}(\omega^{\xi(k-h)})^j\mod p</math> :<math>f^{-1}(f(x))_h=n^{p-2}\sum_{k=0}^{n-1}x_k\left\{\begin{matrix}n,&k=h\\0,&k\ne h\end{matrix}\right\}\mod p</math> (puisque <math>\omega^{\xi} = 1\,</math>) :<math>f^{-1}(f(x))_h=n^{p-2}x_hn\mod p</math> :<math>f^{-1}(f(x))_h=x_h\mod p</math> ==Voir aussi== *[[convolution]] *[[algorithme de multiplication]] ==Lien externe== *[http://www.apfloat.org/ntt.html Site qui (heureusement) relate la même chose que cet article (en anglais)] {{portail mathématiques}} [[Catégorie:Arithmétique modulaire]] [[Catégorie:Analyse harmonique discrète]] [[Catégorie:Transformée]] [[en:Number-theoretic transform]] [[zh:數論轉換]]