Kung Ano ang Aktuwal na Ipinakikita sa Iyo ng CFT

Ang Tanong

Magsuot ng akorde sa piyano — halimbawa, sina C at E. Ang iyong tainga ay nakaririnig ng isang tunog. Subalit ang tunog na iyan ay dalawang frequency superimposed: 261.6 Hz at 329.6 Hz. pisikal na pinaghihiwalay sila ng iyong Kapuluan — iba't ibang selula ng buhok ang kumukumpas sa iba't ibang frequency, na naghahatid ng iba't ibang hudyat sa iyong utak.

Gayundin ang ginagawa ng Mabilis na Fourier Transform, subalit may mga numero sa halip na mga selula ng buhok. Bigyan ito ng hudyat (isang pagkakasunud - sunod ng mga sampol na amplitude sa paglipas ng panahon) at ibinabalik nito ang isang talaan ng mga frequency at ang kanilang lakas. Sumasagot ito: ** Aling frequency ang naroroon, at gaano karami sa bawat isa?**

Ang Talagang Nangyayari

Ang isang hudyat na sampol sa paglipas ng panahon ay isang talaan ng mga numero: ang amplutude sa bawat sampol na dako. Ang isang 1-second recording sa 44,100 Hz ay 44,100 numero. Ang mga numerong ito ay naglalarawan sa signal sa *time domain — amplual bilang isang tungkulin ng panahon.

Binabago ito ng FFT sa frequency domain — amplitude bilang isang tungkulin ng frequency. Parehong impormasyon, iba't ibang representasyon. Tulad ng paglipat sa pagitan ng Cartesian at polar coordinates: walang nalilikha o nasisira, kundi re-expressed lamang.

Ang matematikal na core: ang bawat periodic signal ay maaaring isulat bilang isang kabuuan ng mga alon ng sine at cosine sa iba't ibang frequency. Ito ang pang-orem ng Fourier (1807). Ibinibilang ng FFT ang mga coficity ng halagang iyon — gaano karami sa bawat frequency ang nasa signal.

Kung Bakit "Bukal"

Kailangan ang walang - muwang na paraan upang makabuo ng Apat na Pagbabago N2 operasyon para sa mga sampol ng N. Para sa 1024 sampol, iyan ay halos 1 milyong operasyon. Binabawasan ito ng Cooley-Tukey algorithm (1965) sa N·log2(N) — mga 10,000 operasyon para sa parehong input. Isang 100x na speed-up. Para sa isang milyong sampol, ang speed-up ay 50,000x.

Ang trick: hatiin ang N-point na ginagawang dalawang N/2-point na pagbabago, revisively. Kailangan dito ang N upang maging lakas na 2 (o ikaw pad na may seros). Binabawasan ng bawat hati ang problema. Pinagsasama ng "butterfly" na operasyon ang kalahati:

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

Kung saan ang W ay isang komplikadong exponential (isang ikot sa komplikadong eroplano). Ang parehong dalawang sub-results ay nagbibigay sa iyo ng dalawang output points. Ito ang dahilan kung bakit ang algorithm ay "fast" — ginagamit nitong muli ang bawat kalkulasyon nang dalawang beses.

Ang pagpapatupad ng PinePaper ay isang aklat-aralin na Cooley-Tukey radix-2 DIT (decimation sa panahon). 40 linya ng JavaScript. Isinulat namin ito sa halip na mag - angkat ng aklatan dahil gusto naming mabasa ng mga estudyante ang pinagmulan nito at maunawaan ang bawat linya.

Kung Ano ang Kahulugan ng mga Bigas na Iyon

Kapag nakakita ka ng spectrum analysis — mga bar na tumatalon sa musika — ang bawat bar ay kumakatawan sa isang frequency bin. Ang taas ay ang magnitude (strength) ng dalas na iyon sa kasalukuyang signal.

• ** Ang purong sine wave** ay gumagawa ng isang mataas na bara sa dalas nito at wala nang iba pa.
• ** Ang isang along parisukat* ay gumagawa ng mga bar sa pundamental at bawat kakaibang harmoniko (3rd, 5th, 7th...), bumaba bilang 1/n. Ito ang dahilan kung bakit ang mga along parisukat ay tunog na "buzzy" — ang mga ito ay naglalaman ng mataas-frequency na enerhiya na hindi taglay ng mga purong kasalanan.
• ** Ang puting ingay** ay gumagawa ng mga bar na halos pantay ang taas saanman. Ang bawat dalas ay makikita na may pare - parehong probabilidad.
• ** Ang tinig ng tao** ay gumagawa ng isang pundamental (ang tono na iyong naririnig) at mga formant — mga tumbong na taluktok mula sa hugis ng iyong vocal tract na nakakakilala sa mga patinig.

Windowing: Kung Bakit Mahalaga ang mga Edge

May huli. Ipinapalagay ng FFT ang hudyat na inuulit magpakailanman. Subalit ang aming sampol ay may hangganan — ito ay nagsisimula at humihinto. Kung ang signal ay hindi nagkataong nasa sero sa parehong endpoints, ang biglaang cuff ay lumilikha ng artipisyal na mataas-frequency content. Ito ay tinatawag na spectral na tulo.

Ang fix: paramihin ang signal sa pamamagitan ng isang window function na maayos na bumaba hanggang sero sa mga gilid. Karaniwang mga bintana:

• Hann (cosine bell): mabuting pangkalahatang layunin, ay nawawalan ng ilang frequency resolution
• Hamming: kahawig ng Hann subalit hindi umaabot sa sero sa mga gilid, bahagyang mas mabuting pagsupil sa tagiliran
• *Blackman: Ang mas makitid na pangunahing bahagi ng utak, mas mabuting pagsupil sa tagiliran, ay nawawalan ng mas madalas na resolusyon

Ang pagpili ay laging isang palitan sa pagitan ng frequency resolution (kung paano mo eksaktong makikilala ang isang frequency) at spectral na tulo (kung gaano karaming enerhiya ang pumapasok sa kalapit na mga bin). Walang sakdal na bintana. Ito'y bunga ng walang katiyakang simulain — hindi mo maaaring magkaroon ng tiyak na kaalaman kapuwa sa panahon at dalas nang sabay - sabay.

Kung Saan Nabubuhay ang mga May - edad Na

Palaging nagkakaroon ka ng reaksiyon sa mga resulta ng FFT:

• MP3 at AAC compression: baguhin ang audio sa frequency domain, itapon ang frequency sa ibaba ng pasukan ng pandinig, i - compress ang natitira. Ang transpormasyon ay ang buong batayan ng pagkawala ng audio compression.
• JPEG compression: binabago ng 2D na bersyon (DCT) ang 8×8 pixel blocks sa frequency domain, quantizes high-frequency na mga bahagi. Iyan ang dahilan kung bakit ang mga artipakto ng JPEG ay lumilitaw bilang mga bloke.
• WiFi at 5G: Binibiyak ng OFDM Experiment ang datos sa maraming frequency sub-carriers. Ang FFT ay nagkukumberte sa pagitan ng time-domain transmission at frequency-domain data symbols.
• MRI imaging: ang hilaw na hudyat mula sa isang MRI scanner ay nasa frequency space. Muling binuo ng inverse FFT ang spinial image. Literal: Ang bawat MRI na kailanma'y nakita mo ay isang di - mababagong Fourier na pagbabago.
• Shazam: computes the spectrogram (FFT sa ibabaw ng dumadausos na mga bintana), mga taluktok, ay tumutugma sa disenyo laban sa isang database. Ang FFT ang unang hakbang sa pagkilala sa bawat awit.

Isang 60-year-old algorithm, sa iyong bulsa, na tumatakbo ng bilyun-bilyong beses sa bawat araw.

Subukin Ito

Open PinePaper, piliin ang Spectrum analypler generator. Gumamit ng along kuwadrado. Tingnan ang mga bar — makikita mo ang kakaibang mga harmoniko na nahuhulog bilang 1/n. Lumangoy sa isang lagari — ngayon lahat ng mga harmoniko ay naroroon, bumabagsak bilang 1/n. Lumipat sa ingay — flat spectrum, ang bawat frequency ay malamang na gayundin.

Palitan ang takbo ng bintana. Masdan kung paano pinapatag ni Hann ang espesye sa halaga ng mas malawak na mga tuktok. Lumipat sa Blackman — mas makitid na taluktok ngunit mas mababang mga gilid.

Hindi mo binabasa ang tungkol sa FFT. Sinusukat mo ang mga hudyat at pinagmamasdan mo kung ano ang isinisiwalat ng pagbabago. Iyan ang pagkakaiba ng kaalaman at unawa.

Mga reperensiya

• Brigham, E.O. (1988). * Ang Mabilis na Fourier Transform at ang Gamit Nito*. Prentice Hall.
• Cooley, J.W. & Tukey, J.W. (1965). Isang Algorithm para sa Machine Escription ng Complex Fourier Series. Mathematics of Computation, 19(90), 297-301.
• Fourier, J. (1822). Théorie analytique de la chaleur. Paris: Firmin Diot.
• Harris, F.J. (1978). Sa Paggamit ng Windows for Harmonic Analysis na may Dikretong Apatier na Pagbabago. * Mga hula ng IEE*, 66(1), 51-83.
• Oppenheim, A.V. & Schafer, R.W. (2009). * Discrete-Time Signal Proseso* (3rd ed.). Prentice Hall.
• Shannon, C.E. (1949). Pakikipagtalastasan sa Harap ng Ingay. 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). Isang Industriyal-Strength Audio Search Algorithm. * Mga propesiya ng HIMIR 2003*. (Shazam's audio fingerprinting algorithm.)
• Wallace, G.K. (1991). Ang JPEG Still Picture Compression Standard. Communications of the ACM, 34(4), 30-44.

---

PinePaper's FFT ay isang Cooley-Tukey radix-2 na pagpapatupad kasama ang Hann, Hamming, at Blackman windowing, pati na ang mga low-pass at high-pass filters. Subukin itong malaya sa pinepaper.studio/editor.