Co ti vlastně ukazuje FFT

Otázka

Zahrajte akord na klavír - řekněme C a E dohromady. 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í odlišné signály do mozku.

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 časové oblasti * * * - amplituda jako funkce času.

FFT to převede na * * frekvenční doménu * * - amplituda jako funkce 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). V FFT se počítají 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 · logaritmus (N) - asi 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ý" - znovu použije 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, kterou ryzí hřebci nemají.
• • • White noise * * produkuje tyčinky zhruba stejné výšky všude. Každá frekvence je přítomna se stejnou pravděpodobností.
• • • A human voice * * produces a fundamental (the smold you hear) plus formants - rezonanční vrcholy z tvaru vašeho hlasivky, které rozlišují samohlásky.

První tři jsou níže - klikni mezi nimi. Výšky jsou vzorce, není kresba: sinus je 1 na základní, čtvercová vlna je přesně 1 / n na zvláštní harmonii.

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 zásady 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ě.

Zkus to

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

Změňte funkci okna. Sledujte, jak Hann vyhlazuje spektrum za cenu širších vrcholů. Přepněte na Blackmana - užší vrcholy, 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, GK. (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).