स्प्लिट-रेडिक्स एफएफटी एल्गोरिदम

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

स्प्लिट-रेडिक्स एफएफटी (FFT), अपनी विविधताओं के साथ, लंबे समय से दो आकारों N की शक्ति के डीएफटी की गणना करने के लिए सबसे कम प्रकाशित अंकगणितीय ऑपरेशन गणना (आवश्यक वास्तविक संख्या जोड़ और गुणन की संपूर्ण त्रुटिहीन संख्या) प्राप्त करने का गौरव रखता था। मूल स्प्लिट-रेडिक्स एल्गोरिदम की अंकगणित गणना में 2004 में सुधार किया गया था (N=64 के लिए हाथ अनुकूलन के माध्यम से जे. वान बसकिर्क द्वारा अप्रकाशित कार्य में प्राप्त प्रारंभिक लाभ के साथ), परन्तु यह ज्ञात हुआ है कि कोई अभी भी विभाजित मूलांक (जॉनसन और फ्रिगो, 2007) के संशोधन द्वारा नई न्यूनतम गणना प्राप्त कर सकता है। यद्यपि कंप्यूटर पर डीएफटी की गणना करने के लिए आवश्यक समय निर्धारित करने में अंकगणितीय परिचालनों की संख्या एकमात्र कारक (या यहां तक ​​​​कि अनिवार्य रूप से प्रमुख कारक) नहीं है, न्यूनतम संभव गणना का प्रश्न लंबे समय से सैद्धांतिक रुचि का है। (वर्तमान में ऑपरेशन संख्या पर कोई सख्त निचली सीमा साबित नहीं हुई है।)

स्प्लिट-रेडिक्स एल्गोरिदम केवल तभी प्रस्तावित किया जा सकता है जब N, 4 का गुणक हो, परन्तु चूंकि यह डीएफटी को छोटे डीएफटी में खंडित करता है, इसलिए इसे इच्छानुसार किसी अन्य एफएफटी एल्गोरिदम के साथ जोड़ा जा सकता है।

विभाजन-मूलांक अपघटन

याद रखें कि डीएफटी को सूत्र द्वारा परिभाषित किया गया है:

$X_{k}=\sum _{n=0}^{N-1}x_{n}\omega _{N}^{nk}$

कहाँ $k$ $0$ से लेकर $N-1$ तक का पूर्णांक है और $\omega _{N}$ एकता की आदिम जड़ को दर्शाता है:

$\omega _{N}=e^{-{\frac {2\pi i}{N}}},$

और इस प्रकार: $\omega _{N}^{N}=1$ होता है।

स्प्लिट-रेडिक्स एल्गोरिदम इस योग को तीन छोटे योगों के रूप में व्यक्त करके कार्य करता है। (यहां, हम स्प्लिट-रेडिक्स एफएफटी के समय संस्करण में दशमलव देते हैं; आवृत्ति संस्करण में दोहरी दशमलव अनिवार्य रूप से इन चरणों के विपरीत है।)

सबसे पूर्व, सम और विषम संख्या सूचकांकों का सारांश $x_{2n_{2}}$. दूसरा, दो टुकड़ों में विभाजित विषम सूचकांकों का सारांश: $x_{4n_{4}+1}$ और $x_{4n_{4}+3}$, इसके अनुसार सूचकांक 1 या 3 मॉड्यूलो ऑपरेशन 4 है। यहां, $n_{m}$ एक सूचकांक को दर्शाता है जो 0 से चलता है $N/m-1$. परिणामी योग इस प्रकार दिखते हैं:

$X_{k}=\sum _{n_{2}=0}^{N/2-1}x_{2n_{2}}\omega _{N/2}^{n_{2}k}+\omega _{N}^{k}\sum _{n_{4}=0}^{N/4-1}x_{4n_{4}+1}\omega _{N/4}^{n_{4}k}+\omega _{N}^{3k}\sum _{n_{4}=0}^{N/4-1}x_{4n_{4}+3}\omega _{N/4}^{n_{4}k}$

जहाँ हमने इस तथ्य का प्रयोग किया है $\omega _{N}^{mnk}=\omega _{N/m}^{nk}$. ये तीन योग क्रमशः Cooley-Tukey FFT एल्गोरिदम#Radix-2 DIT केस|radix-2 (आकार N/2) और मूलांक-4 (आकार N/4) Cooley-Tukey चरणों के भागों के अनुरूप हैं। (अंतर्निहित विचार यह है कि मूलांक-2 के सम-सूचकांक उप-परिवर्तन के सामने कोई गुणक कारक नहीं है, इसलिए इसे वैसे ही छोड़ दिया जाना चाहिए, जबकि मूलांक-2 के विषम-सूचकांक उप-परिवर्तन को दूसरे पुनरावर्ती उपविभाजन के संयोजन से लाभ होता है .)

ये छोटे योग अब बिल्कुल N/2 और N/4 लंबाई के डीएफटी हैं, जिन्हें पुनरावर्ती रूप से निष्पादित किया जा सकता है और फिर पुन: संयोजित किया जा सकता है।

अधिक विशेष रूप से, आइए $U_{k}$ लंबाई N/2 के डीएफटी के परिणाम को निरूपित करें (के लिए)। $k=0,\ldots ,N/2-1$), और जाने $Z_{k}$ और $Z'_{k}$ लंबाई N/4 के डीएफटीs के परिणामों को निरूपित करें (के लिए)। $k=0,\ldots ,N/4-1$). फिर आउटपुट $X_{k}$ सादा है:

$X_{k}=U_{k}+\omega _{N}^{k}Z_{k}+\omega _{N}^{3k}Z'_{k}.$

हालाँकि, यह अनावश्यक गणना करता है $k\geq N/4$ के साथ कई गणनाएँ साझा करने का अवसर मिलता है $k<N/4$. विशेष रूप से, यदि हम k में N/4 जोड़ते हैं, तो आकार-N/4 डीएफटी नहीं बदलते हैं (क्योंकि वे N/4 में आवधिक होते हैं), जबकि यदि हम k में N/2 जोड़ते हैं तो आकार-N/2 डीएफटी अपरिवर्तित रहता है। क। तो, केवल वही चीज़ें बदलती हैं जो बदलती हैं $\omega _{N}^{k}$ और $\omega _{N}^{3k}$ शब्द, जिन्हें घुमाव कारक के रूप में जाना जाता है। यहां, हम सर्वसमिकाओं का उपयोग करते हैं:

$\omega _{N}^{k+N/4}=-i\omega _{N}^{k}$

$\omega _{N}^{3(k+N/4)}=i\omega _{N}^{3k}$

अंत में पहुंचने के लिए:

$X_{k}=U_{k}+\left(\omega _{N}^{k}Z_{k}+\omega _{N}^{3k}Z'_{k}\right),$

$X_{k+N/2}=U_{k}-\left(\omega _{N}^{k}Z_{k}+\omega _{N}^{3k}Z'_{k}\right),$

$X_{k+N/4}=U_{k+N/4}-i\left(\omega _{N}^{k}Z_{k}-\omega _{N}^{3k}Z'_{k}\right),$

$X_{k+3N/4}=U_{k+N/4}+i\left(\omega _{N}^{k}Z_{k}-\omega _{N}^{3k}Z'_{k}\right),$

जो सभी आउटपुट देता है $X_{k}$ अगर हम जाने देंगे $k$ से रेंज $0$ को $N/4-1$ उपरोक्त चार भावों में.

ध्यान दें कि इन अभिव्यक्तियों को इस प्रकार व्यवस्थित किया गया है कि हमें विभिन्न डीएफटी आउटपुट को जोड़ और घटाव के जोड़े द्वारा संयोजित करने की आवश्यकता है, जिन्हें बटरफ्लाईज आरेख के रूप में जाना जाता है। इस एल्गोरिदम के लिए न्यूनतम ऑपरेशन गणना प्राप्त करने के लिए, किसी को विशेष मामलों को ध्यान में रखना होगा $k=0$ (जहाँ टेढ़े-मेढ़े कारक एकता हैं) और के लिए $k=N/8$ (जहां टेढ़े-मेढ़े कारक हैं $(1\pm i)/{\sqrt {2}}$ और अधिक तीव्री से गुणा किया जा सकता है); देखें, उदा. सोरेनसेन एट अल. (1986)। से गुणा $\pm 1$ और $\pm i$ सामान्यतः मुक्त के रूप में गिना जाता है (सभी निषेधों को जोड़ को घटाव में परिवर्तित करके या इसके विपरीत अवशोषित किया जा सकता है)।

जब N दो की घात हो तो यह अपघटन पुनरावर्ती रूप से किया जाता है। रिकर्सन के आधार विषय N=1, जहां डीएफटी केवल $X_{0}=x_{0}$ की प्रति है, और N=2 हैं, जहां डीएफटी अतिरिक्त $X_{0}=x_{0}+x_{1}$और घटाव $X_{1}=x_{0}-x_{1}$है।

इन विचारों के परिणामस्वरूप गिनती होती है: $4N\log _{2}N-6N+8$ वास्तविक जोड़ और गुणन, N>1 के लिए दो की घात है। यह गणना मानती है कि, 2 की विषम शक्तियों के लिए, 2 का बचा हुआ कारक (सभी विभाजन-मूलांक चरणों के पश्चात, जो N को 4 से विभाजित करता है) को सीधे डीएफटी परिभाषा (4 वास्तविक जोड़ और गुणा), या समकक्ष द्वारा नियंत्रित किया जाता है। मूलांक-2 कूली-टुकी एफएफटी चरण है।

संदर्भ

• R. Yavne, "An economical method for calculating the discrete Fourier transform," in Proc. AFIPS Fall Joint Computer Conf. 33, 115–125 (1968).
• P. Duhamel and H. Hollmann, "Split-radix FFT algorithm," Electron. Lett. 20 (1), 14–16 (1984).
• M. Vetterli and H. J. Nussbaumer, "Simple FFT and DCT algorithms with reduced number of operations," Signal Processing 6 (4), 267–278 (1984).
• J. B. Martens, "Recursive cyclotomic factorization—a new algorithm for calculating the discrete Fourier transform," IEEE Trans. Acoust., Speech, Signal Processing 32 (4), 750–761 (1984).
• P. Duhamel and M. Vetterli, "Fast Fourier transforms: a tutorial review and a state of the art," Signal Processing 19, 259–299 (1990).
• S. G. Johnson and M. Frigo, "A modified split-radix FFT with fewer arithmetic operations," IEEE Trans. Signal Process. 55 (1), 111–119 (2007).
• Douglas L. Jones, "Split-radix FFT algorithms," Connexions web site (Nov. 2, 2006).
• H. V. Sorensen, M. T. Heideman, and C. S. Burrus, "On computing the split-radix FFT", IEEE Trans. Acoust., Speech, Signal Processing 34 (1), 152–156 (1986).