Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Transformée de Walsh
Résumé
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.
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.
Analyse harmonique sur un groupe abélien fini#Cas particulier : espace vectoriel finiAnalyse 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 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 satisfassent à cette condition. Les deux nombres et é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
La transformation inverse est donnée par
l'inverse de , et , l'inverse de n. (mod p)
On vérifie que cette formule donne bien l'inverse car vaut n pour z=1 et 0 pour tous les autres valeurs de z vérifiant . En effet, on a la relation (qui devrait fonctionner dans toute algèbre à division)
Soit, pour une racine -ème de l'unité
Un corps étant intègre, un des facteurs (au moins) de ce produit est nul. Donc, soit
et trivialement . Soit et nécessairement .
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Cours associés (27)
MICRO-310(a): Signals and systems I (for MT)
Présentation des concepts et des outils de base pour la caractérisation des signaux ainsi que pour l'analyse et la synthèse des systèmes linéaires (filtres ou canaux de transmission). Application de c
PHYS-332: Computational physics III
This course teaches the students practical skills needed for solving modern physics problems by means of computation. A number of examples illustrate the utility of numerical computations in various d
EE-350: Signal processing
Dans ce cours, nous présentons les méthodes de base du traitement des signaux.
Séances de cours associées (57)
Transformée de Fourier discrète : Périodicité de fréquence et reconstruction
Explore la périodicité dans la transformée de Fourier discrète pour la reconstruction du signal.
Estimation de la fréquence: Signaux déterministes à faible niveau de bruit
Explore l'estimation de fréquence dans les signaux déterministes en utilisant la résolution DFT et spectrale.
Texture : Analyse et classification
Explore l'analyse et la classification de la texture dans les images, en mettant l'accent sur le rôle des techniques d'apprentissage automatique telles que les réseaux neuronaux convolutifs.