Transformée de Walsh

Pour les articles homonymes, voir Walsh.

Cet article concernant les mathématiques doit être recyclé (septembre 2006).

Une réorganisation et une clarification du contenu paraissent nécessaires. Améliorez-le, discutez des points à améliorer ou précisez les sections à recycler en utilisant {{section à recycler}}.

Cet article ne cite pas suffisamment ses sources (avril 2019).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

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 à 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.

Définition

Soit G un groupe abélien fini d'ordre g et d'exposant une puissance n-ième d'un nombre premier p, F_pⁿ le corps fini de cardinal pⁿ, χ un caractère à valeur dans F_pⁿ et f une fonction de G dans F_pⁿ. La transformée de Walsh est une fonction, souvent notée ${\displaystyle {\widehat {f}}}$ de l'ensemble des caractères de G dans le corps F_pⁿ définie par :^{[réf. nécessaire]}

${\displaystyle {\widehat {f}}(\chi )\ ={\frac {1}{g}}\sum _{s\in G}f(s)\chi (s)^{-1}}$.

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 :

${\displaystyle \forall f,h\in \mathbb {F} _{p^{n}}^{G}<f|h>={\frac {1}{g}}\sum _{s\in G}f(s)^{-1}.\,h(s)\;}$

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

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

${\displaystyle 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}$

La transformation théorique de nombre^[Quoi ?] opère sur une suite de n nombres, modulo un nombre premier p de la forme ${\displaystyle p=\xi n+1\,}$, où ${\displaystyle \xi \,}$ peut être tout nombre entier positif.

Le nombre ${\displaystyle e^{-{\frac {2\pi i}{n}}}\,}$ est remplacé par un nombre ${\displaystyle \omega ^{\xi }\,}$ où ${\displaystyle \omega \,}$ est une racine primitive de p, un nombre où le plus petit nombre entier positif ${\displaystyle \alpha \,}$ où ${\displaystyle \omega ^{\alpha }=1\,}$ est ${\displaystyle \alpha =p-1\,}$. Il devrait y avoir une quantité d'${\displaystyle \omega \,}$ qui satisfassent à cette condition. Les deux nombres ${\displaystyle e^{-{\frac {2\pi i}{n}}}\,}$ et ${\displaystyle \omega ^{\xi }\,}$ élevés à 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

${\displaystyle f(x)_{j}=\sum _{k=0}^{n-1}x_{k}(\omega ^{\xi })^{jk}\mod p\quad \quad j=0,\dots ,n-1}$

Une preuve de la formule d'inversion

La transformation inverse est donnée par

${\displaystyle 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}$

${\displaystyle \omega ^{(p-1-\xi )}=\omega ^{-\xi }\,}$, l'inverse de ${\displaystyle \omega ^{\xi }\,}$, et ${\displaystyle n^{p-2}=n^{-1}\,}$, l'inverse de n. (mod p)

On vérifie que cette formule donne bien l'inverse car ${\displaystyle \sum _{k=0}^{n-1}z^{k}}$ vaut n pour z=1 et 0 pour tous les autres valeurs de z vérifiant ${\displaystyle z^{n}=1\,}$. En effet, on a la relation (qui devrait fonctionner dans toute algèbre à division)

${\displaystyle (z-1)\left(\sum _{k=0}^{n-1}z^{k}\right)=z^{n}-1}$

Soit, pour une racine ${\displaystyle n}$-ème de l'unité

${\displaystyle (z-1)\left(\sum _{k=0}^{n-1}z^{k}\right)=0}$

Un corps étant intègre, un des facteurs (au moins) de ce produit est nul. Donc, soit ${\displaystyle z=1}$ et trivialement ${\displaystyle \sum _{k=0}^{n-1}z^{k}=\sum _{k=0}^{n-1}1=n}$. Soit ${\displaystyle z\neq 1}$ et nécessairement ${\displaystyle \sum _{k=0}^{n-1}z^{k}=0}$.

Nous pouvons maintenant compléter la démonstration. Nous prenons la transformation inverse de la transformation.

${\displaystyle 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}$

${\displaystyle 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}$

${\displaystyle 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}$

${\displaystyle f^{-1}(f(x))_{h}=n^{p-2}\sum _{k=0}^{n-1}x_{k}\left\{{\begin{matrix}n,&k=h\\0,&k\neq h\end{matrix}}\right\}\mod p}$ (puisque ${\displaystyle \omega ^{\xi }=1\,}$)

${\displaystyle f^{-1}(f(x))_{h}=n^{p-2}x_{h}n\mod p}$

${\displaystyle f^{-1}(f(x))_{h}=x_{h}\mod p}$

Voir aussi

Articles connexes

• Convolution
• Algorithme de multiplication
• Transformée de Hadamard

Lien externe

(en) Mikko Tommila, « Number theoretic transforms », 1997

• Portail des mathématiques