¿Cuál es la diferencia entre la Transformada de Fourier discreta y la Transformada Rápida de Fourier?

Question

¿Puede alguien responder a esta pregunta?

Gracias.

Answer 1

La Transformada Rápida de Fourier es un algoritmo eficiente para calcular la Transformada Discreta de Fourier.

[Más específicamente, FFT es el nombre de cualquier algoritmo eficiente que puede calcular la DFT en aproximadamente $\Theta (n \log n)$ tiempo, en lugar de $\Theta (n^2)$ tiempo. Hay varios algoritmos FFT.]

Answer 2

La Transformada Discreta de Fourier (DFT) es la versión discreta de la Transformada de Fourier (FT) que transforma una señal (o secuencia discreta) de su representación en el dominio del tiempo a su representación en el dominio de la frecuencia.

---

Por otro lado, la Transformada Rápida de Fourier (FFT) es cualquier algoritmo eficiente para calcular la DFT.

---

Calcular una DFT de $n$ puntos utilizando solo su definición, lleva tiempo $\Theta(n^2)$ , mientras que una FFT puede calcular el mismo resultado en solo $\Theta (n \log n)$ pasos. Para secuencias grandes, esto supone una ventaja sustancial.

Answer 3

La Transformada Discreta de Fourier (DFT) es una operación matemática. La Transformada Rápida de Fourier (FFT) es un algoritmo eficiente para la evaluación de esa operación (en realidad, una familia de tales algoritmos). Sin embargo, es fácil confundir estos dos conceptos. A menudo, se puede ver una frase como "tomar la FFT de esta secuencia", lo que realmente significa tomar la DFT de esa secuencia usando el algoritmo FFT para hacerlo de manera eficiente.

Answer 4

DFT es una versión discreta de FT, mientras que FFT es una versión más rápida del algoritmo DFT. DFT establece una relación entre la representación del dominio de tiempo y del dominio de frecuencia, mientras que FFT es una implementación de DFT. La complejidad computacional de DFT es O(M^2), mientras que FFT tiene M(log M), donde M es el tamaño de los datos