फास्ट फूरिये रूपांतर: Difference between revisions

Revision as of 12:33, 2 April 2023

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

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

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

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

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

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

इतिहास

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

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

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

परिभाषा

होने देना $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}$ एकता का आदिम मूल है {{mvar|N}1 का }वाँ मूल।

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

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

एल्गोरिदम

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

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

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

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

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

Cooley-Tukey के अतिरिक्त अन्य FFT एल्गोरिदम भी हैं।

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

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

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

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

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

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

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

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

एक बार यह माना जाता था कि असतत हार्टले ट्रांसफ़ॉर्म (DHT) के माध्यम से वास्तविक-इनपुट DFTs की अधिक कुशलता से गणना की जा सकती है, किन्तु बाद में यह तर्क दिया गया कि एक विशेष वास्तविक-इनपुट DFT एल्गोरिथम (FFT) सामान्यतः पाया जा सकता है जिसके लिए कम संचालन की आवश्यकता होती है समान संख्या में इनपुट के लिए संबंधित DHT एल्गोरिथम (FHT)।^[23]ब्रून का एल्गोरिथम (ऊपर) एक और विधि है जिसे प्रारंभ में वास्तविक इनपुट का लाभ उठाने के लिए प्रस्तावित किया गया था, किन्तु यह लोकप्रिय सिद्ध नहीं हुआ है।

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

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

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

Unsolved problem in computer science:

What is the lower bound on the complexity of fast Fourier transform algorithms? Can they be faster than $O(N\log N)$ ?

(more unsolved problems in computer science)

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

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

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

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

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

सन्निकटन

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

स्पष्ट ता

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

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

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

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

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

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

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

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

{\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}$ मैट्रिक्स, और फिर इस दूसरे मैट्रिक्स के प्रत्येक कॉलम (प्रतिक्रिया पंक्तियों) पर FFT का प्रदर्शन करना, और इसी तरह परिणामों को अंतिम परिणाम मैट्रिक्स में समूहीकृत करना।

दो से अधिक आयामों में, यह अधिकांशतः कैश (कंप्यूटिंग) इलाके के लिए आयामों को पुनरावर्ती रूप से समूहित करने के लिए फायदेमंद होता है। उदाहरण के लिए, एक त्रि-आयामी एफएफटी पहले प्रत्येक निश्चित एन के लिए प्रत्येक प्लानर स्लाइस के द्वि-आयामी एफएफटी का प्रदर्शन कर सकता है₁, और फिर n के साथ एक आयामी FFTs निष्पादित करें₁ दिशा। अधिक सामान्यतः , एक विषम रूप से इष्टतम कैश-बेपरवाह एल्गोरिथ्म में आयामों को दो समूहों में पुनरावर्ती रूप से विभाजित किया जाता है ${\textstyle (n_{1},\ldots ,n_{d/2})}$ और ${\textstyle (n_{d/2+1},\ldots ,n_{d})}$ जो पुनरावर्ती रूप से रूपांतरित होते हैं (यदि d सम नहीं है तो गोल करना) (फ्रिगो और जॉनसन, 2005 देखें)।^[17]फिर भी, यह पंक्ति-स्तंभ एल्गोरिथम का एक सीधा रूपांतर बना हुआ है, जिसके लिए अंततः बेस केस के रूप में केवल एक-आयामी FFT एल्गोरिथम की आवश्यकता होती है, और अभी भी 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) के कारण बहुपद परिवर्तन एल्गोरिथम,^[40]जो संकल्पों और बहुपद उत्पादों के संदर्भ में परिवर्तन को देखते हैं। डुहामेल और वेटरली देखें (1990)^[32]अधिक जानकारी और संदर्भ के लिए।

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

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

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

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

अनुप्रयोग

FFT का उपयोग डिजिटल रिकॉर्डिंग, सैंपलिंग, योजक संश्लेषण और पिच सुधार सॉफ्टवेयर में किया जाता है।^[45] FFT का महत्व इस तथ्य से निकला है कि इसने आवृत्ति डोमेन में काम करना कम्प्यूटेशनल रूप से उतना ही संभव बना दिया है जितना कि अस्थायी या स्थानिक डोमेन में काम करना। FFT के कुछ महत्वपूर्ण अनुप्रयोगों में सम्मिलित हैं:^[15]^[46]

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

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

बिग एफएफटी: खगोल विज्ञान जैसे क्षेत्रों में बड़े डेटा के विस्फोट के साथ, कुछ इंटरफेरोमेट्री गणनाओं के लिए 512K FFTs की आवश्यकता उत्पन्न हुई है। विल्किंसन माइक्रोवेव अनिसोट्रॉपी जांच और एलआईजीओ जैसी परियोजनाओं द्वारा एकत्र किए गए डेटा को अरबों अंकों के एफएफटी की आवश्यकता होती है। चूंकि यह आकार मुख्य मेमोरी में फिट नहीं होता है, तथाकथित आउट-ऑफ-कोर एफएफटी अनुसंधान का एक सक्रिय क्षेत्र है।^[48]; अनुमानित एफएफटी: एमआरआई जैसे अनुप्रयोगों के लिए, गैर-समान दूरी वाले ग्रिड बिंदुओं और/या आवृत्तियों के लिए डीएफटी की गणना करना आवश्यक है। मल्टीपोल आधारित दृष्टिकोण रनटाइम वृद्धि के कारक के साथ अनुमानित मात्रा की गणना कर सकते हैं।^[49]; परिमित समूहों पर फूरियर रूपांतरण: आगे सामान्यीकरण की अनुमति देने वाले समूह प्रतिनिधित्व का उपयोग करके एफएफटी को भी समझाया और व्याख्या किया जा सकता है। गैर-चक्रीय समेत किसी भी कॉम्पैक्ट समूह पर एक फ़ंक्शन, इरेड्यूसिबल मैट्रिक्स तत्वों के आधार पर विस्तार होता है। आधार के इस परिवर्तन को करने के लिए कुशल एल्गोरिथम खोजने के लिए यह अनुसंधान का सक्रिय क्षेत्र बना हुआ है। कुशल गोलाकार हार्मोनिक्स विस्तार सहित अनुप्रयोग, कुछ मार्कोव प्रक्रियाओं का विश्लेषण, रोबोटिक्स इत्यादि।^[50]; क्वांटम फूरियर रूपांतरण: क्वांटम कंप्यूटर पर पूर्णांक गुणनखंडन के लिए ध्वनि के तेज एल्गोरिथ्म में बाइनरी वेक्टर के डीएफटी की गणना करने के लिए एक सबरूटीन है। इसे 1- या 2-बिट क्वांटम गेट्स के अनुक्रम के रूप में कार्यान्वित किया जाता है, जिसे अब क्वांटम एफएफटी के रूप में जाना जाता है, जो प्रभावी रूप से कूली-तुके एफएफटी को फूरियर मैट्रिक्स के एक विशेष कारक के रूप में अनुभूत किया गया है। वर्तमान में इन विचारों के विस्तार का पता लगाया जा रहा है।^[51]

भाषा संदर्भ

Language	Command/Method	Pre-requisites
R	stats::fft(x)	None
Scilab	fft(x)	None
Octave/MATLAB	fft(x)	None
Python	fft.fft(x)	numpy scipy
Mathematica	Fourier[x]	None
Fortran	fftw_one(plan,in,out)	FFTW
Julia	fft(A [,dims])	FFTW
Rust	fft.process(&mut x);	rustfft
Haskell	dft x	fft

यह भी देखें

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

बिट-रिवर्सल क्रमचय

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

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

ALGLIB - वास्तविक/जटिल FFT कार्यान्वयन के साथ एक दोहरी/GPL-लाइसेंसीकृत C++ और C या लाइब्रेरी (अन्य भाषाओं का भी समर्थन करती है)
FFTPACK - एक और फोरट्रान FFT लाइब्रेरी (सार्वजनिक डोमेन)
वास्तुकला-विशिष्ट:
- शाखा प्रदर्शन पुस्तकालय^[52]
- इंटेल एकीकृत प्रदर्शन आदिम
- इंटेल गणित कर्नेल लाइब्रेरी
कई और कार्यान्वयन उपलब्ध हैं,^[53] CPU और GPU के लिए, जैसे C++ के लिए PocketFFT

अन्य लिंक:

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

संदर्भ

↑ ^1.0 ^1.1 ^1.2 ^1.3 Heideman, Michael T.; Johnson, Don H.; Burrus, Charles Sidney (1984). "Gauss and the history of the fast Fourier transform" (PDF). IEEE ASSP Magazine. 1 (4): 14–21. CiteSeerX 10.1.1.309.181. doi:10.1109/MASSP.1984.1162257. S2CID 10032502. Archived (PDF) from the original on 2013-03-19.
↑ Van Loan, Charles (1992). Computational Frameworks for the Fast Fourier Transform. SIAM.
↑ Strang, Gilbert (May–June 1994). "Wavelets". American Scientist. 82 (3): 250–255. JSTOR 29775194.
↑ Kent, Ray D.; Read, Charles (2002). Acoustic Analysis of Speech. ISBN 0-7693-0112-6.
↑ Dongarra, Jack; Sullivan, Francis (January 2000). "Guest Editors Introduction to the top 10 algorithms". Computing in Science & Engineering. 2 (1): 22–23. Bibcode:2000CSE.....2a..22D. doi:10.1109/MCISE.2000.814652. ISSN 1521-9615.
↑ Gauss, Carl Friedrich (1866). "Theoria interpolationis methodo nova tractata" [Theory regarding a new method of interpolation]. Nachlass (Unpublished manuscript). Werke (in Latina and Deutsch). Vol. 3. Göttingen, Germany: Königlichen Gesellschaft der Wissenschaften zu Göttingen. pp. 265–303.
↑ ^7.0 ^7.1 Heideman, Michael T.; Johnson, Don H.; Burrus, Charles Sidney (1985-09-01). "Gauss and the history of the fast Fourier transform". Archive for History of Exact Sciences. 34 (3): 265–277. CiteSeerX 10.1.1.309.181. doi:10.1007/BF00348431. ISSN 0003-9519. S2CID 122847826.
↑ Yates, Frank (1937). "The design and analysis of factorial experiments". Technical Communication No. 35 of the Commonwealth Bureau of Soils. 142 (3585): 90–92. Bibcode:1938Natur.142...90F. doi:10.1038/142090a0. S2CID 23501205.
↑ Danielson, Gordon C.; Lanczos, Cornelius (1942). "Some improvements in practical Fourier analysis and their application to x-ray scattering from liquids". Journal of the Franklin Institute. 233 (4): 365–380. doi:10.1016/S0016-0032(42)90767-1.
↑ Lanczos, Cornelius (1956). Applied Analysis. Prentice–Hall.
↑ Cooley, James W.; Lewis, Peter A. W.; Welch, Peter D. (June 1967). "Historical notes on the fast Fourier transform". IEEE Transactions on Audio and Electroacoustics. 15 (2): 76–79. CiteSeerX 10.1.1.467.7209. doi:10.1109/TAU.1967.1161903. ISSN 0018-9278.
↑ ^12.0 ^12.1 Cooley, James W.; Tukey, John W. (1965). "An algorithm for the machine calculation of complex Fourier series". Mathematics of Computation. 19 (90): 297–301. doi:10.1090/S0025-5718-1965-0178586-1. ISSN 0025-5718.
↑ Cooley, James W. (1987). The Re-Discovery of the Fast Fourier Transform Algorithm (PDF). pp. 33–45. Archived (PDF) from the original on 2016-08-20. {{cite book}}: |work= ignored (help)CS1 maint: location missing publisher (link)
↑ Garwin, Richard (June 1969). "The Fast Fourier Transform As an Example of the Difficulty in Gaining Wide Use for a New Technique" (PDF). IEEE Transactions on Audio and Electroacoustics. AU-17 (2): 68–72. Archived (PDF) from the original on 2006-05-17.
↑ ^15.0 ^15.1 Rockmore, Daniel N. (January 2000). "The FFT: an algorithm the whole family can use". Computing in Science & Engineering. 2 (1): 60–64. Bibcode:2000CSE.....2a..60R. CiteSeerX 10.1.1.17.228. doi:10.1109/5992.814659. ISSN 1521-9615.
↑ ^16.0 ^16.1 Frigo, Matteo; Johnson, Steven G. (January 2007) [2006-12-19]. "A Modified Split-Radix FFT With Fewer Arithmetic Operations". 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.
↑ ^17.0 ^17.1 ^17.2 Frigo, Matteo; Johnson, Steven G. (2005). "The Design and Implementation of FFTW3" (PDF). Proceedings of the IEEE. 93 (2): 216–231. CiteSeerX 10.1.1.66.3097. doi:10.1109/jproc.2004.840301. S2CID 6644892. Archived (PDF) from the original on 2005-02-07.
↑ ^18.0 ^18.1 Gentleman, W. Morven; Sande, G. (1966). "Fast Fourier transforms—for fun and profit". Proceedings of the AFIPS. 29: 563–578. doi:10.1145/1464291.1464352. S2CID 207170956.
↑ Gauss, Carl Friedrich (1866) [1805]. Theoria interpolationis methodo nova tractata. Werke (in Latina and Deutsch). Vol. 3. Göttingen, Germany: Königliche Gesellschaft der Wissenschaften. pp. 265–327.
↑ ^20.0 ^20.1 Brenner, Norman M.; Rader, Charles M. (1976). "A New Principle for Fast Fourier Transformation". IEEE Transactions on Acoustics, Speech, and Signal Processing. 24 (3): 264–266. doi:10.1109/TASSP.1976.1162805.
↑ ^21.0 ^21.1 Winograd, Shmuel (1978). "On computing the discrete Fourier transform". Mathematics of Computation. 32 (141): 175–199. doi:10.1090/S0025-5718-1978-0468306-4. JSTOR 2006266. PMC 430186. PMID 16592303.
↑ Winograd, Shmuel (1979). "On the multiplicative complexity of the discrete Fourier transform". Advances in Mathematics. 32 (2): 83–117. doi:10.1016/0001-8708(79)90037-9.
↑ ^23.0 ^23.1 Sorensen, Henrik V.; Jones, Douglas L.; Heideman, Michael T.; Burrus, Charles Sidney (1987). "Real-valued fast Fourier transform algorithms". IEEE Transactions on Acoustics, Speech, and Signal Processing. 35 (6): 849–863. CiteSeerX 10.1.1.205.4523. doi:10.1109/TASSP.1987.1165220.
↑ Sorensen, Henrik V.; Jones, Douglas L.; Heideman, Michael T.; Burrus, Charles Sidney (1987). "Corrections to "Real-valued fast Fourier transform algorithms"". IEEE Transactions on Acoustics, Speech, and Signal Processing. 35 (9): 1353. doi:10.1109/TASSP.1987.1165284.
↑ Heideman, Michael T.; Burrus, Charles Sidney (1986). "On the number of multiplications necessary to compute a length-2ⁿ DFT". IEEE Transactions on Acoustics, Speech, and Signal Processing. 34 (1): 91–95. doi:10.1109/TASSP.1986.1164785.
↑ ^26.0 ^26.1 Duhamel, Pierre (1990). "Algorithms meeting the lower bounds on the multiplicative complexity of length-2ⁿ DFTs and their connection with practical algorithms". IEEE Transactions on Acoustics, Speech, and Signal Processing. 38 (9): 1504–1511. doi:10.1109/29.60070.
↑ Morgenstern, Jacques (1973). "Note on a lower bound of the linear complexity of the fast Fourier transform". Journal of the ACM. 20 (2): 305–306. doi:10.1145/321752.321761. S2CID 2790142.
↑ Pan, Victor Ya. (1986-01-02). "The trade-off between the additive complexity and the asynchronicity of linear and bilinear algorithms". Information Processing Letters. 22 (1): 11–14. doi:10.1016/0020-0190(86)90035-9. Retrieved 2017-10-31.
↑ Papadimitriou, Christos H. (1979). "Optimality of the fast Fourier transform". Journal of the ACM. 26: 95–102. doi:10.1145/322108.322118. S2CID 850634.
↑ Lundy, Thomas J.; Van Buskirk, James (2007). "A new matrix approach to real FFTs and convolutions of length 2^k". Computing. 80 (1): 23–45. doi:10.1007/s00607-007-0222-6. S2CID 27296044.
↑ Haynal, Steve; Haynal, Heidi (2011). "Generating and Searching Families of FFT Algorithms" (PDF). Journal on Satisfiability, Boolean Modeling and Computation. 7 (4): 145–187. arXiv:1103.5740. Bibcode:2011arXiv1103.5740H. doi:10.3233/SAT190084. S2CID 173109. Archived from the original (PDF) on 2012-04-26.
↑ ^32.0 ^32.1 Duhamel, Pierre; Vetterli, Martin (1990). "Fast Fourier transforms: a tutorial review and a state of the art". Signal Processing. 19 (4): 259–299. doi:10.1016/0165-1684(90)90158-U.
↑ Edelman, Alan; McCorquodale, Peter; Toledo, Sivan (1999). "The Future Fast Fourier Transform?" (PDF). SIAM Journal on Scientific Computing. 20 (3): 1094–1114. CiteSeerX 10.1.1.54.9339. doi:10.1137/S1064827597316266. Archived (PDF) from the original on 2017-07-05.
↑ Guo, Haitao; Burrus, Charles Sidney (1996). "Fast approximate Fourier transform via wavelets transform". Proceedings of SPIE. Wavelet Applications in Signal and Image Processing IV. 2825: 250–259. Bibcode:1996SPIE.2825..250G. CiteSeerX 10.1.1.54.3984. doi:10.1117/12.255236. S2CID 120514955.
↑ Shentov, Ognjan V.; Mitra, Sanjit K.; Heute, Ulrich; Hossen, Abdul N. (1995). "Subband DFT. I. Definition, interpretations and extensions". Signal Processing. 41 (3): 261–277. doi:10.1016/0165-1684(94)00103-7.
↑ Hassanieh, Haitham; Indyk, Piotr; Katabi, Dina; Price, Eric (January 2012). "Simple and Practical Algorithm for Sparse Fourier Transform" (PDF). ACM-SIAM Symposium on Discrete Algorithms. Archived (PDF) from the original on 2012-03-04. (NB. See also the sFFT Web Page.)
↑ Schatzman, James C. (1996). "Accuracy of the discrete Fourier transform and the fast Fourier transform". SIAM Journal on Scientific Computing. 17 (5): 1150–1166. Bibcode:1996SJSC...17.1150S. CiteSeerX 10.1.1.495.9184. doi:10.1137/s1064827593247023.
↑ Welch, Peter D. (1969). "A fixed-point fast Fourier transform error analysis". IEEE Transactions on Audio and Electroacoustics. 17 (2): 151–157. doi:10.1109/TAU.1969.1162035.
↑ Ergün, Funda (1995). Testing multivariate linear functions: Overcoming the generator bottleneck. pp. 407–416. doi:10.1145/225058.225167. ISBN 978-0897917186. S2CID 15512806. {{cite book}}: |journal= ignored (help)CS1 maint: location missing publisher (link)
↑ Nussbaumer, Henri J. (1977). "Digital filtering using polynomial transforms". Electronics Letters. 13 (13): 386–387. Bibcode:1977ElL....13..386N. doi:10.1049/el:19770280.
↑ Mohlenkamp, Martin J. (1999). "A Fast Transform for Spherical Harmonics" (PDF). Journal of Fourier Analysis and Applications. 5 (2–3): 159–184. CiteSeerX 10.1.1.135.9830. doi:10.1007/BF01261607. S2CID 119482349. Archived (PDF) from the original on 2017-05-06. Retrieved 2018-01-11.
↑ "libftsh library". Archived from the original on 2010-06-23. Retrieved 2007-01-09.
↑ Rokhlin, Vladimir; Tygert, Mark (2006). "Fast Algorithms for Spherical Harmonic Expansions" (PDF). SIAM Journal on Scientific Computing. 27 (6): 1903–1928. Bibcode:2006SJSC...27.1903R. CiteSeerX 10.1.1.125.7415. doi:10.1137/050623073. Archived (PDF) from the original on 2014-12-17. Retrieved 2014-09-18. [1]
↑ Potts, Daniel; Steidl, Gabriele; Tasche, Manfred (2001). "Fast Fourier transforms for nonequispaced data: A tutorial" (PDF). In Benedetto, J. J.; Ferreira, P. (eds.). Modern Sampling Theory: Mathematics and Applications. Birkhäuser. Archived (PDF) from the original on 2007-09-26.
↑ Burgess, Richard James (2014). संगीत उत्पादन का इतिहास. Oxford University Press. ISBN 978-0199357178. Retrieved 1 August 2019.
↑ Chu, Eleanor; George, Alan (1999-11-11) [1999-11-11]. "Chapter 16". Inside the FFT Black Box: Serial and Parallel Fast Fourier Transform Algorithms. CRC Press. pp. 153–168. ISBN 978-1-42004996-1.
↑ Fernandez-de-Cossio Diaz, Jorge; Fernandez-de-Cossio, Jorge (2012-08-08). "Computation of Isotopic Peak Center-Mass Distribution by Fourier Transform". Analytical Chemistry. 84 (16): 7052–7056. doi:10.1021/ac301296a. ISSN 0003-2700. PMID 22873736.
↑ Cormen, Thomas H.; Nicol, David M. (1998). "Performing out-of-core FFTs on parallel disk systems". Parallel Computing. 24 (1): 5–20. CiteSeerX 10.1.1.44.8212. doi:10.1016/S0167-8191(97)00114-2. S2CID 14996854.
↑ Dutt, Alok; Rokhlin, Vladimir (1993-11-01). "Fast Fourier Transforms for Nonequispaced Data". SIAM Journal on Scientific Computing. 14 (6): 1368–1393. Bibcode:1993SJSC...14.1368D. doi:10.1137/0914081. ISSN 1064-8275.
↑ Rockmore, Daniel N. (2004). "Recent Progress and Applications in Group FFTs". In Byrnes, Jim (ed.). Computational Noncommutative Algebra and Applications. NATO Science Series II: Mathematics, Physics and Chemistry. Vol. 136. Springer Netherlands. pp. 227–254. CiteSeerX 10.1.1.324.4700. doi:10.1007/1-4020-2307-3_9. ISBN 978-1-4020-1982-1. S2CID 1412268.
↑ Ryo, Asaka; Kazumitsu, Sakai; Ryoko, Yahagi (2020). "फास्ट फूरियर रूपांतरण के लिए क्वांटम सर्किट". Quantum Information Processing. 19 (277): 277. arXiv:1911.03055. Bibcode:2020QuIP...19..277A. doi:10.1007/s11128-020-02776-5. S2CID 207847474.
↑ "शाखा प्रदर्शन पुस्तकालय". Arm. 2020. Retrieved 2020-12-16.
↑ "Complete list of C/C++ FFT libraries". VCV Community (in English). 2020-04-05. Retrieved 2021-03-03.

अग्रिम पठन

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 FFT'.

बाहरी संबंध

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 — FFT – FFT programming in C++ – the Cooley–Tukey algorithm
Online documentation, links, book, and code
Sri Welaratna, "Thirty years of FFT analyzers Archived 2014-01-12 at the Wayback Machine", Sound and Vibration (January 1997, 30th anniversary issue) – a historical review of hardware FFT devices
ALGLIB FFT Code – a dual/GPL-licensed multilanguage (VBA, C++, Pascal, etc.) numerical analysis and data processing library
SFFT: Sparse Fast Fourier Transform – MIT's sparse (sub-linear time) FFT algorithm, sFFT, and implementation
VB6 FFT – a VB6 optimized library implementation with source code
Interactive FFT Tutorial – a visual interactive intro to Fourier transforms and FFT methods

[Heideman_Johnson_Burrus_1984-1] 1.0 ^1.1 ^1.2 ^1.3 Heideman, Michael T.; Johnson, Don H.; Burrus, Charles Sidney (1984). "Gauss and the history of the fast Fourier transform" (PDF). IEEE ASSP Magazine. 1 (4): 14–21. CiteSeerX 10.1.1.309.181. doi:10.1109/MASSP.1984.1162257. S2CID 10032502. Archived (PDF) from the original on 2013-03-19.

[Loan_1992-2] Van Loan, Charles (1992). Computational Frameworks for the Fast Fourier Transform. SIAM.

[Strang_1994-3] Strang, Gilbert (May–June 1994). "Wavelets". American Scientist. 82 (3): 250–255. JSTOR 29775194.

[Kent_2002-4] Kent, Ray D.; Read, Charles (2002). Acoustic Analysis of Speech. ISBN 0-7693-0112-6.

[Dongarra_Sullivan_2000-5] Dongarra, Jack; Sullivan, Francis (January 2000). "Guest Editors Introduction to the top 10 algorithms". Computing in Science & Engineering. 2 (1): 22–23. Bibcode:2000CSE.....2a..22D. doi:10.1109/MCISE.2000.814652. ISSN 1521-9615.

[Gauss_1866-6] Gauss, Carl Friedrich (1866). "Theoria interpolationis methodo nova tractata" [Theory regarding a new method of interpolation]. Nachlass (Unpublished manuscript). Werke (in Latina and Deutsch). Vol. 3. Göttingen, Germany: Königlichen Gesellschaft der Wissenschaften zu Göttingen. pp. 265–303.

[Heideman_Johnson_Burrus_1985-7] 7.0 ^7.1 Heideman, Michael T.; Johnson, Don H.; Burrus, Charles Sidney (1985-09-01). "Gauss and the history of the fast Fourier transform". Archive for History of Exact Sciences. 34 (3): 265–277. CiteSeerX 10.1.1.309.181. doi:10.1007/BF00348431. ISSN 0003-9519. S2CID 122847826.

[Yates_1937-8] Yates, Frank (1937). "The design and analysis of factorial experiments". Technical Communication No. 35 of the Commonwealth Bureau of Soils. 142 (3585): 90–92. Bibcode:1938Natur.142...90F. doi:10.1038/142090a0. S2CID 23501205.

[Danielson_Lanczos_1942-9] Danielson, Gordon C.; Lanczos, Cornelius (1942). "Some improvements in practical Fourier analysis and their application to x-ray scattering from liquids". Journal of the Franklin Institute. 233 (4): 365–380. doi:10.1016/S0016-0032(42)90767-1.

[Lanczos_1956-10] Lanczos, Cornelius (1956). Applied Analysis. Prentice–Hall.

[Cooley_Lewis_Welch_1967-11] Cooley, James W.; Lewis, Peter A. W.; Welch, Peter D. (June 1967). "Historical notes on the fast Fourier transform". IEEE Transactions on Audio and Electroacoustics. 15 (2): 76–79. CiteSeerX 10.1.1.467.7209. doi:10.1109/TAU.1967.1161903. ISSN 0018-9278.

[Cooley_Tukey_1965-12] 12.0 ^12.1 Cooley, James W.; Tukey, John W. (1965). "An algorithm for the machine calculation of complex Fourier series". Mathematics of Computation. 19 (90): 297–301. doi:10.1090/S0025-5718-1965-0178586-1. ISSN 0025-5718.

[Cooley_1987-13] Cooley, James W. (1987). The Re-Discovery of the Fast Fourier Transform Algorithm (PDF). pp. 33–45. Archived (PDF) from the original on 2016-08-20. {{cite book}}: |work= ignored (help)CS1 maint: location missing publisher (link)

[Garwin_1969-14] Garwin, Richard (June 1969). "The Fast Fourier Transform As an Example of the Difficulty in Gaining Wide Use for a New Technique" (PDF). IEEE Transactions on Audio and Electroacoustics. AU-17 (2): 68–72. Archived (PDF) from the original on 2006-05-17.

[Rockmore_2000-15] 15.0 ^15.1 Rockmore, Daniel N. (January 2000). "The FFT: an algorithm the whole family can use". Computing in Science & Engineering. 2 (1): 60–64. Bibcode:2000CSE.....2a..60R. CiteSeerX 10.1.1.17.228. doi:10.1109/5992.814659. ISSN 1521-9615.

[Frigo_Johnson_2007-16] 16.0 ^16.1 Frigo, Matteo; Johnson, Steven G. (January 2007) [2006-12-19]. "A Modified Split-Radix FFT With Fewer Arithmetic Operations". 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.

[Frigo_Johnson_2005-17] 17.0 ^17.1 ^17.2 Frigo, Matteo; Johnson, Steven G. (2005). "The Design and Implementation of FFTW3" (PDF). Proceedings of the IEEE. 93 (2): 216–231. CiteSeerX 10.1.1.66.3097. doi:10.1109/jproc.2004.840301. S2CID 6644892. Archived (PDF) from the original on 2005-02-07.

[Gentleman_Sande_1966-18] 18.0 ^18.1 Gentleman, W. Morven; Sande, G. (1966). "Fast Fourier transforms—for fun and profit". Proceedings of the AFIPS. 29: 563–578. doi:10.1145/1464291.1464352. S2CID 207170956.

[Gauss_1805-19] Gauss, Carl Friedrich (1866) [1805]. Theoria interpolationis methodo nova tractata. Werke (in Latina and Deutsch). Vol. 3. Göttingen, Germany: Königliche Gesellschaft der Wissenschaften. pp. 265–327.

[Brenner_Rader_1976-20] 20.0 ^20.1 Brenner, Norman M.; Rader, Charles M. (1976). "A New Principle for Fast Fourier Transformation". IEEE Transactions on Acoustics, Speech, and Signal Processing. 24 (3): 264–266. doi:10.1109/TASSP.1976.1162805.

[Winograd_1978-21] 21.0 ^21.1 Winograd, Shmuel (1978). "On computing the discrete Fourier transform". Mathematics of Computation. 32 (141): 175–199. doi:10.1090/S0025-5718-1978-0468306-4. JSTOR 2006266. PMC 430186. PMID 16592303.

[Winograd_1979-22] Winograd, Shmuel (1979). "On the multiplicative complexity of the discrete Fourier transform". Advances in Mathematics. 32 (2): 83–117. doi:10.1016/0001-8708(79)90037-9.

[Sorensen_Jones_Heideman_Burrus_1987_1-23] 23.0 ^23.1 Sorensen, Henrik V.; Jones, Douglas L.; Heideman, Michael T.; Burrus, Charles Sidney (1987). "Real-valued fast Fourier transform algorithms". IEEE Transactions on Acoustics, Speech, and Signal Processing. 35 (6): 849–863. CiteSeerX 10.1.1.205.4523. doi:10.1109/TASSP.1987.1165220.

[Sorensen_Jones_Heideman_Burrus_1987_2-24] Sorensen, Henrik V.; Jones, Douglas L.; Heideman, Michael T.; Burrus, Charles Sidney (1987). "Corrections to "Real-valued fast Fourier transform algorithms"". IEEE Transactions on Acoustics, Speech, and Signal Processing. 35 (9): 1353. doi:10.1109/TASSP.1987.1165284.

[Heideman_Burrus_1986-25] Heideman, Michael T.; Burrus, Charles Sidney (1986). "On the number of multiplications necessary to compute a length-2ⁿ DFT". IEEE Transactions on Acoustics, Speech, and Signal Processing. 34 (1): 91–95. doi:10.1109/TASSP.1986.1164785.

[Duhamel_1990-26] 26.0 ^26.1 Duhamel, Pierre (1990). "Algorithms meeting the lower bounds on the multiplicative complexity of length-2ⁿ DFTs and their connection with practical algorithms". IEEE Transactions on Acoustics, Speech, and Signal Processing. 38 (9): 1504–1511. doi:10.1109/29.60070.

[Morgenstern_1973-27] Morgenstern, Jacques (1973). "Note on a lower bound of the linear complexity of the fast Fourier transform". Journal of the ACM. 20 (2): 305–306. doi:10.1145/321752.321761. S2CID 2790142.

[Pan_1986-28] Pan, Victor Ya. (1986-01-02). "The trade-off between the additive complexity and the asynchronicity of linear and bilinear algorithms". Information Processing Letters. 22 (1): 11–14. doi:10.1016/0020-0190(86)90035-9. Retrieved 2017-10-31.

[Papadimitriou_1979-29] Papadimitriou, Christos H. (1979). "Optimality of the fast Fourier transform". Journal of the ACM. 26: 95–102. doi:10.1145/322108.322118. S2CID 850634.

[Lundy_Buskirk_2007-30] Lundy, Thomas J.; Van Buskirk, James (2007). "A new matrix approach to real FFTs and convolutions of length 2^k". Computing. 80 (1): 23–45. doi:10.1007/s00607-007-0222-6. S2CID 27296044.

[Haynal_2011-31] Haynal, Steve; Haynal, Heidi (2011). "Generating and Searching Families of FFT Algorithms" (PDF). Journal on Satisfiability, Boolean Modeling and Computation. 7 (4): 145–187. arXiv:1103.5740. Bibcode:2011arXiv1103.5740H. doi:10.3233/SAT190084. S2CID 173109. Archived from the original (PDF) on 2012-04-26.

[Duhamel_Vetterli_1990-32] 32.0 ^32.1 Duhamel, Pierre; Vetterli, Martin (1990). "Fast Fourier transforms: a tutorial review and a state of the art". Signal Processing. 19 (4): 259–299. doi:10.1016/0165-1684(90)90158-U.

[Edelman_McCorquodale_Toledo_1999-33] Edelman, Alan; McCorquodale, Peter; Toledo, Sivan (1999). "The Future Fast Fourier Transform?" (PDF). SIAM Journal on Scientific Computing. 20 (3): 1094–1114. CiteSeerX 10.1.1.54.9339. doi:10.1137/S1064827597316266. Archived (PDF) from the original on 2017-07-05.

[Guo_Burrus_1996-34] Guo, Haitao; Burrus, Charles Sidney (1996). "Fast approximate Fourier transform via wavelets transform". Proceedings of SPIE. Wavelet Applications in Signal and Image Processing IV. 2825: 250–259. Bibcode:1996SPIE.2825..250G. CiteSeerX 10.1.1.54.3984. doi:10.1117/12.255236. S2CID 120514955.

[Shentov_Mitra_Heute_Hossen_1995-35] Shentov, Ognjan V.; Mitra, Sanjit K.; Heute, Ulrich; Hossen, Abdul N. (1995). "Subband DFT. I. Definition, interpretations and extensions". Signal Processing. 41 (3): 261–277. doi:10.1016/0165-1684(94)00103-7.

[Hassanieh_2012-36] Hassanieh, Haitham; Indyk, Piotr; Katabi, Dina; Price, Eric (January 2012). "Simple and Practical Algorithm for Sparse Fourier Transform" (PDF). ACM-SIAM Symposium on Discrete Algorithms. Archived (PDF) from the original on 2012-03-04. (NB. See also the sFFT Web Page.)

[Schatzman_1996-37] Schatzman, James C. (1996). "Accuracy of the discrete Fourier transform and the fast Fourier transform". SIAM Journal on Scientific Computing. 17 (5): 1150–1166. Bibcode:1996SJSC...17.1150S. CiteSeerX 10.1.1.495.9184. doi:10.1137/s1064827593247023.

[Welch_1969-38] Welch, Peter D. (1969). "A fixed-point fast Fourier transform error analysis". IEEE Transactions on Audio and Electroacoustics. 17 (2): 151–157. doi:10.1109/TAU.1969.1162035.

[Ergün_1995-39] Ergün, Funda (1995). Testing multivariate linear functions: Overcoming the generator bottleneck. pp. 407–416. doi:10.1145/225058.225167. ISBN 978-0897917186. S2CID 15512806. {{cite book}}: |journal= ignored (help)CS1 maint: location missing publisher (link)

[Nussbaumer_1977-40] Nussbaumer, Henri J. (1977). "Digital filtering using polynomial transforms". Electronics Letters. 13 (13): 386–387. Bibcode:1977ElL....13..386N. doi:10.1049/el:19770280.

[Mohlenkamp_1999-41] Mohlenkamp, Martin J. (1999). "A Fast Transform for Spherical Harmonics" (PDF). Journal of Fourier Analysis and Applications. 5 (2–3): 159–184. CiteSeerX 10.1.1.135.9830. doi:10.1007/BF01261607. S2CID 119482349. Archived (PDF) from the original on 2017-05-06. Retrieved 2018-01-11.

[libftsh-42] "libftsh library". Archived from the original on 2010-06-23. Retrieved 2007-01-09.

[Rokhlin_Tygert_2006-43] Rokhlin, Vladimir; Tygert, Mark (2006). "Fast Algorithms for Spherical Harmonic Expansions" (PDF). SIAM Journal on Scientific Computing. 27 (6): 1903–1928. Bibcode:2006SJSC...27.1903R. CiteSeerX 10.1.1.125.7415. doi:10.1137/050623073. Archived (PDF) from the original on 2014-12-17. Retrieved 2014-09-18. [1]

[Potts_Steidl_Tasche_2001-44] Potts, Daniel; Steidl, Gabriele; Tasche, Manfred (2001). "Fast Fourier transforms for nonequispaced data: A tutorial" (PDF). In Benedetto, J. J.; Ferreira, P. (eds.). Modern Sampling Theory: Mathematics and Applications. Birkhäuser. Archived (PDF) from the original on 2007-09-26.

[45] Burgess, Richard James (2014). संगीत उत्पादन का इतिहास. Oxford University Press. ISBN 978-0199357178. Retrieved 1 August 2019.

[Chu_George_1999-46] Chu, Eleanor; George, Alan (1999-11-11) [1999-11-11]. "Chapter 16". Inside the FFT Black Box: Serial and Parallel Fast Fourier Transform Algorithms. CRC Press. pp. 153–168. ISBN 978-1-42004996-1.

[Fernandez-de-Cossio_2012-47] Fernandez-de-Cossio Diaz, Jorge; Fernandez-de-Cossio, Jorge (2012-08-08). "Computation of Isotopic Peak Center-Mass Distribution by Fourier Transform". Analytical Chemistry. 84 (16): 7052–7056. doi:10.1021/ac301296a. ISSN 0003-2700. PMID 22873736.

[Cormen_Nicol_1998-48] Cormen, Thomas H.; Nicol, David M. (1998). "Performing out-of-core FFTs on parallel disk systems". Parallel Computing. 24 (1): 5–20. CiteSeerX 10.1.1.44.8212. doi:10.1016/S0167-8191(97)00114-2. S2CID 14996854.

[Dutt_Rokhlin_1993-49] Dutt, Alok; Rokhlin, Vladimir (1993-11-01). "Fast Fourier Transforms for Nonequispaced Data". SIAM Journal on Scientific Computing. 14 (6): 1368–1393. Bibcode:1993SJSC...14.1368D. doi:10.1137/0914081. ISSN 1064-8275.

[Rockmore_2004-50] Rockmore, Daniel N. (2004). "Recent Progress and Applications in Group FFTs". In Byrnes, Jim (ed.). Computational Noncommutative Algebra and Applications. NATO Science Series II: Mathematics, Physics and Chemistry. Vol. 136. Springer Netherlands. pp. 227–254. CiteSeerX 10.1.1.324.4700. doi:10.1007/1-4020-2307-3_9. ISBN 978-1-4020-1982-1. S2CID 1412268.

[51] Ryo, Asaka; Kazumitsu, Sakai; Ryoko, Yahagi (2020). "फास्ट फूरियर रूपांतरण के लिए क्वांटम सर्किट". Quantum Information Processing. 19 (277): 277. arXiv:1911.03055. Bibcode:2020QuIP...19..277A. doi:10.1007/s11128-020-02776-5. S2CID 207847474.

[Arm_Performance_Libraries-52] "शाखा प्रदर्शन पुस्तकालय". Arm. 2020. Retrieved 2020-12-16.

[53] "Complete list of C/C++ FFT libraries". VCV Community (in English). 2020-04-05. Retrieved 2021-03-03.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

[42]

[43]

[44]

[45]

[46]

[47]

[48]

[49]

[50]

[51]

[52]

[53]

@@ Line 3: / Line 3: @@
 {{redirect|एफएफटी}}
 [[File:DIT-FFT-butterfly.svg|thumb|आधे आकार के एफएफटी में अपघटन का उपयोग करते हुए एक उदाहरण एफएफटी एल्गोरिदम संरचना]]
-[[File:FFT of Cosine Summation Function.svg|thumb|10, 20, 30, 40, और 50 हर्ट्ज पर कोज्या तरंगों के योग का असतत फूरियर विश्लेषण]]एक तेज़ फूरियर ट्रांसफ़ॉर्म (FFT) एक [[कलन विधि]] है जो एक [[अनुक्रम]] के असतत फूरियर ट्रांसफ़ॉर्म (DFT) या इसके व्युत्क्रम (IDFT) की गणना करता है। [[फूरियर विश्लेषण]] एक संकेत को उसके मूल डोमेन (अक्सर समय या स्थान) से [[आवृत्ति डोमेन]] में एक प्रतिनिधित्व में परिवर्तित करता है और इसके विपरीत। विभिन्न आवृत्तियों के घटकों में मूल्यों के अनुक्रम को विघटित करके डीएफटी प्राप्त किया जाता है।<ref name="Heideman_Johnson_Burrus_1984"/>यह संक्रिया कई क्षेत्रों में उपयोगी है, लेकिन सीधे परिभाषा से इसकी गणना करना अक्सर व्यावहारिक होने के लिए बहुत धीमा होता है। एक एफएफटी तेजी से [[मैट्रिक्स अपघटन]] द्वारा [[डीएफटी मैट्रिक्स]] को [[ विरल मैट्रिक्स ]] (ज्यादातर शून्य) कारकों के उत्पाद में इस तरह के परिवर्तनों की गणना करता है।<ref name="Loan_1992"/>नतीजतन, यह डीएफटी की गणना के [[कम्प्यूटेशनल जटिलता सिद्धांत]] को कम करने का प्रबंधन करता है <math display="inline">O\left(N^2\right)</math>, जो उत्पन्न होता है यदि कोई केवल डीएफटी की परिभाषा को लागू करता है <math display="inline">O(N \log N)</math>, कहाँ <math>N</math> डेटा का आकार है। गति में अंतर बहुत अधिक हो सकता है, विशेष रूप से लंबे डेटा सेट के लिए जहां N हजारों या लाखों में हो सकता है। [[राउंड-ऑफ त्रुटि]] की उपस्थिति में, कई एफएफटी एल्गोरिदम प्रत्यक्ष या अप्रत्यक्ष रूप से डीएफटी परिभाषा का मूल्यांकन करने से कहीं अधिक सटीक हैं। प्रकाशित सिद्धांतों की एक विस्तृत श्रृंखला के आधार पर कई अलग-अलग एफएफटी एल्गोरिदम हैं, सरल [[जटिल संख्या]] | जटिल-संख्या अंकगणित से लेकर [[समूह सिद्धांत]] और [[संख्या सिद्धांत]] तक।
+[[File:FFT of Cosine Summation Function.svg|thumb|10, 20, 30, 40, और 50 हर्ट्ज पर कोज्या तरंगों के योग का असतत फूरियर विश्लेषण]]एक तेज़ फूरियर ट्रांसफ़ॉर्म (FFT) एक [[कलन विधि]] है जो एक [[अनुक्रम]] के असतत फूरियर ट्रांसफ़ॉर्म (DFT) या इसके व्युत्क्रम (IDFT) की गणना करता है। [[फूरियर विश्लेषण]] एक संकेत को उसके मूल डोमेन (अधिकांशतः  समय या स्थान) से [[आवृत्ति डोमेन]] में एक प्रतिनिधित्व में परिवर्तित करता है और इसके विपरीत। विभिन्न आवृत्तियों के घटकों में मूल्यों के अनुक्रम को विघटित करके डीएफटी प्राप्त किया जाता है।<ref name="Heideman_Johnson_Burrus_1984"/>यह संक्रिया कई क्षेत्रों में उपयोगी है, किन्तु  सीधे परिभाषा से इसकी गणना करना अधिकांशतः  व्यावहारिक होने के लिए बहुत धीमा होता है। एक एफएफटी तेजी से [[मैट्रिक्स अपघटन]] द्वारा [[डीएफटी मैट्रिक्स]] को [[ विरल मैट्रिक्स ]] (अधिकतर  शून्य) कारकों के उत्पाद में इस तरह के परिवर्तनों की गणना करता है।<ref name="Loan_1992"/>परिणाम स्वरुप  , यह डीएफटी की गणना के [[कम्प्यूटेशनल जटिलता सिद्धांत]] को कम करने का प्रबंधन करता है <math display="inline">O\left(N^2\right)</math>, जो उत्पन्न होता है यदि कोई केवल डीएफटी की परिभाषा को प्रयुक्त  करता है <math display="inline">O(N \log N)</math>, कहाँ <math>N</math> डेटा का आकार है। गति में अंतर बहुत अधिक हो सकता है, विशेष रूप से लंबे डेटा सेट के लिए जहां N हजारों या लाखों में हो सकता है। [[राउंड-ऑफ त्रुटि]] की उपस्थिति में, कई एफएफटी एल्गोरिदम प्रत्यक्ष या अप्रत्यक्ष रूप से डीएफटी परिभाषा का मूल्यांकन करने से कहीं अधिक स्पष्ट  हैं। प्रकाशित सिद्धांतों की एक विस्तृत श्रृंखला के आधार पर कई अलग-अलग एफएफटी एल्गोरिदम हैं, सरल [[जटिल संख्या]] | जटिल-संख्या अंकगणित से लेकर [[समूह सिद्धांत]] और [[संख्या सिद्धांत]] तक।
-[[File:Simple time domain vs frequency domain.svg|thumb|एक ही संकेत का समय-आधारित प्रतिनिधित्व (ऊपर) और आवृत्ति-आधारित प्रतिनिधित्व (नीचे), जहां फूरियर रूपांतरण द्वारा ऊपरी एक से निचला प्रतिनिधित्व प्राप्त किया जा सकता है]]असतत फूरियर रूपांतरण के लिए फास्ट फूरियर रूपांतरण का व्यापक रूप से उपयोग किया जाता है # इंजीनियरिंग, संगीत, विज्ञान और गणित में अनुप्रयोग। बुनियादी विचारों को 1965 में लोकप्रिय बनाया गया था, लेकिन कुछ एल्गोरिदम को 1805 की शुरुआत में ही प्राप्त कर लिया गया था।<ref name="Heideman_Johnson_Burrus_1984"/>1994 में, [[गिल्बर्ट स्ट्रांग]] ने FFT को हमारे जीवनकाल का सबसे महत्वपूर्ण [[संख्यात्मक विश्लेषण]] बताया,<ref name="Strang_1994"/><ref name="Kent_2002"/>और इसे [[IEEE]] पत्रिका कंप्यूटिंग इन साइंस एंड इंजीनियरिंग द्वारा 20वीं शताब्दी के शीर्ष 10 एल्गोरिदम में शामिल किया गया था।<ref name="Dongarra_Sullivan_2000"/>
+[[File:Simple time domain vs frequency domain.svg|thumb|एक ही संकेत का समय-आधारित प्रतिनिधित्व (ऊपर) और आवृत्ति-आधारित प्रतिनिधित्व (नीचे), जहां फूरियर रूपांतरण द्वारा ऊपरी एक से निचला प्रतिनिधित्व प्राप्त किया जा सकता है]]असतत फूरियर रूपांतरण के लिए फास्ट फूरियर रूपांतरण का व्यापक रूप से उपयोग किया जाता है  या  इंजीनियरिंग, संगीत, विज्ञान और गणित में अनुप्रयोग। मूलभूत  विचारों को 1965 में लोकप्रिय बनाया गया था, किन्तु  कुछ एल्गोरिदम को 1805 की प्रारंभिक  में ही प्राप्त कर लिया गया था।<ref name="Heideman_Johnson_Burrus_1984"/>1994 में, [[गिल्बर्ट स्ट्रांग]] ने FFT को हमारे जीवनकाल का सबसे महत्वपूर्ण [[संख्यात्मक विश्लेषण]] बताया,<ref name="Strang_1994"/><ref name="Kent_2002"/>और इसे [[IEEE]] पत्रिका कंप्यूटिंग इन साइंस एंड इंजीनियरिंग द्वारा 20वीं शताब्दी के शीर्ष 10 एल्गोरिदम में सम्मिलित   किया गया था।<ref name="Dongarra_Sullivan_2000"/>
-सबसे प्रसिद्ध एफएफटी एल्गोरिदम एन के [[गुणन]]खंड पर निर्भर करते हैं, लेकिन बिग ओ नोटेशन के साथ एफएफटी हैं। ओ (एन लॉग एन) सभी एन के लिए कम्प्यूटेशनल जटिलता सिद्धांत, यहां तक कि [[अभाज्य संख्या]] एन के लिए भी। कई एफएफटी एल्गोरिदम केवल इस तथ्य पर निर्भर करते हैं कि <math display="inline">e^{-2\pi i/N}</math> एकता का एन-वाँ आदिम मूल है, और इस प्रकार संख्या-सैद्धांतिक रूपांतरण जैसे किसी भी [[परिमित क्षेत्र]] पर अनुरूप परिवर्तनों पर लागू किया जा सकता है। चूंकि उलटा डीएफटी डीएफटी के समान है, लेकिन एक्सपोनेंट में विपरीत चिह्न और 1/एन कारक के साथ, किसी भी एफएफटी एल्गोरिदम को इसके लिए आसानी से अनुकूलित किया जा सकता है।
+सबसे प्रसिद्ध एफएफटी एल्गोरिदम एन के [[गुणन]]खंड पर निर्भर करते हैं, किन्तु  बिग ओ नोटेशन के साथ एफएफटी हैं। ओ (एन लॉग एन) सभी एन के लिए कम्प्यूटेशनल जटिलता सिद्धांत, यहां तक कि [[अभाज्य संख्या]] एन के लिए भी। कई एफएफटी एल्गोरिदम केवल इस तथ्य पर निर्भर करते हैं कि <math display="inline">e^{-2\pi i/N}</math> एकता का एन-वाँ आदिम मूल है, और इस प्रकार संख्या-सैद्धांतिक रूपांतरण जैसे किसी भी [[परिमित क्षेत्र]] पर अनुरूप परिवर्तनों पर प्रयुक्त  किया जा सकता है। चूंकि उलटा डीएफटी डीएफटी के समान है, किन्तु  एक्सपोनेंट में विपरीत चिह्न और 1/एन कारक के साथ, किसी भी एफएफटी एल्गोरिदम को इसके लिए आसानी से अनुकूलित किया जा सकता है।
 == इतिहास ==
-डीएफटी के लिए तेजी से एल्गोरिदम के विकास का पता 1805 में [[कार्ल फ्रेडरिक गॉस]] के अप्रकाशित काम से लगाया जा सकता है, जब उन्हें नमूना अवलोकनों से क्षुद्रग्रहों [[2 पलास]] और [[3 जूनो]] की कक्षा को प्रक्षेपित करने की आवश्यकता थी।<ref name="Gauss_1866"/><ref name="Heideman_Johnson_Burrus_1985"/>उनका तरीका 1965 में [[जेम्स कूली]] और [[जॉन टुकी]] द्वारा प्रकाशित एक के समान था, जिन्हें आम तौर पर आधुनिक जेनेरिक एफएफटी एल्गोरिथम के आविष्कार के लिए श्रेय दिया जाता है। जबकि गॉस का काम 1822 में [[जोसेफ फूरियर]] के परिणामों से भी पहले का था, उन्होंने गणना समय का विश्लेषण नहीं किया और अंततः अपने लक्ष्य को प्राप्त करने के लिए अन्य तरीकों का इस्तेमाल किया।
+डीएफटी के लिए तेजी से एल्गोरिदम के विकास का पता 1805 में [[कार्ल फ्रेडरिक गॉस]] के अप्रकाशित काम से लगाया जा सकता है, जब उन्हें नमूना अवलोकनों से क्षुद्रग्रहों [[2 पलास]] और [[3 जूनो]] की कक्षा को प्रक्षेपित करने की आवश्यकता थी।<ref name="Gauss_1866"/><ref name="Heideman_Johnson_Burrus_1985"/>उनका विधि  1965 में [[जेम्स कूली]] और [[जॉन टुकी]] द्वारा प्रकाशित एक के समान था, जिन्हें सामान्यतः  आधुनिक जेनेरिक एफएफटी एल्गोरिथम के आविष्कार के लिए श्रेय दिया जाता है। जबकि गॉस का काम 1822 में [[जोसेफ फूरियर]] के परिणामों से भी पहले का था, उन्होंने गणना समय का विश्लेषण नहीं किया और अंततः अपने लक्ष्य को प्राप्त करने के लिए अन्य विधि  का उपयोग  किया।
-और 1965 के बीच, FFT के कुछ संस्करण अन्य लेखकों द्वारा प्रकाशित किए गए थे। 1932 में [[फ्रैंक येट्स]] ने इंटरेक्शन एल्गोरिथम नामक अपना संस्करण प्रकाशित किया, जिसने फास्ट वॉल्श-हैडमार्ड रूपांतरण प्रदान किया।<ref name="Yates_1937"/>येट्स का एल्गोरिद्म अभी भी सांख्यिकीय डिजाइन और प्रयोगों के विश्लेषण के क्षेत्र में उपयोग किया जाता है। 1942 में, जी.सी. डेनियलसन और [[कॉर्नेलियस लैंक्ज़ोस]] ने [[ एक्स - रे क्रिस्टलोग्राफी ]] के लिए डीएफटी की गणना करने के लिए अपना संस्करण प्रकाशित किया, एक ऐसा क्षेत्र जहां फूरियर ट्रांसफॉर्म की गणना ने एक दुर्जेय बाधा प्रस्तुत की।<ref name="Danielson_Lanczos_1942"/><ref name="Lanczos_1956"/>जबकि अतीत में कई विधियों ने निरंतर कारक को कम करने पर ध्यान केंद्रित किया था <math display="inline">O\left(N^2\right)</math> समरूपता का लाभ उठाकर गणना, डेनियलसन और लैंक्ज़ोस ने महसूस किया कि कोई भी आवधिकता का उपयोग कर सकता है और <nowiki>[N]</nowiki> को दोगुना करने के लिए दोहरीकरण चाल लागू कर सकता है, हालांकि गॉस की तरह उन्होंने विश्लेषण नहीं किया इसके कारण <math display="inline">O(N \log N)</math> स्केलिंग।<ref name="Cooley_Lewis_Welch_1967"/>
+और 1965 के बीच, FFT के कुछ संस्करण अन्य लेखकों द्वारा प्रकाशित किए गए थे। 1932 में [[फ्रैंक येट्स]] ने इंटरेक्शन एल्गोरिथम नामक अपना संस्करण प्रकाशित किया, जिसने फास्ट वॉल्श-हैडमार्ड रूपांतरण प्रदान किया।<ref name="Yates_1937"/>येट्स का एल्गोरिद्म अभी भी सांख्यिकीय डिजाइन और प्रयोगों के विश्लेषण के क्षेत्र में उपयोग किया जाता है। 1942 में, जी.सी. डेनियलसन और [[कॉर्नेलियस लैंक्ज़ोस]] ने [[ एक्स - रे क्रिस्टलोग्राफी ]] के लिए डीएफटी की गणना करने के लिए अपना संस्करण प्रकाशित किया, एक ऐसा क्षेत्र जहां फूरियर ट्रांसफॉर्म की गणना ने एक दुर्जेय बाधा प्रस्तुत की।<ref name="Danielson_Lanczos_1942"/><ref name="Lanczos_1956"/>जबकि अतीत में कई विधियों ने निरंतर कारक को कम करने पर ध्यान केंद्रित किया था <math display="inline">O\left(N^2\right)</math> समरूपता का लाभ उठाकर गणना, डेनियलसन और लैंक्ज़ोस ने अनुभूत  किया कि कोई भी आवधिकता का उपयोग कर सकता है और <nowiki>[N]</nowiki> को दोगुना करने के लिए दोहरीकरण चाल प्रयुक्त  कर सकता है, चूंकि  गॉस की तरह उन्होंने विश्लेषण नहीं किया इसके कारण <math display="inline">O(N \log N)</math> स्केलिंग।<ref name="Cooley_Lewis_Welch_1967"/>
-James Cooley और John Tukey ने स्वतंत्र रूप से इन पहले के एल्गोरिदम को फिर से खोजा<ref name="Heideman_Johnson_Burrus_1985"/>और 1965 में एक कूली-टुकी एफएफटी एल्गोरिद्म प्रकाशित किया जो तब लागू होता है जब एन समग्र होता है और जरूरी नहीं कि 2 की शक्ति हो, साथ ही विश्लेषण भी करता है <math display="inline">O(N \log N)</math> स्केलिंग।<ref name="Cooley_Tukey_1965"/>राष्ट्रपति केनेडी की विज्ञान सलाहकार समिति की एक बैठक के दौरान तुकी को यह विचार आया, जहां एक चर्चा विषय में देश को बाहर से घेरने के लिए सेंसर स्थापित करके सोवियत संघ द्वारा परमाणु परीक्षणों का पता लगाना शामिल था। इन सेंसरों के आउटपुट का विश्लेषण करने के लिए, एक एफएफटी एल्गोरिथम की आवश्यकता होगी। तुकी के साथ चर्चा में, [[रिचर्ड गारविन]] ने न केवल राष्ट्रीय सुरक्षा समस्याओं के लिए एल्गोरिदम की सामान्य प्रयोज्यता को पहचाना, बल्कि 3-डी क्रिस्टल में स्पिन ओरिएंटेशन की आवधिकता निर्धारित करने के लिए तत्काल रुचि सहित समस्याओं की एक विस्तृत श्रृंखला भी पहचानी। हीलियम -3 का।<ref name="Cooley_1987"/>गारविन ने तुकी का विचार कूली को दिया (दोनों ने थॉमस जे. वाटसन रिसर्च सेंटर | आईबीएम की वाटसन लैब में काम किया) कार्यान्वयन के लिए।<ref name="Garwin_1969"/>Cooley और Tukey ने छह महीने के अपेक्षाकृत कम समय में पेपर प्रकाशित किया।<ref name="Rockmore_2000"/>जैसा कि टुकी ने आईबीएम में काम नहीं किया था, विचार की पेटेंट क्षमता पर संदेह किया गया था और एल्गोरिथ्म सार्वजनिक डोमेन में चला गया, जिसने अगले दशक की कंप्यूटिंग क्रांति के माध्यम से एफएफटी को [[ अंकीय संकेत प्रक्रिया ]] में अपरिहार्य एल्गोरिदम में से एक बना दिया।
+James Cooley और John Tukey ने स्वतंत्र रूप से इन पहले के एल्गोरिदम को फिर से खोजा<ref name="Heideman_Johnson_Burrus_1985"/>और 1965 में एक कूली-टुकी एफएफटी एल्गोरिद्म प्रकाशित किया जो तब प्रयुक्त  होता है जब एन समग्र होता है और आवश्यक  नहीं कि 2 की शक्ति हो, साथ ही विश्लेषण भी करता है <math display="inline">O(N \log N)</math> स्केलिंग।<ref name="Cooley_Tukey_1965"/>राष्ट्रपति केनेडी की विज्ञान सलाहकार समिति की एक बैठक के समय  तुकी को यह विचार आया, जहां एक चर्चा विषय में देश को बाहर से घेरने के लिए सेंसर स्थापित करके सोवियत संघ द्वारा परमाणु परीक्षणों का पता लगाना सम्मिलित   था। इन सेंसरों के आउटपुट का विश्लेषण करने के लिए, एक एफएफटी एल्गोरिथम की आवश्यकता होगी। तुकी के साथ चर्चा में, [[रिचर्ड गारविन]] ने न केवल राष्ट्रीय सुरक्षा समस्याओं के लिए एल्गोरिदम की सामान्य प्रयोज्यता को पहचाना, किंतु  3-डी क्रिस्टल में स्पिन ओरिएंटेशन की आवधिकता निर्धारित करने के लिए तत्काल रुचि सहित समस्याओं की एक विस्तृत श्रृंखला भी पहचानी। हीलियम -3 का।<ref name="Cooley_1987"/>गारविन ने तुकी का विचार कूली को दिया (दोनों ने थॉमस जे. वाटसन रिसर्च सेंटर | आईबीएम की वाटसन लैब में काम किया) कार्यान्वयन के लिए।<ref name="Garwin_1969"/>Cooley और Tukey ने छह महीने के अपेक्षाकृत कम समय में पेपर प्रकाशित किया।<ref name="Rockmore_2000"/>जैसा कि टुकी ने आईबीएम में काम नहीं किया था, विचार की पेटेंट क्षमता पर संदेह किया गया था और एल्गोरिथ्म सार्वजनिक डोमेन में चला गया, जिसने अगले दशक की कंप्यूटिंग क्रांति के माध्यम से एफएफटी को [[ अंकीय संकेत प्रक्रिया ]] में अपरिहार्य एल्गोरिदम में से एक बना दिया।
 == परिभाषा ==
@@ Line 22: / Line 22: @@
 कहाँ <math>e^{i 2\pi/N}</math> एकता का आदिम मूल है {{mvar|N}1 का }वाँ मूल।
-इस परिभाषा का सीधे मूल्यांकन करने की आवश्यकता है <math display="inline">O\left(N^2\right)</math> संचालन: एन आउटपुट एक्स हैं<sub>''k''</sub>, और प्रत्येक आउटपुट के लिए N शब्दों के योग की आवश्यकता होती है। एक FFT समान परिणामों की गणना करने की कोई भी विधि है <math display="inline">O(N \log N)</math> संचालन। सभी ज्ञात एफएफटी एल्गोरिदम के लिए बिग ओ नोटेशन # कंप्यूटर विज्ञान में उपयोग की आवश्यकता होती है<math display="inline">\Theta(N \log N)</math> संचालन, हालांकि इस बात का कोई ज्ञात प्रमाण नहीं है कि कम जटिलता असंभव है।<ref name="Frigo_Johnson_2007"/>
+इस परिभाषा का सीधे मूल्यांकन करने की आवश्यकता है <math display="inline">O\left(N^2\right)</math> संचालन: एन आउटपुट एक्स हैं<sub>''k''</sub>, और प्रत्येक आउटपुट के लिए N शब्दों के योग की आवश्यकता होती है। एक FFT समान परिणामों की गणना करने की कोई भी विधि है <math display="inline">O(N \log N)</math> संचालन। सभी ज्ञात एफएफटी एल्गोरिदम के लिए बिग ओ नोटेशन  या  कंप्यूटर विज्ञान में उपयोग की आवश्यकता होती है<math display="inline">\Theta(N \log N)</math> संचालन, चूंकि  इस बात का कोई ज्ञात प्रमाण नहीं है कि कम जटिलता असंभव है।<ref name="Frigo_Johnson_2007"/>
-एफएफटी की बचत को स्पष्ट करने के लिए, जटिल गुणन और परिवर्धन की गिनती पर विचार करें <math display="inline">N=4096</math> डेटा अंक। डीएफटी की रकम का मूल्यांकन सीधे शामिल है <math display="inline">N^2</math> जटिल गुणन और <math display="inline">N(N-1)</math> जटिल जोड़, जिनमें से <math display="inline">O(N)</math> लगभग 30 मिलियन ऑपरेशन छोड़कर, 1 से गुणा जैसे छोटे ऑपरेशन को हटाकर ऑपरेशन को बचाया जा सकता है। इसके विपरीत, मूलांक-2 #Cooley-Tukey कलन विधि | N a 2 की शक्ति के लिए Cooley-Tukey कलनविधि, केवल के साथ समान परिणाम की गणना कर सकता है। <math display="inline">(N/2)\log_2(N)</math> जटिल गुणन (फिर से, 1 और इसी तरह के गुणन के सरलीकरण की अनदेखी) और <math display="inline">N\log_2(N)</math> जटिल जोड़, कुल मिलाकर लगभग 30,000 ऑपरेशन - प्रत्यक्ष मूल्यांकन की तुलना में एक हजार गुना कम। व्यवहार में, आधुनिक कंप्यूटरों पर वास्तविक प्रदर्शन पर आमतौर पर अंकगणितीय संचालन की गति के अलावा अन्य कारकों का प्रभुत्व होता है और विश्लेषण एक जटिल विषय है (उदाहरण के लिए, फ्रिगो और स्टीवन जी जॉनसन, 2005 देखें)।<ref name="Frigo_Johnson_2005"/>लेकिन से समग्र सुधार <math display="inline">O\left(N^2\right)</math> को <math display="inline">O(N \log N)</math> खंडहर।
+एफएफटी की बचत को स्पष्ट करने के लिए, जटिल गुणन और परिवर्धन की गिनती पर विचार करें <math display="inline">N=4096</math> डेटा अंक। डीएफटी की रकम का मूल्यांकन सीधे सम्मिलित   है <math display="inline">N^2</math> जटिल गुणन और <math display="inline">N(N-1)</math> जटिल जोड़, जिनमें से <math display="inline">O(N)</math> लगभग 30 मिलियन ऑपरेशन छोड़कर, 1 से गुणा जैसे छोटे ऑपरेशन को हटाकर ऑपरेशन को बचाया जा सकता है। इसके विपरीत, मूलांक-2  या Cooley-Tukey कलन विधि | N a 2 की शक्ति के लिए Cooley-Tukey कलनविधि, केवल के साथ समान परिणाम की गणना कर सकता है। <math display="inline">(N/2)\log_2(N)</math> जटिल गुणन (फिर से, 1 और इसी तरह के गुणन के सरलीकरण की अनदेखी) और <math display="inline">N\log_2(N)</math> जटिल जोड़, कुल मिलाकर लगभग 30,000 ऑपरेशन - प्रत्यक्ष मूल्यांकन की तुलना में एक हजार गुना कम। व्यवहार में, आधुनिक कंप्यूटरों पर वास्तविक प्रदर्शन पर सामान्यतः  अंकगणितीय संचालन की गति के अतिरिक्त  अन्य कारकों का प्रभुत्व होता है और विश्लेषण एक जटिल विषय है (उदाहरण के लिए, फ्रिगो और स्टीवन जी जॉनसन, 2005 देखें)।<ref name="Frigo_Johnson_2005"/>किन्तु  से समग्र सुधार <math display="inline">O\left(N^2\right)</math> को <math display="inline">O(N \log N)</math> खंडहर।
 == एल्गोरिदम ==
@@ Line 31: / Line 31: @@
 {{Main|कूली-टकी एफएफटी एल्गोरिथम}}
-अब तक सबसे अधिक इस्तेमाल किया जाने वाला एफएफटी कूली-टुके एल्गोरिथम है। यह एक विभाजन और जीत एल्गोरिथ्म है जो पुनरावर्तन किसी भी [[समग्र संख्या]] आकार के डीएफटी को तोड़ देता है <math display="inline">N = N_1N_2</math> आकार के कई छोटे डीएफटी में <math display="inline">N_1</math> और <math display="inline">N_2</math>, साथ <math>O(N)</math> एकता की जटिल जड़ों द्वारा गुणन को परंपरागत रूप से [[घुमाव कारक]] कहा जाता है (जेंटलमैन और सैंडे के बाद, 1966<ref name="Gentleman_Sande_1966"/>).
+अब तक सबसे अधिक उपयोग  किया जाने वाला एफएफटी कूली-टुके एल्गोरिथम है। यह एक विभाजन और जीत एल्गोरिथ्म है जो पुनरावर्तन किसी भी [[समग्र संख्या]] आकार के डीएफटी को तोड़ देता है <math display="inline">N = N_1N_2</math> आकार के कई छोटे डीएफटी में <math display="inline">N_1</math> और <math display="inline">N_2</math>, साथ <math>O(N)</math> एकता की जटिल जड़ों द्वारा गुणन को परंपरागत रूप से [[घुमाव कारक]] कहा जाता है (जेंटलमैन और सैंडे के बाद, 1966<ref name="Gentleman_Sande_1966"/>).
-इस पद्धति (और एक FFT के सामान्य विचार) को 1965 में Cooley और Tukey के एक प्रकाशन द्वारा लोकप्रिय बनाया गया था,<ref name="Cooley_Tukey_1965"/>लेकिन बाद में इसका पता चला<ref name="Heideman_Johnson_Burrus_1984"/>कि उन दो लेखकों ने स्वतंत्र रूप से 1805 के आसपास कार्ल फ्रेडरिक गॉस को ज्ञात एल्गोरिथम का पुन: आविष्कार किया था<ref name="Gauss_1805"/>(और बाद में सीमित रूपों में कई बार पुनः खोजा गया)।
+इस पद्धति (और एक FFT के सामान्य विचार) को 1965 में Cooley और Tukey के एक प्रकाशन द्वारा लोकप्रिय बनाया गया था,<ref name="Cooley_Tukey_1965"/>किन्तु  बाद में इसका पता चला<ref name="Heideman_Johnson_Burrus_1984"/>कि उन दो लेखकों ने स्वतंत्र रूप से 1805 के आसपास कार्ल फ्रेडरिक गॉस को ज्ञात एल्गोरिथम का पुन: आविष्कार किया था<ref name="Gauss_1805"/>(और बाद में सीमित रूपों में कई बार पुनः खोजा गया)।
-कूली-टुकी एल्गोरिदम का सबसे अच्छा ज्ञात उपयोग प्रत्येक चरण में आकार एन/2 के दो टुकड़ों में परिवर्तन को विभाजित करना है, और इसलिए दो आकारों की शक्ति तक सीमित है, लेकिन सामान्य रूप से किसी भी कारक का उपयोग किया जा सकता है (जैसा था) गॉस और कूली/टकी दोनों के लिए जाना जाता है<ref name="Heideman_Johnson_Burrus_1984"/>). इन्हें क्रमशः रेडिक्स-2 और मिश्रित-रेडिक्स केस कहा जाता है (और अन्य वेरिएंट जैसे [[स्प्लिट-रेडिक्स एफएफटी]] के अपने नाम भी हैं)। हालांकि मूल विचार पुनरावर्ती है, अधिकांश पारंपरिक कार्यान्वयन स्पष्ट पुनरावर्तन से बचने के लिए एल्गोरिथम को पुनर्व्यवस्थित करते हैं। इसके अलावा, क्योंकि Cooley-Tukey एल्गोरिथ्म DFT को छोटे DFTs में तोड़ता है, इसे DFT के लिए किसी भी अन्य एल्गोरिथ्म के साथ मनमाने ढंग से जोड़ा जा सकता है, जैसे कि नीचे वर्णित।
+कूली-टुकी एल्गोरिदम का सबसे अच्छा ज्ञात उपयोग प्रत्येक चरण में आकार एन/2 के दो टुकड़ों में परिवर्तन को विभाजित करना है, और इसलिए दो आकारों की शक्ति तक सीमित है, किन्तु  सामान्य रूप से किसी भी कारक का उपयोग किया जा सकता है (जैसा था) गॉस और कूली/टकी दोनों के लिए जाना जाता है<ref name="Heideman_Johnson_Burrus_1984"/>). इन्हें क्रमशः रेडिक्स-2 और मिश्रित-रेडिक्स केस कहा जाता है (और अन्य वेरिएंट जैसे [[स्प्लिट-रेडिक्स एफएफटी]] के अपने नाम भी हैं)। चूंकि  मूल विचार पुनरावर्ती है, अधिकांश पारंपरिक कार्यान्वयन स्पष्ट पुनरावर्तन से बचने के लिए एल्गोरिथम को पुनर्व्यवस्थित करते हैं। इसके अतिरिक्त , क्योंकि Cooley-Tukey एल्गोरिथ्म DFT को छोटे DFTs में तोड़ता है, इसे DFT के लिए किसी भी अन्य एल्गोरिथ्म के साथ इच्छानुसार से जोड़ा जा सकता है, जैसे कि नीचे वर्णित।
 === अन्य एफएफटी एल्गोरिदम ===
 {{Main|प्राइम-फैक्टर एफएफटी एल्गोरिथम|ब्रून का एफएफटी एल्गोरिदम|राडार का एफएफटी एल्गोरिदम|चिरप जेड-रूपांतरण|हेक्सागोनल फास्ट फूरियर रूपांतरण}}
-Cooley-Tukey के अलावा अन्य FFT एल्गोरिदम भी हैं।
+Cooley-Tukey के अतिरिक्त  अन्य FFT एल्गोरिदम भी हैं।
-एन = एन के लिए<sub>1</sub>N<sub>2</sub> [[सह अभाज्य]] एन के साथ<sub>1</sub> और n<sub>2</sub>, कोई भी [[प्राइम-फैक्टर एफएफटी एल्गोरिथम]] | प्राइम-फैक्टर (गुड-थॉमस) एल्गोरिथम (पीएफए) का उपयोग कर सकता है, [[चीनी शेष प्रमेय]] के आधार पर, कूली-टुकी के समान डीएफटी को कारक बनाने के लिए लेकिन ट्वीडल कारकों के बिना। रेडर-ब्रेनर एल्गोरिथम (1976)<ref name="Brenner_Rader_1976"/>एक Cooley-Tukey- जैसा गुणनखंडन है, लेकिन विशुद्ध रूप से काल्पनिक ट्वीडल कारकों के साथ, बढ़े हुए परिवर्धन और कम [[संख्यात्मक स्थिरता]] की कीमत पर गुणन को कम करना; इसे बाद में [[स्प्लिट-रेडिक्स एफएफटी एल्गोरिथम]] | कूली-टुकी के स्प्लिट-रेडिक्स वेरिएंट द्वारा हटा दिया गया था (जो समान गुणन गणना प्राप्त करता है लेकिन कम परिवर्धन के साथ और सटीकता का त्याग किए बिना)। एल्गोरिथम जो डीएफटी के अलावा अन्य छोटे कार्यों में डीएफटी को पुनरावर्ती रूप से कारक बनाते हैं, उनमें ब्रून और [[त्वरित फूरियर रूपांतरण एल्गोरिथम]] एल्गोरिदम शामिल हैं। (द रेडर-ब्रेनर<ref name="Brenner_Rader_1976"/>और QFT एल्गोरिदम को दो आकारों की शक्ति के लिए प्रस्तावित किया गया था, लेकिन यह संभव है कि उन्हें सामान्य मिश्रित N के लिए अनुकूलित किया जा सकता है। FFT को [[बहुपद]] z के पुनरावर्ती गुणनखंडन के रूप में व्याख्या करना<sup>N</sup> − 1, यहाँ z के रूप के वास्तविक-गुणांक बहुपदों में<sup>एम</sup> − 1 और z<sup>2M + अज़<sup>एम</sup> + 1.
+एन = एन के लिए<sub>1</sub>N<sub>2</sub> [[सह अभाज्य]] एन के साथ<sub>1</sub> और n<sub>2</sub>, कोई भी [[प्राइम-फैक्टर एफएफटी एल्गोरिथम]] | प्राइम-फैक्टर (गुड-थॉमस) एल्गोरिथम (पीएफए) का उपयोग कर सकता है, [[चीनी शेष प्रमेय]] के आधार पर, कूली-टुकी के समान डीएफटी को कारक बनाने के लिए किन्तु  ट्वीडल कारकों के बिना। रेडर-ब्रेनर एल्गोरिथम (1976)<ref name="Brenner_Rader_1976"/>एक Cooley-Tukey- जैसा गुणनखंडन है, किन्तु  विशुद्ध रूप से काल्पनिक ट्वीडल कारकों के साथ, बढ़े हुए परिवर्धन और कम [[संख्यात्मक स्थिरता]] की कीमत पर गुणन को कम करना; इसे बाद में [[स्प्लिट-रेडिक्स एफएफटी एल्गोरिथम]] | कूली-टुकी के स्प्लिट-रेडिक्स वेरिएंट द्वारा हटा दिया गया था (जो समान गुणन गणना प्राप्त करता है किन्तु  कम परिवर्धन के साथ और स्पष्ट ता का त्याग किए बिना)। एल्गोरिथम जो डीएफटी के अतिरिक्त  अन्य छोटे कार्यों में डीएफटी को पुनरावर्ती रूप से कारक बनाते हैं, उनमें ब्रून और [[त्वरित फूरियर रूपांतरण एल्गोरिथम]] एल्गोरिदम सम्मिलित   हैं। (द रेडर-ब्रेनर<ref name="Brenner_Rader_1976"/>और QFT एल्गोरिदम को दो आकारों की शक्ति के लिए प्रस्तावित किया गया था, किन्तु  यह संभव है कि उन्हें सामान्य मिश्रित N के लिए अनुकूलित किया जा सकता है। FFT को [[बहुपद]] z के पुनरावर्ती गुणनखंडन के रूप में व्याख्या करना<sup>N</sup> − 1, यहाँ z के रूप के वास्तविक-गुणांक बहुपदों में<sup>एम</sup> − 1 और z<sup>2M + अज़<sup>एम</sup> + 1.
-विनोग्रैड एफएफटी एल्गोरिथम द्वारा एक अन्य बहुपद दृष्टिकोण का उपयोग किया जाता है,<ref name="Winograd_1978"/><ref name="Winograd_1979"/>जो z का गुणनखंड करता है<sup>N</sup> − 1 [[साइक्लोटोमिक बहुपद]]ों में—इनमें अक्सर 1, 0, या −1 के गुणांक होते हैं, और इसलिए कुछ (यदि कोई हो) गुणन की आवश्यकता होती है, इसलिए विनोग्रैड का उपयोग न्यूनतम-गुणन FFTs प्राप्त करने के लिए किया जा सकता है और अक्सर इसका उपयोग किया जाता है छोटे कारकों के लिए कुशल एल्गोरिदम खोजें। दरअसल, विनोग्रैड ने दिखाया कि डीएफटी की गणना केवल ओ (एन) अपरिमेय गुणन के साथ की जा सकती है, जिससे दो आकारों की शक्ति के लिए गुणन की संख्या पर एक सिद्ध प्राप्त करने योग्य निचली सीमा होती है; दुर्भाग्य से, यह कई और परिवर्धन की कीमत पर आता है, [[फ्लोटिंग-पॉइंट यूनिट]] के साथ आधुनिक [[सेंट्रल प्रोसेसिंग यूनिट]] पर एक ट्रेडऑफ़ अब अनुकूल नहीं है। विशेष रूप से, विनोग्रैड पीएफए के साथ-साथ प्राइम साइज के एफएफटी के लिए राडार द्वारा एल्गोरिदम का भी उपयोग करता है।
+विनोग्रैड एफएफटी एल्गोरिथम द्वारा एक अन्य बहुपद दृष्टिकोण का उपयोग किया जाता है,<ref name="Winograd_1978"/><ref name="Winograd_1979"/>जो z का गुणनखंड करता है<sup>N</sup> − 1 [[साइक्लोटोमिक बहुपद]]ों में—इनमें अधिकांशतः  1, 0, या −1 के गुणांक होते हैं, और इसलिए कुछ (यदि कोई हो) गुणन की आवश्यकता होती है, इसलिए विनोग्रैड का उपयोग न्यूनतम-गुणन FFTs प्राप्त करने के लिए किया जा सकता है और अधिकांशतः  इसका उपयोग किया जाता है छोटे कारकों के लिए कुशल एल्गोरिदम खोजें। दरअसल, विनोग्रैड ने दिखाया कि डीएफटी की गणना केवल ओ (एन) अपरिमेय गुणन के साथ की जा सकती है, जिससे दो आकारों की शक्ति के लिए गुणन की संख्या पर एक सिद्ध प्राप्त करने योग्य निचली सीमा होती है; दुर्भाग्य से, यह कई और परिवर्धन की कीमत पर आता है, [[फ्लोटिंग-पॉइंट यूनिट]] के साथ आधुनिक [[सेंट्रल प्रोसेसिंग यूनिट]] पर एक ट्रेडऑफ़ अब अनुकूल नहीं है। विशेष रूप से, विनोग्रैड पीएफए के साथ-साथ प्राइम साइज के एफएफटी के लिए राडार द्वारा एल्गोरिदम का भी उपयोग करता है।
-राडार का एफएफटी एल्गोरिद्म|राडर का एल्गोरिद्म गुणक [[समूह (गणित)]] मॉडुलो प्राइम एन के लिए एक समूह के जनरेटिंग सेट के अस्तित्व का शोषण करते हुए, अभाज्य आकार एन के एक डीएफटी को (मिश्रित) आकार एन - 1 के चक्रीय [[कनवल्शन]] के रूप में व्यक्त करता है, जो कर सकता है फिर [[कनवल्शन प्रमेय]] के माध्यम से साधारण एफएफटी की एक जोड़ी द्वारा गणना की जाती है (हालांकि विनोग्रैड अन्य कनवल्शन विधियों का उपयोग करता है)। एक अन्य प्राइम-साइज़ एफएफटी एल. आई. ब्लूस्टीन के कारण है, और कभी-कभी इसे [[चिरप-जेड एल्गोरिदम]] कहा जाता है; यह एक डीएफटी को कनवल्शन के रूप में फिर से व्यक्त करता है, लेकिन इस बार एक ही आकार का (जो [[दो की शक्ति]] के लिए शून्य-गद्देदार हो सकता है और रेडिक्स -2 कूली-तुकी एफएफटी द्वारा मूल्यांकन किया जा सकता है, उदाहरण के लिए), पहचान के माध्यम से
+राडार का एफएफटी एल्गोरिद्म|राडर का एल्गोरिद्म गुणक [[समूह (गणित)]] मॉडुलो प्राइम एन के लिए एक समूह के जनरेटिंग सेट के अस्तित्व का शोषण करते हुए, अभाज्य आकार एन के एक डीएफटी को (मिश्रित) आकार एन - 1 के चक्रीय [[कनवल्शन]] के रूप में व्यक्त करता है, जो कर सकता है फिर [[कनवल्शन प्रमेय]] के माध्यम से साधारण एफएफटी की एक जोड़ी द्वारा गणना की जाती है (चूंकि  विनोग्रैड अन्य कनवल्शन विधियों का उपयोग करता है)। एक अन्य प्राइम-साइज़ एफएफटी एल. आई. ब्लूस्टीन के कारण है, और कभी-कभी इसे [[चिरप-जेड एल्गोरिदम]] कहा जाता है; यह एक डीएफटी को कनवल्शन के रूप में फिर से व्यक्त करता है, किन्तु  इस बार एक ही आकार का (जो [[दो की शक्ति]] के लिए शून्य-गद्देदार हो सकता है और रेडिक्स -2 कूली-तुकी एफएफटी द्वारा मूल्यांकन किया जा सकता है, उदाहरण के लिए), पहचान के माध्यम से
 : <math>nk = -\frac{(k-n)^2} 2 + \frac{n^2} 2 + \frac{k^2} 2.</math>
@@ Line 52: / Line 52: @@
 == एफएफटी एल्गोरिदम वास्तविक या सममित डेटा == के लिए विशेष
-कई अनुप्रयोगों में, डीएफटी के लिए इनपुट डेटा विशुद्ध रूप से वास्तविक होते हैं, इस मामले में आउटपुट समरूपता को संतुष्ट करते हैं
+कई अनुप्रयोगों में, डीएफटी के लिए इनपुट डेटा विशुद्ध रूप से वास्तविक होते हैं, इस स्थितियों  में आउटपुट समरूपता को संतुष्ट करते हैं
 :<math>X_{N-k} = X_k^*</math>
-और कुशल एफएफटी एल्गोरिदम इस स्थिति के लिए डिजाइन किए गए हैं (उदाहरण के लिए सोरेनसेन, 1987 देखें)।<ref name="Sorensen_Jones_Heideman_Burrus_1987_1"/><ref name="Sorensen_Jones_Heideman_Burrus_1987_2"/>एक दृष्टिकोण में एक सामान्य एल्गोरिथ्म (जैसे कूली-टुके) लेना और गणना के अनावश्यक भागों को निकालना शामिल है, समय और स्मृति में मोटे तौर पर दो का एक कारक बचाता है। वैकल्पिक रूप से, एक सम-लंबाई वाले वास्तविक-इनपुट डीएफटी को आधी लंबाई के एक जटिल डीएफटी के रूप में व्यक्त करना संभव है (जिसके वास्तविक और काल्पनिक भाग मूल वास्तविक डेटा के सम/विषम तत्व हैं), इसके बाद ओ (एन) पोस्ट- प्रसंस्करण संचालन।
+और कुशल एफएफटी एल्गोरिदम इस स्थिति के लिए डिजाइन किए गए हैं (उदाहरण के लिए सोरेनसेन, 1987 देखें)।<ref name="Sorensen_Jones_Heideman_Burrus_1987_1"/><ref name="Sorensen_Jones_Heideman_Burrus_1987_2"/>एक दृष्टिकोण में एक सामान्य एल्गोरिथ्म (जैसे कूली-टुके) लेना और गणना के अनावश्यक भागों को निकालना सम्मिलित   है, समय और स्मृति में मोटे तौर पर दो का एक कारक बचाता है। वैकल्पिक रूप से, एक सम-लंबाई वाले वास्तविक-इनपुट डीएफटी को आधी लंबाई के एक जटिल डीएफटी के रूप में व्यक्त करना संभव है (जिसके वास्तविक और काल्पनिक भाग मूल वास्तविक डेटा के सम/विषम तत्व हैं), इसके बाद ओ (एन) पोस्ट- प्रसंस्करण संचालन।
-एक बार यह माना जाता था कि असतत हार्टले ट्रांसफ़ॉर्म (DHT) के माध्यम से वास्तविक-इनपुट DFTs की अधिक कुशलता से गणना की जा सकती है, लेकिन बाद में यह तर्क दिया गया कि एक विशेष वास्तविक-इनपुट DFT एल्गोरिथम (FFT) आमतौर पर पाया जा सकता है जिसके लिए कम संचालन की आवश्यकता होती है समान संख्या में इनपुट के लिए संबंधित DHT एल्गोरिथम (FHT)।<ref name="Sorensen_Jones_Heideman_Burrus_1987_1"/>ब्रून का एल्गोरिथम (ऊपर) एक और तरीका है जिसे शुरू में वास्तविक इनपुट का लाभ उठाने के लिए प्रस्तावित किया गया था, लेकिन यह लोकप्रिय साबित नहीं हुआ है।
+एक बार यह माना जाता था कि असतत हार्टले ट्रांसफ़ॉर्म (DHT) के माध्यम से वास्तविक-इनपुट DFTs की अधिक कुशलता से गणना की जा सकती है, किन्तु  बाद में यह तर्क दिया गया कि एक विशेष वास्तविक-इनपुट DFT एल्गोरिथम (FFT) सामान्यतः  पाया जा सकता है जिसके लिए कम संचालन की आवश्यकता होती है समान संख्या में इनपुट के लिए संबंधित DHT एल्गोरिथम (FHT)।<ref name="Sorensen_Jones_Heideman_Burrus_1987_1"/>ब्रून का एल्गोरिथम (ऊपर) एक और विधि  है जिसे प्रारंभ में वास्तविक इनपुट का लाभ उठाने के लिए प्रस्तावित किया गया था, किन्तु  यह लोकप्रिय सिद्ध  नहीं हुआ है।
-वास्तविक डेटा के मामलों के लिए और भी एफएफटी विशेषज्ञताएं हैं जिनमें सम और विषम कार्य हैं। | साइन ट्रांसफॉर्म (एस) (असतत कोसाइन ट्रांसफॉर्म/असतत साइन ट्रांसफॉर्म)। इन मामलों के लिए एफएफटी एल्गोरिदम को सीधे संशोधित करने के बजाय, डीसीटी/डीएसटी को ओ (एन) प्री- और पोस्ट-प्रोसेसिंग के साथ संयुक्त वास्तविक डेटा के एफएफटी के माध्यम से भी गणना की जा सकती है।
+वास्तविक डेटा के स्थितियों  के लिए और भी एफएफटी विशेषज्ञताएं हैं जिनमें सम और विषम कार्य हैं। | साइन ट्रांसफॉर्म (एस) (असतत कोसाइन ट्रांसफॉर्म/असतत साइन ट्रांसफॉर्म)। इन स्थितियों  के लिए एफएफटी एल्गोरिदम को सीधे संशोधित करने के अतिरिक्त , डीसीटी/डीएसटी को ओ (एन) प्री- और पोस्ट-प्रोसेसिंग के साथ संयुक्त वास्तविक डेटा के एफएफटी के माध्यम से भी गणना की जा सकती है।
 == कम्प्यूटेशनल मुद्दे ==
@@ Line 65: / Line 65: @@
 === जटिलता और संचालन की सीमा ===
 {{unsolved|computer science|What is the lower bound on the complexity of fast Fourier transform algorithms?  Can they be faster than <math>O(N\log N)</math>?}}
-लंबे समय से चली आ रही सैद्धांतिक रुचि का एक मूलभूत प्रश्न कम्प्यूटेशनल जटिलता सिद्धांत और तेजी से फूरियर रूपांतरणों की सटीक संचालन गणनाओं पर निचली सीमा को साबित करना है, और कई खुली समस्याएं बनी हुई हैं। यह दृढ़ता से साबित नहीं हुआ है कि डीएफटी को वास्तव में आवश्यकता है या नहीं <math display="inline">\Omega(N \log N)</math> (यानी, आदेश<math>N \log N</math>या अधिक) संचालन, दो आकारों की शक्ति के साधारण मामले के लिए भी, हालांकि कम जटिलता वाले एल्गोरिदम ज्ञात नहीं हैं। विशेष रूप से, अंकगणितीय संक्रियाओं की गणना आमतौर पर ऐसे प्रश्नों का फोकस होती है, हालांकि आधुनिक समय के कंप्यूटरों पर वास्तविक प्रदर्शन [[कैश (कंप्यूटिंग)]] या [[पाइपलाइन (कंप्यूटिंग)]] अनुकूलन जैसे कई अन्य कारकों द्वारा निर्धारित किया जाता है।
+लंबे समय से चली आ रही सैद्धांतिक रुचि का एक मूलभूत प्रश्न कम्प्यूटेशनल जटिलता सिद्धांत और तेजी से फूरियर रूपांतरणों की स्पष्ट  संचालन गणनाओं पर निचली सीमा को सिद्ध  करना है, और कई खुली समस्याएं बनी हुई हैं। यह दृढ़ता से सिद्ध  नहीं हुआ है कि डीएफटी को वास्तव में आवश्यकता है या नहीं <math display="inline">\Omega(N \log N)</math> (अर्थात , आदेश<math>N \log N</math>या अधिक) संचालन, दो आकारों की शक्ति के साधारण स्थितियों े के लिए भी, चूंकि  कम जटिलता वाले एल्गोरिदम ज्ञात नहीं हैं। विशेष रूप से, अंकगणितीय संक्रियाओं की गणना सामान्यतः  ऐसे प्रश्नों का फोकस होती है, चूंकि  आधुनिक समय के कंप्यूटरों पर वास्तविक प्रदर्शन [[कैश (कंप्यूटिंग)]] या [[पाइपलाइन (कंप्यूटिंग)]] अनुकूलन जैसे कई अन्य कारकों द्वारा निर्धारित किया जाता है।
-[[शमूएल विनोग्राद]] (1978) द्वारा निम्नलिखित कार्य,<ref name="Winograd_1978"/>एक तंग Θ(N) निचली सीमा को FFT द्वारा आवश्यक वास्तविक गुणन की संख्या के लिए जाना जाता है। इसे ही दिखाया जा सकता है <math display="inline">4N - 2\log_2^2(N) - 2\log_2(N) - 4</math> दो लंबाई की शक्ति के डीएफटी की गणना करने के लिए तर्कहीन वास्तविक गुणन की आवश्यकता होती है <math>N = 2^m</math>. इसके अलावा, इस गणना को प्राप्त करने वाले स्पष्ट एल्गोरिदम ज्ञात हैं (हेइडमैन और [[चार्ल्स सिडनी बुरस]], 1986;<ref name="Heideman_Burrus_1986"/>डुहामेल, 1990<ref name="Duhamel_1990"/>). हालाँकि, इन एल्गोरिदम को व्यावहारिक होने के लिए बहुत अधिक परिवर्धन की आवश्यकता होती है, कम से कम आधुनिक कंप्यूटरों पर हार्डवेयर मल्टीप्लायरों के साथ (डुहामेल, 1990;<ref name="Duhamel_1990"/>फ्रिगो और स्टीवन जी जॉनसन, 2005)।<ref name="Frigo_Johnson_2005"/>
+[[शमूएल विनोग्राद]] (1978) द्वारा निम्नलिखित कार्य,<ref name="Winograd_1978"/>एक तंग Θ(N) निचली सीमा को FFT द्वारा आवश्यक वास्तविक गुणन की संख्या के लिए जाना जाता है। इसे ही दिखाया जा सकता है <math display="inline">4N - 2\log_2^2(N) - 2\log_2(N) - 4</math> दो लंबाई की शक्ति के डीएफटी की गणना करने के लिए तर्कहीन वास्तविक गुणन की आवश्यकता होती है <math>N = 2^m</math>. इसके अतिरिक्त , इस गणना को प्राप्त करने वाले स्पष्ट एल्गोरिदम ज्ञात हैं (हेइडमैन और [[चार्ल्स सिडनी बुरस]], 1986;<ref name="Heideman_Burrus_1986"/>डुहामेल, 1990<ref name="Duhamel_1990"/>). चूंकि , इन एल्गोरिदम को व्यावहारिक होने के लिए बहुत अधिक परिवर्धन की आवश्यकता होती है, कम से कम आधुनिक कंप्यूटरों पर हार्डवेयर मल्टीप्लायरों के साथ (डुहामेल, 1990;<ref name="Duhamel_1990"/>फ्रिगो और स्टीवन जी जॉनसन, 2005)।<ref name="Frigo_Johnson_2005"/>
-आवश्यक योगों की संख्या पर एक तंग निचली सीमा ज्ञात नहीं है, हालांकि एल्गोरिदम पर कुछ प्रतिबंधात्मक धारणाओं के तहत निचली सीमाएं साबित हुई हैं। 1973 में, मॉर्गनस्टर्न<ref name="Morgenstern_1973"/>एक साबित हुआ <math>\Omega(N \log N)</math> एल्गोरिदम के लिए अतिरिक्त गिनती पर निचली सीमा जहां गुणक स्थिरांक ने परिमाण को सीमित कर दिया है (जो अधिकांश के लिए सही है, लेकिन सभी एफएफटी एल्गोरिदम के लिए नहीं)। [[विक्टर पैन]] (1986)<ref name="Pan_1986"/>एक साबित हुआ <math>\Omega(N \log N)</math> एफएफटी एल्गोरिथम की अतुल्यकालिकता के माप पर एक सीमा मानते हुए निचली सीमा, लेकिन इस धारणा की व्यापकता स्पष्ट नहीं है। दो N की शक्ति के मामले में, [[क्रिस्टोस पापादिमित्रिउ]] (1979)<ref name="Papadimitriou_1979"/>तर्क दिया कि संख्या <math display="inline">N \log_2 N</math> कूली-टुकी एल्गोरिदम द्वारा प्राप्त जटिल-संख्या परिवर्धन एल्गोरिथम के [[ग्राफ (असतत गणित)]] पर कुछ मान्यताओं के तहत इष्टतम है (अन्य बातों के अलावा, उनकी धारणाएं, कि एकता की जड़ों में कोई योगात्मक पहचान का शोषण नहीं किया जाता है)। (इस तर्क का अर्थ यह होगा कि कम से कम <math display="inline">2N \log_2 N</math> वास्तविक जोड़ आवश्यक हैं, हालांकि यह एक तंग सीमा नहीं है क्योंकि जटिल-संख्या गुणन के भाग के रूप में अतिरिक्त जोड़ आवश्यक हैं।) इस प्रकार अब तक, किसी भी प्रकाशित एफएफटी एल्गोरिदम ने इससे कम हासिल नहीं किया है <math display="inline">N \log_2 N</math> दो N की शक्ति के लिए सम्मिश्र-संख्या जोड़ (या उनके समतुल्य)।
+आवश्यक योगों की संख्या पर एक तंग निचली सीमा ज्ञात नहीं है, चूंकि  एल्गोरिदम पर कुछ प्रतिबंधात्मक धारणाओं के अनुसार   निचली सीमाएं सिद्ध  हुई हैं। 1973 में, मॉर्गनस्टर्न<ref name="Morgenstern_1973"/>एक सिद्ध  हुआ <math>\Omega(N \log N)</math> एल्गोरिदम के लिए अतिरिक्त गिनती पर निचली सीमा जहां गुणक स्थिरांक ने परिमाण को सीमित कर दिया है (जो अधिकांश के लिए सही है, किन्तु  सभी एफएफटी एल्गोरिदम के लिए नहीं)। [[विक्टर पैन]] (1986)<ref name="Pan_1986"/>एक सिद्ध  हुआ <math>\Omega(N \log N)</math> एफएफटी एल्गोरिथम की अतुल्यकालिकता के माप पर एक सीमा मानते हुए निचली सीमा, किन्तु  इस धारणा की व्यापकता स्पष्ट नहीं है। दो N की शक्ति के स्थितियों  में, [[क्रिस्टोस पापादिमित्रिउ]] (1979)<ref name="Papadimitriou_1979"/>तर्क दिया कि संख्या <math display="inline">N \log_2 N</math> कूली-टुकी एल्गोरिदम द्वारा प्राप्त जटिल-संख्या परिवर्धन एल्गोरिथम के [[ग्राफ (असतत गणित)]] पर कुछ मान्यताओं के अनुसार   इष्टतम है (अन्य बातों के अतिरिक्त , उनकी धारणाएं, कि एकता की जड़ों में कोई योगात्मक पहचान का शोषण नहीं किया जाता है)। (इस तर्क का अर्थ यह होगा कि कम से कम <math display="inline">2N \log_2 N</math> वास्तविक जोड़ आवश्यक हैं, चूंकि  यह एक तंग सीमा नहीं है क्योंकि जटिल-संख्या गुणन के भाग के रूप में अतिरिक्त जोड़ आवश्यक हैं।) इस प्रकार अब तक, किसी भी प्रकाशित एफएफटी एल्गोरिदम ने इससे कम प्राप्त  नहीं किया है <math display="inline">N \log_2 N</math> दो N की शक्ति के लिए सम्मिश्र-संख्या जोड़ (या उनके समतुल्य)।
-एक तीसरी समस्या वास्तविक गुणन और परिवर्धन की कुल संख्या को कम करना है, जिसे कभी-कभी अंकगणितीय जटिलता कहा जाता है (हालांकि इस संदर्भ में यह सटीक गणना है और स्पर्शोन्मुख जटिलता नहीं है जिसे माना जा रहा है)। फिर से, कोई तंग निचली सीमा सिद्ध नहीं हुई है। हालांकि, 1968 के बाद से, स्प्लिट-रेडिक्स एफएफटी एल्गोरिथम द्वारा पावर-ऑफ-टू एन के लिए सबसे कम प्रकाशित गिनती लंबे समय तक हासिल की गई थी, जिसके लिए आवश्यक है <math display="inline">4N\log_2(N) - 6N + 8</math> N > 1 के लिए वास्तविक गुणन और परिवर्धन। इसे हाल ही में घटाकर <math display="inline">\sim \frac{34}{9} N \log_2 N</math> (जॉनसन और फ्रिगो, 2007;<ref name="Frigo_Johnson_2007"/>लुंडी और वैन बुस्कर्क, 2007<ref name="Lundy_Buskirk_2007"/>). थोड़ी बड़ी गिनती (लेकिन फिर भी एन ≥ 256 के लिए स्प्लिट रेडिक्स से बेहतर) संभावित एल्गोरिदम पर अतिरिक्त प्रतिबंधों के तहत एन ≤ 512 के लिए उपयुक्त रूप से इष्टतम दिखाया गया था (यूनिट-मॉड्यूलस गुणक कारकों के साथ स्प्लिट-रेडिक्स-जैसे फ्लोग्राफ), कमी से [[थकावट से सबूत]] द्वारा हल करने योग्य एक संतुष्टि मॉडुलो सिद्धांतों की समस्या (हेनल और हेनल, 2011)।<ref name="Haynal_2011"/>
+एक तीसरी समस्या वास्तविक गुणन और परिवर्धन की कुल संख्या को कम करना है, जिसे कभी-कभी अंकगणितीय जटिलता कहा जाता है (चूंकि  इस संदर्भ में यह स्पष्ट  गणना है और स्पर्शोन्मुख जटिलता नहीं है जिसे माना जा रहा है)। फिर से, कोई तंग निचली सीमा सिद्ध नहीं हुई है। चूंकि , 1968 के बाद से, स्प्लिट-रेडिक्स एफएफटी एल्गोरिथम द्वारा पावर-ऑफ-टू एन के लिए सबसे कम प्रकाशित गिनती लंबे समय तक प्राप्त  की गई थी, जिसके लिए आवश्यक है <math display="inline">4N\log_2(N) - 6N + 8</math> N > 1 के लिए वास्तविक गुणन और परिवर्धन। इसे हाल ही में घटाकर <math display="inline">\sim \frac{34}{9} N \log_2 N</math> (जॉनसन और फ्रिगो, 2007;<ref name="Frigo_Johnson_2007"/>लुंडी और वैन बुस्कर्क, 2007<ref name="Lundy_Buskirk_2007"/>). थोड़ी बड़ी गिनती (किन्तु  फिर भी एन ≥ 256 के लिए स्प्लिट रेडिक्स से बढ़िया ) संभावित एल्गोरिदम पर अतिरिक्त प्रतिबंधों के अनुसार   एन ≤ 512 के लिए उपयुक्त रूप से इष्टतम दिखाया गया था (यूनिट-मॉड्यूलस गुणक कारकों के साथ स्प्लिट-रेडिक्स-जैसे फ्लोग्राफ), कमी से [[थकावट से सबूत|थकावट से प्रमाण]]  द्वारा हल करने योग्य एक संतुष्टि मॉडुलो सिद्धांतों की समस्या (हेनल और हेनल, 2011)।<ref name="Haynal_2011"/>
-एफएफटी एल्गोरिदम की जटिलता को कम करने या साबित करने के अधिकांश प्रयासों ने साधारण जटिल-डेटा केस पर ध्यान केंद्रित किया है, क्योंकि यह सबसे सरल है। हालांकि, जटिल-डेटा एफएफटी वास्तविक-डेटा एफएफटी, असतत कोज्या रूपांतरण, असतत हार्टले रूपांतरण, और इसी तरह से संबंधित समस्याओं के लिए एल्गोरिदम से इतने निकट से संबंधित हैं, कि इनमें से किसी एक में सुधार से दूसरों में तुरंत सुधार होगा ( डुहामेल और वेटरली, 1990)।<ref name="Duhamel_Vetterli_1990"/>
+एफएफटी एल्गोरिदम की जटिलता को कम करने या सिद्ध  करने के अधिकांश प्रयासों ने साधारण जटिल-डेटा केस पर ध्यान केंद्रित किया है, क्योंकि यह सबसे सरल है। चूंकि , जटिल-डेटा एफएफटी वास्तविक-डेटा एफएफटी, असतत कोज्या रूपांतरण, असतत हार्टले रूपांतरण, और इसी तरह से संबंधित समस्याओं के लिए एल्गोरिदम से इतने निकट से संबंधित हैं, कि इनमें से किसी एक में सुधार से दूसरों में तुरंत सुधार होगा ( डुहामेल और वेटरली, 1990)।<ref name="Duhamel_Vetterli_1990"/>
 === सन्निकटन ===
-ऊपर चर्चा किए गए सभी एफएफटी एल्गोरिदम डीएफटी की सटीक गणना करते हैं (यानी [[ तैरनेवाला स्थल ]] त्रुटियों की उपेक्षा)। हालांकि, कुछ एफएफटी एल्गोरिदम प्रस्तावित किए गए हैं, जो डीएफटी की लगभग गणना करते हैं, एक त्रुटि के साथ जिसे बढ़ी हुई संगणनाओं की कीमत पर मनमाने ढंग से छोटा किया जा सकता है। ऐसे एल्गोरिदम बढ़ी हुई गति या अन्य गुणों के लिए सन्निकटन त्रुटि का व्यापार करते हैं। उदाहरण के लिए, एडेलमैन एट अल द्वारा अनुमानित एफएफटी एल्गोरिदम। (1999)<ref name="Edelman_McCorquodale_Toledo_1999"/>तेजी से मल्टीपोल विधि की मदद से समांतर कंप्यूटिंग के लिए कम संचार आवश्यकताओं को प्राप्त करता है। गुओ और बुरुस द्वारा एक [[ छोटा लहर ]]-आधारित अनुमानित एफएफटी (1996)<ref name="Guo_Burrus_1996"/>सटीक एफएफटी की तुलना में विरल इनपुट/आउटपुट (समय/आवृत्ति स्थानीयकरण) को अधिक कुशलता से ध्यान में रखता है। डीएफटी आउटपुट के एक उपसमुच्चय की अनुमानित गणना के लिए एक अन्य एल्गोरिथ्म Shentov et al के कारण है। (1995)।<ref name="Shentov_Mitra_Heute_Hossen_1995"/><nowiki>एडेलमैन एल्गोरिथ्म विरल और गैर-विरल डेटा के लिए समान रूप से अच्छी तरह से काम करता है, क्योंकि यह डेटा की संपीड्यता (विरलता) के बजाय फूरियर मैट्रिक्स की संपीडनशीलता (रैंक की कमी) पर आधारित है। इसके विपरीत, यदि डेटा विरल हैं - अर्थात, यदि N फूरियर गुणांकों में से केवल K अशून्य हैं - तो जटिलता को O(K) तक कम किया जा सकता है{{nnbsp}लॉग (एन)log(N/K)), और बड़े-N उदाहरण (N = 2</nowiki><sup>22</sup>) एक संभावित अनुमानित एल्गोरिथम का उपयोग करते हुए (जो कई दशमलव स्थानों पर सबसे बड़े K गुणांक का अनुमान लगाता है)।<ref name="Hassanieh_2012"/>
+ऊपर चर्चा किए गए सभी एफएफटी एल्गोरिदम डीएफटी की स्पष्ट  गणना करते हैं (अर्थात  [[ तैरनेवाला स्थल ]] त्रुटियों की उपेक्षा)। चूंकि , कुछ एफएफटी एल्गोरिदम प्रस्तावित किए गए हैं, जो डीएफटी की लगभग गणना करते हैं, एक त्रुटि के साथ जिसे बढ़ी हुई संगणनाओं की कीमत पर इच्छानुसार से छोटा किया जा सकता है। ऐसे एल्गोरिदम बढ़ी हुई गति या अन्य गुणों के लिए सन्निकटन त्रुटि का व्यापार करते हैं। उदाहरण के लिए, एडेलमैन एट अल द्वारा अनुमानित एफएफटी एल्गोरिदम। (1999)<ref name="Edelman_McCorquodale_Toledo_1999"/>तेजी से मल्टीपोल विधि की सहायता से समांतर कंप्यूटिंग के लिए कम संचार आवश्यकताओं को प्राप्त करता है। गुओ और बुरुस द्वारा एक [[ छोटा लहर ]]-आधारित अनुमानित एफएफटी (1996)<ref name="Guo_Burrus_1996"/>स्पष्ट  एफएफटी की तुलना में विरल इनपुट/आउटपुट (समय/आवृत्ति स्थानीयकरण) को अधिक कुशलता से ध्यान में रखता है। डीएफटी आउटपुट के एक उपसमुच्चय की अनुमानित गणना के लिए एक अन्य एल्गोरिथ्म Shentov et al के कारण है। (1995)।<ref name="Shentov_Mitra_Heute_Hossen_1995"/><nowiki>एडेलमैन एल्गोरिथ्म विरल और गैर-विरल डेटा के लिए समान रूप से अच्छी तरह से काम करता है, क्योंकि यह डेटा की संपीड्यता (विरलता) के अतिरिक्त  फूरियर मैट्रिक्स की संपीडनशीलता (रैंक की कमी) पर आधारित है। इसके विपरीत, यदि डेटा विरल हैं - अर्थात, यदि N फूरियर गुणांकों में से केवल K अशून्य हैं - तो जटिलता को O(K) तक कम किया जा सकता है{{nnbsp}लॉग (एन)log(N/K)), और बड़े-N उदाहरण (N = 2</nowiki><sup>22</sup>) एक संभावित अनुमानित एल्गोरिथम का उपयोग करते हुए (जो कई दशमलव स्थानों पर सबसे बड़े K गुणांक का अनुमान लगाता है)।<ref name="Hassanieh_2012"/>
-=== सटीकता ===
+=== स्पष्ट ता ===
-परिमित-सटीक फ़्लोटिंग-पॉइंट अंकगणित का उपयोग करते समय FFT एल्गोरिदम में त्रुटियाँ होती हैं, लेकिन ये त्रुटियाँ आमतौर पर काफी छोटी होती हैं; अधिकांश एफएफटी एल्गोरिदम, उदा। कूली-टुके, एल्गोरिदम की [[जोड़ीदार योग]] संरचना के परिणामस्वरूप उत्कृष्ट संख्यात्मक गुण हैं। कूली-टुके एल्गोरिथम के लिए [[सन्निकटन त्रुटि]] पर ऊपरी सीमा है <math display="inline">O(\epsilon \log N)</math>, की तुलना में <math display="inline">O(\epsilon N^{3/2})</math> भोले डीएफटी सूत्र के लिए,<ref name="Gentleman_Sande_1966"/>जहां ε मशीन फ़्लोटिंग-पॉइंट सापेक्ष परिशुद्धता है। वास्तव में, मूल माध्य वर्ग (rms) त्रुटियाँ इन ऊपरी सीमाओं की तुलना में बहुत बेहतर हैं, केवल होने के नाते <math display="inline">O(\epsilon \sqrt{\log N})</math> कूली-टुके और के लिए <math display="inline">O(\epsilon \sqrt{N})</math> भोले डीएफटी के लिए (शत्ज़मैन, 1996)।<ref name="Schatzman_1996"/>ये परिणाम, हालांकि, FFT (अर्थात त्रिकोणमितीय फ़ंक्शन मान) में उपयोग किए जाने वाले ट्वीडल कारकों की सटीकता के प्रति बहुत संवेदनशील हैं, और असावधान FFT कार्यान्वयन के लिए बहुत अधिक सटीकता होना असामान्य नहीं है, उदा। यदि वे त्रिकोणमितीय तालिकाओं के सूत्रों को बनाने में गलत का उपयोग करते हैं। कूली-टुकी के अलावा कुछ एफएफटी, जैसे कि रेडर-ब्रेनर एल्गोरिथम, आंतरिक रूप से कम स्थिर हैं।
+परिमित-स्पष्ट  फ़्लोटिंग-पॉइंट अंकगणित का उपयोग करते समय FFT एल्गोरिदम में त्रुटियाँ होती हैं, किन्तु  ये त्रुटियाँ सामान्यतः  अधिक   छोटी होती हैं; अधिकांश एफएफटी एल्गोरिदम, उदा। कूली-टुके, एल्गोरिदम की [[जोड़ीदार योग]] संरचना के परिणामस्वरूप उत्कृष्ट संख्यात्मक गुण हैं। कूली-टुके एल्गोरिथम के लिए [[सन्निकटन त्रुटि]] पर ऊपरी सीमा है <math display="inline">O(\epsilon \log N)</math>, की तुलना में <math display="inline">O(\epsilon N^{3/2})</math> भोले डीएफटी सूत्र के लिए,<ref name="Gentleman_Sande_1966"/>जहां ε मशीन फ़्लोटिंग-पॉइंट सापेक्ष परिशुद्धता है। वास्तव में, मूल माध्य वर्ग (rms) त्रुटियाँ इन ऊपरी सीमाओं की तुलना में बहुत उत्तम हैं, केवल होने के नाते <math display="inline">O(\epsilon \sqrt{\log N})</math> कूली-टुके और के लिए <math display="inline">O(\epsilon \sqrt{N})</math> भोले डीएफटी के लिए (शत्ज़मैन, 1996)।<ref name="Schatzman_1996"/>ये परिणाम, चूंकि , FFT (अर्थात त्रिकोणमितीय फ़ंक्शन मान) में उपयोग किए जाने वाले ट्वीडल कारकों की स्पष्ट ता के प्रति बहुत संवेदनशील हैं, और असावधान FFT कार्यान्वयन के लिए बहुत अधिक स्पष्ट ता होना असामान्य नहीं है, उदा। यदि वे त्रिकोणमितीय तालिकाओं के सूत्रों को बनाने में गलत का उपयोग करते हैं। कूली-टुकी के अतिरिक्त  कुछ एफएफटी, जैसे कि रेडर-ब्रेनर एल्गोरिथम, आंतरिक रूप से कम स्थिर हैं।
-फिक्स्ड-पॉइंट अंकगणित में, एफएफटी एल्गोरिदम द्वारा संचित परिमित-परिशुद्धता त्रुटियां बदतर हैं, आरएमएस त्रुटियों के रूप में बढ़ रही हैं <math display="inline">O(\sqrt{N})</math> कूली-टुके एल्गोरिथम (वेल्च, 1969) के लिए।<ref name="Welch_1969"/>इस सटीकता को प्राप्त करने के लिए सटीकता के नुकसान को कम करने के लिए स्केलिंग पर सावधानीपूर्वक ध्यान देने की आवश्यकता होती है, और फिक्स्ड-पॉइंट एफएफटी एल्गोरिदम में कूली-टुकी जैसे अपघटन के प्रत्येक मध्यवर्ती चरण में पुनर्विक्रय शामिल होता है।
+फिक्स्ड-पॉइंट अंकगणित में, एफएफटी एल्गोरिदम द्वारा संचित परिमित-परिशुद्धता त्रुटियां बदतर हैं, आरएमएस त्रुटियों के रूप में बढ़ रही हैं <math display="inline">O(\sqrt{N})</math> कूली-टुके एल्गोरिथम (वेल्च, 1969) के लिए।<ref name="Welch_1969"/>इस स्पष्ट ता को प्राप्त करने के लिए स्पष्ट ता के हानि  को कम करने के लिए स्केलिंग पर सावधानीपूर्वक ध्यान देने की आवश्यकता होती है, और फिक्स्ड-पॉइंट एफएफटी एल्गोरिदम में कूली-टुकी जैसे अपघटन के प्रत्येक मध्यवर्ती चरण में पुनर्विक्रय सम्मिलित   होता है।
-एफएफटी कार्यान्वयन की शुद्धता को सत्यापित करने के लिए, कठोर गारंटी प्राप्त की जा सकती है <math display="inline">O(N \log N)</math> यादृच्छिक आदानों पर परिवर्तन की रैखिकता, आवेग-प्रतिक्रिया और समय-शिफ्ट गुणों की जांच करने के लिए एक सरल प्रक्रिया द्वारा समय (एर्गन, 1995)।<ref name="Ergün_1995"/>
+एफएफटी कार्यान्वयन की शुद्धता को सत्यापित करने के लिए, कठोर गारंटी प्राप्त की जा सकती है <math display="inline">O(N \log N)</math> यादृच्छिक आदानों पर परिवर्तन की रैखिकता, आवेग-प्रतिक्रिया और समय-शिफ्ट गुणों की जांच करने के लिए एक सरलप्रक्रिया द्वारा समय (एर्गन, 1995)।<ref name="Ergün_1995"/>
 == बहुआयामी एफएफटी ==
-जैसा कि असतत फूरियर ट्रांसफॉर्म#बहुआयामी डीएफटी आलेख में परिभाषित किया गया है, बहुआयामी डीएफटी
+जैसा कि असतत फूरियर ट्रांसफॉर्म या बहुआयामी डीएफटी आलेख में परिभाषित किया गया है, बहुआयामी डीएफटी
 :<math>X_\mathbf{k} = \sum_{\mathbf{n}=0}^{\mathbf{N}-1} e^{-2\pi i \mathbf{k} \cdot (\mathbf{n} / \mathbf{N})} x_\mathbf{n}</math>
 एक सरणी एक्स को बदल देता है<sub>'''n'''</sub> सूचकांकों के डी-डायमेंशनल [[समन्वय वेक्टर]] के साथ <math display="inline">\mathbf{n} = \left(n_1, \ldots, n_d\right)</math> d नेस्टेड योगों के एक सेट द्वारा (over <math display="inline">n_j = 0 \ldots N_j - 1</math> प्रत्येक जे के लिए), जहां डिवीजन 'एन'/'एन', के रूप में परिभाषित किया गया है <math display="inline">\mathbf{n} / \mathbf{N} = \left(n_1/N_1, \ldots, n_d/N_d\right)</math>, तत्व-वार किया जाता है। समतुल्य रूप से, यह एक-आयामी डीएफटी के डी सेट के अनुक्रम की संरचना है, जो एक समय में एक आयाम के साथ किया जाता है (किसी भी क्रम में)।
-यह रचनात्मक दृष्टिकोण तुरंत सबसे सरल और सबसे आम बहुआयामी डीएफटी एल्गोरिदम प्रदान करता है, जिसे 'पंक्ति-स्तंभ' एल्गोरिदम (नीचे द्वि-आयामी मामले के बाद) के रूप में जाना जाता है। यही है, कोई केवल d एक-आयामी FFTs (उपरोक्त एल्गोरिदम में से किसी के द्वारा) का अनुक्रम करता है: पहले आप n के साथ बदलते हैं<sub>1</sub> आयाम, फिर n के साथ<sub>2</sub> आयाम, और इसी तरह (या वास्तव में, कोई ऑर्डरिंग काम करता है)। इस विधि को सामान्य होने के लिए आसानी से दिखाया गया है <math display="inline">O(N \log N)</math> जटिलता, कहाँ <math display="inline">N = N_1 \cdot N_2 \cdot \cdots \cdot N_d</math> रूपांतरित डेटा बिंदुओं की कुल संख्या है। विशेष रूप से, एन/एन हैं<sub>1</sub> आकार एन के परिवर्तन<sub>1</sub>, वगैरह, इसलिए FFTs के अनुक्रम की जटिलता है:
+यह रचनात्मक दृष्टिकोण तुरंत सबसे सरल और सबसे आम बहुआयामी डीएफटी एल्गोरिदम प्रदान करता है, जिसे 'पंक्ति-स्तंभ' एल्गोरिदम (नीचे द्वि-आयामी स्थितियों  के बाद) के रूप में जाना जाता है। यही है, कोई केवल d एक-आयामी FFTs (उपरोक्त एल्गोरिदम में से किसी के द्वारा) का अनुक्रम करता है: पहले आप n के साथ बदलते हैं<sub>1</sub> आयाम, फिर n के साथ<sub>2</sub> आयाम, और इसी तरह (या वास्तव में, कोई ऑर्डरिंग काम करता है)। इस विधि को सामान्य होने के लिए आसानी से दिखाया गया है <math display="inline">O(N \log N)</math> जटिलता, कहाँ <math display="inline">N = N_1 \cdot N_2 \cdot \cdots \cdot N_d</math> रूपांतरित डेटा बिंदुओं की कुल संख्या है। विशेष रूप से, एन/एन हैं<sub>1</sub> आकार एन के परिवर्तन<sub>1</sub>, वगैरह, इसलिए FFTs के अनुक्रम की जटिलता है:
 :<math>\begin{align}
@@ Line 103: / Line 103: @@
 दो आयामों में, x<sub>'''k'''</sub> रूप में देखा जा सकता है <math>n_1 \times n_2</math> [[मैट्रिक्स (गणित)]], और यह एल्गोरिथम पहले सभी पंक्तियों (प्रतिक्रिया कॉलम) के एफएफटी का प्रदर्शन करने के अनुरूप होता है, परिणामी रूपांतरित पंक्तियों (प्रतिक्रिया कॉलम) को एक दूसरे के रूप में समूहीकृत करता है। <math>n_1 \times n_2</math> मैट्रिक्स, और फिर इस दूसरे मैट्रिक्स के प्रत्येक कॉलम (प्रतिक्रिया पंक्तियों) पर FFT का प्रदर्शन करना, और इसी तरह परिणामों को अंतिम परिणाम मैट्रिक्स में समूहीकृत करना।
-दो से अधिक आयामों में, यह अक्सर कैश (कंप्यूटिंग) इलाके के लिए आयामों को पुनरावर्ती रूप से समूहित करने के लिए फायदेमंद होता है। उदाहरण के लिए, एक त्रि-आयामी एफएफटी पहले प्रत्येक निश्चित एन के लिए प्रत्येक प्लानर स्लाइस के द्वि-आयामी एफएफटी का प्रदर्शन कर सकता है<sub>1</sub>, और फिर n के साथ एक आयामी FFTs निष्पादित करें<sub>1</sub> दिशा। अधिक आम तौर पर, एक [[विषम रूप से इष्टतम]] कैश-बेपरवाह एल्गोरिथ्म में आयामों को दो समूहों में पुनरावर्ती रूप से विभाजित किया जाता है <math display="inline">(n_1, \ldots, n_{d/2})</math> और <math display="inline">(n_{d/2+1}, \ldots, n_d)</math> जो पुनरावर्ती रूप से रूपांतरित होते हैं (यदि d सम नहीं है तो गोल करना) (फ्रिगो और जॉनसन, 2005 देखें)।<ref name="Frigo_Johnson_2005"/>फिर भी, यह पंक्ति-स्तंभ एल्गोरिथम का एक सीधा रूपांतर बना हुआ है, जिसके लिए अंततः बेस केस के रूप में केवल एक-आयामी FFT एल्गोरिथम की आवश्यकता होती है, और अभी भी O(N log N) जटिलता है। फिर भी एक और भिन्नता बाद के आयामों को बदलने के बीच में मैट्रिक्स [[ खिसकाना ]]़ करना है, ताकि ट्रांसफ़ॉर्म सन्निहित डेटा पर काम करें; यह [[बाहर के कोर]] और वितरित मेमोरी स्थितियों के लिए विशेष रूप से महत्वपूर्ण है जहां गैर-सन्निहित डेटा तक पहुँचने में अत्यधिक समय लगता है।
+दो से अधिक आयामों में, यह अधिकांशतः  कैश (कंप्यूटिंग) इलाके के लिए आयामों को पुनरावर्ती रूप से समूहित करने के लिए फायदेमंद होता है। उदाहरण के लिए, एक त्रि-आयामी एफएफटी पहले प्रत्येक निश्चित एन के लिए प्रत्येक प्लानर स्लाइस के द्वि-आयामी एफएफटी का प्रदर्शन कर सकता है<sub>1</sub>, और फिर n के साथ एक आयामी FFTs निष्पादित करें<sub>1</sub> दिशा। अधिक सामान्यतः , एक [[विषम रूप से इष्टतम]] कैश-बेपरवाह एल्गोरिथ्म में आयामों को दो समूहों में पुनरावर्ती रूप से विभाजित किया जाता है <math display="inline">(n_1, \ldots, n_{d/2})</math> और <math display="inline">(n_{d/2+1}, \ldots, n_d)</math> जो पुनरावर्ती रूप से रूपांतरित होते हैं (यदि d सम नहीं है तो गोल करना) (फ्रिगो और जॉनसन, 2005 देखें)।<ref name="Frigo_Johnson_2005"/>फिर भी, यह पंक्ति-स्तंभ एल्गोरिथम का एक सीधा रूपांतर बना हुआ है, जिसके लिए अंततः बेस केस के रूप में केवल एक-आयामी FFT एल्गोरिथम की आवश्यकता होती है, और अभी भी O(N log N) जटिलता है। फिर भी एक और भिन्नता बाद के आयामों को बदलने के बीच में मैट्रिक्स [[ खिसकाना ]]़ करना है, जिससे ट्रांसफ़ॉर्म सन्निहित डेटा पर काम करें; यह [[बाहर के कोर]] और वितरित मेमोरी स्थितियों के लिए विशेष रूप से महत्वपूर्ण है जहां गैर-सन्निहित डेटा तक पहुँचने में अत्यधिक समय लगता है।
-अन्य बहुआयामी एफएफटी एल्गोरिदम हैं जो पंक्ति-स्तंभ एल्गोरिदम से अलग हैं, हालांकि उनमें से सभी हैं <math display="inline">O(N \log N)</math> जटिलता। शायद सबसे सरल गैर-पंक्ति-स्तंभ एफएफटी [[वेक्टर-रेडिक्स एफएफटी एल्गोरिदम]] है, जो साधारण कूली-तुकी एल्गोरिदम का सामान्यीकरण है जहां एक वेक्टर द्वारा परिवर्तन आयामों को विभाजित करता है। <math display="inline">\mathbf{r} = \left(r_1, r_2, \ldots, r_d\right)</math> प्रत्येक चरण पर रेडिस का। (इसमें कैश लाभ भी हो सकते हैं।) वेक्टर-मूलांक का सबसे सरल मामला वह है जहां सभी मूलांक समान होते हैं (उदाहरण के लिए वेक्टर-मूलांक-2 सभी आयामों को दो से विभाजित करता है), लेकिन यह आवश्यक नहीं है। वेक्टर मूलांक एक समय में केवल एक गैर-इकाई मूलांक के साथ, अर्थात <math display="inline">\mathbf{r} = \left(1, \ldots, 1, r, 1, \ldots, 1\right)</math>अनिवार्य रूप से एक पंक्ति-स्तंभ एल्गोरिथम है। अन्य, अधिक जटिल, विधियों में शामिल हैं नुस्बाउमर (1977) के कारण बहुपद परिवर्तन एल्गोरिथम,<ref name="Nussbaumer_1977"/>जो संकल्पों और बहुपद उत्पादों के संदर्भ में परिवर्तन को देखते हैं। डुहामेल और वेटरली देखें (1990)<ref name="Duhamel_Vetterli_1990"/>अधिक जानकारी और संदर्भ के लिए।
+अन्य बहुआयामी एफएफटी एल्गोरिदम हैं जो पंक्ति-स्तंभ एल्गोरिदम से अलग हैं, चूंकि  उनमें से सभी हैं <math display="inline">O(N \log N)</math> जटिलता। संभवतः  सबसे सरल गैर-पंक्ति-स्तंभ एफएफटी [[वेक्टर-रेडिक्स एफएफटी एल्गोरिदम]] है, जो साधारण कूली-तुकी एल्गोरिदम का सामान्यीकरण है जहां एक वेक्टर द्वारा परिवर्तन आयामों को विभाजित करता है। <math display="inline">\mathbf{r} = \left(r_1, r_2, \ldots, r_d\right)</math> प्रत्येक चरण पर रेडिस का। (इसमें कैश लाभ भी हो सकते हैं।) वेक्टर-मूलांक का सबसे सरल मामला वह है जहां सभी मूलांक समान होते हैं (उदाहरण के लिए वेक्टर-मूलांक-2 सभी आयामों को दो से विभाजित करता है), किन्तु  यह आवश्यक नहीं है। वेक्टर मूलांक एक समय में केवल एक गैर-इकाई मूलांक के साथ, अर्थात <math display="inline">\mathbf{r} = \left(1, \ldots, 1, r, 1, \ldots, 1\right)</math>अनिवार्य रूप से एक पंक्ति-स्तंभ एल्गोरिथम है। अन्य, अधिक जटिल, विधियों में सम्मिलित   हैं नुस्बाउमर (1977) के कारण बहुपद परिवर्तन एल्गोरिथम,<ref name="Nussbaumer_1977"/>जो संकल्पों और बहुपद उत्पादों के संदर्भ में परिवर्तन को देखते हैं। डुहामेल और वेटरली देखें (1990)<ref name="Duhamel_Vetterli_1990"/>अधिक जानकारी और संदर्भ के लिए।
 == अन्य सामान्यीकरण ==
-एक <math display="inline">O(N^{5/2} \log N)</math> गोले एस पर [[गोलाकार हार्मोनिक्स]] के लिए सामान्यीकरण<sup>2</sup> एन के साथ<sup>2</sup> नोड्स का वर्णन मोहलेनकैंप द्वारा किया गया था,<ref name="Mohlenkamp_1999"/>एक एल्गोरिथम के साथ अनुमान लगाया गया (लेकिन साबित नहीं हुआ)। <math display="inline">O(N^2 \log^2(N))</math> जटिलता; मोहलेनकैंप भी libftsh लाइब्रेरी में कार्यान्वयन प्रदान करता है।<ref name="libftsh"/>एक गोलाकार-हार्मोनिक एल्गोरिथम <math display="inline">O(N^2 \log N)</math>जटिलता का वर्णन रोखलिन और टायगर्ट द्वारा किया गया है।<ref name="Rokhlin_Tygert_2006"/>
+एक <math display="inline">O(N^{5/2} \log N)</math> गोले एस पर [[गोलाकार हार्मोनिक्स]] के लिए सामान्यीकरण<sup>2</sup> एन के साथ<sup>2</sup> नोड्स का वर्णन मोहलेनकैंप द्वारा किया गया था,<ref name="Mohlenkamp_1999"/>एक एल्गोरिथम के साथ अनुमान लगाया गया (किन्तु  सिद्ध  नहीं हुआ)। <math display="inline">O(N^2 \log^2(N))</math> जटिलता; मोहलेनकैंप भी libftsh लाइब्रेरी में कार्यान्वयन प्रदान करता है।<ref name="libftsh"/>एक गोलाकार-हार्मोनिक एल्गोरिथम <math display="inline">O(N^2 \log N)</math>जटिलता का वर्णन रोखलिन और टायगर्ट द्वारा किया गया है।<ref name="Rokhlin_Tygert_2006"/>
-[[फास्ट फोल्डिंग एल्गोरिदम]] एफएफटी के अनुरूप है, सिवाय इसके कि यह वास्तविक या जटिल स्केलर मानों की श्रृंखला के बजाय बिन्ड वेवफॉर्म की श्रृंखला पर चल रहा है। रोटेशन (जो एफएफटी में एक जटिल फेजर द्वारा गुणा है) घटक तरंग का एक गोलाकार बदलाव है।
+[[फास्ट फोल्डिंग एल्गोरिदम]] एफएफटी के अनुरूप है, सिवाय इसके कि यह वास्तविक या जटिल स्केलर मानों की श्रृंखला के अतिरिक्त  बिन्ड वेवफॉर्म की श्रृंखला पर चल रहा है। रोटेशन (जो एफएफटी में एक जटिल फेजर द्वारा गुणा है) घटक तरंग का एक गोलाकार बदलाव है।
-पॉट्स एट अल में समीक्षा के अनुसार, विभिन्न समूहों ने गैर-सुसज्जित डेटा के लिए एफएफटी एल्गोरिदम भी प्रकाशित किए हैं। (2001)।<ref name="Potts_Steidl_Tasche_2001"/>इस तरह के एल्गोरिदम सख्ती से डीएफटी की गणना नहीं करते हैं (जो केवल समस्थानिक डेटा के लिए परिभाषित है), बल्कि इसके कुछ सन्निकटन (एक [[गैर-समान असतत फूरियर रूपांतरण]], या एनडीएफटी, जो स्वयं अक्सर केवल लगभग गणना की जाती है)। अधिक आम तौर पर वर्णक्रमीय आकलन के कई अन्य तरीके हैं।
+पॉट्स एट अल में समीक्षा के अनुसार, विभिन्न समूहों ने गैर-सुसज्जित डेटा के लिए एफएफटी एल्गोरिदम भी प्रकाशित किए हैं। (2001)।<ref name="Potts_Steidl_Tasche_2001"/>इस तरह के एल्गोरिदम सख्ती से डीएफटी की गणना नहीं करते हैं (जो केवल समस्थानिक डेटा के लिए परिभाषित है), किंतु  इसके कुछ सन्निकटन (एक [[गैर-समान असतत फूरियर रूपांतरण]], या एनडीएफटी, जो स्वयं अधिकांशतः  केवल लगभग गणना की जाती है)। अधिक सामान्यतः  वर्णक्रमीय आकलन के कई अन्य विधि  हैं।
 == अनुप्रयोग ==
 FFT का उपयोग डिजिटल रिकॉर्डिंग, सैंपलिंग, [[ योजक संश्लेषण ]] और [[ पिच सुधार ]] सॉफ्टवेयर में किया जाता है।<ref>{{cite book |last1=Burgess |first1=Richard James |title=संगीत उत्पादन का इतिहास|date=2014 |publisher= Oxford University Press |isbn=978-0199357178 |url=https://books.google.com/books?id=qMKiAwAAQBAJ |access-date=1 August 2019}}</ref>
-FFT का महत्व इस तथ्य से निकला है कि इसने आवृत्ति डोमेन में काम करना कम्प्यूटेशनल रूप से उतना ही संभव बना दिया है जितना कि अस्थायी या स्थानिक डोमेन में काम करना। FFT के कुछ महत्वपूर्ण अनुप्रयोगों में शामिल हैं:<ref name="Rockmore_2000"/><ref name="Chu_George_1999"/>
+FFT का महत्व इस तथ्य से निकला है कि इसने आवृत्ति डोमेन में काम करना कम्प्यूटेशनल रूप से उतना ही संभव बना दिया है जितना कि अस्थायी या स्थानिक डोमेन में काम करना। FFT के कुछ महत्वपूर्ण अनुप्रयोगों में सम्मिलित   हैं:<ref name="Rockmore_2000"/><ref name="Chu_George_1999"/>
 * तेज बड़े-पूर्णांक गुणन एल्गोरिदम और बहुपद गुणन,
@@ Line 127: / Line 127: @@
 == अनुसंधान क्षेत्र ==
-; बिग एफएफटी: खगोल विज्ञान जैसे क्षेत्रों में बड़े डेटा के विस्फोट के साथ, कुछ इंटरफेरोमेट्री गणनाओं के लिए 512K FFTs की आवश्यकता उत्पन्न हुई है। [[विल्किंसन माइक्रोवेव अनिसोट्रॉपी जांच]] और एलआईजीओ जैसी परियोजनाओं द्वारा एकत्र किए गए डेटा को अरबों अंकों के एफएफटी की आवश्यकता होती है। चूंकि यह आकार मुख्य मेमोरी में फिट नहीं होता है, तथाकथित आउट-ऑफ-कोर एफएफटी अनुसंधान का एक सक्रिय क्षेत्र है।<ref name="Cormen_Nicol_1998"/>; अनुमानित एफएफटी: एमआरआई जैसे अनुप्रयोगों के लिए, गैर-समान दूरी वाले ग्रिड बिंदुओं और/या आवृत्तियों के लिए डीएफटी की गणना करना आवश्यक है। मल्टीपोल आधारित दृष्टिकोण रनटाइम वृद्धि के कारक के साथ अनुमानित मात्रा की गणना कर सकते हैं।<ref name="Dutt_Rokhlin_1993"/>; परिमित समूहों पर फूरियर रूपांतरण: आगे सामान्यीकरण की अनुमति देने वाले [[समूह प्रतिनिधित्व]] का उपयोग करके एफएफटी को भी समझाया और व्याख्या किया जा सकता है। गैर-चक्रीय समेत किसी भी कॉम्पैक्ट समूह पर एक फ़ंक्शन, इरेड्यूसिबल मैट्रिक्स तत्वों के आधार पर विस्तार होता है। आधार के इस परिवर्तन को करने के लिए कुशल एल्गोरिथम खोजने के लिए यह अनुसंधान का सक्रिय क्षेत्र बना हुआ है। कुशल गोलाकार हार्मोनिक्स विस्तार सहित अनुप्रयोग, कुछ [[मार्कोव प्रक्रिया]]ओं का विश्लेषण, रोबोटिक्स इत्यादि।<ref name="Rockmore_2004"/>; [[क्वांटम फूरियर रूपांतरण]]: क्वांटम कंप्यूटर पर [[पूर्णांक गुणनखंडन]] के लिए शोर के तेज एल्गोरिथ्म में बाइनरी वेक्टर के डीएफटी की गणना करने के लिए एक सबरूटीन है। इसे 1- या 2-बिट क्वांटम गेट्स के अनुक्रम के रूप में कार्यान्वित किया जाता है, जिसे अब क्वांटम एफएफटी के रूप में जाना जाता है, जो प्रभावी रूप से कूली-तुके एफएफटी को फूरियर मैट्रिक्स के एक विशेष कारक के रूप में महसूस किया गया है। वर्तमान में इन विचारों के विस्तार का पता लगाया जा रहा है।<ref>{{Cite journal |title=फास्ट फूरियर रूपांतरण के लिए क्वांटम सर्किट|journal=Quantum Information Processing |volume=19 |issue=277 |year=2020 |first1=Asaka |last1=Ryo |first2=Sakai |last2=Kazumitsu |first3=Yahagi |last3=Ryoko |page=277 |doi=10.1007/s11128-020-02776-5 |arxiv=1911.03055 |bibcode=2020QuIP...19..277A |s2cid=207847474 |url=https://link.springer.com/article/10.1007/s11128-020-02776-5}}</ref>
+; बिग एफएफटी: खगोल विज्ञान जैसे क्षेत्रों में बड़े डेटा के विस्फोट के साथ, कुछ इंटरफेरोमेट्री गणनाओं के लिए 512K FFTs की आवश्यकता उत्पन्न हुई है। [[विल्किंसन माइक्रोवेव अनिसोट्रॉपी जांच]] और एलआईजीओ जैसी परियोजनाओं द्वारा एकत्र किए गए डेटा को अरबों अंकों के एफएफटी की आवश्यकता होती है। चूंकि यह आकार मुख्य मेमोरी में फिट नहीं होता है, तथाकथित आउट-ऑफ-कोर एफएफटी अनुसंधान का एक सक्रिय क्षेत्र है।<ref name="Cormen_Nicol_1998"/>; अनुमानित एफएफटी: एमआरआई जैसे अनुप्रयोगों के लिए, गैर-समान दूरी वाले ग्रिड बिंदुओं और/या आवृत्तियों के लिए डीएफटी की गणना करना आवश्यक है। मल्टीपोल आधारित दृष्टिकोण रनटाइम वृद्धि के कारक के साथ अनुमानित मात्रा की गणना कर सकते हैं।<ref name="Dutt_Rokhlin_1993"/>; परिमित समूहों पर फूरियर रूपांतरण: आगे सामान्यीकरण की अनुमति देने वाले [[समूह प्रतिनिधित्व]] का उपयोग करके एफएफटी को भी समझाया और व्याख्या किया जा सकता है। गैर-चक्रीय समेत किसी भी कॉम्पैक्ट समूह पर एक फ़ंक्शन, इरेड्यूसिबल मैट्रिक्स तत्वों के आधार पर विस्तार होता है। आधार के इस परिवर्तन को करने के लिए कुशल एल्गोरिथम खोजने के लिए यह अनुसंधान का सक्रिय क्षेत्र बना हुआ है। कुशल गोलाकार हार्मोनिक्स विस्तार सहित अनुप्रयोग, कुछ [[मार्कोव प्रक्रिया]]ओं का विश्लेषण, रोबोटिक्स इत्यादि।<ref name="Rockmore_2004"/>; [[क्वांटम फूरियर रूपांतरण]]: क्वांटम कंप्यूटर पर [[पूर्णांक गुणनखंडन]] के लिए ध्वनि  के तेज एल्गोरिथ्म में बाइनरी वेक्टर के डीएफटी की गणना करने के लिए एक सबरूटीन है। इसे 1- या 2-बिट क्वांटम गेट्स के अनुक्रम के रूप में कार्यान्वित किया जाता है, जिसे अब क्वांटम एफएफटी के रूप में जाना जाता है, जो प्रभावी रूप से कूली-तुके एफएफटी को फूरियर मैट्रिक्स के एक विशेष कारक के रूप में अनुभूत  किया गया है। वर्तमान में इन विचारों के विस्तार का पता लगाया जा रहा है।<ref>{{Cite journal |title=फास्ट फूरियर रूपांतरण के लिए क्वांटम सर्किट|journal=Quantum Information Processing |volume=19 |issue=277 |year=2020 |first1=Asaka |last1=Ryo |first2=Sakai |last2=Kazumitsu |first3=Yahagi |last3=Ryoko |page=277 |doi=10.1007/s11128-020-02776-5 |arxiv=1911.03055 |bibcode=2020QuIP...19..277A |s2cid=207847474 |url=https://link.springer.com/article/10.1007/s11128-020-02776-5}}</ref>
@@ Line 182: / Line 182: @@
 एफएफटी कार्यान्वयन:
-* [[ALGLIB]] - वास्तविक/जटिल FFT कार्यान्वयन के साथ एक दोहरी/GPL-लाइसेंसीकृत C++ और C# लाइब्रेरी (अन्य भाषाओं का भी समर्थन करती है)
+* [[ALGLIB]] - वास्तविक/जटिल FFT कार्यान्वयन के साथ एक दोहरी/GPL-लाइसेंसीकृत C++ और C या  लाइब्रेरी (अन्य भाषाओं का भी समर्थन करती है)
 * [[FFTPACK]] - एक और फोरट्रान FFT लाइब्रेरी (सार्वजनिक डोमेन)
 * वास्तुकला-विशिष्ट:
@@ Line 191: / Line 191: @@
 अन्य लिंक:
-* ओडिल्ज़को-शॉनहेज एल्गोरिद्म एफएफटी को [[डिरिचलेट श्रृंखला]] को परिमित करने के लिए लागू करता है
+* ओडिल्ज़को-शॉनहेज एल्गोरिद्म एफएफटी को [[डिरिचलेट श्रृंखला]] को परिमित करने के लिए प्रयुक्त  करता है
 * शॉनहेज-स्ट्रैसन एल्गोरिथम - बड़े पूर्णांकों के लिए स्पर्शोन्मुख रूप से तेज़ गुणन एल्गोरिथम
-* [[ तितली आरेख ]] - एफएफटी का वर्णन करने के लिए इस्तेमाल किया जाने वाला डायग्राम
+* [[ तितली आरेख ]] - एफएफटी का वर्णन करने के लिए उपयोग  किया जाने वाला डायग्राम
-* स्पेक्ट्रल संगीत (संगीत रचना के लिए डीएफटी विश्लेषण का अनुप्रयोग शामिल है)
+* स्पेक्ट्रल संगीत (संगीत रचना के लिए डीएफटी विश्लेषण का अनुप्रयोग सम्मिलित   है)
-* स्पेक्ट्रम विश्लेषक - स्पेक्ट्रम विश्लेषण करने वाले कई उपकरणों में से कोई भी, अक्सर डीएफटी के माध्यम से
+* स्पेक्ट्रम विश्लेषक - स्पेक्ट्रम विश्लेषण करने वाले कई उपकरणों में से कोई भी, अधिकांशतः  डीएफटी के माध्यम से
 * [[समय श्रृंखला]]
 * फास्ट वॉल्श-हैडमार्ड ट्रांसफॉर्म
-* [[सामान्यीकृत वितरण कानून]]
+* [[सामान्यीकृत वितरण कानून|सामान्यीकृत वितरण नियम]]
 * [[कम से कम वर्ग वर्णक्रमीय विश्लेषण]]
 * [[बहुआयामी परिवर्तन]]

Anonymous

Search

फास्ट फूरिये रूपांतर: Difference between revisions

Namespaces

More

Page actions

Revision as of 12:33, 2 April 2023

Contents

इतिहास

परिभाषा

एल्गोरिदम

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

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

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

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

सन्निकटन

स्पष्ट ता

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

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

अनुप्रयोग

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

भाषा संदर्भ

यह भी देखें

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

फास्ट फूरिये रूपांतर: Difference between revisions

Revision as of 12:33, 2 April 2023

इतिहास

परिभाषा

एल्गोरिदम

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

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

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

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

सन्निकटन

स्पष्ट ता

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

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

अनुप्रयोग

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

भाषा संदर्भ

यह भी देखें

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories