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

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

स्प्लिट-रेडिक्स एफएफटी, अपनी विविधताओं के साथ, अधिक समय से दो आकारों की घात 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}$है। ये तीन योग क्रमशः मूलांक-2 (आकार N/2) और मूलांक-4 (आकार N/4) कूली-टुकी चरणों के भागों के अनुरूप हैं। (अंतर्निहित विचार यह है कि मूलांक-2 के सम-सूचकांक उप-परिवर्तन के सामने कोई गुणक कारक नहीं है, इसलिए इसे वैसे ही छोड़ दिया जाना चाहिए, जबकि मूलांक-2 के विषम-सूचकांक उप-परिवर्तन को दूसरे पुनरावर्ती उपविभाजन के संयोजन से लाभ होता है।)

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

अधिक विशेष रूप से, $U_{k}$ लंबाई N/2 ($k=0,\ldots ,N/2-1$ के लिए) के डीएफटी के परिणाम को निरूपित करें, और $Z_{k}$ और $Z'_{k}$ लंबाई N/4 ($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).