Pourquoi la transformation de Fourier est-elle si importante?

129

Tout le monde discute de la transformation de Fourier lors du traitement du signal. Pourquoi est-il si important de traiter le signal et que nous dit-il sur le signal?

S'applique-t-il uniquement au traitement du signal numérique ou aux signaux analogiques?

fourier-transform jcolebrand
la source

10

Récemment, une discussion sur les transformations de Fourier a été relancée sur math.SE, et j’ai pensé que les utilisateurs de ce site pourraient en trouver une partie intéressante et même vouloir y participer.

Dilip Sarwate

1

cf. cette réponse pour d'excellents antécédents historiques. Les séries de Fourier remontent au moins à l'astronomie épicycloïdale de Ptolémée . En ajoutant plus d’excentriques et d’épicycles, ce qui revient à ajouter plus de termes à une série de Fourier, on peut rendre compte de tout mouvement continu d’un objet dans le ciel.

Geremia

144

C'est une question assez vaste et il est en effet assez difficile de déterminer pourquoi les transformations de Fourier sont si importantes dans le traitement du signal. La réponse la plus simple, qui soit faite à la main, est qu’il s’agit d’un outil mathématique extrêmement puissant qui vous permet de visualiser vos signaux dans un domaine différent, au sein duquel plusieurs problèmes difficiles deviennent très simples à analyser.

Son omniprésence dans presque tous les domaines de l'ingénierie et des sciences physiques, toutes pour des raisons différentes, rend encore plus difficile la recherche d'une raison. J'espère que l'examen de certaines de ses propriétés qui ont conduit à son adoption généralisée, ainsi que de quelques exemples pratiques et d'une touche d'histoire, peut aider à comprendre son importance.

Histoire:

Pour comprendre l’importance de la transformation de Fourier, il est important de prendre un peu de recul et d’apprécier le pouvoir de la série de Fourier présentée par Joseph Fourier. Dans un écrou de coque, toute fonction périodique intégrable sur le domaine peut être écrite comme une somme infinie de sinus et de cosinus $g(x)$ $\mathcal{D}=[-\pi,\pi]$

g (x) = \sum_{k = - \infty}^{\infty} τ_{k} e^{ȷ k x}

$g(x)=\sum_{k=-\infty}^{\infty}\tau_k e^{\jmath k x}$

τ_{k} = \frac{1}{2 π} \int_{D} g (x) e^{- ȷ k x} d x

$\tau_k=\frac{1}{2\pi}\int_{\mathcal{D}}g(x)e^{-\jmath k x}\ dx$

où . Cette idée selon laquelle une fonction pouvait être décomposée en ses fréquences constitutives (c'est-à-dire en sinus et cosinus de toutes les fréquences) était puissante et constituait le pivot de la transformée de Fourier. $e^{\imath\theta}=\cos(\theta)+\jmath\sin(\theta)$

La transformée de Fourier:

La transformée de Fourier peut être vue comme une extension de la série de Fourier ci-dessus à des fonctions non périodiques. Par souci de clarté et de complétude, je définirai ici la transformation de Fourier. Si est un signal continu intégrable, alors sa transformée de Fourier, est donnée par $x(t)$ $X(f)$

X (f) = \int_{R} x (t) e^{- ȷ 2 π f t} d t, \forall f \in R

$X(f)=\int_{\mathbb{R}}x(t)e^{-\jmath 2\pi f t}\ dt,\quad \forall f\in\mathbb{R}$

et la transformation inverse est donnée par

x (t) = \int_{R} X (f) e^{ȷ 2 π f t} d f, \forall t \in R

$x(t)=\int_{\mathbb{R}}X(f)e^{\jmath 2\pi f t}\ df,\quad \forall t\in\mathbb{R}$

Importance dans le traitement du signal:

Tout d’abord, une transformée de Fourier d’un signal vous indique les fréquences présentes dans votre signal et dans quelles proportions .

Exemple: Avez-vous déjà remarqué que chacune des touches numériques de votre téléphone sonne différemment lorsque vous appuyez sur pendant un appel et qu'elle sonne de la même manière pour chaque modèle de téléphone? C'est parce qu'ils sont chacun composé de deux sinusoïdes différents qui peuvent être utilisés pour identifier le bouton de manière unique. Lorsque vous utilisez votre téléphone pour combiner des combinaisons pour naviguer dans un menu, le correspondant sait quelles touches vous avez appuyées en effectuant une transformation de Fourier de l'entrée et en regardant les fréquences présentes.

Outre quelques propriétés élémentaires très utiles qui simplifient les opérations mathématiques, les raisons pour lesquelles elles ont une importance si répandue dans le traitement du signal sont les suivantes:

Le carré de magnitude de la transformée de Fourier, nous dit instantanément combien de puissance le signal a à une fréquence particulière . $\vert X(f)\vert^2$ $x(t)$ $f$
D'après le théorème de Parseval (plus généralement le théorème de Plancherel), on a ce qui signifie que l'énergie totale d'un signal sur toute la durée est égale à l'énergie totale de la transformation sur toutes les fréquences . Ainsi, la transformation permet de préserver l'énergie. $\int_{R} | x (t) |^{2} d t = \int_{R} | X (f) |^{2} d f$ $\int_\mathbb{R}\vert x(t)\vert^2\ dt = \int_\mathbb{R}\vert X(f)\vert^2\ df$
Les convolutions dans le domaine temporel sont équivalentes aux multiplications dans le domaine fréquentiel, c’est-à-dire avec deux signaux et , alors si $x(t)$ $y(t)$

$z (t) = x (t) ⋆ y (t)$ $z(t)=x(t)\star y(t)$ où désigne la convolution, la transformation de Fourier de est simplement $\star$ $z(t)$
$Z (f) = X (f) \cdot Y (f)$ $Z(f)=X(f)\cdot Y(f)$
Pour les signaux discrets, avec le développement d’algorithmes FFT efficaces, il est presque toujours plus rapide de mettre en œuvre une opération de convolution dans le domaine fréquentiel que dans le domaine temporel.
Semblable à l'opération de convolution, les corrélations croisées sont également facilement implémentées dans le domaine fréquentiel, car , où désigne un conjugué complexe. $Z(f)=X(f)^*Y(f)$ $^*$
En étant capable de scinder les signaux en leurs fréquences constitutives, on peut facilement bloquer certaines fréquences de manière sélective en annulant leurs contributions.

Exemple: si vous êtes un fan de football, vous avez peut-être été ennuyé par le drone constant des vuvuzelas, qui a pratiquement noyé tous les commentaires de la coupe du monde de football en Afrique du Sud. Cependant, la hauteur de la vuvuzela est constante et d ~ environ 235Hz, ce qui permet aux radiodiffuseurs de mettre en place un filtre coupe-bande pour supprimer le bruit incriminé. ^[1]
Un signal décalé (retardé) dans le domaine temporel se manifeste par un changement de phase dans le domaine fréquentiel. Bien que cela appartienne à la catégorie des propriétés élémentaires, il s’agit d’une propriété largement utilisée dans la pratique, en particulier dans les applications d’imagerie et de tomographie.

Exemple: lorsqu'une onde traverse un milieu hétérogène, elle ralentit et s'accélère en fonction de l'évolution de la vitesse de propagation des ondes dans le milieu. Ainsi, en observant un changement de phase par rapport aux attentes et aux mesures, vous pouvez en déduire le retard excessif qui vous indique à quel point la vitesse de la vague a changé dans le milieu. Ceci est bien sûr, une explication profane très simplifiée, mais constitue la base de la tomographie.
Les dérivés de signaux (les n ^èmes dérivés aussi) peuvent être facilement calculés (voir 106) en utilisant des transformées de Fourier.

Traitement du signal numérique (DSP) et traitement du signal analogique (ASP)

La théorie des transformées de Fourier est applicable indépendamment du fait que le signal soit continu ou discret, tant qu'il est "agréable" et parfaitement intégrable. Alors oui, ASP utilise des transformations de Fourier tant que les signaux répondent à ce critère. Cependant, il est peut-être plus courant de parler de transformées de Laplace, qui est une transformée de Fourier généralisée, en ASP. La transformation de Laplace est définie comme

X (s) = \int_{0}^{\infty} x (t) e^{- s t} d t, \forall s \in C

$X(s)=\int_{0}^{\infty}x(t)e^{-st}\ dt,\quad \forall s\in\mathbb{C}$

L’avantage est que l’on ne se limite pas nécessairement aux "signaux sympas" comme dans la transformée de Fourier, mais que la transformée n’est valable que dans une certaine région de convergence. Il est largement utilisé dans l'étude / l'analyse / la conception de circuits LC / RC / LCR, qui sont à leur tour utilisés dans les radios / guitares électriques, les pédales wah-wah, etc.

C’est à peu près tout ce à quoi je pouvais penser en ce moment, mais notez qu’aucune quantité d’écritures / explications ne permet de saisir pleinement l’importance réelle des transformations de Fourier dans le traitement du signal et dans le domaine de la science / ingénierie.

Lorem Ipsum
la source

2

Belle réponse en donnant une application du monde réel utilisant FT et ses propriétés. +1

goldenmean

3

@endolith Je n'ai pas dit que la transformation de Fourier était la première, mais qu'elle était puissante . Notez qu'une série de Taylor n'est pas une expansion en termes de fréquences constituantes. Par exemple, la série de Taylor de sur est , alors que la transformation de Fourier de est (donne ou prend des facteurs de normalisation). Ce dernier est la représentation de fréquence correcte, donc je ne suis pas sûr si une comparaison avec la série de Taylor est appropriée ici.

\sin (α x)

$\sin(\alpha x)$

0

$0$

α x - α^{3} x^{3} / 3! + α^{5} x^{5} / 5! \dots

$\alpha x-\alpha^3x^3/3!+\alpha^5x^5/5!\ldots$

\sin (α x)

$\sin(\alpha x)$

[δ (ω - α) - δ (ω + α)] / (2 ȷ)

$\left[\delta(\omega-\alpha)-\delta(\omega+\alpha)\right]/(2\jmath)$

Lorem Ipsum

6

Quand j'ai commencé à lire cette réponse, je savais que @yoda l'avait écrit avant de faire défiler l'écran pour voir qui c'était réellement =)

Phonon,

2

Pour élaborer # 3: la convolution est ce que vous faites lorsque vous appliquez un filtre à une image, tel qu'un filtre moyen ou un filtre gaussien (bien que vous ne puissiez pas utiliser de filtres non linéaires à transformation de Fourier).

Jonas

1

Le point de Peter K est vraiment critique. Les signaux peuvent être représentés par rapport à de nombreuses bases différentes. Les sinus et les cosinus sont spéciaux car ce sont les fonctions propres des systèmes LTI.

nibot

53

La réponse de Lorem Ipsum manque une chose: la transformée de Fourier décompose les signaux en exponentielles complexes constitutives:

e^{ȷ ω t}

$e^{\jmath \omega t}$

et les exponentielles complexes sont les fonctions propres des systèmes linéaires invariants dans le temps .

En termes simples, si un système, est linéaire et invariant dans le temps, sa réponse à une exponentielle complexe sera une exponentielle complexe de même fréquence mais (éventuellement) différente de phase, , et d'amplitude, , --- et l'amplitude peut être nulle: $H$ $\phi$ $A$

y = H [e^{ȷ ω t}] = A e^{ȷ ϕ} e^{ȷ ω t}

$y = H[e^{\jmath \omega t}] = A e^{\jmath \phi} e^{\jmath \omega t}$

La transformée de Fourier est donc un outil utile pour l'analyse de systèmes linéaires invariants dans le temps.

Peter K.
la source

@ Peter K. Je pense que, suivant la philosophie du choix sur l'exactitude (académique) plutôt que sur la "popularité" d'une réponse, votre réponse devrait être intégrée à la réponse ci-dessus fournie par Lorem Ipsum, qui, malgré sa sélection points par les utilisateurs, manque ce point de vue très important.

Fat32

@Peter Désolé de vous déranger avec cette demande, mais vous êtes 1) un modérateur, 2) votre nom est apparu sur la liste des utilisateurs "actifs" avec votre tag beamforming. Pouvez-vous donner un avis rapide si ce poste dans Math.SE serait bien reçu ici? Je ne sais pas si DSP.SE, Math.SE ou EE.SE ont les meilleures chances d'aider ce demandeur. J'envisage une migration (que je peux faire en tant que modérateur de Math.SE).

Jyrki Lahtonen

@ Peter K., pourriez-vous rouvrir la question à l' adresse suivante : dsp.stackexchange.com/questions/37468 . Je l'ai corrigé. Merci.

Royi

@Royi c'est déjà ouvert?

Peter K.

Peter (comment se fait-il qu'on puisse approcher certaines personnes en utilisant @et d'autres non? Où est-il possible?), Il semble que quelqu'un l'ait ouvert. Merci.

Royi

16

Une autre raison:

C'est rapide (par exemple utile pour la convolution), en raison de sa complexité temporelle linéarithmique (plus précisément celle de la FFT ).
Je dirais que si ce n’était pas le cas, nous ferions probablement beaucoup plus dans le domaine temporel et beaucoup moins dans le domaine de Fourier.

Edit: Depuis que les gens m'ont demandé d'écrire pourquoi la FFT est rapide ...

C'est parce qu'il évite astucieusement de faire du travail supplémentaire.

Pour donner un exemple concret de son fonctionnement, supposons que vous multipliez deux polynômes, et . $a_0 x^0 + a_1 x^1 + \ldots + a_nx^n$ $b_0 x^0 + b_1 x^1 + \ldots + b_nx^n$

Si vous deviez le faire naïvement (en utilisant la méthode FOIL ), il vous faudrait environ opérations arithmétiques (donnez ou prenez un facteur constant). $n^2$

Cependant, nous pouvons faire une observation apparemment banale: pour multiplier deux polynômes, nous n’avons pas besoin de contrer les coefficients . Au lieu de cela, nous pouvons simplement évaluer les polynômes sur un nombre (suffisant) de points, multiplier par points les valeurs évaluées, puis interpoler pour obtenir le résultat.

Pourquoi est-ce utile? Après tout, chaque polynôme a termes, et si nous devions évaluer chacun d’entre eux à points, cela produirait opérations, donc cela ne semble pas nous aider. $n$ $2n$ $\approx n^2$

Mais si, si nous le faisons correctement! Évaluer un polynôme unique sur plusieurs points à la fois est plus rapide que de l'évaluer individuellement sur ces points, si nous évaluons les "bons" points . Quels sont les "bons" points?

Il s’avère que ce sont les racines de l’unité (c’est-à-dire tous les nombres complexes tels que ). Si nous choisissons d’évaluer le polynôme à la base de l’unité, beaucoup d’expressions auront le même résultat (car beaucoup de monômes s’avéreront identiques). Cela signifie que nous pouvons faire leur calcul une fois , puis le réutiliser par la suite pour évaluer le polynôme à tous les autres points. $z$ $z^n = 1$

Nous pouvons faire un processus très similaire pour interpoler par les points afin de récupérer les coefficients polynomiaux du résultat, en utilisant simplement les racines inverses de l'unité.

Il est évident que je saute beaucoup de calculs, mais dans les faits, la FFT est essentiellement l'algorithme que je viens de décrire, qui permet d'évaluer et d'interpoler les polynômes.
Comme je l'ai montré, l'une de ses utilisations était de multiplier les polynômes en beaucoup moins de temps que la normale. Il s'avère que cela économise une énorme quantité de travail, ramenant le temps d'exécution à être proportionnel à (c'est-à-dire linéarithmique) au lieu de (quadratique). $n \log n$ $n^2$

Ainsi, la possibilité d'utiliser la FFT pour effectuer une opération typique (telle que la multiplication polynomiale) beaucoup plus rapidement est ce qui la rend utile, et c'est aussi pourquoi les gens sont maintenant enthousiasmés par la nouvelle découverte du MIT de l' algorithme Sparse FFT .

Mehrdad
la source

Qu'est-ce que la complexité temporelle linéarithmique? Je ne baisserai pas les yeux sur cette réponse, mais je ne pense pas que cela ajoute quelque chose de précieux à cette discussion sur les transformations de Fourier .

Dilip Sarwate

1

@DilipSarwate J'imagine qu'il l'utilise comme raccourci pour O (n * log (n)).

Jim Clay

@DilipSarwate: Jim a raison. Cela a tout à voir avec les transformées (discrètes) de Fourier. Sans la FFT, vos transformations de Fourier prendraient un temps proportionnel au carré de la taille de l’entrée, ce qui les rendrait beaucoup moins utiles. Mais avec la FFT, elles prennent du temps proportionnellement à la taille de l'entrée (fois son logarithme), ce qui les rend beaucoup plus utiles et accélère de nombreux calculs. Aussi cela pourrait être une lecture intéressante.

Mehrdad

Vous devriez mentionner pourquoi c'est rapide. Où est-ce rapide et pourquoi nous soucions-nous que c'est rapide?

CyberMen

1

Je pense que cette réponse est légitime. Il devrait être paraphrasé - "En plus de toutes les caractéristiques intéressantes expliquées dans la réponse des autres peuples, FFT lui permet de devenir une approche réalisable dans les applications en temps réel".

Andrey Rubshtein

15

Outre la réponse de Peter, il existe une autre raison qui est également liée à la fonction propre. C'est, est la fonction propre de l'opérateur différentiel . C'est pourquoi la transformée de Fourier (correspondant à imaginaire pur ) et la transformée de Laplace (correspondant au complexe ) peuvent être utilisées pour résoudre des équations différentielles. $e^{kx}$ $\frac{d^n}{dx^n}$ $k$ $k$

Puisque est la fonction propre de l'opérateur de convolution et de l'opérateur différentiel, c'est peut-être l'une des raisons pour lesquelles le système LSIV peut être représenté par des équations différentielles. $e^{kx}$

EDIT: En fait, les opérateurs différentiels (et intégraux) sont des opérateurs LSIV, voir ici .

chaohuang
la source

8

Certaines des autres réponses de ce fil ont d’excellentes discussions mathématiques sur la définition et les propriétés de la transformée de Fourier; en tant que programmeur audio, je veux simplement fournir ma propre intuition personnelle quant à la raison pour laquelle c'est important pour moi.

La transformée de Fourier me permet de répondre à des questions sur un son qui sont difficiles ou impossibles à répondre avec d'autres méthodes. Cela facilite les problèmes difficiles.

Un enregistrement contient trois notes de musique. Quelles sont les notes? Si vous laissez l'enregistrement sous forme d'amplitudes, ce n'est pas un problème facile. Si vous convertissez l'enregistrement en un ensemble de fréquences au fil du temps, c'est très simple.

Je veux changer la hauteur d'un enregistrement sans changer sa durée. Comment puis-je faire cela? C'est possible, mais pas facile à faire, en manipulant simplement l'amplitude d'un signal d'entrée. Mais c'est facile si vous connaissez les fréquences qui composent le signal.

Cet enregistrement contient-il de la parole ou contient-il de la musique? Très difficile à faire en utilisant uniquement des méthodes basées sur l'amplitude. Mais il existe de bonnes solutions qui supposent la bonne réponse presque tout le temps en fonction de la transformée de Fourier et de sa famille.

Presque chaque question que vous souhaitez poser sur un enregistrement audio numérique est facilitée par la transformation de l'enregistrement à l'aide d'une version discrète de la transformation de Fourier.

En pratique, tous les appareils audio numériques modernes reposent sur des fonctions très similaires à la transformation de Fourier.

Encore une fois, pardonnez la description très informelle; C’est simplement mon intuition personnelle de savoir pourquoi la transformation de Fourier est importante.

johnwbyrd
la source

Hey John, j'ai une question idiote. Je souhaite calculer la TWA ( osha.gov/pls/oshaweb/… ) à partir du son que nous avons enregistré sur un lieu de travail. Je me demande si je pourrais mesurer cette valeur plus précisément si j'utilise la transformation de Fourier pour analyser mon fichier audio.

Hossein Sarshar

Non, sauf si le microphone et l'environnement d'enregistrement ont été calibrés, non.

johnwbyrd

6

Les autres personnes ont donné d'excellentes réponses utiles. Pensez simplement à un signal: vous ne vous souciez que des fréquences qu'il contient (et de leur phase), pas du domaine temporel. Je ne sais pas s'il s'agit d'une réponse finale ou complète, mais c'est simplement une autre raison pour laquelle la transformation de Fourier est utile.

Lorsque vous avez un signal, il peut être composé d’un nombre infini (ou proche de) fréquences, en fonction de votre fréquence d’échantillonnage. Mais ce n'est pas le cas: nous savons que la plupart des signaux ont le moins de fréquences possible ou que nous échantillonnons à une fréquence suffisamment élevée.

Si nous le savons, pourquoi ne pouvons-nous pas l'utiliser? C'est ce que fait le domaine de la détection comprimée. Ils savent que le signal le plus probable est celui qui présente le moins d’erreurs et le moins de fréquences. Ainsi, ils minimisent l'erreur globale relative à nos mesures ainsi que la magnitude de la transformée de Fourier.

Un signal de quelques fréquences a souvent une transformée de Fourier minimale, ou la plupart du temps des zéros (aka "clairsemé", comme on dit dans la détection comprimée). Un signal d'une fréquence a par exemple une fonction delta comme transformée.

Nous pouvons aussi utiliser la définition mathématique formelle.

$\bar{x} = \textrm{arg min } ||y-Ax|| + \lambda||F(x)||$

$||\cdot||$ $||\cdot||$

$\bar{x}$
$y$
$A$
$x$
$\lambda$
$F(x)$

Vous vous souviendrez peut-être que Nyquist avait déclaré qu'il fallait mesurer deux fois plus souvent pour obtenir une bonne représentation. Eh bien, cela supposait que vous ayez des fréquences infinies dans votre signal. Nous pouvons aller au-delà de ça!

Le champ de détection comprimée peut reconstituer n'importe quel signal composé principalement de zéros (ou peu nombreux) dans un domaine donné. Eh bien, c'est le cas pour la transformation de Fourier.

Scott
la source

5

L’importance principale de la transformation de Fourier réside dans l’analyse du système. Le constituant principal de notre univers est le vide, et le vide est un porteur de champs fondamentalement linéaire et invariant dans le temps: différents champs se superposent en ajoutant leurs vecteurs respectifs et, quel que soit le moment où vous répétez l'application de certains champs, le résultat sera le même. .

En conséquence, de nombreux systèmes impliquant également de la matière physique se rapprochent, de manière approximative, comme des systèmes linéaires invariants dans le temps.

De tels systèmes LTI peuvent être décrits par leur "réponse impulsionnelle", et la réponse à tout signal distribué dans le temps est décrite par convolution du signal avec la réponse impulsionnelle.

La convolution est une opération commutative et associative, mais elle est également assez onéreuse en termes de calcul et de concept. Cependant, la convolution des fonctions est cartographiée par la transformation de Fourier en une multiplication par morceaux.

Cela signifie que les propriétés des systèmes linéaires invariants dans le temps et leurs combinaisons sont beaucoup mieux décrites et manipulées après la transformation de Fourier.

En conséquence, des éléments tels que la "réponse en fréquence" sont assez caractéristiques pour décrire le comportement de nombreux systèmes et deviennent utiles pour les caractériser.

Les transformations rapides de Fourier appartiennent à la catégorie "presque, mais pas tout à fait, totalement différente de celle de Fourier", car leurs résultats ne sont pas interprétables de manière raisonnable, car les transformations de Fourier sont bien ancrées dans leur théorie. Ils ne correspondent complètement aux transformations de Fourier que lorsqu'il est question d'un signal échantillonné avec la périodicité de l'intervalle de transformation. En particulier, le critère de "périodicité" n'est presque toujours pas rempli.

Il existe plusieurs techniques pour résoudre ce problème, comme l'utilisation de fonctions de fenêtrage qui se chevauchent.

Cependant, la FFT peut être utilisée pour faire de la convolution à temps discret lorsque tout est bien fait. C’est un algorithme efficace, qui le rend utile pour beaucoup de choses.

On peut aussi utiliser l'algorithme FFT de base pour les transformations théoriques sur les nombres (qui fonctionnent dans des champs de nombres discrets plutôt que dans des "réels" complexes) afin d'effectuer une convolution rapide, comme lors de la multiplication de nombres énormes ou de polynômes. Dans ce cas, le "domaine de fréquence" ne peut pas être distingué du bruit blanc pour pratiquement n'importe quelle entrée et n'a pas d'interprétation utile avant de refaire la transformation inverse.

David
la source

2

La pertinence physique de la transformée de Fourier est qu’elle indique l’amplitude relative des fréquences présentes dans le signal. il peut être défini pour un signal à temps discret ou continu. Tout signal peut être représenté par un mélange de nombreuses fréquences harmoniques. La transformée de Fourier aide dans les applications de filtrage, où nous n’avons besoin que de certaines plages de fréquences, nous devons d’abord savoir quelles sont les amplitudes des fréquences contenues dans le signal.

Vatsyayan
la source