¿Por qué es tan importante la transformación de Fourier?

129

Todos discuten la transformación de Fourier cuando discuten el procesamiento de señales. ¿Por qué es tan importante procesar la señal y qué nos dice acerca de la señal?

¿Solo se aplica al procesamiento de señales digitales o también a las señales analógicas?

fourier-transform jcolebrand
fuente

10

Recientemente, se reanimó una discusión sobre las transformadas de Fourier en matemáticas. SE, y pensé que las personas en este sitio podrían encontrar algo que valga la pena, e incluso podrían querer participar.

Dilip Sarwate

1

cf. Esta respuesta para algunos antecedentes históricos excelentes. La serie de Fourier data al menos desde la astronomía epicíclica de Ptolomeo . Al agregar más excéntricos y epiciclos, similar a agregar más términos a una serie de Fourier, se puede dar cuenta de cualquier movimiento continuo de un objeto en el cielo.

Geremia

144

Esta es una pregunta bastante amplia y, de hecho, es bastante difícil determinar por qué exactamente las transformadas de Fourier son importantes en el procesamiento de la señal. La respuesta más simple que puede proporcionar es que es una herramienta matemática extremadamente poderosa que le permite ver sus señales en un dominio diferente, dentro del cual varios problemas difíciles se vuelven muy simples de analizar.

Su ubicuidad en casi todos los campos de la ingeniería y las ciencias físicas, todo por diferentes razones, hace que sea aún más difícil precisar una razón. Espero que mirar algunas de sus propiedades que llevaron a su adopción generalizada junto con algunos ejemplos prácticos y una pizca de historia pueda ayudarlo a comprender su importancia.

Historia:

Para comprender la importancia de la transformación de Fourier, es importante dar un paso atrás y apreciar el poder de la serie de Fourier presentada por Joseph Fourier. En una cáscara de nuez, cualquier función periódica integrable en el dominio puede escribirse como una suma infinita de senos y cosenos como $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$

donde . Esta idea de que una función podría descomponerse en sus frecuencias constituyentes (es decir, en senos y cosenos de todas las frecuencias) fue poderosa y constituye la columna vertebral de la transformada de Fourier. $e^{\imath\theta}=\cos(\theta)+\jmath\sin(\theta)$

La transformada de Fourier:

La transformación de Fourier se puede ver como una extensión de la serie de Fourier anterior a funciones no periódicas. Para completar y para mayor claridad, definiré la transformada de Fourier aquí. Si es una señal continua e integrable, entonces su transformada de Fourier, viene dada por $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}$

y la transformación inversa está dada por

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}$

Importancia en el procesamiento de señales:

En primer lugar, una transformada de Fourier de una señal le dice qué frecuencias están presentes en su señal y en qué proporciones .

Ejemplo: ¿Alguna vez ha notado que cada uno de los botones numéricos de su teléfono suena diferente cuando presiona durante una llamada y que suena igual para cada modelo de teléfono? Esto se debe a que cada uno está compuesto por dos sinusoides diferentes que se pueden usar para identificar de forma exclusiva el botón. Cuando usa su teléfono para combinar combinaciones para navegar por un menú, la forma en que la otra parte sabe qué teclas presionó es haciendo una transformación de Fourier de la entrada y observando las frecuencias presentes.

Además de algunas propiedades elementales muy útiles que hacen que las matemáticas sean simples, algunas de las otras razones por las que tiene tanta importancia en el procesamiento de señales son:

El cuadrado de magnitud de la transformada de Fourier, nos dice instantáneamente cuánta potencia tiene la señal a una frecuencia particular . $\vert X(f)\vert^2$ $x(t)$ $f$
Del teorema de Parseval (más generalmente el teorema de Plancherel), tenemos que significa que la energía total en una señal en todo momento es igual a la energía total en la transformación en todas las frecuencias . Por lo tanto, la transformación es la conservación de energía. $\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$
Las convoluciones en el dominio del tiempo son equivalentes a las multiplicaciones en el dominio de la frecuencia, es decir, dadas dos señales e , entonces si $x(t)$ $y(t)$

$z (t) = x (t) ⋆ y (t)$ $z(t)=x(t)\star y(t)$ donde denota convolución, entonces la transformada de Fourier de es simplemente $\star$ $z(t)$
$Z (f) = X (f) \cdot Y (f)$ $Z(f)=X(f)\cdot Y(f)$
Para señales discretas, con el desarrollo de algoritmos de FFT eficientes, casi siempre es más rápido implementar una operación de convolución en el dominio de la frecuencia que en el dominio del tiempo.
Similar a la operación de convolución, las correlaciones cruzadas también se implementan fácilmente en el dominio de frecuencia como , donde denota conjugado complejo. $Z(f)=X(f)^*Y(f)$ $^*$
Al poder dividir las señales en sus frecuencias constituyentes, uno puede bloquear fácilmente ciertas frecuencias selectivamente anulando sus contribuciones.

Ejemplo: si eres un fanático del fútbol (soccer), es posible que te haya molestado el constante zumbido de las vuvuzelas que casi ahogó todos los comentarios durante la copa mundial de 2010 en Sudáfrica. Sin embargo, la vuvuzela tiene un tono constante de ~ 235Hz, lo que facilitó a los organismos de radiodifusión implementar un filtro de muesca para cortar el ruido molesto. ^[1]
Una señal desplazada (retrasada) en el dominio del tiempo se manifiesta como un cambio de fase en el dominio de la frecuencia. Si bien esto pertenece a la categoría de propiedad elemental, esta es una propiedad ampliamente utilizada en la práctica, especialmente en aplicaciones de imágenes y tomografía,

Ejemplo: cuando una onda viaja a través de un medio heterogéneo, se ralentiza y acelera según los cambios en la velocidad de propagación de la onda en el medio. Entonces, al observar un cambio en la fase de lo que se espera y lo que se mide, se puede inferir el retraso de tiempo en exceso que a su vez le indica cuánto ha cambiado la velocidad de la onda en el medio. Por supuesto, esta es una explicación laica muy simplificada, pero constituye la base para la tomografía.
Los derivados de señales (n ^Th derivados también) puede ser calculado fácilmente (ver 106) usando transformadas de Fourier.

Procesamiento de señal digital (DSP) frente a procesamiento de señal analógica (ASP)

La teoría de las transformadas de Fourier es aplicable independientemente de si la señal es continua o discreta, siempre que sea "agradable" y absolutamente integrable. Entonces, sí, ASP usa transformadas de Fourier siempre que las señales cumplan este criterio. Sin embargo, quizás sea más común hablar de transformadas de Laplace, que es una transformada de Fourier generalizada, en ASP. La transformación de Laplace se define como

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}$

La ventaja es que uno no está necesariamente limitado a "señales agradables" como en la transformada de Fourier, pero la transformación es válida solo dentro de cierta región de convergencia. Es ampliamente utilizado en el estudio / análisis / diseño de circuitos LC / RC / LCR, que a su vez se utilizan en radios / guitarras eléctricas, pedales wah-wah, etc.

Esto es casi todo lo que se me ocurre en este momento, pero tenga en cuenta que ninguna cantidad de escritura / explicación puede capturar completamente la verdadera importancia de las transformadas de Fourier en el procesamiento de señales y en ciencia / ingeniería

Lorem Ipsum
fuente

2

Buena respuesta al dar alguna aplicación del mundo real usando FT y sus propiedades. +1.

goldenmean

3

@endolith No dije que la transformación de Fourier fuera la primera, solo que es poderosa . Tenga en cuenta que una serie de Taylor no es una expansión en términos de las frecuencias constituyentes. Por ejemplo, la serie Taylor de sobre es , mientras que la transformada de Fourier de es (da o toma algunos factores de normalización). Esta última es la representación de frecuencia correcta, por lo que no estoy seguro de si alguna comparación con la serie Taylor es adecuada aquí.

\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

66

Cuando comencé a leer esta respuesta, de alguna manera supe que @yoda la escribió antes de desplazarme hacia abajo para ver quién era en realidad =)

Phonon

2

Para desarrollar el # 3: la convolución es lo que haces cuando aplicas un filtro a una imagen, como un filtro promedio o un filtro gaussiano (aunque no puedes transformar los filtros no lineales de Fourier).

Jonas

1

El punto de Peter K es realmente crítico. Las señales se pueden representar con respecto a muchas bases diferentes. Los senos y cosenos son especiales porque son las funciones propias de los sistemas LTI.

nibot

53

La gran respuesta de Lorem Ipsum pierde una cosa: la transformada de Fourier descompone las señales en exponenciales complejos constituyentes:

e^{ȷ ω t}

$e^{\jmath \omega t}$

y exponenciales complejos son las funciones propias para sistemas lineales invariantes en el tiempo .

En pocas palabras, si un sistema, es lineal e invariante en el tiempo, entonces su respuesta a un exponencial complejo será un exponencial complejo de la misma frecuencia pero (posiblemente) diferente fase, y amplitud, , --- y la amplitud puede ser cero: $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}$

Por lo tanto, la transformación de Fourier es una herramienta útil para analizar sistemas lineales invariantes en el tiempo.

Peter K.
fuente

@ Peter K. Creo que siguiendo la filosofía de elección sobre la corrección (académica) sobre la "popularidad" de una respuesta, su respuesta debería integrarse en la respuesta anterior proporcionada por Lorem Ipsum, que a pesar de haber sido seleccionada como la respuesta con 96 puntos por los usuarios, carece de este punto de vista muy importante.

Fat32

@ Peter Perdón por molestarlo con esta solicitud, pero usted es 1) un moderador, 2) su nombre apareció en la lista de usuarios "activos" con su etiqueta de formación de haces. ¿Puedes dar una opinión rápida sobre si esta publicación en Math.SE sería bien recibida aquí? No estoy seguro de si DSP.SE, Math.SE o EEEE tienen la mejor oportunidad de ayudar a ese autor de la pregunta. Estoy considerando la migración (que puedo hacer como moderador de Math.SE).

Jyrki Lahtonen

@ Peter K., ¿podría volver a abrir la pregunta en: dsp.stackexchange.com/questions/37468 . Lo arreglé. Gracias.

Royi

@Royi ya está abierto?

Peter K.

Peter (¿Cómo es que algunas personas pueden ser abordadas usando @y otras no? ¿Dónde está la opción para eso?) Parece que alguien la abrió. Gracias.

Royi

16

Otra razón:

Es rápido (por ejemplo, útil para la convolución), debido a su complejidad lineal de tiempo lineal (específicamente, la de la FFT ).
Yo diría que, si este no fuera el caso, probablemente estaríamos haciendo mucho más en el dominio del tiempo, y mucho menos en el dominio de Fourier.

Editar: como la gente me pidió que escribiera por qué el FFT es rápido ...

Es porque inteligentemente evita hacer un trabajo extra.

Para dar un ejemplo concreto de cómo funciona, suponga que está multiplicando dos polinomios, y . $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 hiciera esto ingenuamente (usando el método FOIL ), necesitaría aproximadamente operaciones aritméticas (dar o tomar un factor constante). $n^2$

Sin embargo, podemos hacer una observación aparentemente mundana: para multiplicar dos polinomios, no necesitamos FALLAR los coeficientes . En cambio, simplemente podemos evaluar los polinomios en un número (suficiente) de puntos, hacer una multiplicación puntual de los valores evaluados y luego interpolar para obtener el resultado.

¿Por qué es útil? Después de todo, cada polinomio tiene términos, y si tuviéramos que evaluar cada uno en puntos, eso todavía resultaría en operaciones, por lo que no parece ayudar. $n$ $2n$ $\approx n^2$

¡Pero lo hace, si lo hacemos correctamente! Evaluar un solo polinomio en muchos puntos a la vez es más rápido que evaluarlo en esos puntos individualmente, si evaluamos en los puntos "correctos" . ¿Cuáles son los puntos "correctos"?

Resulta que esas son las raíces de la unidad (es decir, todos los números complejos tales que ). Si elegimos evaluar el polinomio en las raíces de la unidad, muchas expresiones resultarán iguales (porque muchos monomios resultarán iguales). Esto significa que podemos hacer su aritmética una vez , y reutilizarla después para evaluar el polinomio en todos los demás puntos. $z$ $z^n = 1$

Podemos hacer un proceso muy similar para interpolar a través de los puntos para recuperar los coeficientes polinómicos del resultado, simplemente usando las raíces inversas de la unidad.

Obviamente, estoy omitiendo muchas matemáticas aquí, pero efectivamente, la FFT es básicamente el algoritmo que acabo de describir, para evaluar e interpolar los polinomios.
Uno de sus usos, como mostré, fue multiplicar polinomios en mucho menos tiempo de lo normal. Resulta que esto ahorra una gran cantidad de trabajo, reduciendo el tiempo de ejecución a ser proporcional a (es decir, linearithmic) en lugar de (cuadrático). $n \log n$ $n^2$

Por lo tanto, la capacidad de usar la FFT para realizar una operación típica (como la multiplicación polinómica) mucho más rápido es lo que la hace útil, y esa es también la razón por la cual las personas ahora están entusiasmadas con el nuevo descubrimiento del algoritmo FFT de Sparse por parte del MIT .

Mehrdad
fuente

¿Qué es la complejidad lineal lineal del tiempo? No rechazaré esta respuesta, pero no creo que agregue nada de valor a esta discusión sobre las transformadas de Fourier .

Dilip Sarwate

1

@DilipSarwate Sospecho que lo está usando como abreviatura de O (n * log (n)).

Jim Clay

@DilipSarwate: Jim tiene razón. Tiene todo que ver con transformadas de Fourier (discretas). Sin la FFT, sus transformadas de Fourier tomarían un tiempo proporcional al cuadrado del tamaño de entrada, lo que las haría mucho menos útiles. Pero con la FFT, toman un tiempo proporcional al tamaño de la entrada (multiplicado por su logaritmo), lo que los hace mucho más útiles y acelera muchos cálculos. También esta podría ser una lectura interesante.

Mehrdad

Deberías mencionar POR QUÉ es rápido. ¿Dónde es rápido y por qué nos importa que sea rápido?

CyberMen

1

Creo que esta respuesta es legítima. Debe parafrasearse: "Además de todas las bonitas características explicadas en la respuesta de otras personas, FFT le permite convertirse en un enfoque factible en aplicaciones en tiempo real".

Andrey Rubshtein

15

Adicional a la respuesta de Peter, hay otra razón que también está relacionada con la función propia. Es decir, es la función propia del operador diferencial . Es por eso que la transformada de Fourier (correspondiente al imaginario puro ) y la transformada de Laplace (correspondiente al complejo ) se pueden usar para resolver ecuaciones diferenciales. $e^{kx}$ $\frac{d^n}{dx^n}$ $k$ $k$

Dado que es la función propia del operador de convolución y diferencial, tal vez esa sea una de las razones por las que el sistema LSIV puede representarse mediante ecuaciones diferenciales. $e^{kx}$

EDITAR: De hecho, los operadores diferenciales (e integrales) son operadores LSIV, vea aquí .

chaohuang
fuente

8

Algunas de las otras respuestas en este hilo tienen excelentes discusiones matemáticas sobre la definición y las propiedades de la transformada de Fourier; Como programador de audio, simplemente quiero proporcionar mi propia intuición personal de por qué es importante para mí.

La transformación de Fourier me permite responder preguntas sobre un sonido que son difíciles o imposibles de responder con otros métodos. Hace que los problemas difíciles sean fáciles.

Una grabación contiene un conjunto de tres notas musicales. ¿Cuáles son las notas? Si deja la grabación como un conjunto de amplitudes a lo largo del tiempo, este no es un problema fácil. Si convierte la grabación a un conjunto de frecuencias a lo largo del tiempo, es realmente fácil.

Quiero cambiar el tono de una grabación sin cambiar su duración. ¿Cómo hago esto? Es posible, pero no fácil de hacer, simplemente manipulando la amplitud de una señal de entrada. Pero es fácil si conoce las frecuencias que comprenden la señal.

¿Esta grabación contiene discurso o música? Súper difícil de hacer usando solo métodos basados en amplitud. Pero hay buenas soluciones que adivinan la respuesta correcta casi todo el tiempo en función de la transformación de Fourier y su familia.

Casi todas las preguntas que le gustaría hacer sobre una grabación de audio digital se hacen más fáciles al transformar la grabación utilizando una versión discreta de la transformación de Fourier.

En la práctica, cada dispositivo de audio digital moderno depende en gran medida de funciones muy similares a la transformación de Fourier.

Nuevamente, perdone la descripción altamente informal; Esta es simplemente mi intuición personal de por qué la transformación de Fourier es importante.

johnwbyrd
fuente

Hola John, tengo una pregunta tonta. Quiero calcular el TWA ( osha.gov/pls/oshaweb/… ) a partir del sonido que grabamos en un lugar de trabajo, me pregunto si podría medir este valor con mayor precisión si utilizo la Transformación de Fourier para analizar mi archivo de audio.

Hossein Sarshar

No, a menos que el micrófono y el entorno de grabación hayan sido calibrados, no.

johnwbyrd

6

Las otras personas han dado respuestas geniales y útiles. Solo piense en alguna señal: solo le importan las frecuencias que contiene (y su fase), no el dominio del tiempo. No sé si esta es una respuesta final o completa, pero solo otra razón por la cual la transformación de Fourier es útil.

Cuando tenga alguna señal, podría estar compuesta por un número infinito (o cercano) de frecuencias, dependiendo de su frecuencia de muestreo. Pero ese no es el caso: sabemos que la mayoría de las señales tienen el menor número de frecuencias posible, o que estamos muestreando a una velocidad lo suficientemente alta.

Si sabemos eso, ¿por qué no podemos usarlo? Eso es lo que hace el campo de la detección comprimida. Saben que la señal más probable es la que tiene el menor error y la menor frecuencia. Por lo tanto, minimizan el error general en relación con nuestras mediciones, así como la magnitud de la transformada de Fourier.

Una señal de algunas frecuencias a menudo tiene una transformada de Fourier mínima, o mayormente ceros (también conocido como "disperso", como se dice en la detección comprimida). Una señal de una frecuencia solo tiene una función delta como la transformación, por ejemplo.

También podemos usar la definición matemática formal.

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

Aquí, todo lo que estamos haciendo es minimizar el error (primer conjunto de ) y minimizar la transformación de Fourier (segundo conjunto de ). Aquí tenemos $||\cdot||$ $||\cdot||$

$\bar{x}$ como nuestra señal reconstruida (muy probablemente cerca del original)
$y$ , nuestras medidas
$A$ , una matriz de selección
$x$ , nuestra señal
$\lambda$ alguna constante
$F(x)$ la transformada de Fourier.

Puede recordar que Nyquist dijo que debe medir el doble de la frecuencia más alta para obtener una buena representación. Bueno, eso suponía que tuvieras frecuencias infinitas en tu señal. ¡Podemos superar eso!

El campo de detección comprimida puede reconstruir cualquier señal que sea principalmente ceros (o dispersos) en algún dominio. Bueno, ese es el caso de la transformación de Fourier.

Scott
fuente

5

La principal importancia de la transformación de Fourier reside en el análisis del sistema. El componente principal de nuestro universo es el vacío, y el vacío es un portador de campos fundamentalmente lineal e invariable en el tiempo: los diferentes campos se superponen agregando sus respectivos vectores, e independientemente de cuándo repita la aplicación de ciertos campos, el resultado será el mismo .

Como consecuencia, muchos sistemas que también involucran materia física tienen una buena aproximación y se comportan como sistemas lineales invariantes en el tiempo.

Dichos sistemas LTI se pueden describir por su "respuesta de impulso", y la respuesta a cualquier señal distribuida en el tiempo se describe haciendo girar la señal con la respuesta de impulso.

La convolución es una operación conmutativa y asociativa, pero también es bastante computacional y conceptualmente costosa. Sin embargo, la convolución de funciones está mapeada por la transformada de Fourier en multiplicación por partes.

Eso significa que las propiedades de los sistemas lineales invariantes en el tiempo y sus combinaciones se describen y manipulan mucho mejor después de la transformación de Fourier.

Como resultado, cosas como la "respuesta de frecuencia" son bastante características para describir el comportamiento de muchos sistemas y se vuelven útiles para caracterizarlos.

Las transformaciones rápidas de Fourier se encuentran en la clase "casi, pero no del todo, completamente diferente de las transformadas de Fourier", ya que sus resultados no son realmente interpretables de manera sensata, ya que las transformadas de Fourier se enrutan firmemente en su teoría. Corresponden a transformadas de Fourier completamente solo cuando se habla de una señal muestreada con la periodicidad del intervalo de transformación. En particular, el criterio de "periodicidad" casi siempre no se cumple.

Existen varias técnicas para solucionarlo, como el uso de funciones de ventanas superpuestas.

Sin embargo, el FFT puede emplearse para hacer una convolución de tiempo discreto cuando se hacen las cosas bien, y es un algoritmo eficiente que lo hace útil para muchas cosas.

Se puede emplear el algoritmo FFT básico también para transformaciones teóricas de números (que funcionan en campos de números discretos en lugar de "reales" complejos) para hacer una convolución rápida, como cuando se multiplican números o polinomios enormes. En este caso, el "dominio de frecuencia" es indistinguible del ruido blanco para básicamente cualquier entrada y no tiene una interpretación útil antes de volver a realizar la transformación inversa.

David
fuente

2

La relevancia física de la transformada de Fourier es que indica la amplitud relativa de las frecuencias presentes en la señal. se puede definir tanto para tiempo discreto como para señal de tiempo continuo. Cualquier señal puede representarse como una mezcla de muchas frecuencias armónicas. Ayuda de transformada de Fourier en aplicaciones de filtro, donde solo necesitamos cierto rango de frecuencias, primero necesitamos saber cuáles son las amplitudes de frecuencias que contiene la señal.

vatsyayan
fuente