¿Cómo funciona la FFT?

Question

Durante cinco años intenté entender cómo funciona la transformada de Fourier. Leí muchos artículos, pero nadie podía explicarlo de forma sencilla. Hace dos semanas me topé con el vídeo sobre una máquina de 100 años que calcula mecánicamente las series de Fourier: https://www.youtube.com/watch?v=NAsM30MAHLg - Lo vi y, de repente, me quedó muy claro. ¡Resulta ser algo muy simple!

Ahora quiero entender cómo funciona la FFT. Y de nuevo nadie puede explicarlo en términos simples.

¿Puede alguien explicárselo a un no matemático? Gracias.

Answer 1

Como ha dicho @user289075, la FFT es sólo un procedimiento computacional eficiente y no explica la teoría que hay detrás de la transformada discreta de Fourier.

La idea clave es que para calcular la transformada de una señal $n$ de longitud, se pueden calcular las transformadas de las dos mitades de longitud $n/2$ independientemente y recombinarlas para obtener la transformación global. Este principio se aplica recursivamente, es decir, para calcular la transformada en $n/2$ puntos se combinan dos transformaciones en $n/4$ puntos y así sucesivamente hasta $n$ ya no puede dividirse.

Mediante un análisis de complejidad, se puede demostrar que el número de operaciones aritméticas se reduce de $n^2$ (para una aplicación ingenua) a $n\log n$ un ahorro significativo.

Answer 2

La FFT no es más que un algoritmo para calcular la transformada discreta de Fourier (DFT). Resulta que la matriz DFT es altamente simétrica (debido a las propiedades de simetría y periodicidad de $e^{ix}$ ). La FFT no es más que una factorización matricial de la DFT en una serie de matrices dispersas. Se pueden multiplicar las matrices dispersas y obtener la DFT en menos operaciones que multiplicando simplemente la matriz DFT.

Answer 3

Creo que todos los elementos teóricos están presentes en las respuestas de los demás, pero no la razón pragmática por la que la FFT reduce la complejidad en un factor significativo (y de ahí la popularidad de este algoritmo, entre otras cosas).

Aplicar la DFT equivale a multiplicar una matriz por un vector (la señal original muestreada, por ejemplo, en la que cada entrada del vector es una muestra). Esa matriz es la matriz de Fourier. Digamos que tenemos $2n$ muestras, la matriz a considerar es entonces (hasta un factor constante)

$(F_{2n})_{jk} = \exp(i\pi \times jk/n)$

donde $i=\sqrt{-1}$ . Estas son las raíces de la unidad.

Ahora la magia se produce gracias a un mariposa de estas matrices, puedes descomponerlas en un producto de matrices: cada una de las cuales es barata de aplicar a un vector (cf. a continuación)

Por ejemplo $F_4$ viene dada (hasta un factor) por:

$$ F_4 \propto \left(\begin{array}{cccc} 1 & 1 & 1 & 1\\ 1 & i & i^2 & i^3 \\ 1 & i^2 & i^4 & i^6 \\ 1 & i^3 & i^6 & i^9 \end{array} \right) \propto \left(\begin{array}{cc|cc} 1 & 0 & 1 & 0\\ 0 & 1 & 0 & i\\\hline 1 & 0 & -1 & 0\\ 0 & 1 & 0 & -i \end{array} \right) \left(\begin{array}{cc|cc} 1 & 1 & 0 & 0\\ 1 & i^2 & 0 & 0\\\hline 0 & 0 & 1 & 1\\ 0 & 0 & 1 & i^2 \end{array} \right) \left(\begin{array}{cccc} 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 \end{array} \right) $$

Veamos las dos primeras matrices: su estructura es muy típica, (se podría demostrar mediante recursividad cómo se generaliza esto) pero hablaremos de esto más adelante. Lo que nos importa ahora es que hay sólo 2 entradas distintas de cero por línea . Esto significa que al considerar la aplicación de una de esas matrices a un vector, el número de operaciones a realizar es una modesta constante de veces $n$ . Por otra parte, el número de matrices en la descomposición crece como $\log n$ . Así que en general la complejidad se escala como $n\times \log n$ donde un producto matricial-vectorial básico no estructurado se escalaría como $n^2$ .

(Para aclarar este punto: empezando por la derecha, se aplica una matriz a un vector, esto cuesta $O(n)$ entonces se aplica una matriz al vector resultante, de nuevo $O(n)$ ya que hay $O(\log n)$ matrices, la complejidad global es $O(n\log n)$ donde $O$ significa (aproximadamente) "del orden de", para más información sobre la notación big-O, consulte la página de la wikipedia (1))

Finalmente, la última matriz de la descomposición es a inversión de bits matriz. Sin entrar en detalles, puede calcularse de forma extremadamente eficiente. (Pero incluso ingenuamente, el coste no es obviamente más que lineal en $n$ ).

Siempre que no te haya perdido aquí, vamos a generalizar un poco: la matriz $F_{2n}$ tiene la siguiente forma (no es difícil de comprobar)

$$ F_{2n} \propto \left(\begin{array}{cc} I_n & A_n \\ I_n & -A_n \end{array}\right) \left(\begin{array}{cc} F_n & 0 \\ 0 & F_n \end{array}\right) B_{2n} $$

donde $B_{2n}$ es una matriz de inversión de bits de dimensiones adecuadas, $F_n$ es la matriz DFT de orden $n$ y, por tanto, esta matriz puede expresarse como un producto, etc. $I_n$ es la matriz de identidad de tamaño $n\times n$ y $A_n$ es una matriz diagonal con las potencias de $i$ de $0$ a $n-1$ .

Por cierto, ahora puedes observar que es deseable que el tamaño de tu vector-muestra original sea una potencia de $2$ . Si no es el caso, es más barato para rellenar su vector con ceros (esto se llama en realidad relleno cero )

Lo último que hay que aclarar es el mariposa (véase también [2]). Para ello, nada mejor que un pequeño dibujo (siento no haber querido hacer esto en Tikz, si hay algún héroe por ahí...). Si representas los vectores después de cada etapa por puntos y conectas los puntos del vector original al vector después de aplicar la matriz, obtienes este bonito diagrama (ignorando la inversión de bits)

He intentado dejar claro en el diagrama que el primer nivel corresponde a 4 aplicaciones de $F_2$ , el siguiente nivel a 2 aplicaciones de $F_4$ etc. Para que quede más claro, empezando por la derecha significa que la primera multiplicación matricial después de la inversión de bits será

• para la primera entrada, hay que mirar la primera y la segunda entrada del vector original (correspondientes a entradas distintas de cero en las posiciones (1,1) y (1,2) de la matriz de ese nivel)
• para la siguiente entrada, hay que mirar la primera y la segunda entrada (esto hace que el primer bloque de la columna "F2" (correspondiente a las entradas distintas de cero en las posiciones (2,1) y (2,2))

etc. Además, obsérvese que, en cada nivel, podemos considerar bloques de entradas independientemente. De nuevo, esto conduce a una mayor optimización que puede hacer que la FFT sea muy muy eficiente.

Ps: He ignorado todas las constantes de multiplicación ya que es un cálculo O(1), es fácil comprobar cuales son y dependerá de las convenciones que estés usando.

1. https://en.wikipedia.org/wiki/Big_O_notation
2. https://en.wikipedia.org/wiki/Butterfly_diagram

ver también: https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm#Pseudocode

donde hay disponible un pseudocódigo que ilustra cómo se codificaría la FFT recursivamente.

Otro buen recurso para ver cómo codificar la FFT desde cero: https://jakevdp.github.io/blog/2013/08/28/understanding-the-fft/