6.14. FFT

Eine Fourier-Transformation zerlegt ein Zeitbereichssignal in seine einzelnen Frequenzen. Die schnelle Fourier-Transformation (FFT) ist der Standardalgorithmus, um eine solche effizient zu berechnen – der Grund, warum dieses Modul existiert, und der Grund, warum Transformationen, die lang genug sind, um nützlich zu sein (1024 Punkte, 4096 Punkte), auf einem Mikrocontroller überhaupt machbar sind.

Auf einer Kamera ist die Eingabe typischerweise ein Puffer aus gleichmäßig verteilten Abtastwerten von einem Mikrofon, einer Beschleunigungssensor-Achse, einem Stromsensor oder einer Vibrationssonde; die Ausgabe ist ein Spektrum, das die Anwendung anschließend auf Spitzen, Energie oder Klassifizierungsmerkmale untersucht.

numpy.fft stellt die eindimensionale diskrete Fourier-Transformation bereit. Die beiden Funktionen sind fft() (vorwärts) und ifft() (invers, normalisiert mit N).

Die Transformationslänge muss eine Zweierpotenz sein. Andere Längen lösen ValueError aus. N = 256 und N = 1024 sind gängige Wahlen: lang genug für eine brauchbare Frequenzauflösung bei den meisten eingebetteten Abtastraten, kurz genug, um in den RAM zu passen und deutlich innerhalb einer Einzelbildperiode fertig zu werden.

fft() nimmt den Realteil der Eingabe als erstes Positionsargument und einen optionalen Imaginärteil als zweites und gibt ein 2-Tupel (real, imag) aus reellen Arrays zurück.

6.14.1. Reelle Eingabe, Betragsausgabe

Wenn die Anwendung nur reelle Eingaben einspeist und nur das Betragsspektrum benötigt:

real, imag = np.fft.fft(x)
magnitude  = np.sqrt(real * real + imag * imag)

Das Ergebnis ist ein reelles ndarray von derselben Länge wie die Eingabe. Die Hilfsfunktion spectrogram() macht genau das ohne die zwischenzeitlichen Allokationen – der richtige Aufruf innerhalb einer Streaming-Schleife.

6.14.2. Inverse Transformation

ifft() ist so normalisiert, dass der Hin- und Rückweg die ursprüngliche Eingabe bis auf Gleitkommafehler zurückgibt. Beide Aufrufe nehmen und geben ein Paar reeller Arrays zurück:

real, imag       = np.fft.fft(y)
re_back, im_back = np.fft.ifft(real, imag)

6.14.3. Die dominante Frequenz finden

Ein gängiges Muster ist das Auffinden der größten Spitze in einem Puffer von Abtastwerten – Audio, Vibration, moduliertes IR. Das Rezept:

  1. Erfasse N Abtastwerte, wobei N eine Zweierpotenz ist.

  2. Berechne die FFT.

  3. Finde den Bin mit dem größten Betrag.

  4. Wandle den Bin-Index unter Verwendung der Abtastrate in Hz um.

from ulab import numpy as np

N  = 1024
fs = 8000.0                       # sample rate, Hz

# ... fill ``samples`` with N data points ...

real, imag = np.fft.fft(samples)
spectrum   = np.sqrt(real * real + imag * imag)

half      = spectrum[:N // 2]     # only first half is meaningful
peak_bin  = np.argmax(half)
peak_hz   = peak_bin * fs / N

print("peak at", peak_hz, "Hz")