La aplicación de la FFT

Question

Una discreta de Fourier de la transformación de N-ésimo orden es el mapa $F:\mathbb{C}^N\to\mathbb{C}^N$ dada por $$w=Fz\qquad w_k=\frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}\zeta_N^{jk}z_j,$$ donde $\zeta_N=e^{-\frac{2\pi i}{N}}$.

Ahora podemos calcular el $w_k$ por la FFT para $N=2n$ por $$w_{2m}=\frac{1}{\sqrt{N}}\sum_{j=0}^{n-1}\zeta_n^{jm}z_j^g, z_j^g=z_j+z_{j+n}\qquad w_{2m+1}=\frac{1}{\sqrt{N}}\sum_{j=0}^{n-1}\zeta_n^{jm}z_j^u, z_j^u=\zeta_{2n}^j(z_j-z_{j+n})$$

para $m\in\{0,...,n-1\}$.

Ahora entiendo que este FFT da una poderosa herramienta para reducir el cálculo para dos coeficientes de la mitad de la orden de $\frac{N}{2}$. También se puede recorrer por $N=2^n$.

Pero lo que es bueno para? Mi pregunta es, quizás, uno suave. Me refiero a por $z\in\mathbb{C}^N$ I se puede calcular el $w\in\mathbb{C}^N$ y la FFT me ayuda a hacerlo de forma efectiva. Pero, ¿por qué debo hacer esto?

1.) ¿Cuál es la relevancia de cálculo de $w$ para un determinado $z$?

2.) ¿Qué es la intuición detrás de la discretos de la transformación de Fourier? ¿Qué hacer con mis valores iniciales de las $z$?

Espero que mi pregunta es lo suficientemente específico. Si no, deja un comentario.

Answer 1

Mientras que el estándar de la transformada de Fourier (integral) pertenece realmente a las matemáticas, creo que la DFT se escapa a la ingeniería. Me tienden a enseñar de la siguiente manera (soy ingeniero eléctrico por la formación):

1. Tenemos la asombrosa integral de la transformación de Fourier, que por ejemplo diagonalizes de convolución
2. Tenemos instrumentos (sensores, por ejemplo) que, con suerte, una respuesta lineal (no saturar) y esperamos que sus funciones no alterar demasiado rápido: son invariante en el tiempo, y que actúe como circunvoluciones. De manera continua complejo de sines (cisoids) son sus vectores propios
3. Nosotros, los seres humanos y las computadoras sólo pueden funcionar en secuencias finitas con un número finito de operaciones (y de cómputo exacto de las integrales)

Entonces, ¿qué podemos hacer para tener algo "discreta" y "finito" con todos los bonitos propiedades de la transformada de Fourier? Esto es difícil, desde el discreto y el continuo son diferentes, y las correspondientes propiedades no siempre coinciden. Y de alguna manera, vamos a tener que perder algo. Pero la DFT es el más cercano-como-que-puede a la transformada de Fourier (FT) para nosotros, los ordenadores y los seres humanos.

Así:

1. Primera discretizar los índices de la primera de dominio ( $t$ $s(t)$ ) para obtener $s_n=s(nT)$ algunos $T$, y nosotros el tiempo discreto la transformada de Fourier (DTFT). Ahora supongamos que sólo tenemos $N$ puntos en la secuencia de $s_n $. De tiempo continuo $t$ se ha ido. Podemos comprobar que mantenemos lo que podamos de los PIES propiedades (cambio, la inversión, ortogonalidad, Parseval-Plancherel, etc.). Ahora podemos trabajar con discretos secuencias o series de $s_n\to S(\omega)$. Nos damos cuenta de que hay periodicidad involucrados, y tratamos de trabajar en un círculo de radio $1$ en el plano complejo.
2. En segundo lugar, nos discretizar la variable dual de $\omega$. Nos damos cuenta de que si tomamos sólo $N$ puntos regularmente alrededor del círculo unidad en el sistema dual de dominio, bajo ciertas condiciones, ahora tenemos un lineal de transformación que es ortogonal, imita la FT como-cerrar-como-se-puede. Continua frecuencia $f$ se ha ido.

Ahora tienes la DFT. Con respecto a todos los daños colaterales inducidos por el doble de discretización, DFT ahora hace un gran trabajo como el truco de intérprete para los PIES: lo hace todo el duro trabajo con una computadora, mientras que el FT obtiene los créditos.

Pero es ahora que puede ser utilizado y estudiado por su propio derecho, véase, por ejemplo, "tiempo Discreto y discreta de Fourier", de "Las Transformaciones y Aplicaciones de Manual", Ed. Alexander D. Poularikas, 2000.

Así que, para resumir:

1. ¿Cuál es la relevancia de cálculo de $w$ para un determinado $z$? Detectar periodicidades en la novela de la serie, calcular los operadores más rápido (debido a la FFT), etc. lo que habría esperado si la serie continua
2. ¿Qué es la intuición detrás de la discretos de la transformación de Fourier? Compute como un humano o una computadora, como se detalla más arriba

Pero recuerde Fourier hizo inventar la teoría para resolver la ecuación del calor (y de alguna manera inventado distribuciones, como casi tropezó con la delta de Dirac operador). La DFT es útil para ecuaciones diferenciales.

Y después, vino el wavelets... (cliffhanger).

Answer 2

Muchas funciones que se pueden medir o estimar en la ciencia y la ingeniería se pueden beneficiar de una de fourier de la frecuencia de la descripción y muestreo digital se realiza en valores discretos (por lo tanto, el Discreto y no Continuo). Ejemplos bien conocidos:

1. Pura música tonos son los senos.
2. Funciones periódicas de conseguir un muy específicos de la transformada de Fourier Discreta - al menos si el muestreo se alinea con el período de tiempo. Muchas de las funciones en la naturaleza son periódicas - latidos del corazón, la maquinaria rotatoria. DFT proporcionar una descripción natural para ellos.

Pero también es de cálculo de propiedades:

1. Las circunvoluciones convertirse en productos en el dominio de Fourier, y
2. La diferenciación ha exponenciales complejas como funciones propias.

Para la práctica de los cálculos de hacer (o deshacer) por convolución se puede beneficiar de la DFT, sino también en tratar de resolver ecuaciones diferenciales.