FFT

Fourier Transform

भौतिकी और गणित में Fourier Transform अक्सर देखने को मिलता है, और इसीलिए इसके रोज़मर्रा के भी कई उपयोग हैं।

संक्षेप में, Fourier Transform एक इनपुट सिग्नल लेता है, जो अक्सर समय या स्थान के डोमेन में होता है, और उसे आवृत्ति डोमेन में बदल देता है। और ठोस रूप में: इनपुट सिग्नल अलग-अलग आवृत्तियों का मिश्रण (यानी सुपरपोज़िशन) होता है, और यह ट्रांसफॉर्म हर आवृत्ति को अलग कर देता है और उनकी सापेक्ष शक्ति दिखाता है।

इसी वजह से यह ट्रांसफॉर्म सिग्नल प्रोसेसिंग (जैसे फ़िल्टरिंग, कम्प्रेशन आदि) और डेटा साइंस के कई कामों में एक प्रमुख टूल बन जाता है। इसलिए इसका उपयोग शायद उससे कहीं ज़्यादा होता है जितना पहली नज़र में लगता है। और चूँकि Fourier Transform का आउटपुट सामान्यतः एक सम्मिश्र संख्या होती है, यह इस बात का भी बढ़िया उदाहरण है कि काल्पनिक संख्याएँ कितनी अनिवार्य हो सकती हैं।

Fourier Transform का एक समाकल रूप भी है, लेकिन हम डिजिटल दुनिया में हैं, इसलिए हमारी दिलचस्पी इसके डिस्क्रीट रूप में है। इस ट्रांसफॉर्म की व्युत्पत्ति इस अभ्यास के दायरे से बाहर है, लेकिन फ़ॉरवर्ड डिस्क्रीट रूपांतरण (जो आवृत्ति डोमेन में ले जाता है) इस रूप का होता है: Xₖ = Σ xₙ * ℯ^(-2iπk * n/N) यहाँ योग n पर चलता है, N सैंपल की संख्या है, k आवृत्ति है, i काल्पनिक इकाई है और xₙ एक अकेला सैंपल है।

Fast Fourier Transform

Fourier Transform बेहद उपयोगी है, लेकिन सीधे-सीधे लागू करने पर यह थोड़ा धीमा रहता है (O(n²))। Fast Fourier Transform (FFT) एक ऐसा एल्गोरिदम है जो इसे बहुत तेज़ कर देता है। आमतौर पर यह काम 'बाँटो और जीतो' जैसी रणनीति से होता है। यह रणनीति इस सूत्र के कुछ सममिति गुणों का उपयोग करती है, और इससे जटिलता एसिंप्टोटिक रूप से O(Nlog(N)) हो जाती है। यह तेज़ी इस ट्रांसफॉर्म की व्यावहारिकता बढ़ाती है, और यह भी बढ़ा देती है कि इसे किन-किन कामों में इस्तेमाल किया जा सकता है।