La transformada rápida de Fourier

Una transformada de Fourier discreta de N muestras son N sumas de N términos. Divide la suma en sumas más pequeñas y el mismo resultado cuesta mucho menos. Observa cómo ocurre la división en el diagrama de mariposa, o como lo hizo Gauss, en doce números sobre el asteroide Palas.

Ejemplo resuelto — La transformada rápida de Fourier

Cuántas veces menos	5,3

Estos son los valores que muestra la calculadora al abrir la página. Cambia cualquier entrada de arriba para recalcularlos.

Cargando simulación interactiva...

Lección

La teoría — La transformada rápida de Fourier

La transformada rápida de Fourier (FFT) es cualquier algoritmo que calcula la transformada de Fourier discreta X[k] = Σ x[n] W^kn, W = e^−2πi/N, de forma exacta salvo el redondeo, en unas N log N operaciones en lugar de N². La forma de Cooley-Tukey divide N = N₁N₂: N₂ transformadas intercaladas de longitud N₁, cada salida k₁ de la transformada n₂ multiplicada por su propio factor de rotación W^n₂k₁, seguidas de N₁ transformadas de longitud N₂ a través de ellas. Aplicada una y otra vez a N = 2^m es la FFT de base 2: m etapas de N/2 mariposas.

Qué significa cada símbolo

N: el número de muestras, y de frecuencias calculadas
W: la raíz de la unidad e^−2πi/N; sus potencias son los factores de rotación
m: log₂N, el número de etapas de una FFT de base 2

Gauss anotó la división de la FFT unos 160 años antes que Cooley y Tukey 🖖

Pulsa Gauss, 3 periodos de 4. Estos doce números proceden del manuscrito de Gauss: la declinación del borde norte de la franja de cielo por la que puede vagar el asteroide Palas, cada 30° de ascensión recta, en minutos de arco, copiados de la revista de von Zach. Quería obtener la serie trigonométrica que los atravesara. En lugar de una suma de doce términos, tomó cada tercer valor (0°, 90°, 180°, 270°; luego 30°, 120°, …; luego 60°, …), ajustó cada conjunto de cuatro por su cuenta y combinó los tres ajustes cortos. Las curvas a trazos son esos ajustes, y no coinciden. Cuatro puntos no pueden ver las oscilaciones más rápidas, de modo que cada conjunto obtiene un resultado distinto, lo que le llevó a buscar la combinación. La tabla bajo los resultados es su cálculo hecho de nuevo. El primer periodo da 779,5, −415,0, −726,0 y 43,5, las cifras del manuscrito, y la serie combinada es la directa de doce términos. Lo hizo de una segunda manera, cuatro periodos de tres, y obtuvo la misma serie. La aritmética de índices es la que Cooley y Tukey publicaron en 1965, como demostraron Heideman, Johnson y Burrus en 1984. Lo que omite el manuscrito importa igual. Nunca cuenta el trabajo ahorrado: donde Gauss afirma que la división es más rápida, deja la demostración a la práctica, praxis tentantem docebit, quien lo intente lo verá. Sus ejemplos resueltos tienen dos factores, 12 = 3 × 4 y 36 = 6 × 6, y el artículo 27 solo dice que la división se extiende a más. No se publicó en vida; apareció en latín en sus obras completas en 1866 y no tiene fecha. El editor de las Werke lo llama una revisión de un borrador aparentemente iniciado en octubre de 1805. Heideman, Johnson y Burrus lo sitúan en octubre o noviembre de 1805 a partir de una serie de pistas, entre ellas una excentricidad de Juno, 0,254236, que utiliza el manuscrito y que se imprimió en mayo de 1805.

El ahorro no es un factor fijo: crece con N 🖖

Pulsa 1.024 puntos. La suma directa multiplica cada muestra por cada factor de rotación: N² = 1.048.576 multiplicaciones. La FFT ejecuta log₂N = 10 etapas de N/2 = 512 mariposas con una multiplicación cada una: 5.120. Eso es 204,8 veces menos, y la proporción es 2N/log₂N, por lo que sigue creciendo. Pulsa Un millón de puntos: 1.099.511.627.776 multiplicaciones frente a 10.485.760, una proporción de 104.857,6. Duplica N y el trabajo de la suma directa se multiplica por cuatro; el de la FFT sube 2,2 veces a los mil puntos, y más cerca del doble cuanto más avanzas. A los 8 puntos el ahorro es de solo 5,3 veces, razón por la cual el diagrama parece mucho cableado para poca ganancia. Ambos recuentos incluyen las multiplicaciones por W⁰ = 1, al igual que el N² propio de Cooley y Tukey. Ellos contaron los pares de multiplicar y sumar y obtuvieron menos de 2N log₂N, y de cualquier manera la proporción crece como N/log N. Ningún ordenador cambia ninguno de los recuentos ni su proporción. Uno más rápido cambia los tiempos, y no necesariamente ambos por el mismo factor. El botón debajo de las tablas cronometra ambos en tu navegador. La proporción medida también sube con N, aunque no hasta estas cifras, porque el tráfico de memoria y las sumas cuestan tiempo y el recuento los ignora.

Con N grande el método rápido también es el más exacto 🖖

La tabla de exactitud ejecuta ambos métodos con cada operación redondeada a precisión simple, unos siete dígitos significativos, frente a un resultado en doble precisión. A los 1.024 puntos la suma directa se desvía en 5,75×10⁻⁷ del tamaño del resultado y la FFT en 1,23×10⁻⁷, unas 4,7 veces menos. Pasar de 16 puntos a 1.024, 64 veces más, hizo que el error de la suma directa fuera 7,3 veces mayor y el de la FFT 1,4 veces. Cada salida de la suma directa es un total acumulado de N productos redondeados, de manera que sus errores de redondeo se acumulan a lo largo de 1.024 sumas. Cada salida de la FFT pasa por solo log₂N = 10 mariposas. A los 16 puntos no hay diferencia, y con esta entrada la FFT es incluso ligeramente peor, 8,74×10⁻⁸ frente a 7,91×10⁻⁸. Ambos métodos obtienen cada factor de rotación de la misma manera, calculado en doble precisión y redondeado una vez, por lo que la tabla compara los dos algoritmos y no dos formas de obtener un seno.

Problema resuelto al detalle

El otro ejemplo de Gauss: Juno, 36 valores 4 pasos
El artículo 41 del manuscrito de Gauss interpola la ecuación de centro de Juno a partir de 36 valores, uno cada 10°, divididos como 6 × 6. Según el recuento de Cooley y Tukey, ¿cuánto trabajo exige la suma directa, cuánto ahorra la división de Gauss y podría una división más fina mejorar el resultado? Pulsa antes Gauss, 3 periodos de 4: la página cuenta de la misma manera para los doce valores.

Abre este problema en la herramienta
1. La suma directa, una operación por muestra por frecuencia:
  
  $N^{2} = 3 6^{2} = 1, 296$
2. La división de Gauss, seis periodos de seis: el recuento en dos pasos de Cooley y Tukey es N veces la suma de los factores.
  
  $T = N (N_{1} + N_{2}) = 36 \times (6 + 6) = 432$
3. Dividida hasta el fondo, 36 = 2 × 2 × 3 × 3:
  
  $T = 36 \times (2 + 2 + 3 + 3) = 360$
4. La regla de Cooley y Tukey: un factor r = st con s, t > 1 siempre cumple que s + t < r, salvo si s = t = 2:
  
  $s + t < s t (s, t > 1, (s, t) \neq = (2, 2)); 6 = 2 \times 3 : 2 + 3 = 5 < 6$
Respuesta

1.296 operaciones directa, 432 con la división 6 × 6 de Gauss, 360 dividida hasta el fondo. La división de Gauss ya hace tres veces menos trabajo, y la división más fina ahorra un sexto de lo restante. Los doce valores de la página funcionan igual: 144 directa y 84 dividida, o 12 × (2 + 2 + 3) = 84 otra vez hasta el fondo, porque un factor de 4 dividido en 2 × 2 cuesta lo mismo.

$1, 296 \to 432 \to 360; 1 2^{2} = 144 \to 12 \times (4 + 3) = 12 \times (2 + 2 + 3) = 84$

Ruta de aprendizaje

La transformada de Fourier en la práctica

Referencias (3)

Gauss's manuscript on trigonometric interpolation, printed after his death. Article 28 is the page's Gauss mode: twelve declinations of the northern limit of Pallas's zodiac at every 30° of right ascension, split into three periods of four and into four periods of three. Article 27 says the split extends to three or more factors and that practice will teach whoever tries it ("praxis tentantem docebit"); article 41 works Juno's equation of the centre from 36 values with the eccentricity 0.254236. The editor's note calls the text a reworking of a draft apparently begun in October 1805: C. F. Gauss, Theoria interpolationis methodo nova tractata (Nachlass). Werke, Band III, Königliche Gesellschaft der Wissenschaften, Göttingen, 1866; second printing 1876, where the treatise begins on p. 265 and arts. 25–28 are on pp. 303–310.
The paper that showed Gauss's split is the Cooley–Tukey FFT: the change of index n = N₂n₁ + n₂, k = k₁ + N₁k₂ written as Gauss's procedure, his examples (N = 12 as 4 × 3 and 3 × 4, N = 36 as 6 × 6), the dating to October–November 1805 from the Juno eccentricity and other clues, and what the manuscript does not contain: "Gauss did not, however, go on to quantify the computational requirements of his method": M. T. Heideman, D. H. Johnson and C. S. Burrus, Gauss and the history of the fast Fourier transform. IEEE ASSP Magazine 1(4), 14–21 (October 1984). doi:10.1109/MASSP.1984.1162257
The paper that made the FFT standard: the split N = r₁r₂ with T = N(r₁ + r₂) operations, its repetition to T = N(r₁ + … + r_m), the radix-2 form with bit-reversed order, and the count of N² operations for the direct sum against fewer than 2N log₂N, where an operation is a complex multiplication followed by a complex addition: J. W. Cooley and J. W. Tukey, An algorithm for the machine calculation of complex Fourier series. Mathematics of Computation 19(90), 297–301 (1965). doi:10.1090/S0025-5718-1965-0178586-1

Por el equipo de 42Math · Contrastado con fuentes publicadas. Se agradecen correcciones.