Mitä FFT todella näyttää sinulle ... Fourier Transform selitetty.. (Suomi)

Kysymys

Soita sointu pianolla sanotaan, C ja E yhdessä. Korvasi kuulee yhden äänen. Mutta tuo ääni on kaksi taajuutta ylitetty: 261,6 Hz ja 329,6 Hz. Sinun cochlea fyysisesti erottaa ne eri hiussolut resonoivat eri taajuuksilla ja lähettävät erilaisia signaaleja aivoihin.

Fast Fourier Transform tekee samoin, mutta numerot sijaan hiussoluja. Anna sille signaali (sarja amplitudinäytteitä ajan mittaan) ja se palauttaa listan taajuuksista ja niiden vahvuuksista. Se vastaa: Mitkä taajuudet ovat läsnä, ja kuinka paljon kukin?

Mitä oikeasti tapahtuu

Ajan mittaan otettu signaali on numeroluettelo: amplitudi kussakin näytteenottopisteessä. 1 sekunnin tallennus 44100 Hz:n nopeudella on 44100 numeroa. Nämä numerot kuvaavat signaalia aika-alueella amplitudi ajan funktiona.

FFT muuntaa tämän taajuusalueeksi amplitudi taajuuden funktiona. Sama tieto, eri edustus. Kuten siirtyminen kartesialaisten ja napakoordinaattien välillä: mitään ei synny tai tuhota, vaan vain ilmaistaan uudelleen.

Matemaattinen ydin: jokainen jaksollinen signaali voidaan kirjoittaa summa sininen ja kosine aaltoja eri taajuuksilla. Tämä on Fourier lause (1807). FFT laskee tämän summan kertoimet kuinka paljon kutakin taajuutta signaalissa on.

Miksi "Nopeasti"

Naiivi tapa laskea Fourier-muunnos vaatii N2-operaatiot N-näytteille. 1024 näytteestä noin miljoona operaatiota. Cooley-Tukey-algoritmi (1965) vähentää tämän N·log2(N) noin 10 000 operaatiota samasta palvelusta. 100 kertaa nopeampi. Miljoonasta näytteestä nopeus on 50 000x.

Temppu: Jaa N-piste muuntaa kaksi N/2-pisteen muuntaa, rekursiivisesti. Tämä edellyttää, että N on teho 2 (tai pad nollia). Jokainen puolittaa ongelman. "Butterfly"-operaatiossa yhdistyvät puoliskot:

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

Jossa W on monimutkainen eksponentiaalinen (kierto monimutkainen taso). Samat kaksi alitulosta antavat sinulle kaksi lähtöpistettä. Siksi algoritmi on "nopea" se käyttää jokaista laskentaa kahdesti.

PinePaper:n toteutus on oppikirja Cooley-Tukey radix-2 DIT (desimaatio ajassa). 40 riviä JavaScriptiä. Kirjoitimme sen tyhjästä sen sijaan, että tuomme kirjaston, koska halusimme opiskelijoiden voivan lukea lähde ja ymmärtää jokaisen rivin.

Mitä nuo baarit tarkoittavat

Kun näet spektrianalysaattorin baarit hyppäävät musiikkiin kukin palkki edustaa taajuusastiaa. Korkeus on kyseisen taajuuden suuruus (voimakkuus) nykyisessä signaalissa.

Puhdasta siniaaltoa tuottaa yhden korkean baarin sen taajuudella eikä mitään muuta.
Neliöaalto tuottaa baareja perus- ja jokaisessa oudossa harmonisessa (3., 5., 7...), vähenevästi 1/n. Siksi neliöaallot kuulostavat "pörinältä" ne sisältävät korkeataajuista energiaa, jota puhtaat synnit eivät.
Valkoinen melu tuottaa suunnilleen samanpituisia baareja kaikkialla. Jokainen taajuus on läsnä yhtä todennäköisesti.
Ihmisääni tuottaa perustavanlaatuisen (kuulemasi) ja muotoseikat resonantti huiput muoto laulukanavan, joka erottaa vokels.

Ensimmäiset kolme ovat alle klikkaa niiden välistä. Korkeudet ovat kaavoja, ei piirros: sini on 1 perus, neliö aalto on täsmälleen 1/n oudoista yliaalloista.

Ikkuna: Miksi reunat asia

Siinä on juju. FFT olettaa signaalin toistuvan ikuisesti. Mutta meidän näyte on rajallinen se alkaa ja loppuu. Jos signaali ei satu olemaan nollassa molemmissa päätepisteissä, äkillinen katkaisu luo keinotekoisen korkean taajuuden sisällön. Tätä kutsutaan spektrivuodoksi.

Kiinnitys: Kerro signaali ikkunatoiminnolla, joka kapenee tasaisesti nollaan reunoilla. Yleiset ikkunat:

Hann (kosiinin kello): hyvä yleinen tarkoitus, menettää jonkin verran taajuusresoluutiota
Hamming: samanlainen kuin Hann, mutta ei saavuta nollaa reunoilla, hieman parempi sidelobe esto
Musta mies: kapeampi päälohko, parempi sidelobe esto, menettää enemmän taajuusresoluutio

Valinta on aina kompromissi taajuusresoluutiosta (miten tarkasti voit tunnistaa taajuuden) ja spektrivuodosta (kuinka paljon energiaa vuotaa naapurin roskiksiin). Täydellistä ikkunaa ei ole. Tämä on seurausta epävarmuuden periaatteesta sinulla ei voi olla mielivaltaisesti tarkkaa tietoa sekä aikaa että taajuutta samanaikaisesti.

FFT:n ja FFT:n välillä

Olet vuorovaikutuksessa FFT:n tulosten kanssa jatkuvasti:

MP3 ja AAC pakkaus: muuntaa äänen taajuusalue, heittää taajuudet alle kuulokynnyksen, pakata mitä jäljellä. Muunnos on koko perusta häviöllinen äänen pakkaus.
JPEG-pakkaus: 2D-versio (DCT) muuntaa 8×8 pikselilohkoa taajuusalueeksi, määrittää korkean taajuuden komponentteja. Siksi JPEG-esineet näkyvät lohkoina.
WiFi ja 5G: OFDM-koodaus jakaa dataa moniin taajuusalgoritmeihin. FFT muuntaa aika-alan lähetys- ja taajuusalueen tietosymbolit.
MRI-kuvantaminen: MRI-skannerin raakasignaali on taajuusavaruudessa. Käänteinen FFT rekonstruoi tilakuvan. Kaikki näkemäsi magneettikuvat ovat käänteistä Fourier-muunnosta.
Shazam: lasketaan spektrogrammi (FFT liukuvien ikkunoiden yllä), otteet huiput, vastaa kaavaa tietokantaan. FFT on ensimmäinen askel jokaisen kappaleen tunnistamisessa.

60-vuotias algoritmi taskussasi.

Kokeile sitä

Avaa PinePaper, valitse Spectrum Analyzer -generaattori. Luo neliöaalto. Katsokaa baareja oudot yliaallot putoavat 1/n. Vaihda sahahampaisiin nyt kaikki yliaallot ovat läsnä, putoavat 1/n. Siirtyminen meluun tasainen spektri, jokainen taajuus yhtä todennäköistä.

Vaihda ikkunatoimintoa. Katso, miten Hann tasoittaa spektriä laajempien huippujen kustannuksella. Vaihda Blackmaniin kapeammat huiput, mutta alemmat sivulehdet.

Et lue FFT:stä. Mittaat signaaleja ja tarkkailet, mitä muutos paljastaa. Se on ero tietämisen ja ymmärtämisen välillä.

Lähteet

Brigham, E.O. (1988). Fast Fourier Transform ja sen sovellukset. Prentice Hall.
Cooley, J.W. & Tukey, J.W. (1965). Algoritmi koneen laskenta Complex Fourier Series. * Laskemisen matematiikka*, 19(90), 297-301.
Fourier, J. (1822). *Théorie analytique de la chaleur *. Pariisi: Firmin Didot.
Harris, FJ. (1978). On käyttö Windows Harmonic Analysis kanssa discrete Fourier Transform. * IEEE:n* käsittelyt, 66(1), 51-83.
Oppenheim, AV. & Schafer, R.W. (2009). * Discrete-Time Signal Processing* (3rd ed.). Prentice Hall.
Shannon, C.E. (1949). Viestintä melun läsnä ollessa. IRE, 37(1), 10-21.
Smith, S.W. (1997). Tieteilijän ja insinöörin opas digitaaliseen signaalinkäsittelyyn. California Technical Publishing.
Wang, A., et al. (2003). Teollisuus-vahva Audio Etsi algoritmi. * ISMIR 2003*. (Shazamin äänisormenjälkialgoritmi.)
Wallace, GK. (1991). JPEG Still Picture Compression Standard. ACM:n tiedonannot, 34(4), 30-44.

PinePaper:n FFT on Cooley-Tukey radix-2 -sovellus, jossa on Hann, Hamming ja Blackman -ikkunat sekä matalat ja korkeapäästöiset suodattimet. Kokeile sitä ilmaiseksi mäntypaperi.studio / editor.