La física básica de la transformada rápida de Fourier Cooley-Tukey radix-2 es bien conocida.
Hace log2 N "capas" de operaciones de mariposa. Cada capa hace N / 2 mariposas. Cada mariposa hace 2 multiplicaciones y 2 adiciones.
Para una muestra de un millón binario (2 ^ 20), eso es 20 millones de multiplicaciones y 20 millones de adiciones.
También necesitas una tabla de factores de Twiddle de un millón de puntos (tal vez medio millón, no estoy del todo seguro), que precalculas.
En un DSP, para ejecutarse en tiempo real, eso es aproximadamente 40 millones de operaciones / segundo, lo que no es del todo irracional hoy en día. Un x86 moderno no debería tener ningún problema con esto, PROPORCIONADO DEL CURSO de que está haciendo un código de máquina compilado y una aritmética de hardware, y que su código FFT está correctamente optimizado para su hardware particular.
Comience con la conocida FFT más rápida en el oeste .
Si intentas hacer esto en un Arduino, vas a tener algunos problemas. Simplemente no tiene la potencia.
Todo lo que es fondo.
Lo primero que debes preguntar es esto: ¿NECESITAS un rango de frecuencia de hasta 1 MHz Y de hasta 1 Hz?
Si no necesita una resolución de 1 Hz, pero está buscando señales de alta frecuencia, mantenga su frecuencia de muestreo de 1 MHz y realice FFT más pequeños. Reducir a la mitad el tamaño de la muestra, reducir a la mitad el número de mariposas / capas y disminuir el número de capas en una unidad: en lugar de hacer 20 capas de medio millón de mariposas, puede hacer 19 capas de un cuarto de millón de mariposas.
Si está buscando señales de baja frecuencia y no necesita una resolución de frecuencia extrema, vaya a una frecuencia de muestreo más lenta, o disminuya la cantidad de muestras de 1 MHz. Esto tiene el mismo efecto.