Transformation de Fourier rapide

Résumé

La transformation de Fourier rapide (sigle anglais : FFT ou fast Fourier transform) est un algorithme de calcul de la transformation de Fourier discrète (TFD). Sa complexité varie en O(n log n) avec le nombre n de points, alors que la complexité de l’algorithme « naïf » s'exprime en O(n). Ainsi, pour n = , le temps de calcul de l'algorithme rapide peut être 100 fois plus court que le calcul utilisant la formule de définition de la TFD. C'est en 1965 que James Cooley et John Tukey publient l’article qui « lance » définitivement l'adoption massive de cette méthode en traitement du signal et dans les télécommunications. On a découvert par la suite que l'algorithme avait déjà été imaginé par Carl Friedrich Gauss en 1805, et adapté à plusieurs reprises (notamment par Lanczos en 1942) sous des formes différentes. L'algorithme a aussi été découvert indépendamment par le chanoine Lemaître. Cet algorithme est couramment utilisé en traitement numérique du signal pour transformer des données

Source officielle

https://fr.wikipedia.org/wiki/Transformation_de_Fourier_rapide

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

Publications associées (100)

Publications associées

Chargement

Personnes associées (41)

Personnes associées

Chargement

Unités associées (30)

Unités associées

Chargement

Concepts associés (83)

Concepts associés

Chargement

Cours associés (107)

Cours associés

Chargement

Séances de cours associées (272)

Afficher plus

Séances de cours associées

Chargement

Shift-Invariant and Sampling Spaces Associated With the Fractional Fourier Transform Domain

Ayush Bhandari

Shift-invariant spaces play an important role in sampling theory, multiresolution analysis, and many other areas of signal and image processing. A special class of the shift-invariant spaces is the class of sampling spaces in which functions are determined by their values on a discrete set of points. One of the vital tools used in the study of sampling spaces is the Zak transform. The Zak transform is also related to the Poisson summation formula and a common thread between all these notions is the Fourier transform.

2012

Chargement

Perturbed Fourier uniqueness and interpolation results in higher dimensions

Martin Peter Stoller

We obtain new Fourier interpolation and uniqueness results in all dimensions, extending methods and results by the first author and M. Sousa [11] and the second author [12]. We show that the only Schwartz function which, together with its Fourier transform, vanishes on surfaces close to the origin-centered spheres whose radii are square roots of integers, is the zero function. In the radial case, these surfaces are spheres with perturbed radii, while in the non-radial case, they can be graphs of continuous functions over the sphere. As an applica-tion, we translate our perturbed Fourier uniqueness results to perturbed Heisenberg uniqueness for the hyperbola, using the interrelation between these fields introduced and studied by Bakan, Hedenmalm, Montes-Rodriguez, Radchenko and Via-zovska [1].(c) 2022 Published by Elsevier Inc.

ACADEMIC PRESS INC ELSEVIER SCIENCE2022

Chargement

Fourier uniqueness and interpolation in Euclidean space

Martin Peter Stoller

We prove that every Schwartz function in Euclidean space can be completely recovered given only its restrictions and the restrictions of its Fourier transform to all origin-centered spheres whose radii are square roots of integers. In particular, the only Schwartz function which, together with its Fourier transform, vanishes on these spheres, is the zero function. We show that this remains true if we replace the spheres by surfaces or discrete sets of points which are sufficiently small perturbations of these spheres. In a complementary, opposite direction, we construct infinite dimensional spaces of Fourier eigenfunctions vanishing on on certain discrete subsets of those spheres. The proofs combine harmonic analysis, the theory of modular forms and algebraic number theory.

EPFL2022

Chargement