Die grundlegende Physik der Cooley-Tukey-Radix-2-Fast-Fourier-Transformation ist bekannt.

Sie führt log2 N "Schichten" von Schmetterlingsoperationen durch. Jede Schicht macht N / 2 Schmetterlinge. Jeder Schmetterling führt 2 Multiplikationen und 2 Additionen durch.

Für eine binäre Million (2 ^ 20) Punkte-Stichprobe sind das 20 Millionen Multiplikationen und 20 Millionen Additionen.

Sie benötigen auch eine Million- Punkt (vielleicht eine halbe Million, ich bin nicht absolut sicher) Twiddle-Faktor-Tabelle, die Sie vorberechnen.

Auf einem DSP, der in Echtzeit ausgeführt werden soll, sind das ungefähr 40 Millionen Operationen / Sekunde heute überhaupt nicht unvernünftig. Ein moderner x86 sollte damit kein Problem haben, vorausgesetzt natürlich, dass Sie kompilierten Maschinencode und Hardware-Arithemik ausführen und dass Ihr FFT-Code für Ihre spezielle Hardware richtig optimiert ist.

Beginnen Sie mit dem Bekannten Schnellste FFT im Westen.

Wenn Sie dies auf einem Arduino versuchen, werden Sie einige Probleme haben. Es hat einfach nicht die Leistung.

Alles, was Hintergrund ist.

Das erste, was Sie fragen müssen, ist Folgendes: BRAUCHEN Sie einen Frequenzbereich bis zu 1 MHz UND Auflösung bis zu 1 Hz?

Wenn Sie keine Auflösung von 1 Hz benötigen, aber nach Hochfrequenzsignalen suchen, behalten Sie Ihre 1-MHz-Abtastrate bei und führen Sie kleinere FFTs durch. Durch die Halbierung Ihrer Stichprobengröße wird die Anzahl Ihrer Schmetterlinge / Schichten halbiert und die Anzahl der Schichten um eins verringert: Anstatt 20 Schichten mit einer halben Million Schmetterlingen zu machen, machen Sie 19 Schichten mit einer Viertelmillion Schmetterlingen.

Wenn Sie Sie suchen nach niederfrequenten Signalen, und Sie benötigen keine extreme Frequenzauflösung, gehen nicht zu einer langsameren Abtastrate oder sampeln Ihre 1-MHz-Abtastwerte herunter. Dies hat den gleichen Effekt.