FFT वास्तव में आपको क्या दिखाता है

प्रश्न

एक पियानो पर एक chord खेलते हैं - कहते हैं, C और E एक साथ। आपका कान एक ध्वनि सुनता है। लेकिन यह ध्वनि दो आवृत्तियों पर निर्भर है: 261.6 हर्ट्ज और 329.6 हर्ट्ज। आपकी शारीरिक रूप से उन्हें अलग करती है - विभिन्न बाल कोशिकाएं विभिन्न आवृत्तियों पर अनुनाद करती हैं, जो आपके मस्तिष्क को अलग सिग्नल भेजती हैं।.

फास्ट फोरियर ट्रांसफॉर्म एक ही चीज है, लेकिन बालों की कोशिकाओं के बजाय संख्याओं के साथ। इसे एक संकेत दें (समय पर आयाम नमूने का एक अनुक्रम) और यह आवृत्तियों और उनकी ताकत की एक सूची देता है। यह उत्तर है: *क्या आवृत्तियां मौजूद हैं, और कितने प्रत्येक?

वास्तव में क्या है

समय के साथ नमूना एक संकेत संख्या की एक सूची है: प्रत्येक नमूना बिंदु पर आयाम। 44,100 हर्ट्ज पर 1-सेकंड रिकॉर्डिंग 44,100 नंबर है। इन संख्याओं में संकेत का वर्णन ** समय डोमेन* — समय के एक समारोह के रूप में आयाम।.

FFT इसे ** फ़्रीक्वेंसी डोमेन* में बदल देता है - फ़्रीक्वेंसी के एक कार्य के रूप में आयाम। समान जानकारी, विभिन्न प्रतिनिधित्व। कार्टेशियन और ध्रुवीय निर्देशांक के बीच स्विचन की तरह: कुछ भी नहीं बनाया गया है या नष्ट किया गया है, केवल फिर से व्यक्त किया गया है।.

गणितीय कोर: प्रत्येक आवधिक संकेत विभिन्न आवृत्तियों पर साइन और कॉसिन तरंगों के योग के रूप में लिखा जा सकता है। यह फोरियर का प्रमेय (1807) है। FFT उस राशि के गुणांकों की गणना करता है - प्रत्येक आवृत्ति का कितना संकेत में है।.

क्यों "फास्ट"

एक फोरियर को बदलने के लिए नौसैनिक तरीके की आवश्यकता होती है N2 के नमूने के लिए N2 ऑपरेशन। 1024 नमूनों के लिए, यह लगभग 1 मिलियन ऑपरेशन है। Cooley-Tukey एल्गोरिथ्म (1965) इसे N·log2(N) को कम करता है - उसी इनपुट के लिए लगभग 10,000 ऑपरेशन। 100x speedup. एक मिलियन नमूने के लिए, स्पीडअप 50,000x है।.

चाल: एन-पॉइंट को विभाजित करने से दो एन / 2-पॉइंट में बदल जाता है, फिर से बदल जाता है। इसके लिए एन को 2 (या आप शून्य के साथ पैड) की शक्ति की आवश्यकता होती है। प्रत्येक विभाजन समस्या को हल करता है। "बटरफ्लाई" ऑपरेशन आधा को जोड़ती है:

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

जहां W एक जटिल एक्सोनेंशियल (एक जटिल विमान में घूर्णन) है। एक ही दो उप-परिणाम आपको दो आउटपुट अंक देते हैं। यही कारण है कि एल्गोरिथ्म "फास्ट" है - यह दो बार प्रत्येक गणना का पुन: उपयोग करता है।.

PinePaper का कार्यान्वयन एक पाठ्यपुस्तक Cooley-Tukey radix-2 DIT (समय पर विघटन) है। जावास्क्रिप्ट की 40 लाइनें। हमने इसे लाइब्रेरी आयात करने के बजाय स्क्रैच से लिखा क्योंकि हम चाहते थे कि छात्र स्रोत को पढ़ने और हर लाइन को समझने में सक्षम हों।.

उन बार्स का क्या मतलब है

जब आप स्पेक्ट्रम विश्लेषक देखते हैं - बार संगीत में कूदते हैं - प्रत्येक बार एक आवृत्ति बिन का प्रतिनिधित्व करता है। वर्तमान सिग्नल में उस आवृत्ति की ऊंचाई (शक्ति) है।.

• ** एक शुद्ध साइन लहर** अपनी आवृत्ति पर एक लंबा बार पैदा करता है और कुछ नहीं।.
• ** एक वर्ग लहर* मूल और हर विषम हार्मोनिक (3rd, 5th, 7th...) पर सलाखों का उत्पादन करता है, जो 1/n के रूप में घटता है। यही कारण है कि वर्ग तरंगें ध्वनि "buzzy" - उनमें उच्च आवृत्ति ऊर्जा होती है जो शुद्ध पाप नहीं करते हैं।.
• ** व्हाइट शोर* हर जगह लगभग बराबर ऊंचाई के सलाखों का उत्पादन करता है। प्रत्येक आवृत्ति बराबर संभावना के साथ मौजूद है।.
• ** एक मानव आवाज* एक मौलिक (आप जो पिच सुनते हैं) प्लस फॉर्मेंट्स - अपने मुखर ट्रैक्ट के आकार से अनुनाद चोटी जो स्वरों को अलग करती हैं।.

खिड़की: क्यों एज्स मैटर

वहाँ एक पकड़ है। FFT हमेशा के लिए संकेत दोहराता है। लेकिन हमारा नमूना परिमित है - यह शुरू होता है और रुक जाता है। यदि संकेत दोनों समापन बिंदुओं पर शून्य नहीं होता है, तो अचानक कटऑफ कृत्रिम उच्च आवृत्ति सामग्री बनाता है। इसे *स्पेक्ट्रल रिसाव कहा जाता है।.

फिक्स: एक **विंडो फ़ंक्शन * द्वारा संकेत को गुणा करें जो किनारों पर शून्य होने के लिए आसानी से टैप करता है। आम खिड़कियां:

• ** हैन ** (cosine bell): अच्छा सामान्य उद्देश्य, कुछ आवृत्ति संकल्प खो देता है
• ** हैमिंग*: हैन के समान लेकिन किनारों पर शून्य नहीं पहुंचता, थोड़ा बेहतर साइडलोब दमन
• ** ब्लैकमैन*: संकीर्ण मुख्य लोब, बेहतर sidelobe दमन, अधिक आवृत्ति संकल्प खो देता है

पसंद हमेशा आवृत्ति संकल्प के बीच एक व्यापार है (कैसे ठीक आप एक आवृत्ति की पहचान कर सकते हैं) और वर्णक्रमीय रिसाव (कैसे पड़ोसी डिब्बे में ऊर्जा bleeds)। कोई सही विंडो नहीं है। यह अनिश्चितता सिद्धांत का एक परिणाम है - आपको एक साथ समय और आवृत्ति दोनों का मनमाने ढंग से सटीक ज्ञान नहीं मिल सकता है।.

जहां FFT Lives

आप लगातार FFT परिणाम के साथ बातचीत करते हैं:

• ** एमपी 3 और एएसी संपीड़न **: ऑडियो को आवृत्ति डोमेन में बदल दें, सुनवाई सीमा के नीचे आवृत्तियों को हटा दें, जो कि बनी हुई है। The change is the full form of lossy audio संपीड़न.
• ** JPEG संपीड़न*: 2D संस्करण (DCT) 8 × 8 पिक्सेल ब्लॉकों को आवृत्ति डोमेन में बदल देता है, उच्च आवृत्ति घटकों को मापता है। क्यों JPEG कलाकृतियों ब्लॉक के रूप में दिखाई देते हैं।.
• ** वाईफ़ाई और 5G *: OFDM कई आवृत्ति उप वाहकों में डेटा को विभाजित करता है। FFT टाइम-डोमेन ट्रांसमिशन और फ्रीक्वेंसी-डोमेन डेटा प्रतीकों के बीच परिवर्तित होता है।.
• *MRI इमेजिंग: एक MRI स्कैनर से कच्चे संकेत आवृत्ति अंतरिक्ष में है। उलटा FFT स्थानिक छवि का पुनर्निर्माण करता है। शाब्दिक रूप से: हर MRI जिसे आपने कभी देखा है वह एक उलटा फोरियर बदलाव है।.
• ** Shazam*: स्पेक्ट्रोग्राम (FFT ओवर स्लाइडिंग विंडो), एक्सट्रैक्ट चोटियों की गणना करता है, एक डेटाबेस के खिलाफ पैटर्न से मेल खाता है। FFT प्रत्येक गीत को पहचानने में पहला कदम है।.

60 वर्षीय एल्गोरिथ्म, आपकी जेब में, प्रति दिन अरब बार चल रहा है।.

इसे आज़माएं

PinePaper खोलें, स्पेक्ट्रम विश्लेषक जनरेटर का चयन करें। एक वर्ग लहर उत्पन्न करना। बार देखें - आप 1 / n के रूप में गिरते हुए अजीब हार्मोनिक्स देखेंगे। एक sawtooth पर स्विच करें - अब सभी हार्मोनिक मौजूद हैं, जो 1/n के रूप में गिरते हैं। शोर करने के लिए स्विच - फ्लैट स्पेक्ट्रम, समान रूप से हर आवृत्ति की संभावना है।.

विंडो फंक्शन बदलें। देखें कि हंस व्यापक चोटियों की लागत पर स्पेक्ट्रम को कैसे चिकना करता है। ब्लैकमैन को स्विच करें - संकीर्ण चोटियों लेकिन निचले sidelobes।.

आप FFT के बारे में नहीं पढ़ रहे हैं। आप संकेतों को माप रहे हैं और देख रहे हैं कि क्या परिवर्तन प्रकट होता है। यह जानने और समझने के बीच अंतर है।.

संदर्भ

• Brigham, E.O. (1988)। * फास्ट फोरियर ट्रांसफॉर्म और इसके अनुप्रयोग* प्रेंटिस हॉल।.
• कूली, जेडब्ल्यू और टकी, जेडब्ल्यू (1965)। जटिल फोरियर सीरीज की मशीन गणना के लिए एक एल्गोरिथ्म। * संगणन के गणित*, 19(90), 297-301.
• फोरियर, जे (1822)। Théorie analytique de la chaleur पेरिस: फर्मिन डिडॉट।.
• हैरिस, FJ (1978)। डिस्क्रेट फोरियर ट्रांसफॉर्म के साथ हार्मोनिक विश्लेषण के लिए विंडोज के उपयोग पर। * IEEE*, 66 (1), 51-83 की प्रक्रिया।.
• Oppenheim, A.V. और Schafer, RW (2009)। *डिस्क्रीट टाइम सिग्नल प्रोसेसिंग * (3rd ed)। प्रेंटिस हॉल।.
• शैनन, सी.ई. (1949)। शोर की उपस्थिति में संचार। IRE*, 37 (1), 10-21 की प्रक्रिया।.
• स्मिथ, एसडब्ल्यू (1997)। * वैज्ञानिक और इंजीनियर डिजिटल सिग्नल प्रोसेसिंग के लिए गाइड*। कैलिफोर्निया तकनीकी प्रकाशन।.
• वांग, ए., एट अल (2003)। एक औद्योगिक-शक्ति ऑडियो खोज एल्गोरिथ्म। ISMIR 2003* की प्रक्रिया (Shazam के ऑडियो फिंगरप्रिंटिंग एल्गोरिदम)।
• वैलेस, जीके (1991)। JPEG अभी भी चित्र संपीड़न मानक। * ACM *, 34(4), 30-44 के संचार।.

---

• PinePaper का FFT एक Cooley-Tukey radix-2 कार्यान्वयन है जिसमें हन्न, हम्मिंग और ब्लैकमैन विंडोिंग, प्लस लो-पास और हाई-पास फिल्टर शामिल हैं। इसे [pinepaper.studio/editor] (/editor) में मुफ्त आज़माएं।