Ce vă arată de fapt FFT

Întrebarea

Cântă o coardă pe un pian, să zicem, C şi E împreună. Urechea ta aude un sunet. Dar sunetul este suprapus la două frecvențe: 261.6 Hz și 329.6 Hz. Cohlea dvs. fizic le separă .

Fast Fourier Transform face același lucru, dar cu numere în loc de celule de păr. Dă-i un semnal (o secvență de eșantioane de amplitudine în timp) și returnează o listă de frecvențe și punctele lor forte. Ea răspunde: ** ce frecvenţe sunt prezente, şi cât de mult din fiecare?**

Ce se întâmplă de fapt

Un semnal eșantionat în timp este o listă de numere: amplitudinea la fiecare punct de eșantionare. O înregistrare de 1 secundă la 44,100 Hz este 44,100 numere. Aceste numere descriu semnalul în domeniul ** timp** .

În cazul în care se utilizează o metodă de calcul a ratei dobânzii, se utilizează o rată a dobânzii mai mică de 10%. Aceleaşi informaţii, reprezentare diferită. Cum ar fi schimbarea coordonatelor carteziene şi polare: nimic nu este creat sau distrus, doar re-exprimat.

Nucleul matematic: fiecare semnal periodic poate fi scris ca o sumă de unde sinusale și cosine la frecvențe diferite. Aceasta este teoria lui Fourier (1807). În cazul în care, în conformitate cu articolul 107 alineatul (3) litera (c) din tratat, se aplică articolul 107 alineatul (1) din tratat, se aplică articolul 107 alineatul (1) din tratat.

De ce "Fast"

Modul naiv de a calcula o transformare Fourier necesită Operațiuni N2 pentru eșantioane N. Pentru 1024 de mostre, asta înseamnă cam 1 milion de operaţiuni. Algoritmul Cooley-Tukey (1965) reduce acest lucru la N·log2(N) aproximativ 10.000 de operațiuni pentru aceeași intrare. O viteză de 100x. Pentru un milion de mostre, viteza este de 50.000x.

Trucul: se împarte N-punct transforma în două N/2-punct se transformă, recursiv. Acest lucru necesită N să fie o putere de 2 (sau pad cu zerouri). Fiecare împărţire în două face problema. Operaţiunea "Butterfly" combină jumătăţile:

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

În cazul în care W este un complex exponențial (o rotație în planul complex). Aceleaşi două sub-rezultate vă oferă două puncte de ieşire. Acesta este motivul pentru care algoritmul este "rapid" .

Punerea în aplicare a PinePaper este un manual Cooley-Tukey radix-2 DIT (decimare în timp). 40 de linii de JavaScript. Am scris-o de la zero în loc să importăm o bibliotecă pentru că am vrut ca elevii să poată citi sursa şi să înţeleagă fiecare linie.

Ce înseamnă aceste bare

Când vedeți un analizor de spectru baruri sărituri la muzică Înălțimea este magnitudinea (puterea) acestei frecvențe în semnalul curent.

• ** Un val de sine pur** produce un bar înalt la frecvenţa sa şi nimic altceva.
• ** Un val pătrat** produce bare la baza și fiecare armonică ciudată (3, 5, 7...), în scădere cu 1/n. Acesta este motivul pentru valuri patrate sunet "buzzy" .
• ** Zgomot alb** produce bare de aproximativ egală înălțime peste tot. Fiecare frecvenţă este prezentă cu probabilitate egală.
• O voce umană produce un element fundamental (smoul pe care îl auziți) plus formatori .

Fereastra: De ce contează marginile

Există o captură. În cazul în care se utilizează o metodă de stabilire a prețurilor de transfer, trebuie să se țină seama de faptul că, în cazul în care o astfel de evaluare este efectuată în conformitate cu articolul 107 alineatul (3) litera (c) punctul (ii) din tratat, trebuie să se țină seama de faptul că, în cazul în care o astfel de evaluare este efectuată în conformitate cu articolul 107 alineatul (3) litera (c) din tratat, este necesar să se ia în considerare o ajustare a valorii de piață a profitului. Dar proba noastră este finită. Începe şi se opreşte. În cazul în care semnalul nu se întâmplă să fie la zero la ambele obiective, întreruperea bruscă creează un conținut artificial de înaltă frecvență. Acest lucru se numește ** scurgere spectral**.

Fix: multiplicaţi semnalul cu o funcţie ** de fereastră** care se reduce uşor la zero la margini. Ferestre comune:

• Hann (Cosine Bell): bun scop general, pierde unele rezoluție a frecvenței
• Hamming: similar cu Hann, dar nu ajunge la zero la margini, suprimarea lobului lateral ușor mai bine
• Blackman: lobul principal mai îngust, o mai bună suprimare a lobului lateral, pierde mai multă rezoluție a frecvenței

Alegerea este întotdeauna un compromis între rezoluția frecvenței (cât de precis puteți identifica o frecvență) și scurgeri spectrale (câtă energie sângerează în pubele învecinate). Nu există fereastră perfectă. Aceasta este o consecinţă a principiului incertitudinii .

În cazul în care FFT trăiește

Interacţionaţi constant cu rezultatele FFT:

• MP3 şi compresia AAC: transformaţi audio în domeniu de frecvenţă, aruncaţi frecvenţele sub pragul auditiv, comprimaţi ce rămâne. Transforma este întreaga bază de compresie audio pierdere.
• JPEG compresie: versiunea 2D (DCT) transformă 8×8 blocuri de pixeli în domeniul de frecvenţă, cuantizează componentele de înaltă frecvenţă. De aceea artefactele JPEG apar ca blocuri.
• WiFi and 5G: OFDM coding divide date pe mai multe sub-carrieri de frecventa. În cazul în care se utilizează o metodă bazată pe rata dobânzii, se utilizează o rată a dobânzii mai mică de 10%.
• Imagistica RMN: semnalul brut de la un scaner RMN este în spațiul de frecvență. Inversul FFT reconstituie imaginea spațială. La propriu: fiecare RMN pe care l-ai văzut vreodată este o transformare Fourier inversă.
• Shazam: calculează spectrograma (FFT peste ferestre glisante), extrase vârfuri, se potrivește modelului cu o bază de date. FFT este primul pas în recunoașterea fiecărui cântec.

Un algoritm vechi de 60 de ani, în buzunar, care rulează de miliarde de ori pe zi.

{widget: function-plot}

Încearcă

Deschideți PinePaper, selectați generatorul de analiză a spectrului. Generează un val pătrat. Uită-te la baruri . Veți vedea armonicile ciudate care se încadrează off ca 1/n. Treceți la un fierăstrău Treceţi la frecvenţa de zgomot .

Schimbă funcţia ferestrei. Uită-te cum Hann netede spectrul cu costul vârfurilor mai largi. Treceți la Blackman .

Nu citeşti despre FFT. Măsori semnale şi observi ce dezvăluie transformarea. Asta e diferenţa dintre cunoaştere şi înţelegere.

Referințe

• Brigham, E.O. (1988). The Fast Fourier Transform and Its Applications. Prentice Hall.
• Cooley, J.W. & Tukey, J.W. (1965). Un Algoritm pentru calculul mecanic al Complexului Fourier Series. Matematică de calcul, 19(90), 297-301.
• Fourier, J. (1822). Théorie analytique de la chaleur. Paris: Firmin Didot.
• Harris, F.J. (1978). Cu privire la utilizarea Windows pentru analiza armonică cu Discrete Fourier Transform. Proceedings of the IEEE, 66(1), 51-83.
• Oppenheim, A.V. & Schafer, R.W. (2009). Discrete-Time Signal Processing (3rd ed.). Prentice Hall.
• Shannon, e.n. (1949). Comunicare în prezența zgomotului. 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). A Industrial-Forngth Audio Search Algoritm. Proceedings of ISMIR 2003. (Algoritmul de amprentare audio Shazam.)
• Wallace, G.K. (1991). The JPEG Still Picture Compression Standard. Comunications of the ACM, 34(4), 30-44.

---

PinePaper's FFT este o implementare Cooley-Tukey radix-2 cu Hann, Hamming, și Blackman ferestre, plus mici-pass și filtre de mare trecere. Încercaţi gratuit la paper.studio/editor.