फास्ट फूरिये रूपांतर

"एफएफटी" redirects here. For other uses, see एफएफटी (disambiguation).

आधे आकार के एफएफटी में अपघटन का उपयोग करते हुए एक उदाहरण एफएफटी एल्गोरिदम संरचना

10, 20, 30, 40, और 50 हर्ट्ज पर कोज्या तरंगों के योग का असतत फूरियर विश्लेषण

एक तेज़ फूरियर रूपांतरण (एफएफटी) एक कलन विधि है जो एक अनुक्रम के असतत फूरियर रूपांतरण (डीएफटी) या इसके व्युत्क्रम (डीएफटी) की गणना करता है। फूरियर विश्लेषण एक संकेत को उसके मूल डोमेन (अधिकांशतः समय या स्थान) से आवृत्ति डोमेन में एक प्रतिनिधित्व में परिवर्तित करता है और इसके विपरीत। विभिन्न आवृत्तियों के घटकों में मूल्यों के अनुक्रम को विघटित करके डीएफटी प्राप्त किया जाता है। यह संक्रिया कई क्षेत्रों में उपयोगी है, किन्तु सीधे परिभाषा से इसकी गणना करना अधिकांशतः व्यावहारिक होने के लिए बहुत धीमा होता है। एक एफएफटी तेजी से आव्यूह अपघटन द्वारा डीएफटी आव्यूह को विरल आव्यूह (अधिकतर शून्य) कारकों के उत्पाद में इस तरह के परिवर्तनों की गणना करता है। परिणाम स्वरुप,${\textstyle O\left(N^{2}\right)}$ से डीएफटी की गणना के कम्प्यूटेशनल जटिलता सिद्धांत को कम करने का प्रबंधन करता है , जो उत्पन्न होता है यदि कोई केवल डीएफटी की परिभाषा को ${\textstyle O(N\log N)}$ प्रयुक्त करता है , जहां $N$ डेटा का आकार है। गति में अंतर बहुत अधिक हो सकता है, विशेष रूप से लंबे डेटा समूह के लिए बहुत अधिक हो सकता है जहां N हजारों या लाखों में हो सकता है।पूर्णांक त्रुटि,की उपस्थिति में, कई एफएफटी एल्गोरिदम प्रत्यक्ष या अप्रत्यक्ष रूप से डीएफटी परिभाषा का मूल्यांकन करने से कहीं अधिक स्पष्ट हैं। सरल जटिल-संख्या अंकगणित से समूह सिद्धांत और संख्या सिद्धांत तक प्रकाशित सिद्धांतों की एक विस्तृत श्रृंखला के आधार पर कई अलग-अलग एफएफटी एल्गोरिदम हैं।

एक ही संकेत का समय-आधारित प्रतिनिधित्व (ऊपर) और आवृत्ति-आधारित प्रतिनिधित्व (नीचे), जहां फूरियर रूपांतरण द्वारा ऊपरी एक से निचला प्रतिनिधित्व प्राप्त किया जा सकता है

इंजीनियरिंग संगीत विज्ञान और गणित में अनुप्रयोगों के लिए फास्ट फूरियर रूपांतरण का व्यापक रूप से उपयोग किया जाता है। बुनियादी विचारों को 1965 में लोकप्रिय किया गया था किन्तु कुछ एल्गोरिदम 1805 की प्रारंभिक में ही प्राप्त किए गए थे। 1994 में गिल्बर्ट स्ट्रैंग ने FFT को "हमारे जीवनकाल का सबसे महत्वपूर्ण संख्यात्मक एल्गोरिदम" के रूप में वर्णित किया ।और इसे IEEE द्वारा 20वीं शताब्दी के शीर्ष 10 एल्गोरिदम में सम्मिलित किया गया था। विज्ञान और इंजीनियरिंग में पत्रिका कम्प्यूटिंग करना है।,

सबसे प्रसिद्ध एफएफटी एल्गोरिदम $N$ के गुणनखंड पर निर्भर करते हैं, किन्तु सभी $N$ के लिए O(N log N) जटिलता वाले एफएफटी हैं, यहां तक कि प्राइम $N$ के लिए भी। कई एफएफटी एल्गोरिदम केवल इस तथ्य पर निर्भर करते हैं कि ${\textstyle e^{-2\pi i/N}}$ एकता का N-वाँ आदिम मूल है, और इस प्रकार संख्या-सैद्धांतिक रूपांतरण जैसे किसी भी परिमित क्षेत्र पर अनुरूप परिवर्तनों पर प्रयुक्त किया जा सकता है। चूंकि उलटा डीएफटी डीएफटी के समान है, किन्तु एक्सपोनेंट में विपरीत चिह्न और 1/N कारक के साथ, किसी भी एफएफटी एल्गोरिदम को इसके लिए आसानी से अनुकूलित किया जा सकता है।

इतिहास

डीएफटी के लिए तेजी से एल्गोरिदम के विकास का पता 1805 में कार्ल फ्रेडरिक गॉस के अप्रकाशित काम से लगाया जा सकता है, जब उन्हें नमूना अवलोकनों से क्षुद्रग्रहों पलास और जूनो की कक्षा को प्रक्षेपित करने की आवश्यकता थी। उनका विधि 1965 में जेम्स कूली और जॉन टुकी द्वारा प्रकाशित एक के समान था, जिन्हें सामान्यतः आधुनिक जेनेरिक एफएफटी एल्गोरिथम के आविष्कार के लिए श्रेय दिया जाता है। जबकि गॉस का काम 1822 में जोसेफ फूरियर के परिणामों से भी पहले का था, उन्होंने गणना समय का विश्लेषण नहीं किया और अंततः अपने लक्ष्य को प्राप्त करने के लिए अन्य विधि का उपयोग किया।

1805 और 1965 के बीच, एफएफटी के कुछ संस्करण अन्य लेखकों द्वारा प्रकाशित किए गए थे। 1932 में फ्रैंक येट्स ने पारस्परिक क्रिया एल्गोरिथम नामक अपना संस्करण प्रकाशित किया, जिसने तेजी से वॉल्श-हदमर्ड रूपांतरण प्रदान किया। येट्स का एल्गोरिद्म अभी भी सांख्यिकीय डिजाइन और प्रयोगों के विश्लेषण के क्षेत्र में उपयोग किया जाता है। 1942 में, जी.सी. डेनियलसन और कॉर्नेलियस लैंक्ज़ोस ने एक्स - रे क्रिस्टलोग्राफी के लिए डीएफटी की गणना करने के लिए अपना संस्करण प्रकाशित किया, एक ऐसा क्षेत्र जहां फूरियर रूपांतरण की गणना ने एक दुर्जेय बाधा प्रस्तुत की। जबकि अतीत में कई विधियों ने "समरूपता" का लाभ उठाकर ${\textstyle O\left(N^{2}\right)}$ गणना के लिए निरंतर कारक को कम करने पर ध्यान केंद्रित किया था, डेनियलसन और लैंक्ज़ोस ने अनुभूत किया कि कोई भी आवधिकता का उपयोग कर सकता है और [N] को दोगुना करने के लिए दोहरीकरण चाल प्रयुक्त कर सकता है, चूंकि गॉस की तरह उन्होंने विश्लेषण नहीं किया इसके कारण ${\textstyle O(N\log N)}$ स्केलिंग हुई थी।

जेम्स कूली और जॉन टुकी ने स्वतंत्र रूप से इन पहले के एल्गोरिदम को फिर से खोजा और 1965 में एक अधिक सामान्य एफएफटी प्रकाशित किया जो तब प्रयुक्त होता है जब N समग्र होता है और आवश्यक नहीं कि 2 की शक्ति हो, साथ ही ${\textstyle O(N\log N)}$ स्केलिंग का विश्लेषण भी करता है। राष्ट्रपति केनेडी की विज्ञान सलाहकार समिति की एक बैठक के समय तुकी को यह विचार आया, जहां एक चर्चा विषय में देश को बाहर से घेरने के लिए सेंसर स्थापित करके सोवियत संघ द्वारा परमाणु परीक्षणों का पता लगाना सम्मिलित था। इन सेंसरों के आउटपुट का विश्लेषण करने के लिए, एक एफएफटी एल्गोरिथम की आवश्यकता होगी। तुकी के साथ चर्चा में, रिचर्ड गारविन ने न केवल राष्ट्रीय सुरक्षा समस्याओं के लिए एल्गोरिदम की सामान्य प्रयोज्यता को पहचाना, किंतु 3-डी क्रिस्टल में स्पिन ओरिएंटेशन की आवधिकता निर्धारित करने के लिए तत्काल रुचि सहित समस्याओं की एक विस्तृत श्रृंखला भी पहचानी। हीलियम -3 का गारविन ने तुकी का विचार कूली को दिया (दोनों ने थॉमस जे. वाटसन रिसर्च सेंटर | आईबीएम की वाटसन लैब में काम किया) कार्यान्वयन के लिए। कूली और टुकी ने छह महीने के अपेक्षाकृत कम समय में पेपर प्रकाशित किया। जैसा कि टुकी ने आईबीएम में काम नहीं किया था, विचार की पेटेंट क्षमता पर संदेह किया गया था और एल्गोरिथ्म सार्वजनिक डोमेन में चला गया, जिसने अगले दशक की कंप्यूटिंग क्रांति के माध्यम से एफएफटी को अंकीय संकेत प्रक्रिया में अपरिहार्य एल्गोरिदम में से एक बना दिया।

परिभाषा

होने दे $x_{0}$, …, $x_{N-1}$ जटिल संख्या हो। असतत फूरियर रूपांतरण सूत्र द्वारा परिभाषित किया गया है

$X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-i2\pi kn/N}\qquad k=0,\ldots ,N-1,$

जहां $e^{i2\pi /N}$ 1 का आदिम Nth मूल है।

इस परिभाषा का मूल्यांकन करने के लिए सीधे ${\textstyle O\left(N^{2}\right)}$ संचालन की आवश्यकता होती है: N आउटपुट X_k हैं, और प्रत्येक आउटपुट के लिए N शब्दों के योग की आवश्यकता होती है। ${\textstyle O(N\log N)}$ संचालन में समान परिणामों की गणना करने के लिए एक FFT कोई भी विधि है।संचालन। सभी ज्ञात एफएफटी एल्गोरिदम के ${\textstyle \Theta (N\log N)}$ संचालन की आवश्यकता होती है, चूंकि हालांकि कोई ज्ञात प्रमाण नहीं है कि कम जटिलता असंभव है।।

एफएफटी की बचत को स्पष्ट करने के लिए,${\textstyle N=4096}$ डेटा बिंदुओं के लिए जटिल गुणन और परिवर्धन की गणना पर विचार करें।डीएफटी के योगों का सीधे मूल्यांकन करने में ${\textstyle N^{2}}$ जटिल गुणन और ${\textstyle N(N-1)}$ जटिल जोड़, सम्मिलित होते हैं जिनमें से ${\textstyle O(N)}$ परिचालनों को तुच्छ कार्यों को समाप्त करके बचाया जा सकता है जैसे कि 1 से गुणा करने पर लगभग 30 मिलियन संक्रियाएँ बचती हैं इसके विपरीत, N के लिए मूलांक-2 या कूली-टुके कलन विधि N a 2 की शक्ति केवल ${\textstyle (N/2)\log _{2}(N)}$ जटिल गुणन के साथ समान परिणाम की गणना कर सकता है। (फिर से, 1 और इसी तरह के गुणन के सरलीकरण की अनदेखी) और ${\textstyle N\log _{2}(N)}$ जटिल जोड़, कुल मिलाकर लगभग 30,000 संचालन - प्रत्यक्ष मूल्यांकन की तुलना में एक हजार गुना कम। व्यवहार में, आधुनिक कंप्यूटरों पर वास्तविक प्रदर्शन पर सामान्यतः अंकगणितीय संचालन की गति के अतिरिक्त अन्य कारकों का प्रभुत्व होता है और विश्लेषण एक जटिल विषय है (उदाहरण के लिए, फ्रिगो और स्टीवन जी जॉनसन, 2005 देखें)। किन्तु समग्र सुधार${\textstyle O\left(N^{2}\right)}$से ${\textstyle O(N\log N)}$ तक रहता है।

एल्गोरिदम

कूली-तुकी एल्गोरिथम

Main article: कूली-टकी एफएफटी एल्गोरिथम

अब तक सबसे अधिक उपयोग किया जाने वाला एफएफटी कूली-टुके एल्गोरिथम है। यह एक विभाजन और जीत एल्गोरिथ्म है जो पुनरावर्तन किसी भी समग्र संख्या आकार ${\textstyle N=N_{1}N_{2}}$ के ${\textstyle N_{1}}$और ${\textstyle N_{2}}$ आकारों के कई छोटे डीएफटी में पुनरावर्ती रूप से तोड़ता है एकता के जटिल मूलों द्वारा $O(N)$ गुणन के साथ पारंपरिक रूप से ट्वीडल कारक (सज्जन और सैंडे 1966 के बाद) कहलाते हैं।

इस पद्धति (और एक एफएफटी के सामान्य विचार) को 1965 में कूली और तुकी के एक प्रकाशन द्वारा लोकप्रिय बनाया गया था, किन्तु बाद में इसका पता चला कि उन दो लेखकों ने स्वतंत्र रूप से 1805 के आसपास कार्ल फ्रेडरिक गॉस को ज्ञात एल्गोरिथम का पुन: आविष्कार किया था (और बाद में सीमित रूपों में कई बार पुनः खोजा गया)।

कूली-टुकी एल्गोरिदम का सबसे अच्छा ज्ञात उपयोग प्रत्येक चरण में आकार N/2 के दो टुकड़ों में परिवर्तन को विभाजित करना है, और इसलिए दो आकारों की शक्ति तक सीमित है, किन्तु सामान्य रूप से किसी भी कारक का उपयोग किया जा सकता है (जैसा था) गॉस और कूली/टकी दोनों के लिए जाना जाता है). इन्हें क्रमशः मूलांक -2 और मिश्रित-मूलांक केस कहा जाता है (और अन्य वेरिएंट जैसे स्प्लिट-मूलांक एफएफटी के अपने नाम भी हैं)। चूंकि मूल विचार पुनरावर्ती है, अधिकांश पारंपरिक कार्यान्वयन स्पष्ट पुनरावर्तन से बचने के लिए एल्गोरिथम को पुनर्व्यवस्थित करते हैं। इसके अतिरिक्त , क्योंकि Cooley-तुकी एल्गोरिथ्म डीएफटी को छोटे डीएफटीs में तोड़ता है, इसे डीएफटी के लिए किसी भी अन्य एल्गोरिथ्म के साथ इच्छानुसार से जोड़ा जा सकता है, जैसे कि नीचे वर्णित है।

अन्य एफएफटी एल्गोरिदम

Main articles: प्राइम-फैक्टर एफएफटी एल्गोरिथम, ब्रून का एफएफटी एल्गोरिदम, राडार का एफएफटी एल्गोरिदम, चिरप जेड-रूपांतरण, and हेक्सागोनल फास्ट फूरियर रूपांतरण

कूली-टुके के अतिरिक्त अन्य एफएफटी एल्गोरिदम हैं।

सह अभाज्य N₁ और N₂के साथ N = N₁N₂ के लिए कोई भी प्राइम-फैक्टर एफएफटी एल्गोरिथम | प्राइम-फैक्टर (गुड-थॉमस) एल्गोरिथम (पीएफए) का उपयोग कर सकता है, डी एफटी को कूली-टुके के समान लेकिन ट्वीडल कारकों के बिना फैक्टर करने के लिए।। रेडर-ब्रेनर एल्गोरिथम (1976) एक कूली-टुके जैसा गुणनखंडन है, किन्तु विशुद्ध रूप से काल्पनिक ट्वीडल कारकों के साथ, बढ़े हुए परिवर्धन और कम संख्यात्मक स्थिरता की कीमत पर गुणन को कम करता है; इसे बाद में कूली-टुकी के विभाजन-मूलांक संस्करण (जो समान प्राप्त करता है) द्वारा हटा दिया गया था (जो समान गुणन गणना प्राप्त करता है किन्तु कम परिवर्धन के साथ और स्पष्ट ता का त्याग किए बिना)। एल्गोरिथम जो डीएफटी के अतिरिक्त अन्य छोटे कार्यों में डीएफटी को पुनरावर्ती रूप से कारक बनाते हैं, उनमें ब्रून और त्वरित फूरियर रूपांतरण एल्गोरिथम एल्गोरिदम सम्मिलित हैं। (द रेडर-ब्रेनर और क्यूएफटी एल्गोरिदम को दो आकारों की शक्ति के लिए प्रस्तावित किया गया था, किन्तु यह संभव है कि उन्हें सामान्य मिश्रित N के लिए अनुकूलित किया जा सकता है। एफएफटी को बहुपद के पुनरावर्ती गुणनखंडन के रूप में व्याख्या करना z^N − 1, यहाँ z के रूप के वास्तविक-गुणांक बहुपदों z^M − 1 and z^2M + az^M + 1आधारित है

विनोग्रैड एफएफटी एल्गोरिथम द्वारा एक अन्य बहुपद दृष्टिकोण का उपयोग किया जाता है, जो साइक्लोटोमिक बहुपदों में z^N − 1 को कारक बनाता है-इनमें अधिकांशतः 1, 0, या −1 के गुणांक होते हैं, और इसलिए कुछ (यदि कोई हो) गुणन की आवश्यकता होती है, इसलिए विनोग्रैड का उपयोग न्यूनतम-गुणन एफएफटीएस प्राप्त करने के लिए किया जा सकता है और अधिकांशतः इसका उपयोग किया जाता है छोटे कारकों के लिए कुशल एल्गोरिदम खोजें। दरअसल, विनोग्रैड ने दिखाया कि डीएफटी की गणना केवल O(N) अपरिमेय गुणन के साथ की जा सकती है, जिससे दो आकारों की शक्ति के लिए गुणन की संख्या पर एक सिद्ध प्राप्त करने योग्य निचली सीमा होती है; दुर्भाग्य से, यह कई और परिवर्धन की कीमत पर आता है,अस्थायी बिंदु इकाई के साथ आधुनिक सेंट्रल प्रोसेसिंग इकाई पर एक ट्रेडऑफ़ अब अनुकूल नहीं है। विशेष रूप से, विनोग्रैड पीएफए ​​के साथ-साथ प्राइम साइज के एफएफटी के लिए राडार द्वारा एल्गोरिदम का भी उपयोग करता है।

गुणक समूह मोडुलो प्राइम N के लिए एक जनरेटर के अस्तित्व का शोषण करने वाले राडार का एल्गोरिदम प्राइम आकार N के एक डीएफटी को (मिश्रित) आकार N -1 के चक्रीय दृढ़ संकल्प के रूप में व्यक्त करता है जिसे बाद में कनवल्शन प्रमेय के माध्यम से सामान्य एफएफटी की एक जोड़ी द्वारा गणना की जा सकती है(चूंकि विनोग्रैड अन्य कनवल्शन विधियों का उपयोग करता है)। एक अन्य मुख्य आकार एफएफटी एल. आई. ब्लूस्टीन के कारण है, और कभी-कभी इसे चिरप-जेड एल्गोरिदम कहा जाता है; यह एक डीएफटी को कनवल्शन के रूप में फिर से व्यक्त करता है, किन्तु इस बार एक ही आकार का (जो दो की शक्ति के लिए शून्य-गद्देदार हो सकता है और मूलांक -2 कूली-तुकी एफएफटी द्वारा मूल्यांकन किया जा सकता है, उदाहरण के लिए), पहचान के माध्यम से

$nk=-{\frac {(k-n)^{2}}{2}}+{\frac {n^{2}}{2}}+{\frac {k^{2}}{2}}.$

हेक्सागोनल फास्ट फूरियर रूपांतरण (एचएफएफटी) का उद्देश्य हेक्सागोनल ग्रिड के लिए एक नई एड्रेसिंग योजना का उपयोग करके हेक्सागोनल-नमूना डेटा के लिए एक कुशल एफएफटी की गणना करना है, जिसे ऐरे समूह एड्रेसिंग (एएसए) कहा जाता है।

एफएफटी एल्गोरिदम वास्तविक या सममित डेटा के लिए विशिष्ट है

कई अनुप्रयोगों में, डीएफटी के लिए निवेश डेटा विशुद्ध रूप से वास्तविक होते हैं, इस स्थितियों में आउटपुट समरूपता को संतुष्ट करते हैं

$X_{N-k}=X_{k}^{*}$

और कुशल एफएफटी एल्गोरिदम इस स्थिति के लिए डिजाइन किए गए हैं (उदाहरण के लिए सोरेनसेन, 1987 देखें)। एक दृष्टिकोण में एक सामान्य एल्गोरिथ्म (जैसे कूली-टुके) लेना और गणना के अनावश्यक भागों को हटाने से समय और स्मृति में लगभग दो का कारक बचत होता है। वैकल्पिक रूप से, एक सम-लंबाई वाले वास्तविक-निवेश डीएफटी को आधी लंबाई के एक जटिल डीएफटी के रूप में व्यक्त करना संभव है (जिसके वास्तविक और काल्पनिक भाग मूल वास्तविक डेटा के सम/विषम तत्व हैं), जिसके बाद O(N) प्रसंस्करण के बाद के संचालन होते हैं।

एक बार यह माना जाता था कि असतत हार्टले परिवर्तन (डीएचटी ) के माध्यम से वास्तविक-इनपुट डीएफटीs की अधिक कुशलता से गणना की जा सकती है, किन्तु बाद में यह तर्क दिया गया कि एक विशेष वास्तविक-इनपुट डीएफटी एल्गोरिथम (एफएफटी) सामान्यतः पाया जा सकता है जिसके लिए कम संचालन की आवश्यकता होती है समान संख्या में इनपुट के लिए संबंधित डीएचटी एल्गोरिथम (एफएचटी )। ब्रून का एल्गोरिथम (ऊपर) एक और विधि है जिसे प्रारंभ में वास्तविक इनपुट का लाभ उठाने के लिए प्रस्तावित किया गया था, किन्तु यह लोकप्रिय सिद्ध नहीं हुआ है।

वास्तविक डेटा के स्थितियों के लिए और भी एफएफटी विशेषज्ञताएं हैं जिनमें सम और विषम कार्य हैं। | साइन रूपांतरण (एस) (असतत कोसाइन ट्रांसफॉर्म/असतत साइन ट्रांसफॉर्म)। इन स्थितियों के लिए एफएफटी एल्गोरिदम को सीधे संशोधित करने के अतिरिक्त , डीसीटी/डीएसटी को O(N) पूर्व और बाद के प्रसंस्करण के साथ संयुक्त वास्तविक डेटा के एफएफटी के माध्यम से भी गणना की जा सकती है।

कम्प्यूटेशनल उद्देश्य

जटिलता और संचालन की सीमा

Unsolved problem in कंप्यूटर विज्ञान:

फास्ट फूरियर ट्रांसफॉर्म एल्गोरिदम की जटिलता पर निचली सीमा क्या है? क्या वे इससे तेज हो सकते हैं$O(N\log N)$?

(more unsolved problems in कंप्यूटर विज्ञान)

लंबे समय से चली आ रही सैद्धांतिक रुचि का एक मूलभूत प्रश्न कम्प्यूटेशनल जटिलता सिद्धांत और तेजी से फूरियर रूपांतरणों की स्पष्ट संचालन गणनाओं पर निचली सीमा को सिद्ध करना है, और कई खुली समस्याएं बनी हुई हैं। यह दृढ़ता से सिद्ध नहीं हुआ है कि क्या डीएफटी को वास्तव में दो आकारों की शक्ति के साधारण स्थितियों के लिए भी ${\textstyle \Omega (N\log N)}$ (अर्थात , आदेश$N\log N$या अधिक) संचालन की आवश्यकता होती है, चूंकि कम जटिलता वाले एल्गोरिदम ज्ञात नहीं हैं। विशेष रूप से, अंकगणितीय संक्रियाओं की गणना सामान्यतः ऐसे प्रश्नों का फोकस होती है, चूंकि आधुनिक समय के कंप्यूटरों पर वास्तविक प्रदर्शन कैश (कंप्यूटिंग) या पाइपलाइन (कंप्यूटिंग) अनुकूलन जैसे कई अन्य कारकों द्वारा निर्धारित किया जाता है।

शमूएल विनोग्राद (1978) द्वारा निम्नलिखित कार्य,एक तंग Θ(N) निचली सीमा को एफएफटी द्वारा आवश्यक वास्तविक गुणन की संख्या के लिए जाना जाता है। इसे ही दिखाया जा सकता है ${\textstyle 4N-2\log _{2}^{2}(N)-2\log _{2}(N)-4}$ दो लंबाई की शक्ति के डीएफटी की गणना करने के लिए तर्कहीन वास्तविक गुणन की आवश्यकता होती है $N=2^{m}$. इसके अतिरिक्त , इस गणना को प्राप्त करने वाले स्पष्ट एल्गोरिदम ज्ञात हैं (हेइडमैन और चार्ल्स सिडनी बुरस, 1986;डुहामेल, 1990). चूंकि , इन एल्गोरिदम को व्यावहारिक होने के लिए बहुत अधिक परिवर्धन की आवश्यकता होती है, कम से कम आधुनिक कंप्यूटरों पर हार्डवेयर मल्टीप्लायरों के साथ (डुहामेल, 1990;फ्रिगो और स्टीवन जी जॉनसन, 2005)।

आवश्यक परिवर्धन की संख्या पर एक तंग निचली सीमा ज्ञात नहीं है चूंकि एल्गोरिदम पर कुछ प्रतिबंधात्मक धारणाओं के अनुसार निचली सीमाएं सिद्ध हुई हैं। 1973 में, मॉर्गनस्टर्न ने एल्गोरिदम के लिए अतिरिक्त गिनती पर एक $\Omega (N\log N)$ निचली सीमा साबित की, जहां गुणक स्थिरांक ने परिमाण को सीमित कर दिया है (जो अधिकांश के लिए सही है, किन्तु सभी एफएफटी एल्गोरिदम के लिए नहीं)। विक्टर पैन (1986) एक सिद्ध हुआ एफएफटी एल्गोरिथम की अतुल्यकालिकता के माप $\Omega (N\log N)$पर एक सीमा मानते हुए निचली सीमा, किन्तु इस धारणा की व्यापकता स्पष्ट नहीं है। दो N की शक्ति के स्थितियों में, क्रिस्टोस पापादिमित्रिउ (1979) तर्क दिया कि संख्या ${\textstyle N\log _{2}N}$ कूली-टुकी एल्गोरिदम द्वारा प्राप्त जटिल-संख्या परिवर्धन एल्गोरिथम के ग्राफ (असतत गणित) पर कुछ मान्यताओं के अनुसार इष्टतम है (अन्य बातों के अतिरिक्त , उनकी धारणाएं, कि एकता की जड़ों में कोई योगात्मक पहचान का शोषण नहीं किया जाता है)। (इस तर्क का अर्थ यह होगा कि कम से कम ${\textstyle 2N\log _{2}N}$ वास्तविक जोड़ आवश्यक हैं, चूंकि यह एक तंग सीमा नहीं है क्योंकि जटिल-संख्या गुणन के भाग के रूप में अतिरिक्त जोड़ आवश्यक हैं।) इस प्रकार अब तक, किसी भी प्रकाशित एफएफटी एल्गोरिदम ने इससे कम प्राप्त नहीं किया है ${\textstyle N\log _{2}N}$ दो N की शक्ति के लिए सम्मिश्र-संख्या जोड़ (या उनके समतुल्य) से कम हासिल किया है।

एक तीसरी समस्या वास्तविक गुणन और परिवर्धन की कुल संख्या को कम करना है, जिसे कभी-कभी अंकगणितीय जटिलता कहा जाता है (चूंकि इस संदर्भ में यह स्पष्ट गणना है और स्पर्शोन्मुख जटिलता नहीं है जिसे माना जा रहा है)। फिर से, कोई तंग निचली सीमा सिद्ध नहीं हुई है। चूंकि , 1968 के बाद से, स्प्लिट-मूलांक एफएफटी एल्गोरिथम द्वारा दो N की शक्ति के लिए सबसे कम प्रकाशित गिनती लंबे समय तक प्राप्त की गई थी, जिसके लिए आवश्यक है ${\textstyle 4N\log _{2}(N)-6N+8}$ N > 1 के लिए वास्तविक गुणन और परिवर्धन। इसे हाल ही में घटाकर ${\textstyle \sim {\frac {34}{9}}N\log _{2}N}$ (जॉनसन और फ्रिगो, 2007;लुंडी और वैन बुस्कर्क, 2007). थोड़ी बड़ी गिनती (किन्तु फिर भी N ≥ 256 के लिए स्प्लिट मूलांक से बढ़िया ) संभावित एल्गोरिदम पर अतिरिक्त प्रतिबंधों के अनुसार N ≤ 512 के लिए उपयुक्त रूप से इष्टतम दिखाया गया था (यूनिट-मॉड्यूलस गुणक कारकों के साथ स्प्लिट-मूलांक -जैसे फ्लोग्राफ), कमी से थकावट से प्रमाण द्वारा हल करने योग्य एक संतुष्टि मॉडुलो सिद्धांतों की समस्या (हेनल और हेनल, 2011)।

एफएफटी एल्गोरिदम की जटिलता को कम करने या सिद्ध करने के अधिकांश प्रयासों ने साधारण जटिल-डेटा केस पर ध्यान केंद्रित किया है, क्योंकि यह सबसे सरल है। चूंकि , जटिल-डेटा एफएफटी वास्तविक-डेटा एफएफटी, असतत कोज्या रूपांतरण, असतत हार्टले रूपांतरण, और इसी तरह से संबंधित समस्याओं के लिए एल्गोरिदम से इतने निकट से संबंधित हैं, कि इनमें से किसी एक में सुधार से दूसरों में तुरंत सुधार होगा ( डुहामेल और वेटरली, 1990)।

सन्निकटन

ऊपर चर्चा किए गए सभी एफएफटी एल्गोरिदम डीएफटी की स्पष्ट गणना करते हैं (अर्थात अस्थायी बिंदु त्रुटियों की उपेक्षा)। चूंकि , कुछ एफएफटी एल्गोरिदम प्रस्तावित किए गए हैं, जो डीएफटी की लगभग गणना करते हैं, एक त्रुटि के साथ जिसे बढ़ी हुई संगणनाओं की कीमत पर इच्छानुसार से छोटा किया जा सकता है। ऐसे एल्गोरिदम बढ़ी हुई गति या अन्य गुणों के लिए सन्निकटन त्रुटि का व्यापार करते हैं। उदाहरण के लिए, एडेलमैन एट अल द्वारा अनुमानित एफएफटी एल्गोरिदम। (1999) तेजी से बहुस्तम्भ विधि की सहायता से समांतर कंप्यूटिंग के लिए कम संचार आवश्यकताओं को प्राप्त करता है। गुओ और बुरुस द्वारा एक छोटा लहर -आधारित अनुमानित एफएफटी (1996) स्पष्ट एफएफटी की तुलना में विरल इनपुट/आउटपुट (समय/आवृत्ति स्थानीयकरण) को अधिक कुशलता से ध्यान में रखता है। डीएफटी आउटपुट के एक उपसमुच्चय की अनुमानित गणना के लिए एक अन्य एल्गोरिथ्म शेंटोव एट अल के कारण है। (1995)। एडेलमैन एल्गोरिथ्म विरल और गैर-विरल डेटा के लिए समान रूप से अच्छी तरह से काम करता है, क्योंकि यह डेटा की संपीड्यता (विरलता) के अतिरिक्त फूरियर आव्यूह की संपीडनशीलता (रैंक की कमी) पर आधारित है। इसके विपरीत, यदि डेटा विरल हैं - अर्थात, यदि N फूरियर गुणांकों में से केवल K अशून्य हैं - तो जटिलता को O(K log(N) log(N/K)) तक कम किया जा सकता है और इसे व्यावहारिक बनाने के लिए प्रदर्शित किया गया है बड़े-N उदाहरण (N = 2²²) में N/K > 32के लिए एक सामान्य एफएफटी की तुलना में स्पीडअप एक संभावित अनुमानित एल्गोरिदम (जो कई दशमलव स्थानों पर सबसे बड़े के गुणांक का अनुमान लगाता है) का उपयोग करता है।)।

स्पष्टता

परिमित-स्पष्ट अस्थायी बिंदु अंकगणित का उपयोग करते समय एफएफटी एल्गोरिदम में त्रुटियाँ होती हैं, किन्तु ये त्रुटियाँ सामान्यतः अधिक छोटी होती हैं; अधिकांश एफएफटी एल्गोरिदम, उदा। कूली-टुके, एल्गोरिदम की जोड़ीदार योग संरचना के परिणामस्वरूप उत्कृष्ट संख्यात्मक गुण हैं। कूली-टुके एल्गोरिथम के लिए सन्निकटन त्रुटि पर ऊपरी सीमा है ${\textstyle O(\epsilon \log N)}$, की तुलना में ${\textstyle O(\epsilon N^{3/2})}$ भोले डीएफटी सूत्र के लिए, जहां ε मशीनअस्थायी बिंदु सापेक्ष परिशुद्धता है। वास्तव में, मूल माध्य वर्ग (आरएमएस) त्रुटियाँ इन ऊपरी सीमाओं की तुलना में बहुत उत्तम हैं, केवल होने के नाते ${\textstyle O(\epsilon {\sqrt {\log N}})}$ कूली-टुके और के लिए ${\textstyle O(\epsilon {\sqrt {N}})}$ भोले डीएफटी के लिए (शत्ज़मैन, 1996)। ये परिणाम चूंकि , एफएफटी (अर्थात त्रिकोणमितीय फ़ंक्शन मान) में उपयोग किए जाने वाले ट्वीडल कारकों की स्पष्ट ता के प्रति बहुत संवेदनशील हैं, और असावधान एफएफटी कार्यान्वयन के लिए बहुत अधिक स्पष्ट ता होना असामान्य नहीं है, उदा। यदि वे त्रिकोणमितीय तालिकाओं के सूत्रों को बनाने में गलत का उपयोग करते हैं। कूली-टुकी के अतिरिक्त कुछ एफएफटी, जैसे कि रेडर-ब्रेनर एल्गोरिथम, आंतरिक रूप से कम स्थिर हैं।

स्थिर केंद्र अंकगणित में, एफएफटी एल्गोरिदम द्वारा संचित परिमित-परिशुद्धता त्रुटियां बदतर हैं, , कूली-टुकी एल्गोरिदम (वेल्च, 1969) के लिए आरएमएस त्रुटियां${\textstyle O({\sqrt {N}})}$ के रूप में बढ़ रही हैं।। इस स्पष्टता को प्राप्त करने के लिए स्पष्ट ता के हानि को कम करने के लिए स्केलिंग पर सावधानीपूर्वक ध्यान देने की आवश्यकता होती है, और स्थिर केंद्र एफएफटी एल्गोरिदम में कूली-टुकी जैसे अपघटन के प्रत्येक मध्यवर्ती चरण में पुनर्विक्रय सम्मिलित होता है।

एफएफटी कार्यान्वयन की शुद्धता को सत्यापित करने के लिए, ${\textstyle O(N\log N)}$ समय में एक सरल प्रक्रिया द्वारा रैखिकता आवेग-प्रतिक्रिया, और यादृच्छिक आदानों पर परिवर्तन के समय-शिफ्ट गुणों की जांच करके कठोर आश्वासन प्राप्त की जा सकती है (एर्गन) , 1995)।

बहुआयामी एफएफटी

जैसा कि असतत फूरियर रूपांतरण या बहुआयामी डीएफटी आलेख में परिभाषित किया गया है, बहुआयामी डीएफटी

$X_{\mathbf {k} }=\sum _{\mathbf {n} =0}^{\mathbf {N} -1}e^{-2\pi i\mathbf {k} \cdot (\mathbf {n} /\mathbf {N} )}x_{\mathbf {n} }$

एक सरणी x_n को बदल देता है सूचकांकों के डी-डायमेंशनल समन्वय वेक्टर के साथ ${\textstyle \mathbf {n} =\left(n_{1},\ldots ,n_{d}\right)}$ d नेस्टेड योगों के एक समूह द्वारा (over ${\textstyle n_{j}=0\ldots N_{j}-1}$ प्रत्येक जे के लिए), जहां डिवीजन n/N, के रूप में परिभाषित किया गया है ${\textstyle \mathbf {n} /\mathbf {N} =\left(n_{1}/N_{1},\ldots ,n_{d}/N_{d}\right)}$, तत्व-वार किया जाता है। समतुल्य रूप से, यह एक-आयामी डीएफटी के डी समूह के अनुक्रम की संरचना है, जो (किसी भी क्रम में) एक समय में एक आयाम के साथ किया जाता है ।

यह रचनात्मक दृष्टिकोण तुरंत सबसे सरल और सबसे सामान्य बहुआयामी डीएफटी एल्गोरिदम प्रदान करता है, जिसे 'पंक्ति-स्तंभ' एल्गोरिदम (नीचे द्वि-आयामी स्थितियों के बाद) के रूप में जाना जाता है। यही है, कोई केवल d एक-आयामी एफएफटीएस (उपरोक्त एल्गोरिदम में से किसी के द्वारा) का अनुक्रम करता है: पहले आप n₁ के साथ बदलते हैं₁ आयाम, फिर n₂के साथ₂ आयाम, और इसी तरह (या वास्तव में, कोई ऑर्डरिंग काम करता है)। इस विधि को सामान्य${\textstyle O(N\log N)}$ जटिलता के रूप में दिखाया गया है, जहाँ ${\textstyle N=N_{1}\cdot N_{2}\cdot \cdots \cdot N_{d}}$ है रूपांतरित डेटा बिंदुओं की कुल संख्या है। विशेष रूप से आकार N₁ वगैरह के N/N₁रूपांतरण हैं, इसलिए एफएफटीएस के अनुक्रम की जटिलता है:

${\begin{aligned}&{\frac {N}{N_{1}}}O(N_{1}\log N_{1})+\cdots +{\frac {N}{N_{d}}}O(N_{d}\log N_{d})\\[6pt]={}&O\left(N\left[\log N_{1}+\cdots +\log N_{d}\right]\right)=O(N\log N).\end{aligned}}$

दो आयामों में, x_k को एक $n_{1}\times n_{2}$ आव्यूह (गणित),रूप में देखा जा सकता है और यह एल्गोरिथम पहले सभी पंक्तियों (प्रतिक्रिया कॉलम) के एफएफटी का प्रदर्शन करने के अनुरूप होता है, परिणामी रूपांतरित पंक्तियों (प्रतिक्रिया कॉलम) को एक दूसरे के रूप में समूहीकृत करता है। एक साथ एक और $n_{1}\times n_{2}$ आव्यूह , और फिर इस दूसरे आव्यूह के प्रत्येक स्तम्भ (प्रतिक्रिया पंक्तियों) पर एफएफटी का प्रदर्शन करना, और इसी तरह परिणामों को अंतिम परिणाम आव्यूह में समूहीकृत करना।

दो से अधिक आयामों में, यह अधिकांशतः कैश (कंप्यूटिंग) इलाके के लिए आयामों को पुनरावर्ती रूप से समूहित करने के लिए फायदेमंद होता है। उदाहरण के लिए, एक त्रि-आयामी एफएफटी पहले प्रत्येक निश्चित n₁ के लिए प्रत्येक प्लानर स्लाइस के द्वि-आयामी एफएफटी का प्रदर्शन कर सकता है, और फिर n₁के साथ एक आयामी एफएफटीएस का प्रदर्शन कर सकता है। अधिक सामान्यतः , एक विषम रूप से इष्टतम कैश-बेपरवाह एल्गोरिथ्म में आयामों को दो समूहों में पुनरावर्ती रूप से विभाजित किया जाता है ${\textstyle (n_{1},\ldots ,n_{d/2})}$ और ${\textstyle (n_{d/2+1},\ldots ,n_{d})}$ जो पुनरावर्ती रूप से रूपांतरित होते हैं (यदि d सम नहीं है तो गोल करना) (फ्रिगो और जॉनसन, 2005 देखें)। फिर भी, यह पंक्ति-स्तंभ एल्गोरिथम का एक सीधा रूपांतर बना हुआ है, जिसके लिए अंततः बेस केस के रूप में केवल एक-आयामी एफएफटी एल्गोरिथम की आवश्यकता होती है, और अभी भी O(N log N) जटिलता है। फिर भी एक और भिन्नता बाद के आयामों को बदलने के बीच में आव्यूह खिसकाना करना है, जिससे परिवर्तन सन्निहित डेटा पर काम करें; यह बाहर के कोर और वितरित मेमोरी स्थितियों के लिए विशेष रूप से महत्वपूर्ण है जहां गैर-सन्निहित डेटा तक पहुँचने में अत्यधिक समय लगता है।

अन्य बहुआयामी एफएफटी एल्गोरिदम हैं जो पंक्ति-स्तंभ एल्गोरिदम से अलग हैं, चूंकि उनमें से सभी हैं ${\textstyle O(N\log N)}$ जटिलता। संभवतः सबसे सरल गैर-पंक्ति-स्तंभ एफएफटी वेक्टर-मूलांक एफएफटी एल्गोरिदम है, जो साधारण कूली-तुकी एल्गोरिदम का सामान्यीकरण है जहां एक वेक्टर द्वारा परिवर्तन आयामों को विभाजित करता है। ${\textstyle \mathbf {r} =\left(r_{1},r_{2},\ldots ,r_{d}\right)}$ प्रत्येक चरण पर मूलांक का। (इसमें कैश लाभ भी हो सकते हैं।) वेक्टर-मूलांक का सबसे सरल स्थिति वह है जहां सभी मूलांक समान होते हैं (उदाहरण के लिए वेक्टर-मूलांक-2 सभी आयामों को दो से विभाजित करता है), किन्तु यह आवश्यक नहीं है। वेक्टर मूलांक एक समय में केवल एक गैर-इकाई मूलांक के साथ, अर्थात ${\textstyle \mathbf {r} =\left(1,\ldots ,1,r,1,\ldots ,1\right)}$अनिवार्य रूप से एक पंक्ति-स्तंभ एल्गोरिथम है। अन्य, अधिक जटिल, विधियों में सम्मिलित हैं नुस्बाउमर (1977) के कारण बहुपद परिवर्तन एल्गोरिथम, जो संकल्पों और बहुपद उत्पादों के संदर्भ में परिवर्तन को देखते हैं।अधिक जानकारी और संदर्भों के लिए डुहामेल और वेटरली (1990) देखें।

अन्य सामान्यीकरण

एक ${\textstyle O(N^{5/2}\log N)}$ N² नोड्स के साथ स्फेयर S² पर गोलाकार हार्मोनिक्स के लिए सामान्यीकरण का वर्णन मोहलेनकैंप द्वारा किया गया था, एक एल्गोरिथम के साथ अनुमान लगाया गया (किन्तु सिद्ध नहीं हुआ)। ${\textstyle O(N^{2}\log ^{2}(N))}$ जटिलता; मोहलेनकैंप भी लिब एफटीएसएच लाइब्रेरी में कार्यान्वयन प्रदान करता है। ${\textstyle O(N^{2}\log N)}$ एक गोलाकार-हार्मोनिक एल्गोरिथम जटिलता का वर्णन रोखलिन और टायगर्ट द्वारा वर्णित किया गया है।

तेजी से मुड़ा हुआ एल्गोरिदम एफएफटी के अनुरूप है, सिवाय इसके कि यह वास्तविक या जटिल स्केलर मानों की श्रृंखला के अतिरिक्त बिन्ड वेवफॉर्म की श्रृंखला पर चल रहा है। घुमाव (जो एफएफटी में एक जटिल फेजर द्वारा गुणा है) घटक तरंग का एक गोलाकार बदलाव है।

पॉट्स एट अल में समीक्षा के अनुसार, विभिन्न समूहों ने गैर-सुसज्जित डेटा के लिए एफएफटी एल्गोरिदम भी प्रकाशित किए हैं। (2001)। इस तरह के एल्गोरिदम सख्ती से डीएफटी की गणना नहीं करते हैं (जो केवल समस्थानिक डेटा के लिए परिभाषित है), किंतु इसके कुछ सन्निकटन (एक गैर-समान असतत फूरियर रूपांतरण, या एनडीएफटी, जो स्वयं अधिकांशतः केवल लगभग गणना की जाती है)। अधिक सामान्यतः वर्णक्रमीय आकलन के कई अन्य विधि हैं।

अनुप्रयोग

एफएफटी का उपयोग डिजिटल रिकॉर्डिंग, नमूनाकरण, योजक संश्लेषण और पिच सुधार सॉफ्टवेयर में किया जाता है।

एफएफटी का महत्व इस तथ्य से निकला है कि इसने आवृत्ति डोमेन में काम करना कम्प्यूटेशनल रूप से उतना ही संभव बना दिया है जितना कि अस्थायी या स्थानिक डोमेन में काम करना है। एफएफटी के कुछ महत्वपूर्ण अनुप्रयोगों में सम्मिलित हैं:

• तेज बड़े-पूर्णांक गुणन एल्गोरिदम और बहुपद गुणन,
• टोप्लेट्ज़ आव्यूह , परिचालित आव्यूह और अन्य संरचित आव्यूह के लिए कुशल आव्यूह -वेक्टर गुणन,
• छनन एल्गोरिदम (ओवरलैप-एड विधि देखें। ओवरलैप-एड और ओवरलैप-सेव मेथड। ओवरलैप-सेव मेथड्स),
• असतत कोसाइन परिवर्तन या असतत साइन परिवर्तन के लिए तेज़ एल्गोरिदम (उदाहरण के लिए जेपीईजी और बिका हुआईजी / एमपी 3 एन्कोडिंग और डिकोडिंग के लिए उपयोग किए जाने वाले डिस्क्रीट कोसाइन परिवर्तन ),
• तेज चेबीशेव सन्निकटन,
• पुनरावृत्ति संबंध को हल करना,
• मास स्पेक्ट्रोमेट्री की गणना।* 5जी, एलटीई, वाई-फाई, डीएसएल और अन्य आधुनिक संचार प्रणालियों के लिए ऑर्थोगोनल फ्रीक्वेंसी डिवीजन मल्टीप्लेक्सिंग (ओएफडीएम) का उपयोग करके जटिल डेटा प्रतीकों का मॉड्यूलेशन और डिमॉड्यूलेशन।

अनुसंधान क्षेत्र

बड़े एफएफटीएस

खगोल विज्ञान जैसे क्षेत्रों में बड़े डेटा के विस्फोट के साथ, कुछ व्यतिकरणमिति गणनाओं के लिए 512K एफएफटीएस की आवश्यकता उत्पन्न हुई है। विल्किंसन माइक्रोवेव अनिसोट्रॉपी जांच और एलआईजीओ जैसी परियोजनाओं द्वारा एकत्र किए गए डेटा को अरबों अंकों के एफएफटी की आवश्यकता होती है। चूंकि यह आकार मुख्य मेमोरी में फिट नहीं होता है, तथाकथित मूल से बाहर एफएफटी अनुसंधान का एक सक्रिय क्षेत्र है।;:

अनुमानित एफएफटी:

एमआरआई जैसे अनुप्रयोगों के लिए, गैर-समान दूरी वाले ग्रिड बिंदुओं और/या आवृत्तियों के लिए डीएफटी की गणना करना आवश्यक है। बहुस्तम्भ आधारित दृष्टिकोण कार्यावधि वृद्धि के कारक के साथ अनुमानित मात्रा की गणना कर सकते हैं।;

समूह एफएफटी

आगे सामान्यीकरण की अनुमति देने वाले समूह प्रतिनिधित्व का उपयोग करके एफएफटी को भी समझाया और व्याख्या किया जा सकता है। गैर-चक्रीय समेत किसी भी कॉम्पैक्ट समूह पर एक कार्य , अलघुकरणीय आव्यूह तत्वों के आधार पर विस्तार होता है। आधार के इस परिवर्तन को करने के लिए कुशल एल्गोरिथम खोजने के लिए यह अनुसंधान का सक्रिय क्षेत्र बना हुआ है। कुशल गोलाकार हार्मोनिक्स विस्तार सहित अनुप्रयोग, कुछ मार्कोव प्रक्रियाओं का विश्लेषण, रोबोटिक्स इत्यादि।;

क्वांटम एफएफटी

क्वांटम कंप्यूटर पर पूर्णांक गुणनखंडन के लिए ध्वनि के तेज एल्गोरिथ्म में बाइनरी वेक्टर के डीएफटी की गणना करने के लिए एक उप-दैनिकि है। इसे 1- या 2-बिट क्वांटम गेट्स के अनुक्रम के रूप में कार्यान्वित किया जाता है, जिसे अब क्वांटम एफएफटी के रूप में जाना जाता है, जो प्रभावी रूप से कूली-तुके एफएफटी को फूरियर आव्यूह के एक विशेष कारक के रूप में अनुभूत किया गया है। वर्तमान में इन विचारों के विस्तार का पता लगाया जा रहा है।

भाषा संदर्भ

भाषा	कमान / विधि	आवश्यक शर्तें
आर	आँकड़े::एफएफटी(एक्स)	कोई नहीं
साइलैब	एफएफटी(एक्स)	कोई नहीं
ऑक्टेव/मैटलैब	एफएफटी(एक्स)	कोई नहीं
पायथन	एफएफटी.एफएफटी(एक्स)	नम्पी सीपी
गणितज्ञ	फूरियर [एक्स]	कोई नहीं
फोरट्रान	एफएफटीडब्ल्यू_ वन (योजना, अंदर, बाहर)	एफएफटीडब्ल्यू
जूलिया	एफएफटी(ए [,डिम्स])	एफएफटीडब्ल्यू
रस्ट	एफएफटी.प्रोसेस (&म्यूट एक्स;	रस्ट एफएफटी
हास्केल	डीएफटी एक्स	एफएफटी

यह भी देखें

एफएफटी से संबंधित एल्गोरिदम:

• बिट-व्युत्क्रम क्रमचय

• गोएर्टज़ेल एल्गोरिथम - असतत फूरियर रूपांतरण की अलग-अलग शर्तों की गणना करता है

एफएफटी कार्यान्वयन:

• अल्गलिब - वास्तविक/जटिल एफएफटी कार्यान्वयन के साथ एक दोहरी/जीपीएल-लाइसेंसीकृत सी++ और सी या लाइब्रेरी (अन्य भाषाओं का भी समर्थन करती है)
• एफएफटीपैक- एक और फोरट्रान एफएफटी लाइब्रेरी (सार्वजनिक डोमेन)
• वास्तुकला-विशिष्ट:
  • शाखा प्रदर्शन पुस्तकालय
  • इंटेल एकीकृत प्रदर्शन आदिम
  • इंटेल गणित कर्नेल पुस्तकालय
• कई और कार्यान्वयन उपलब्ध हैं, सीपीयू और जीपीयू के लिए, जैसे सी++ के लिए पॉकेटएफएफटी

अन्य लिंक:

• ओडिल्ज़को-शॉनहेज एल्गोरिद्म एफएफटी को डिरिचलेट श्रृंखला को परिमित करने के लिए प्रयुक्त करता है
• शॉनहेज-स्ट्रैसन एल्गोरिथम - बड़े पूर्णांकों के लिए स्पर्शोन्मुख रूप से तेज़ गुणन एल्गोरिथम
• तितली आरेख - एफएफटी का वर्णन करने के लिए उपयोग किया जाने वाला डायग्राम
• स्पेक्ट्रल संगीत (संगीत रचना के लिए डीएफटी विश्लेषण का अनुप्रयोग सम्मिलित है)
• स्पेक्ट्रम विश्लेषक - स्पेक्ट्रम विश्लेषण करने वाले कई उपकरणों में से कोई भी, अधिकांशतः डीएफटी के माध्यम से
• समय श्रृंखला
• फास्ट वॉल्श-हैडमार्ड ट्रांसफॉर्म
• सामान्यीकृत वितरण नियम
• कम से कम वर्ग वर्णक्रमीय विश्लेषण
• बहुआयामी परिवर्तन
• बहुआयामी असतत कनवल्शन
• फास्ट फूरियर रूपांतरण टेलीस्कोप

अग्रिम पठन

• Brigham, E. Oran (2002). The Fast Fourier Transform. New York: Prentice-Hall.
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Chapter 30: Polynomials and the FFT". Introduction to Algorithms (2 ed.). MIT Press / McGraw-Hill. ISBN 0-262-03293-7.
• Elliott, Douglas F.; Rao, K. Ramamohan (1982). Fast transforms: Algorithms, analyses, applications. New York, USA: Academic Press.
• Guo, Haitao; Sitton, Gary A.; Burrus, Charles Sidney (1994). "The Quick Discrete Fourier Transform". Proceedings of ICASSP '94. IEEE International Conference on Acoustics, Speech and Signal Processing. pp. 445–448. doi:10.1109/ICASSP.1994.389994. ISBN 978-0-7803-1775-8. S2CID 42639206. {{cite book}}: |journal= ignored (help)
• Johnson, Steven G.; Frigo, Matteo (2007). "A modified split-radix FFT with fewer arithmetic operations" (PDF). IEEE Transactions on Signal Processing. 55 (1): 111–119. Bibcode:2007ITSP...55..111J. CiteSeerX 10.1.1.582.5497. doi:10.1109/tsp.2006.882087. S2CID 14772428. Archived (PDF) from the original on 2005-05-26.
• Press, William H.; Teukolsky, Saul A.; Vetterling, William T.; Flannery, Brian P. (2007). "Chapter 12. Fast Fourier Transform". Numerical Recipes: The Art of Scientific Computing (3 ed.). New York, USA: Cambridge University Press. ISBN 978-0-521-88068-8.
• Singleton, Richard Collom (June 1969). "A Short Bibliography on the Fast Fourier Transform". Special Issue on Fast Fourier Transform. pp. 166–169. doi:10.1109/TAU.1969.1162029. {{cite book}}: |journal= ignored (help) (NB. Contains extensive bibliography.)
• Elena Prestini: "The Evolution of Applied Harmonic Analysis", Springer, ISBN 978-0-8176-4125-2 (2004), Sec.3.10 'Gauss and the asteroids: history of the एफएफटी'.

बाहरी संबंध

• Fast Fourier Transform for Polynomial Multiplication – fast Fourier algorithm
• Fast Fourier Transforms, Connexions online book edited by Charles Sidney Burrus, with chapters by Charles Sidney Burrus, Ivan Selesnick, Markus Pueschel, Matteo Frigo, and Steven G. Johnson (2008)
• Fast Fourier transform — एफएफटी – एफएफटी programming in C++ – the Cooley–तुकी algorithm
• Online documentation, links, book, and code
• Sri Welaratna, "Thirty years of एफएफटी analyzers Archived 2014-01-12 at the Wayback Machine", Sound and Vibration (January 1997, 30th anniversary issue) – a historical review of hardware एफएफटी devices
• ALGLIB एफएफटी Code – a dual/GPL-licensed multilanguage (VBA, C++, Pascal, etc.) numerical analysis and data processing library
• Sएफएफटी: Sparse Fast Fourier Transform – MIT's sparse (sub-linear time) एफएफटी algorithm, sएफएफटी, and implementation
• VB6 एफएफटी – a VB6 optimized library implementation with source code
• Interactive एफएफटी Tutorial – a visual interactive intro to Fourier transforms and एफएफटी methods