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

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

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

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

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

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

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

हमारा मानना ​​है कि 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}$ h> के रूप में देखा जा सकता है $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$, Cooley-Tukey FFT एल्गोरिथम में और देखें।

चरों के परिवर्तन का उपयोग करना:

• $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$ वेक्टर-रेडिक्स एल्गोरिदम के साथ तुलना में सरणी।