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

Kysymys

Soita pianolla C ja E yhdessä. Korvasi kuulee yhden äänen. Mutta tuo ääni on kaksi taajuutta ylitetty: 261,6 Hz ja 329,6 Hz. Cochlea fyysisesti erottaa ne eri hiussolut resonoi eri taajuuksilla, lähettää erillisiä 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** amplitudilla ajan funktiona.

FFT muuntaa tämän ** frequency domain** . 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 kyseisen summan kertoimet ... kuinka paljon kukin taajuus on signaalissa.

Miksi "Nopeasti"

Naiivi tapa laskea Fourier-muunnos vaatii N2-operaatiot N-näytteille. 1024 näytteestä noin miljoona operaatiota. Cooley-Tukey-algoritmi (1965) pienentää tämän N·log2(N) . 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ä. Tämän vuoksi algoritmi on "nopea" ... se käyttää jokaisen laskelman 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... jokainen baari 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örröinen" . Ne sisältävät korkeataajuista energiaa, että puhdas sines eivät.
Valkoinen melu tuottaa suunnilleen samanpituisia baareja kaikkialla. Jokainen taajuus on läsnä yhtä todennäköisesti.
**Ihmisääni ** tuottaa perustavanlaatuisen (pitkiä kuulet) ja muotonsa resonantteja, jotka erottavat vokaalisi.

Ikkuna: Miksi reunat asia

Siinä on juju. FFT olettaa signaalin toistuvan ikuisesti. Mutta meidän näyte on rajallinen se alkaa ja pysähtyy. 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 .

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.

{{widget:function- plat}

Kokeile sitä

Avaa PinePaper, valitse Spectrum Analyzer -generaattori. Luo neliöaalto. Katsokaa baareja, näette outoja harmonisia putoaa 1/n. Vaihda sahahameeseen. Nyt kaikki yliaallot ovat läsnä. Vaihda meluun tasainen taajuus, jokainen taajuus yhtä todennäköistä.

Vaihda ikkunatoimintoa. Katso, miten Hann tasoittaa spektriä laajempien huippujen kustannuksella. Vaihda Blackmaniin.

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, F.J. (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, CE (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 Hann, Hamming ja Blackman ikkunat, sekä matalat ja korkea-passi suodattimet. Kokeile sitä ilmaiseksi mäntypaperi.studio/editori.