Co do FFT właściwie pokazuje

Pytanie

Zagraj akord na fortepianie - powiedzmy, C i E razem. Twoje ucho słyszy jeden dźwięk. Ale ten dźwięk to dwie nadrzędne częstotliwości: 261,6 Hz i 329.6 Hz. Twoja cochlea fizycznie je rozdziela - różne komórki włosów rezonują na różnych częstotliwościach, wysyłając wyraźne sygnały do mózgu.

Szybka transformata Fouriera robi to samo, ale z liczbami zamiast komórek włosowych. Daj mu sygnał (sekwencja próbek amplitudy w czasie) i zwraca listę częstotliwości i ich mocnych stron. Odpowiada: * * jakie częstotliwości są obecne i ile z każdego? * *

Co się właściwie dzieje

Sygnał pobierany z czasem jest listą liczb: amplituda w każdym punkcie próbki. 1-sekundowe nagranie przy 44,100 Hz to 44,100 liczb. Liczby te opisują sygnał w domenie czasu * * - amplituda jako funkcję czasu.

FFT konwertuje to do domeny * * częstotliwości * * - amplitudy jako funkcji częstotliwości. Te same informacje, inna reprezentacja. Podobnie jak zmiana współrzędnych kartezjańskich i polarnych: nic nie jest tworzone ani niszczone, tylko ponownie wyrażone.

Rdzeń matematyczny: każdy sygnał okresowy może być zapisany jako suma fal sinusowych i cosinusowych na różnych częstotliwościach. To twierdzenie Fouriera (1807). FFT oblicza współczynniki tej sumy - ile każdej częstotliwości jest w sygnale.

Dlaczego "szybko"

Naiwny sposób obliczenia transformaty Fouriera wymaga Operacje N ² dla próbek N. Dla 1024 próbek to około miliona operacji. Algorytm Cooley- Tukey (1965) redukuje ten poziom do N · logarytmiczny (N) - około 10 000 operacji dla tego samego wejścia. 100 razy szybciej. Dla miliona próbek prędkość wynosi 50,000x.

Sztuczka: podzielić punkt N na dwie transformaty punktu N / 2, rekursywnie. Wymaga to N być moc 2 (lub pad z zera). Każdy podział sprawia, że problem jest o połowę mniejszy. Operacja "motyl" łączy połowę:

X[k]     = Even[k] + W · Odd[k]
X[k+N/2] = Even[k] - W · Odd[k]

Gdzie W jest złożonym wykładnikiem (rotacja w złożonej płaszczyźnie). Te same wyniki dają dwa punkty wyjściowe. Dlatego algorytm jest "szybki" - ponownie wykorzystuje wszystkie obliczenia dwukrotnie.

Wdrożenie PinePaper jest podręcznikiem Cooley- Tukey radix-2 DIT (decimation in time). 40 linii JavaScript. Napisaliśmy to od podstaw, zamiast importować bibliotekę, ponieważ chcieliśmy, aby uczniowie mogli odczytać źródło i zrozumieć każdą linię.

Co te bary oznaczają

Kiedy widzisz analizator widma - bary skaczące do muzyki - każdy bar reprezentuje kosz częstotliwości. Wysokość jest wielkością (siłą) tej częstotliwości w bieżącym sygnale.

• • • Czysta sinus wave * * produkuje jeden wysoki bar z jego częstotliwością i nic więcej.
• • • Fala kwadratowa * * produkuje pręty w podstawowej i każdej nieparzystej harmonii (3, 5, 7...), zmniejszając się o 1 / n. To dlatego fale kwadratowe brzmią "buzzy" - zawierają energię wysokiej częstotliwości, której czyste sine nie.
• • • Biały hałas * * produkuje pręty o mniej więcej równej wysokości wszędzie. Każda częstotliwość jest obecna z równym prawdopodobieństwem.
• • • Głos ludzki * * wytwarza fundamentalny (dźwięk, który słyszysz) plus formaty - rezonansowe szczyty z kształtu twojego przewodu głosowego, które odróżniają samogłoski.

Windowing: Dlaczego krawędzie mają znaczenie

Jest haczyk. FFT zakłada, że sygnał powtarza się zawsze. Ale nasza próbka jest skończona - zaczyna się i kończy. Jeśli sygnał nie będzie w punkcie zerowym w obu punktach końcowych, nagłe odcięcie tworzy sztuczną zawartość wysokiej częstotliwości. To się nazywa spektakularny wyciek.

Fix: pomnożyć sygnał przez funkcję * * okna * *, która płynnie kurczy się do zera na krawędziach. Wspólne okna:

• • • Hann * * (cosine bell): dobry ogólny cel, traci pewną rozdzielczość częstotliwości
• • • Hamming * *: podobny do Hanna, ale nie osiąga zera na krawędziach, nieco lepsze tłumienie sidelobe
• • • Blackman * *: węższy płat główny, lepsze tłumienie boczne, traci większą rozdzielczość częstotliwości

Wybór jest zawsze przełączeniem między rozdzielczością częstotliwości (jak dokładnie można zidentyfikować częstotliwość) i wyciekiem widmowym (ile energii krwawi do sąsiednich pojemników). Nie ma idealnego okna. Jest to konsekwencją zasady niepewności - nie można mieć arbitralnie precyzyjnej wiedzy o czasie i częstotliwości jednocześnie.

Gdzie mieszka FFT

Ciągle oddziałujesz z wynikami FFT:

• • • MP3 i AAC kompresja * *: przekształcić dźwięk w domenę częstotliwości, wyrzucić częstotliwości poniżej progu słuchu, kompresować to, co pozostaje. Transformacja jest podstawą stratnej kompresji dźwięku.
• • • kompresja JPEG * *: wersja 2D (DCT) przekształca 8 × 8 bloków pikseli w domenę częstotliwości, kwantyfikuje komponenty wysokiej częstotliwości. Dlatego artefakty JPEG wyglądają jak bloki.
• • • WiFi i 5G * *: kodowanie OFDM dzieli dane na wiele podnośników częstotliwości. FFT konwertuje pomiędzy symbolami transmisji danych w domenie czasu i częstotliwości.
• • • MRI obrazowanie * *: surowy sygnał ze skanera MRI jest w przestrzeni częstotliwości. Odwrotna FFT rekonstruuje obraz przestrzenny. Dosłownie: każdy rezonans jest odwrotną transformatą Fouriera.
• • • Shazam * *: oblicza spektrogram (FFT nad przesuwanymi oknami), ekstrakty szczytowe, dopasowuje wzór do bazy danych. FFT jest pierwszym krokiem w rozpoznawaniu każdej piosenki.

60-letni algorytm, w twojej kieszeni, działa miliardy razy dziennie.

{{widget: function- fact}}

Spróbuj

Otwórz PinePaper, wybierz generator Spectrum Analyzer. Generuj falę kwadratową. Spójrz na bary - zobaczysz dziwne harmoniki spadające jako 1 / n. Przełącz na tarczę - teraz wszystkie harmonie są obecne, spadają jako 1 / n. Przejście na hałas - płaskie spektrum, każda częstotliwość jest równie prawdopodobna.

Zmień funkcję okna. Patrz jak Hann wygładza widmo kosztem większych szczytów. Przełącz na Blackman - węższe szczyty, ale niższe boczne.

Nie czytasz o FFT. Mierzysz sygnały i obserwujesz, co odkrywa transformata. To jest różnica między wiedzą a zrozumieniem.

Odniesienia

• Brigham, E.O. (1988). * Szybka transformata Fouriera i jej aplikacje *. Prentice Hall.
• Cooley, J.W. & Tukey, J.W. (1965). Algorytm do obliczania maszyny złożonej serii Fouriera. * Matematyka obliczeń *, 19 (90), 297- 301.
• Fourier, J. (1822). * Theorie analytique de la chaleur *. Paris: Firmin Didot.
• Harris, F.J. (1978). Na temat korzystania z systemu Windows do analizy harmonicznej z dyskretną transformatą Fouriera. * Działalność IEEE *, 66 (1), 51- 83.
• Oppenheim, A.V. & Schafer, R.W. (2009). * Discrete- Time Signal Processing * (3rd ed.). Prentice Hall.
• Shannon, C.E. (1949). Komunikacja w obecności hałasu. * Proceedings of the IRE *, 37 (1), 10- 21.
• Smith, S.W. (1997). * The Scientist and Engineer 's Guide to Digital Signal Processing *. California Technical Publishing.
• Wang, A., et al. (2003). Algorytm wyszukiwania audio o sile przemysłowej. * Działalność ISMIR 2003 *. (Algorytm odcisku palca Shazama)
• Wallace, G.K. (1991). JPEG Still Picture Compression Standard. * Komunikacja ACM *, 34 (4), 30- 44.

---

• PinePaper 's FFT jest implementacja Cooley- Tukey radix-2 z Hann, Hamming i Blackman windowing, plus niskopass i highpass filtry. Spróbuj za darmo w [pinepaper.studio / editor] (/editor). *