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

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

इस प्रकार रेडिक्स-वेक्टर एल्गोरिदम की तुलना में वेक्टर-रेडिक्स एफएफटी एल्गोरिदम सम्मिश्र गुणन की संख्या को अधिक कम कर सकता है। उदाहरण के लिए, अवयव आव्यूह (M आयाम, और प्रत्येक आयाम पर आकार N) के लिए, रेडिक्स -2 के लिए वेक्टर-रेडिक्स एफएफटी एल्गोरिदम के सम्मिश्र गुणकों की संख्या $N^{M}$ है, इस मध्य, रेडिक्स के लिए -कॉलम एल्गोरिथम, यह ${\frac {2^{M}-1}{2^{M}}}N^{M}\log _{2}N$ है। और सामान्यतः, जब यह एल्गोरिदम बड़े मूलांकों और उच्च आयामी सरणियों पर संचालित होता है, तो गुणकों में भी बड़ी बचत प्राप्त होती है।

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

2-डी डीआईटी केस

इस प्रकार कूली-टुकी एफएफटी एल्गोरिथम की प्रकार, दो आयामी वेक्टर-रेडिक्स एफएफटी को नियमित 2-डी डीएफटी को ट्विडल कारकों द्वारा गुणा किए गए छोटे डीएफटी के योग में विघटित करके प्राप्त किया जाता है।

डेसीमेशन-इन-टाइम (डीआईटी) एल्गोरिदम का कारण है कि अपघटन समय डोमेन $x$ पर आधारित है, कूली-टुकी एफएफटी एल्गोरिदम में और देखें।

हमारा मानना ​​है कि 2-डी डीएफटी परिभाषित है

$X(k_{1},k_{2})=\sum _{n_{1}=0}^{N_{1}-1}\sum _{n_{2}=0}^{N_{2}-1}x[n_{1},n_{2}]\cdot W_{N_{1}}^{k_{1}n_{1}}W_{N_{2}}^{k_{2}n_{2}},$

जहाँ $k_{1}=0,\dots ,N_{1}-1$,और $k_{2}=0,\dots ,N_{2}-1$, और $x[n_{1},n_{2}]$ $N_{1}\times N_{2}$ आव्यूह, और $W_{N}=\exp(-j2\pi /N)$.

सरलता के लिए, आइए मान लें $N_{1}=N_{2}=N$, और मूलांक-$(r\times r)$ इस प्रकार कि $N/r$ पूर्णांक है.

वैरिएबल के परिवर्तन का उपयोग करना:

• $n_{i}=rp_{i}+q_{i}$, जहाँ $p_{i}=0,\ldots ,(N/r)-1;q_{i}=0,\ldots ,r-1;$
• $k_{i}=u_{i}+v_{i}N/r$, जहाँ $u_{i}=0,\ldots ,(N/r)-1;v_{i}=0,\ldots ,r-1;$

जहाँ $i=1$ या $2$, तो दो आयामी डीएफटी को इस प्रकार लिखा जा सकता है:

$X(u_{1}+v_{1}N/r,u_{2}+v_{2}N/r)=\sum _{q_{1}=0}^{r-1}\sum _{q_{2}=0}^{r-1}\left[\sum _{p_{1}=0}^{N/r-1}\sum _{p_{2}=0}^{N/r-1}x[rp_{1}+q_{1},rp_{1}+q_{1}]W_{N/r}^{p_{1}u_{1}}W_{N/r}^{p_{2}u_{2}}\right]\cdot W_{N}^{q_{1}u_{1}+q_{2}u_{2}}W_{r}^{q_{1}v_{1}}W_{r}^{q_{2}v_{2}},$

डीआईटी वेक्टर-रेडिक्स 2x2 एफएफटी के लिए चरण बटरफ्लाई

इस प्रकार उपरोक्त समीकरण 2-डी डीआईटी मूलांक-$(r\times r)$ "बटरफ्लाई" की मूल संरचना को परिभाषित करता है। (कूली-टुकी एफएफटी एल्गोरिदम में 1-डी "बटरफ्लाई" देखें)

जब $r=2$, समीकरण को चार योगों में विभाजित किया जा सकता है, और इससे यह प्राप्त होता है:

$X(k_{1},k_{2})=S_{00}(k_{1},k_{2})+S_{01}(k_{1},k_{2})W_{N}^{k_{2}}+S_{10}(k_{1},k_{2})W_{N}^{k_{1}}+S_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}$ के लिए $0\leq k_{1},k_{2}<{\frac {N}{2}}$,

जहाँ $S_{ij}(k_{1},k_{2})=\sum _{n_{1}=0}^{N/2-1}\sum _{n_{2}=0}^{N/2-1}x[2n_{1}+i,2n_{2}+j]\cdot W_{N/2}^{n_{1}k_{1}}W_{N/2}^{n_{2}k_{2}}$.

$S_{ij}$ को $N/2$-आयामी डीएफटी के रूप में देखा जा सकता है, प्रत्येक मूल प्रारूप के सबसेट पर

• $S_{00}$ उन प्रारूपो पर डीएफटी $x$ है जिसके लिए दोनों $n_{1}$ और $n_{2}$ सम हैं;
• $S_{01}$ जिसके लिए प्रारूपो पर डीएफटी है $n_{1}$ सम है और $n_{2}$ विषम है;
• $S_{10}$ जिसके लिए प्रारूपो पर डीएफटी है $n_{1}$ विषम है और $n_{2}$ सम है;
• $S_{11}$ दोनों के लिए प्रारूपो पर डीएफटी है $n_{1}$ और $n_{2}$ विषम हैं.

इस प्रकार त्रिकोणमितीय पहचानों की सूची शिफ्ट्स और आवधिकता के लिए धन्यवाद, हम निम्नलिखित अतिरिक्त पहचानें प्राप्त कर सकते हैं, जो इसके $0\leq k_{1},k_{2}<{\frac {N}{2}}$ लिए मान्य हैं :

• $X{\biggl (}k_{1}+{\frac {N}{2}},k_{2}{\biggr )}=S_{00}(k_{1},k_{2})+S_{01}(k_{1},k_{2})W_{N}^{k_{2}}-S_{10}(k_{1},k_{2})W_{N}^{k_{1}}-S_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}$;
• $X{\biggl (}k_{1},k_{2}+{\frac {N}{2}}{\biggr )}=S_{00}(k_{1},k_{2})-S_{01}(k_{1},k_{2})W_{N}^{k_{2}}+S_{10}(k_{1},k_{2})W_{N}^{k_{1}}-S_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}$;
• $X{\biggl (}k_{1}+{\frac {N}{2}},k_{2}+{\frac {N}{2}}{\biggr )}=S_{00}(k_{1},k_{2})-S_{01}(k_{1},k_{2})W_{N}^{k_{2}}-S_{10}(k_{1},k_{2})W_{N}^{k_{1}}+S_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}$.

2-डी डीआईएफ केस

इसी प्रकार, डिकिमेशन-इन-फ़्रीक्वेंसी (डीआईएफ, जिसे सैंडे-टुकी एल्गोरिदम भी कहा जाता है) एल्गोरिदम का कारण है कि अपघटन फ़्रीक्वेंसी डोमेन $X$ पर आधारित है , कूली-टुकी एफएफटी एल्गोरिथम में और देखें।

वैरिएबल के परिवर्तन का उपयोग करना:

• $n_{i}=p_{i}+q_{i}N/r$, जहाँ $p_{i}=0,\ldots ,(N/r)-1;q_{i}=0,\ldots ,r-1;$
• $k_{i}=ru_{i}+v_{i}$, जहाँ $u_{i}=0,\ldots ,(N/r)-1;v_{i}=0,\ldots ,r-1;$

जहाँ $i=1$ या $2$, और डीएफटी समीकरण को इस प्रकार लिखा जा सकता है::$X(ru_{1}+v_{1},ru_{2}+v_{2})=\sum _{p_{1}=0}^{N/r-1}\sum _{p_{2}=0}^{N/r-1}\left[\sum _{q_{1}=0}^{r-1}\sum _{q_{2}=0}^{r-1}x[p_{1}+q_{1}N/r,p_{1}+q_{1}N/r]W_{r}^{q_{1}v_{1}}W_{r}^{q_{2}v_{2}}\right]\cdot W_{N}^{p_{1}v_{1}+p_{2}v_{2}}W_{N/r}^{p_{1}u_{1}}W_{N/r}^{p_{2}u_{2}},$

अन्य दृष्टिकोण

इस प्रकार स्प्लिट-रेडिक्स एफएफटी एल्गोरिदम 1-डी डीएफटी के लिए उपयोगी विधि सिद्ध हुई है। और विभाजित वेक्टर-रेडिक्स एफएफटी प्राप्त करने के लिए इस विधि को वेक्टर-रेडिक्स एफएफटी पर प्रयुक्त किया गया है। पारंपरिक 2-डी वेक्टर-रेडिक्स एल्गोरिदम में, हम सूचकांकों $k_{1},k_{2}$ को 4 समूहों में विघटित करते हैं :

${\begin{array}{lcl}X(2k_{1},2k_{2})&:&{\text{even-even}}\\X(2k_{1},2k_{2}+1)&:&{\text{even-odd}}\\X(2k_{1}+1,2k_{2})&:&{\text{odd-even}}\\X(2k_{1}+1,2k_{2}+1)&:&{\text{odd-odd}}\end{array}}$

विभाजित वेक्टर-रेडिक्स एल्गोरिदम द्वारा, पहले तीन समूह अपरिवर्तित रहते हैं, चौथे विषम-विषम समूह को अन्य चार उप-समूहों और कुल सात समूहों में विघटित किया जाता है:

${\begin{array}{lcl}X(2k_{1},2k_{2})&:&{\text{even-even}}\\X(2k_{1},2k_{2}+1)&:&{\text{even-odd}}\\X(2k_{1}+1,2k_{2})&:&{\text{odd-even}}\\X(4k_{1}+1,4k_{2}+1)&:&{\text{odd-odd}}\\X(4k_{1}+1,4k_{2}+3)&:&{\text{odd-odd}}\\X(4k_{1}+3,4k_{2}+1)&:&{\text{odd-odd}}\\X(4k_{1}+3,4k_{2}+3)&:&{\text{odd-odd}}\end{array}}$

इसका कारण है 2-डी डीआईटी मूलांक में चौथा पद-$(2\times 2)$ समीकरण, $S_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}$ बन जाता है:

$A_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}+A_{13}(k_{1},k_{2})W_{N}^{k_{1}+3k_{2}}+A_{31}(k_{1},k_{2})W_{N}^{3k_{1}+k_{2}}+A_{33}(k_{1},k_{2})W_{N}^{3(k_{1}+k_{2})},$

जहाँ $A_{ij}(k_{1},k_{2})=\sum _{n_{1}=0}^{N/4-1}\sum _{n_{2}=0}^{N/4-1}x[4n_{1}+i,4n_{2}+j]\cdot W_{N/4}^{n_{1}k_{1}}W_{N/4}^{n_{2}k_{2}}$

इस प्रकार एन डीएफटी द्वारा 2-डी एन को अंतिम चरण तक उपरोक्त अपघटन के क्रमिक उपयोग द्वारा प्राप्त किया जाता है।

यह दिखाया गया है कि स्प्लिट वेक्टर रेडिक्स एल्गोरिदम ने वेक्टर-रेडिक्स एल्गोरिदम की तुलना में लगभग 30% सम्मिश्र गुणन और विशिष्ट $1024\times 1024$ सरणी के लिए लगभग समान संख्या में सम्मिश्र जोड़ बचाए हैं।