Mi az FFT valójában megmutatja neked

A kérdés

Játssz egy akkordot egy zongorán - mondjuk, C és E együtt. A füled egy hangot hall. De ez a hang két frekvencián van felül: 261,6 Hz és 329,6 Hz. A cochlea fizikailag elválasztja őket - különböző hajsejtek rezonálnak különböző frekvenciákon, küldés különböző jeleket az agyba.

A Fast Fourier Transform ugyanezt teszi, de a számok helyett a hajsejtek. Adja meg a jelet (egy sor amplitúdóminta idővel) és visszaadja a frekvenciák és erősségeik listáját. Válaszol: * * milyen frekvenciák vannak jelen, és mennyi minden? * *

Mi történik valójában

Az idő múlásával vett jel a számok listája: az egyes mintavételi pontokon mért amplitúdó. Egy 1 másodperces felvétel 44,100 Hz-en 44,100 szám. Ezek a számok a * * időtartomány * * - amplitúdót az idő függvényében írják le.

Az FFT ezt a * * frekvenciatartományt * * - amplitúdóvá alakítja a frekvencia függvényében. Ugyanaz az információ, más képviselet. Mint a Cartesian és a poláris koordináták közötti váltás: semmi sem keletkezik vagy semmisül meg, csak újra kifejeződik.

A matematikai mag: minden periodikus jel írható szinusz- és kozinhullámok összegeként különböző frekvenciákon. Ez a Fourier-tétel (1807). Az FFT kiszámítja ennek az összegnek az együtthatóit - az egyes frekvenciák mennyiségét a jelben.

Miért "gyors"

A naiv mód, hogy kiszámítsa a Fourier átalakulás megköveteli N ² műveletek N minták esetében. 1024 minta, ez körülbelül 1 millió művelet. A Cooley- Tukey algoritmus (1965) ezt N · log- (N) - körülbelül 10.000 művelet ugyanerre a bemenetre. 100-szoros gyorsulás. Egymillió minta esetén a sebesség 50,000x.

A trükk: az N-pont átalakulása két N / 2-pont átalakulásra, rekurzívan. Ehhez az N-nek 2-nek kell lennie (vagy nullákkal kell letenni). Minden feleződik. A "pillangó" művelet egyesíti a feleket:

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

Ahol W összetett exponenciális (forgás az összetett síkban). Ugyanaz a két részeredmény két kimeneti pontot ad. Ezért "gyors" az algoritmus - kétszer újrahasznál minden számítást.

PinePaper végrehajtása egy tankönyv Cooley- Tukey radix2 DIT (tizedelés időben). 40 sor JavaScript. A semmiből írtuk, ahelyett, hogy egy könyvtárat importáltunk volna, mert azt akartuk, hogy a diákok képesek legyenek olvasni a forrást és megérteni minden sort.

Mit jelentenek azok a bárok

Ha egy spektrumanalizátort látunk - a zenére ugró bárokat - mindegyik sáv egy frekvenciablokkot jelent. A magasság az adott frekvencia nagyságrendje (szilárdsága) az aktuális jelben.

• • • A tiszta szinuszhullám * * egy magas bárt termel a frekvenciáján és semmi mást.
• • • A Square wave * * bárokat termel az alapvető és minden furcsa harmonikus (3., 5., 7....), csökken 1 / n. Ezért hangzik a négyzetes hullámok "buzzy" - tartalmaznak magas frekvenciájú energia, hogy tiszta szinusz nem.
• A fehér zaj mindenhol nagyjából azonos magasságú rudakat termel. Minden frekvencia azonos valószínűséggel van jelen.
• • • Egy emberi hang * * létrehoz egy alapvető (a szurok, amit hallasz) plusz formai - rezonáns csúcsok az alakja a hang traktus, hogy megkülönbözteti magánhangzók.

Windowing: Miért az Edges Matter

Van egy csapda. Az FFT feltételezi, hogy a jel örökké ismétlődik. De a mi mintánk véges - kezdődik és megáll. Ha a jel nem a nullán van mindkét végponton, a hirtelen lezárás mesterséges magas frekvenciájú tartalmat eredményez. Ez az úgynevezett * * * spektrális szivárgás * *.

A fix: szorozzuk meg a jelet egy * * ablakfunkcióval * *, ami a széleknél simán nullára csökken. Közös ablakok:

• • • Hann * * (cosine bell): jó általános cél, veszít néhány frekvencia felbontás
• • • Hamming * *: hasonló Hann, de nem éri el a nulla széleknél, kissé jobb oldalsó elnyomás
• • • Blackman * *: szűkebb fő lebeny, jobb sidelobe elnyomása, veszít több frekvencia felbontás

A választás mindig egy kereskedelmi között frekvencia-felbontás (milyen pontosan lehet azonosítani a frekvenciát) és a spektrális szivárgás (mennyi energia vérzik a szomszédos kukák). Nincs tökéletes ablak. Ez a bizonytalanság elvének következménye - nem lehet önkényesen pontos ismerete mind az idő, mind a gyakoriság egyszerre.

Where the FFT lives

Folyamatosan kölcsönhatásba lép az FFT eredményeivel:

• • • MP3 és AAC tömörítés * *: az audio átalakítása frekvenciatartományba, a hallási küszöb alatti frekvenciák eldobása, a maradék tömörítése. Az átalakulás a teljes alapja a lossy audio tömörítés.
• • • JPEG tömörítés * *: a 2D verzió (DCT) átalakítja a 8 × 8 pixel blokkokat frekvenciatartományba, számszerűsíti a magas frekvenciájú komponenseket. Ezért jelennek meg a JPEG műtárgyak tömbként.
• • • WiFi és 5G * *: Az OFDM kódolása számos frekvenciás alhordozóra osztja az adatokat. Az FFT az idő- domain átvitel és a gyakori domain adatjelek között konvertálódik.
• • • MRI képalkotó * *: az MRI szkenner nyers jele a frekvenciatartományban van. Az inverz FFT rekonstruálja a térképet. Szó szerint minden MRI, amit valaha láttál, egy fordított Fourier átalakulás.
• • • Shazam * *: kiszámítja a spektrogramot (FFT a tolóablakok felett), kivonatok csúcsok, egyezik a minta egy adatbázis. Az FFT az első lépés minden dal felismerésében.

Egy 60 éves algoritmus, a zsebedben, naponta milliárdszor fut.

{{widget: function- plot}

Próbáld ki

Nyissa meg a PinePaper-et, válassza ki a Spectrum Analyzer generátort. Készíts egy négyzethullámot. Nézd a rácsokat - látni fogod, ahogy a furcsa harmonikusok leesnek 1 / n-ként. Váltás egy fűrészfog - most minden harmonika jelen van, leesik 1 / n. Váltás a zaj - lapos spektrum, minden frekvenciát egyformán valószínű.

Az ablakfunkció megváltoztatása. Nézd meg, hogyan simítja Hann a spektrumot a szélesebb csúcsok árán. Váltás Blackman - szűkebb csúcsok, de alsó oldalsó.

Nem az FFT-ről olvasol. Méred a jeleket, és megfigyeled, mit mutat az átalakulás. Ez a különbség a tudás és a megértés között.

Hivatkozások

• Brigham, E.O. (1988). * The Fast Fourier Transform and Its Applications *. Prentice Hall.
• Cooley, J.W. & Tukey, J.W. (1965). Egy algoritmus a komplex Fourier sorozat gépi számításához. * Matematika of Compution *, 19 (90), 297-301.
• Fourier, J. (1822). * Théorie analitique de la chaleur *. Paris: Firmin Didot.
• Harris, F.J. (1978). A Windows használata Harmonikus elemzés a Diszkrét Fourier Transform. * Proceedings of the IEEE *, 66 (1), 51 -83.
• Oppenheim, A.V. & Schafer, R.W. (2009). * Discrete- Time Signal Processing * (3. Prentice Hall.
• Shannon, C.E. (1949). Kommunikáció a zaj jelenlétében. * Proceedings of the IRE *, 37 (1), 10- 21.
• Smith, S.W. (1997). * The Scientist and Engineer 's Guide to Digital Signal Processing *. Kaliforniai Műszaki Kiadó.
• Wang, A., et al. (2003). A Industrial-Strength Audio Search Algoritmus. * Proceedings of ISMIR 2003 *. (Shazam audió ujjlenyomat algoritmusa.)
• Wallace, G.K. (1991). A JPEG még mindig képtömörítő szabvány. * Communications of the ACM *, 34 (4), 30- 44.

---

• PinePaper FFT egy Cooley- Tukey radix2 implementáció Hann, Hamming, és Blackman windowing, plusz alacsony-pass és magas-pass szűrők. Próbálja meg ingyen a [pinepaper.studio / editor] (/editor). *