Co ti vlastně ukazuje FFT

Otázka

Zahrajte akord na klavír - řekněme C a E společně. Tvoje ucho slyší jeden zvuk. Ale ten zvuk jsou dvě frekvence překryty: 261.6 Hz a 329.6 Hz. Vaše kochlea je fyzicky odděluje - různé vlasové buňky rezonují na různých frekvencích, vysílají do vašeho mozku odlišné signály.

Rychlá Fourierova transformace dělá to samé, ale s čísly místo vlasových buněk. Dejte mu signál (sekvenci amplitudových vzorků v průběhu času) a vrátí seznam frekvencí a jejich silných stránek. Odpověď zní: * * jaké frekvence jsou přítomny a kolik z každého? * *

Co se vlastně děje

Signál vzorkovaný v průběhu času je seznam čísel: amplituda v každém bodě odběru vzorků. 1sekundový záznam při 44,100 Hz je 44,100 čísel. Tato čísla popisují signál v oblasti * * času * * - amplituda jako funkci času.

FFT to převede na * * kmitočtovou doménu * * - amplitudu jako funkci frekvence. Stejné informace, odlišné zastoupení. Stejně jako přepínání mezi kartézskými a polárními souřadnicemi: nic není vytvořeno nebo zničeno, pouze znovu vyjádřeno.

Matematické jádro: každý pravidelný signál může být napsán jako součet sinus a cosinus vlny na různých frekvencích. To je Fourierova věta (1807). FFT počítá koeficienty této částky - kolik z každé frekvence je ve signálu.

Proč "rychle"

Naivní způsob výpočtu Fourierovy transformace vyžaduje N ² operace pro N vzorky. Pro 1024 vzorků je to asi milion operací. Algoritmus Cooley- Tukey (1965) redukuje tuto hodnotu na N · log К (N) - přibližně 10 000 operací pro stejný vstup. 100x rychlost. Pro milion vzorků je rychlost 50,000x.

Trik: rozdělit N-point transformace na dvě N / 2-bodové transformace, rekurzivně. To vyžaduje N být výkon 2 (nebo vy pad se nuly). Každý rozštěp rozdělí problém. Operace "motýl" kombinuje polovinu:

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

Kde W je komplexní exponenciální (rotace v komplexní rovině). Ze stejných dvou podvýsledků máte dva výstupní body. Proto je algoritmus "rychlý" - opakuje každý výpočet dvakrát.

PinePaper implementace je učebnice Cooley-Tukey radix-2 DIT (decimace v čase). 40 řádků JavaScriptu. Napsali jsme to od nuly, místo toho, abychom dováželi knihovnu, protože jsme chtěli, aby studenti byli schopni přečíst zdroj a pochopit každý řádek.

Co znamenají ty bary

Když vidíte spektrální analyzátor - bary skákající do hudby - každý bar představuje frekvenční koš. Výška je velikost (síla) této frekvence v aktuálním signálu.

• • • A pure sinus wave * * produkuje jeden vysoký bar na své frekvenci a nic jiného.
• • • A square wave * * produkuje bary na základní a každou lichou harmonii (3rd, 5th, 7th...), klesá jako 1 / n. To je důvod, proč čtvercové vlny zní "buzzy" - obsahují vysokofrekvenční energii, která ryzí sines ne.
• • • White noise * * produkuje tyčinky zhruba stejné výšky všude. Každá frekvence je přítomna se stejnou pravděpodobností.
• • • Lidský hlas * * produkuje základní (stoupání slyšíte) plus formanty - rezonanční vrcholy z tvaru vašeho hlasového traktu, který rozlišuje samohlásky.

Windowing: Proč hrany hmota

Je tu háček. FFT předpokládá, že se signál opakuje navždy. Ale náš vzorek je konečný - začíná a končí. Pokud nebude signál na nule na obou koncích, náhlý odstřih vytvoří umělý vysokofrekvenční obsah. Toto se nazývá * * spektrální únik * *.

Oprava: signál vynásobte funkcí * * okna * *, která na hranách plynule zmenšuje na nulu. Společná okna:

• • • Hann * * (cosinus bell): dobrý obecný účel, ztratí nějaké frekvenční rozlišení
• • • Hamming * *: podobné Hann, ale nedosáhne nuly na hranách, mírně lepší potlačení sidelobe
• • • Blackman * *: užší hlavní lalok, lepší potlačení sidelobe, ztrácí více kmitočtového rozlišení

Volba je vždy obchod mezi kmitočtovým rozlišením (jak přesně můžete určit frekvenci) a spektrální únik (kolik energie krvácí do sousedních košů). Není žádné perfektní okno. To je důsledkem principu nejistoty - nemůžete mít svévolně přesné znalosti času i frekvence současně.

Kde FFT žije

Neustále interagujete s výsledky FFT:

• • • MP3 a AAC komprese * *: transformovat audio na frekvenční doménu, vyřadit frekvence pod práh sluchu, komprimovat, co zůstává. Transformace je celý základ lossy audio komprese.
• • • JPEG komprese * *: 2D verze (DCT) transformuje 8 × 8 pixelů bloků na frekvenční doménu, kvantifikuje vysokofrekvenční komponenty. Proto se artefakty JPEG objevují jako bloky.
• • • WiFi a 5G * *: kódování OFDM rozděluje data na mnoho frekvenčních subpřenašečů. FFT konvertuje mezi datovými symboly časové domény a kmitočtové domény.
• • • MRI zobrazování * *: surový signál z MRI skeneru je v kmitočtovém prostoru. Inverzní FFT rekonstruuje prostorový obraz. Doslova: každý MRI, který jste kdy viděli, je inverzní Fourierova transformace.
• • • Shazam * *: počítá spektrogram (FFT nad posuvnými okny), extrahuje vrcholy, odpovídá vzoru proti databázi. FFT je první krok k rozpoznání každé písně.

60letý algoritmus, ve vaší kapse, běží miliardkrát denně.

{{widget: function- plot}}

Zkus to

Otevřít PinePaper, vyberte generátor Spectrum Analyzer. Vytvořit čtvercovou vlnu. Podívejte se na mříže - uvidíte, že lichá harmonika padá jako 1 / n. Přepněte na piliny - nyní jsou přítomny všechny harmonické, padají jako 1 / n. Přepnout na hluk - ploché spektrum, každá frekvence stejně pravděpodobná.

Změňte funkci okna. Sledujte, jak Hann vyhlazuje spektrum za cenu širších vrcholů. Přepněte na Blackman - užší vrcholky, ale nižší sideloby.

Nečteš o FFT. Měříte signály a pozorujete, co transformace odhalí. To je rozdíl mezi vědomím a pochopením.

Odkazy

• Brigham, E.O. (1988). * The Fast Fourier Transform and Its Applications *. Prentice Hall.
• Cooley, J.W. & Tukey, J.W. (1965). Algorithm pro Stroj Výpočet Komplexní Fourierova série. * Matematika výpočtu *, 19 (90), 297-301.
• Fourier, J. (1822). * Théorie analytique de la chaleur *. Paris: Firmin Didot.
• Harris, F.J. (1978). O použití Windows pro harmonickou analýzu pomocí diskrétní Fourierovy transformace. * Řízení IEEE *, 66 (1), 51-83.
• Oppenheim, A.V. & Schafer, R.W. (2009). * Discrete-Time Signal Processing * (3rd ed.). Prentice Hall.
• Shannon, C.E. (1949). Komunikace v přítomnosti hluku. * 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). An Industrial- Strength Audio Search Algorithm. * Činnost ISMIR 2003 *. (Shazamův algoritmus pro snímání otisků prstů.)
• Wallace, G.K. (1991). JPEG stále obraz kompresní standard. * Komunikace ACM *, 34 (4), 30-44.

---

• PinePaper je FFT je Cooley- Tukey radix-2 implementace s Hann, Hamming, a Blackman windowing, plus low-pass a high-pass filtry. Zkuste to zdarma na [pinepaper.studio / editor] (/editor). *