Saltar al contenido principal
LibreTexts Español

5.9: Transformada Rápida de Fourier (FFT)

  • Page ID
    85377
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    Objetivos de aprendizaje
    • La DFT se puede reducir desde el tiempo exponencial con el algoritmo de Transformada Rápida de Fourier.

    Uno se pregunta si el DFT se puede calcular más rápido: ¿Existe otro procedimiento computacional —un algoritmo — que pueda calcular la misma cantidad, pero de manera más eficiente. Podríamos buscar métodos que reduzcan la constante de proporcionalidad, pero que no cambien la complejidad O (N 2) de la DFT. Aquí, tenemos algo más dramático en mente: ¿Se pueden reestructurar los cómputos para que resulte una complejidad menor?

    En 1965, el investigador de IBM Jim Cooley y el miembro de la facultad de Princeton John Tukey desarrollaron lo que ahora se conoce como la Transformada Rápida de Fourier (FFT). Es un algoritmo para calcular esa DFT que tiene orden O (N log N) para ciertas entradas de longitud. Ahora, cuando la longitud de los datos se duplica, el tiempo computacional espectral no se cuadruplicará como ocurre con el algoritmo DFT; en cambio, se duplica aproximadamente. Investigaciones posteriores mostraron que ningún algoritmo para computar la DFT podría tener una complejidad menor que la FFT. Sorprendentemente, la obra histórica ha demostrado que Gauss a principios del siglo XIX desarrolló el mismo algoritmo, ¡pero no lo publicó! Después del redescubrimiento de FFT, no solo se aceleró enormemente el cálculo del espectro de una señal, sino que también la característica añadida del algoritmo significó que los cálculos tenían flexibilidad no disponible para las implementaciones analógicas.

    Ejercicio\(\PageIndex{1}\)

    Antes de desarrollar la FFT, intentemos apreciar el impacto del algoritmo. Supongamos que una transformación de longitud corta toma 1 ms. Queremos calcular una transformación de una señal que sea 10 veces más larga. Compare cuánto tiempo tardaría una implementación sencilla de la DFT en comparación con una FFT, las cuales computan exactamente la misma cantidad.

    Solución

    Si un DFT requirió 1 ms para calcular, y la señal que tiene diez veces la duración requeriría 100 ms para calcular. Usando la FFT, un tiempo de computación de 1 ms aumentaría en un factor de aproximadamente

    \[10\log_{2}10=33 \nonumber \]

    Un factor de 3 menos de lo que hubiera necesitado el DFT.

    Para derivar la FFT, asumimos que la duración de la señal es una potencia de dos:

    \[N=2^{L} \nonumber \]

    Considere lo que sucede con los elementos pares e impares de la secuencia en el cálculo de DFT.

    \[S(k)=s(0)+s(2)e^{(-i)\frac{2\pi 2k}{N}}+...+s(N-2)e^{(-i)\frac{2\pi (N-2)k}{N}}+s(1)e^{(-i)\frac{2\pi k}{N}}+s(3)e^{(-i)\frac{2\pi \times (2+1)k}{N}}+...+s(N-1)e^{(-i)\frac{2\pi (N-(2-1))k}{N}} \nonumber \]

    \[S(k)=\left [ s(0)+s(2)e^{(-i)\frac{2\pi 2k}{\frac{N}{2}}}+...+s(N-2)e^{(-i)\frac{2\pi \left ( \frac{N}{2}-1 \right )k}{\frac{N}{2}}}\right ]+\left [ s(1)e^{(-i)\frac{2\pi k}{N}}+s(3)e^{(-i)\frac{2\pi k}{\frac{N}{2}}}+...+s(N-1)e^{(-i)\frac{2\pi \left ( \frac{N}{2}-1 \right )k}{\frac{N}{2}}}\right ]e^{\frac{-(i2\pi k)}{N}} \nonumber \]

    Cada término entre corchetes tiene la forma de un DFT de N/2 de longitud. El primero es un DFT de los elementos pares y el segundo de los elementos impares. El primer DFT se combina con el segundo multiplicado por el complejo exponencial\[e^{\frac{-(i2\pi k)}{N}} \nonumber \]

    Las transformaciones de media longitud se evalúan cada una en índices de frecuencia k=0,... , N-1. Normalmente, el número de índices de frecuencia en un cálculo de DFT oscila entre cero y la longitud de transformación menos uno. La ventaja computacional de la FFT proviene del reconocimiento de la naturaleza periódica de la transformada discreta de Fourier. La FFT simplemente reutiliza los cálculos realizados en las transformaciones de media longitud y las combina a través de adiciones y la multiplicación por la\[e^{\frac{-(i2\pi k)}{N}} \nonumber \] cual no es periódica sobre N/2.

    La Figura 5.9.1 a continuación ilustra esta descomposición. Tal como está, ahora calculamos dos transformaciones N/2 de longitud de complejidad

    \[2O\left ( \frac{N^{2}}{4} \right ) \nonumber \]

    multiplicar uno de ellos por el complejo exponencial de complejidad O (N) y sumar los resultados (complejidad O (N)). En este punto, la complejidad total aún está dominada por los cálculos de DFT de longitud media, pero el coeficiente de proporcionalidad se ha reducido.

    Ahora por la diversión. Porque

    \[N=2^{L} \nonumber \]

    cada una de las transformaciones de media longitud se puede reducir a dos transformadas de un cuarto de longitud, cada una de estas a dos transformadas de octava longitud, etc. Esta descomposición continúa hasta que nos quedamos con transformaciones de longitud-2. Esta transformación es bastante simple, involucrando solo adiciones. Así, la primera etapa de la FFT tiene N/2 transformaciones longitud-2 (ver la parte inferior de la Figura 5.9.1). Los pares de estas transformaciones se combinan sumando una a la otra multiplicada por un exponencial complejo. Cada par requiere 4 adiciones y 2 multiplicaciones, dando un número total de cómputos iguales

    \[6\cdot \frac{N}{4}=\frac{3N}{2} \nonumber \]

    Este número de cómputos no cambia de una etapa a otra. Debido a que el número de etapas, el número de veces que la longitud se puede dividir por dos, es igual\[\log_{2}N \nonumber \] al número de operaciones aritméticas es igual

    \[\frac{3N}{2}\log_{2}N \nonumber \]

    lo que hace que la complejidad de la FFT

    \[O(N\log_{2}N) \nonumber \]

    Figura 5.9.1a Descomposición de DFT de longitud-8
    Figura 5.9.1b Cálculo de DFT de longitud-8

    Figura 5.9.1 la descomposición inicial de una DFT de longitud 8 en los términos usando entradas indexadas pares e impares marca la primera fase de desarrollo del algoritmo FFT. Cuando estas transformaciones de media longitud se descomponen sucesivamente, nos quedamos con el diagrama que se muestra en el panel inferior que representa el cálculo FFT de longitud 8.

    Hacer un ejemplo hará que el ahorro computacional sea más obvio. Veamos los detalles de un DFT de longitud 8. Como se muestra en la Figura 5.9.1b, Hacer un ejemplo hará que el ahorro computacional sea más obvio. Veamos los detalles de un DFT de longitud 8. Considerando la Figura 5.9.2 a continuación, a medida que el índice de frecuencia va de 0 a 7, reciclamos valores de los DFT de longitud-4 al cálculo final debido a la periodicidad de la salida de DFT. Al examinar cómo se recopilan los pares de salidas, creamos el elemento computacional básico conocido como mariposa como se muestra en la Figura 5.9.2.

    Figura 5.9.2 El elemento computacional básico de la transformada rápida de Fourier es la mariposa. Toma dos números complejos, representados por a y b, y forma las cantidades mostradas. Cada mariposa requiere una multiplicación compleja y dos adiciones complejas.

    Al considerar juntos los cálculos que involucran frecuencias de salida comunes de las dos DFT de media longitud, vemos que las dos multiplica complejas están relacionadas entre sí, y podemos reducir aún más nuestro trabajo computacional. Al descomponer aún más las DFT de longitud 4 en dos DFT de longitud 2 y combinar sus salidas, llegamos al diagrama que resume la transformada rápida de Fourier de longitud 8 (Figura 5.9.1b). Aunque la mayoría de las multiplica complejas son bastante simples como multiplicar por

    \[e^{-(i\frac{\pi }{2})} \nonumber \]

    significa intercambiar partes reales e imaginarias y cambiar sus signos. Vamos a contarlos con el propósito de evaluar la complejidad como multiplicaciones complejas completas.

    Tenemos N/2 = 4 multiplicaciones complejas y N = 8 adiciones complejas para cada etapa y

    \[\log_{2}N=3 \nonumber \]

    etapas, haciendo el número de cálculos básicos

    \[\frac{3N}{2}\log_{2}N \nonumber \]

    como se predijo.

    Ejercicio\(\PageIndex{1}\)

    Tenga en cuenta que el orden de la secuencia de entrada en las dos partes de la Figura 5.9.1 no es exactamente el mismo. ¿Por qué no? ¿Cómo se determina el orden?

    Solución

    El panel superior no ha utilizado el algoritmo FFT para calcular los DFT de longitud 4 mientras que el inferior tiene. El orden está determinado por el algoritmo.

    Se descubrieron otros algoritmos “rápidos”, todos los cuales hacen uso de cuántos factores comunes es la longitud de la transformación

    Ejercicio\(\PageIndex{1}\)

    Supongamos que la longitud de la señal eran 500? ¿Cómo computarías el espectro de esta señal usando el algoritmo Cooley-Tukey? ¿Cuál sería la longitud N de la transformada?

    Solución

    La transformada puede tener cualquier duración mayor o igual a la duración real de la señal. Simplemente “pad” la señal con muestras de valor cero hasta que resulte una longitud de señal computacionalmente ventajosa. Recordemos que la FFT es un algoritmo para calcular la DFT. Extender la longitud de la señal de esta manera simplemente significa que estamos muestreando el eje de frecuencia más finamente de lo requerido. Para utilizar el algoritmo Cooley-Tukey, la longitud de la señal resultante con relleno cero puede ser de 512, 1024, etc. muestras de longitud.


    This page titled 5.9: Transformada Rápida de Fourier (FFT) is shared under a CC BY 1.0 license and was authored, remixed, and/or curated by Don H. Johnson via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.