चिर्प जेड-रूपांतरण: Difference between revisions

Revision as of 17:06, 23 November 2023

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

विशेष रूप से, चिरप Z ट्रांसफॉर्म, Z ट्रांसफॉर्म की गणना बिंदु z_k की एक सीमित संख्या पर करता है एक लघुगणकीय सर्पिल समोच्च के साथ, इसे इस प्रकार परिभाषित किया गया है:^[1]^[3]

X_{k}=\sum _{n=0}^{N-1}x(n)z_{k}^{-n}

z_{k}=A\cdot W^{-k},k=0,1,\dots ,M-1

जहां A सम्मिश्र प्रारंभिक बिंदु है, W बिंदुओं के बीच सम्मिश्र अनुपात है, और M गणना किए जाने वाले बिंदुओं की संख्या है।

डीएफटी की तरह, चिरप जेड-ट्रांसफॉर्म की गणना O(n log n) ऑपरेशंस में की जा सकती है जहां n=\max(M,N)।

व्युत्क्रम चिरप जेड-ट्रांसफॉर्म (आईसीजेडटी) के लिए एक O(n log n) एल्गोरिदम 2003 और 2019 में वर्णित किया गया था।^[4]^[5] ^[6]

ब्लूस्टीन का एल्गोरिदम

ब्लूस्टीन का एल्गोरिदम^[7]^[8] सीजेडटी को एक कनवल्शन के रूप में व्यक्त करता है और तेज़ फूरियर ट्रांसफॉर्म/आईएफएफटी का उपयोग करके इसे कुशलतापूर्वक कार्यान्वित करता है।

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

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

X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}nk}\qquad k=0,\dots ,N-1.

यदि हम घातांक में गुणनफल nk को पहचान से प्रतिस्थापित करते हैं

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

हम इस प्रकार प्राप्त करते हैं:

X_{k}=e^{-{\frac {\pi i}{N}}k^{2}}\sum _{n=0}^{N-1}\left(x_{n}e^{-{\frac {\pi i}{N}}n^{2}}\right)e^{{\frac {\pi i}{N}}(k-n)^{2}}\qquad k=0,\dots ,N-1.

यह योग वास्तव में दो अनुक्रमों a और bn का एक संलयन है जिसे निम्न द्वारा परिभाषित किया गया है:

a_{n}=x_{n}e^{-{\frac {\pi i}{N}}n^{2}}

b_{n}=e^{{\frac {\pi i}{N}}n^{2}},

कनवल्शन के आउटपुट को N चरण कारकों b_k^* से गुणा किया जाता है। वह है:

X_{k}=b_{k}^{*}\left(\sum _{n=0}^{N-1}a_{n}b_{k-n}\right)\qquad k=0,\dots ,N-1.

यह कनवल्शन, परिवर्तन में, कनवल्शन प्रमेय के माध्यम से एफएफटी की जोड़ी (साथ ही सम्मिश्र कलरव b_n की पूर्व-गणना की गई एफएफटी)) के साथ किया जा सकता है । इस प्रकार से मुख्य तथ्य यह है कि ये एफएफटी समान लंबाई N के नहीं हैं: इस तरह के कनवल्शन की गणना एफएफटी से केवल शून्य-पैडिंग द्वारा 2N-1 से अधिक या उसके समान लंबाई तक की जा सकती है। विशेष रूप से, कोई दो या किसी अन्य अत्यधिक समग्र संख्या आकार की शक्ति तक पैड कर सकता है, कूली-टुकी एफएफटी एल्गोरिथ्म O(N log N) समय में कूली-टुकी एल्गोरिथ्म जिसके लिए एफएफटी को कुशलतापूर्वक निष्पादित किया जा सकता है। इस प्रकार, ब्लूस्टीन का एल्गोरिदम प्राइम-आकार डीएफटी की गणना करने के लिए एक O(N log N) विधि प्रदान करता है, चूंकि समग्र आकार के लिए कूली-टुकी एल्गोरिदम की तुलना में कई गुना धीमा है।

इस प्रकार से ब्लूस्टीन के एल्गोरिदम में कनवल्शन के लिए शून्य-पैडिंग का उपयोग कुछ अतिरिक्त टिप्पणी का पात्र है। मान लीजिए कि हम लंबाई M ≥ 2N–1 पर शून्य-पैड करते हैं। इसका अर्थ यह है कि a_n को लंबाई M की एक सरणी A_n तक विस्तारित किया गया है, जहां A_n = a_n 0 ≤ n < N के लिए और A_n = 0 अन्यथा - "शून्य-पैडिंग" का सामान्य अर्थ। चूंकि, कनवल्शन में b_k_–n पद के कारण, b_n के लिए n के धनात्मक और ऋणात्मक (ध्यान दें कि b_–n = b_n) दोनों मान आवश्यक हैं। शून्य-पैडेड सरणी के डीएफटी द्वारा निहित आवधिक सीमाओं का अर्थ है कि -n M–n के समान है। इस प्रकार, b_n को लंबाई M की एक सरणी B_n तक विस्तारित किया गया है, जहां B₀ = b₀, B_n = B_M_–n = b_n 0 < n < N के लिए, और B_n = 0 अन्यथा। सामान्य कनवल्शन प्रमेय के अनुसार, a और b का कनवल्शन प्राप्त करने के लिए A और B को एफएफटी किया जाता है, बिंदुवार गुणा किया जाता है, और विपरीत एफएफटी किया जाता है।

आइए हम इस बारे में और अधिक स्पष्ट हों कि डीएफटी के लिए ब्लूस्टीन के एल्गोरिदम में किस प्रकार के कनवल्शन की आवश्यकता है। यदि अनुक्रम b_n अवधि n के साथ N में आवधिक थे, तो यह लंबाई N का चक्रीय घुमाव होगा, और शून्य-पैडिंग केवल कम्प्यूटेशनल सुविधा के लिए होगी। चूंकि, सामान्यतः ऐसा नहीं होता है:

b_{n+N}=e^{{\frac {\pi i}{N}}(n+N)^{2}}=b_{n}\left[e^{{\frac {\pi i}{N}}(2Nn+N^{2})}\right]=(-1)^{N}b_{n}.

इसलिए, N सम और विषम संख्याओं के लिए कनवल्शन चक्रीय है, किन्तु इस स्तिथि में N समग्र संख्या है और कोई सामान्यतः कूली-टुकी जैसे अधिक कुशल एफएफटी एल्गोरिदम का उपयोग करेगा। चूंकि, N विषम के लिए, फिर b_n एंटीपेरियोडिक फलन है और हमारे पास तकनीकी रूप से लंबाई N का ऋणात्मक चक्रीय घुमाव है। चूंकि, ऊपर बताए अनुसार एक शून्य-पैड a_n को कम से कम 2N−1 की लंबाई तक ले जाने पर ऐसे अंतर विलुप्त हो जाते हैं। इसलिए, इसे एक सरल रैखिक कनवल्शन के आउटपुट के उपसमुच्चय के रूप में विचार कदाचित्स सबसे सरल है (अर्थात डेटा का कोई वैचारिक विस्तार, आवधिक या अन्यथा नहीं) है।

z-परिवर्तन

ब्लूस्टीन के एल्गोरिदम का उपयोग (एकतरफा) जेड-ट्रांसफॉर्म (रेबिनर एट अल।, 1969) के आधार पर अधिक सामान्य परिवर्तन की गणना करने के लिए भी किया जा सकता है। विशेष रूप से, यह प्रपत्र के किसी भी परिवर्तन की गणना कर सकता है:

X_{k}=\sum _{n=0}^{N-1}x_{n}z^{nk}\qquad k=0,\dots ,M-1,

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

इस प्रकार से एल्गोरिदम को चिरप ज़ेड-ट्रांसफ़ॉर्म एल्गोरिदम करार दिया गया था, क्योंकि फूरियर-ट्रांसफ़ॉर्म केस (|z| = 1) के लिए, अनुक्रम b_n ऊपर से रैखिक रूप से बढ़ती आवृत्ति का एक सम्मिश्र साइनसॉइड है, जिसे राडार सिस्टम में (रैखिक) चिरप कहा जाता है।

यह भी देखें

फ्रैक्शनल फूरियर रूपांतरण

संदर्भ

↑ ^1.0 ^1.1 A study of the Chirp Z-transform and its applications - Shilling, Steve Alan
↑ "चिरप जेड-ट्रांसफॉर्म - MATLAB czt". www.mathworks.com. Retrieved 2016-09-22.
↑ Martin, Grant D. (November 2005). "Chirp Z-Transform Spectral Zoom Optimization with MATLAB®" (PDF).
↑ Bostan, Alin (2003). बुनियादी कंप्यूटर बीजगणित संचालन के लिए कुशल एल्गोरिदम (PDF) (PhD). Ecole polytechnique.
↑ Bostan, Alin; Schost, Éric (2005). "बिंदुओं के विशेष सेट पर बहुपद मूल्यांकन और प्रक्षेप". Journal of Complexity (in English). 21 (4): 420–446. doi:10.1016/j.jco.2004.09.009.
↑ Engineers Solve 50-Year-Old Puzzle in Signal Processing – Inverse Chirp Z-Transform, By IOWA STATE UNIVERSITY OCTOBER 10, 2019
↑ ^7.0 ^7.1 Bluestein, L. (1970-12-01). "असतत फूरियर रूपांतरण की गणना के लिए एक रैखिक फ़िल्टरिंग दृष्टिकोण". IEEE Transactions on Audio and Electroacoustics. 18 (4): 451–455. doi:10.1109/TAU.1970.1162132. ISSN 0018-9278.
↑ "ब्लूस्टीन का एफएफटी एल्गोरिदम". DSPRelated.com.

सामान्य

लियो आई. ब्लूस्टीन, असतत फूरियर ट्रांसफॉर्म की गणना के लिए एक रैखिक फ़िल्टरिंग दृष्टिकोण, पूर्वोत्तर इलेक्ट्रॉनिक्स अनुसंधान और इंजीनियरिंग मीटिंग रिकॉर्ड '10', 218-219 (1968)।
लॉरेंस आर. रैबिनर, रोनाल्ड डब्ल्यू. शेफ़र, और चार्ल्स एम. रेडर, आलेख/bstj48-5-1249.pdf चिरप ज़ेड-ट्रांसफॉर्म एल्गोरिदम और उसका अनुप्रयोग, बेल सिस्ट। टेक. जे. '48', 1249-1292 (1969)। इसमें भी प्रकाशित: रैबिनर, शेफर, और रेडर, द चिरप ज़ेड-ट्रांसफॉर्म एल्गोरिथ्म , आईईईई ट्रांस। ऑडियो इलेक्ट्रोकॉस्टिक्स '17' (2), 86-92 (1969)।
डी. एच. बेली और पी. एन. स्वार्जट्रॉबर, द फ्रैक्शनल फूरियर ट्रांसफॉर्म एंड एप्लिकेशन, सियाम समीक्षा '33', 389-404 (1991)। (ध्यान दें कि z-परिवर्तन के लिए यह शब्दावली गैरमानक है: एक भिन्नात्मक फूरियर परिवर्तन पारंपरिक रूप से एक पूरी तरह से अलग, निरंतर परिवर्तन को संदर्भित करता है।)
लॉरेंस रैबिनर, द चिर ज़ेड-ट्रांसफ़ॉर्म एल्गोरिदम-सेरेन्डिपिटी में एक पाठ, आईईईई सिग्नल प्रोसेसिंग पत्रिका '21', 118-119 (मार्च 2004)। (ऐतिहासिक टिप्पणी।)
व्लादिमीर सुखॉय और अलेक्जेंडर स्टॉयचेव: यूनिट सर्कल से व्युत्क्रम एफएफटी को सामान्य बनाना, (अक्टूबर 2019)। # खुला एक्सेस।
व्लादिमीर सुखॉय और अलेक्जेंडर स्टोयचेव: यूनिट सर्कल पर चिर आकृति के लिए आईसीजेडटी एल्गोरिदम का संख्यात्मक त्रुटि विश्लेषण, विज्ञान प्रतिनिधि 10, 4852 (2020)।

बाहरी संबंध

A DSP algorithm for frequency analysis - the Chirp-Z Transform (CZT)
Solving a 50-year-old puzzle in signal processing, part two

[Shilling-1] 1.0 ^1.1 A study of the Chirp Z-transform and its applications - Shilling, Steve Alan

[2] "चिरप जेड-ट्रांसफॉर्म - MATLAB czt". www.mathworks.com. Retrieved 2016-09-22.

[3] Martin, Grant D. (November 2005). "Chirp Z-Transform Spectral Zoom Optimization with MATLAB®" (PDF).

[4] Bostan, Alin (2003). बुनियादी कंप्यूटर बीजगणित संचालन के लिए कुशल एल्गोरिदम (PDF) (PhD). Ecole polytechnique.

[5] Bostan, Alin; Schost, Éric (2005). "बिंदुओं के विशेष सेट पर बहुपद मूल्यांकन और प्रक्षेप". Journal of Complexity (in English). 21 (4): 420–446. doi:10.1016/j.jco.2004.09.009.

[6] Engineers Solve 50-Year-Old Puzzle in Signal Processing – Inverse Chirp Z-Transform, By IOWA STATE UNIVERSITY OCTOBER 10, 2019

[bluestein-7] 7.0 ^7.1 Bluestein, L. (1970-12-01). "असतत फूरियर रूपांतरण की गणना के लिए एक रैखिक फ़िल्टरिंग दृष्टिकोण". IEEE Transactions on Audio and Electroacoustics. 18 (4): 451–455. doi:10.1109/TAU.1970.1162132. ISSN 0018-9278.

[8] "ब्लूस्टीन का एफएफटी एल्गोरिदम". DSPRelated.com.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

@@ Line 1: / Line 1: @@
-चिरप [[z-परिणत]] (सीजेडटी) [[असतत फूरियर रूपांतरण]] (डीएफटी) का सामान्यीकरण है। जबकि डीएफटी यूनिट सर्कल के साथ समान रूप से दूरी वाले बिंदुओं पर जेड-ट्रांसफॉर्म का नमूना लेता है, [[ एस विमान |एस विमान]] में सीधी रेखाओं के अनुरूप, जेड-प्लेन में सर्पिल आर्क्स के साथ चहचहाना जेड-ट्रांसफॉर्म नमूने।<ref name=Shilling>[https://krex.k-state.edu/dspace/bitstream/handle/2097/7844/LD2668R41972S43.pdf A study of the Chirp Z-transform and its applications] - Shilling, Steve Alan</ref><ref>{{Cite web|url=http://www.mathworks.com/help/signal/ref/czt.html|title=चिरप जेड-ट्रांसफॉर्म - MATLAB czt|website=www.mathworks.com|access-date=2016-09-22}}</ref> डीएफटी, वास्तविक डीएफटी और ज़ूम डीएफटी की गणना सीजेडटी के विशेष मामलों के रूप में की जा सकती है।
+चिरप [[z-परिणत|जेड-ट्रांसफॉर्म]] (सीजेडटी) [[असतत फूरियर रूपांतरण]] (डीएफटी) का एक सामान्यीकरण है। जबकि डीएफटी यूनिट सर्कल के साथ समान रूप से दूरी वाले बिंदुओं पर जेड-ट्रांसफॉर्म का नमूना लेता है, [[ एस विमान |एस विमान]] में सीधी रेखाओं के अनुरूप, जेड-प्लेन में सर्पिल आर्क्स के साथ चहचहाना जेड-ट्रांसफॉर्म नमूने लेता है।<ref name=Shilling>[https://krex.k-state.edu/dspace/bitstream/handle/2097/7844/LD2668R41972S43.pdf A study of the Chirp Z-transform and its applications] - Shilling, Steve Alan</ref><ref>{{Cite web|url=http://www.mathworks.com/help/signal/ref/czt.html|title=चिरप जेड-ट्रांसफॉर्म - MATLAB czt|website=www.mathworks.com|access-date=2016-09-22}}</ref> इस प्रकार से डीएफटी, वास्तविक डीएफटी और ज़ूम डीएफटी की गणना सीजेडटी के विशेष स्तिथियों के रूप में की जा सकती है।
-विशेष रूप से, चिरप Z ट्रांसफॉर्म, Z ट्रांसफॉर्म की गणना बिंदु z की एक सीमित संख्या पर करता है<sub>k</sub> एक [[लघुगणकीय सर्पिल]] समोच्च के साथ, इसे इस प्रकार परिभाषित किया गया है:<ref name=Shilling/><ref>{{Cite web|url=http://prod.sandia.gov/techlib/access-control.cgi/2005/057084.pdf|title=Chirp Z-Transform Spectral Zoom Optimization with MATLAB®|last=Martin|first=Grant D.|date=November 2005|website=|access-date=}}</ref>
+विशेष रूप से, चिरप Z ट्रांसफॉर्म, Z ट्रांसफॉर्म की गणना बिंदु z<sub>k</sub> की एक सीमित संख्या पर करता है एक [[लघुगणकीय सर्पिल]] समोच्च के साथ, इसे इस प्रकार परिभाषित किया गया है:<ref name=Shilling/><ref>{{Cite web|url=http://prod.sandia.gov/techlib/access-control.cgi/2005/057084.pdf|title=Chirp Z-Transform Spectral Zoom Optimization with MATLAB®|last=Martin|first=Grant D.|date=November 2005|website=|access-date=}}</ref>
 :<math>X_k = \sum_{n=0}^{N-1} x(n) z_{k}^{-n} </math>
 :<math>z_k = A\cdot W^{-k}, k=0,1,\dots,M-1</math>
-जहां A जटिल प्रारंभिक बिंदु है, W बिंदुओं के बीच जटिल अनुपात है, और M गणना किए जाने वाले बिंदुओं की संख्या है।
+जहां A सम्मिश्र प्रारंभिक बिंदु है, W बिंदुओं के बीच सम्मिश्र अनुपात है, और M गणना किए जाने वाले बिंदुओं की संख्या है।
-डीएफटी की तरह, चिरप जेड-ट्रांसफॉर्म की गणना ओ (एन लॉग एन) ऑपरेशंस में की जा सकती है जहां <मैथ डिस्प्ले = "इनलाइन"> एन = \ मैक्स (एम, एन) </मैथ>।
-व्युत्क्रम चिरप जेड-ट्रांसफॉर्म (आईसीजेडटी) के लिए एक ओ(एन लॉग एन) एल्गोरिदम का वर्णन 2003 में किया गया था,<ref>{{Cite thesis |type=PhD |last=Bostan |first=Alin |date=2003 |title=बुनियादी कंप्यूटर बीजगणित संचालन के लिए कुशल एल्गोरिदम|publisher=Ecole polytechnique |url=https://specfun.inria.fr/bostan/these/These.pdf}}</ref><ref>{{Cite journal|last=Bostan|first=Alin|last2=Schost|first2=Éric|date=2005|title=बिंदुओं के विशेष सेट पर बहुपद मूल्यांकन और प्रक्षेप|journal=Journal of Complexity|language=en|volume=21|issue=4|pages=420–446|doi=10.1016/j.jco.2004.09.009|doi-access=free}}</ref> और 2019 में.<ref>[https://scitechdaily.com/engineers-solve-50-year-old-puzzle-in-signal-processing-inverse-chirp-z-transform/ Engineers Solve 50-Year-Old Puzzle in Signal Processing – Inverse Chirp Z-Transform], By IOWA STATE UNIVERSITY OCTOBER 10, 2019</ref>
+डीएफटी की तरह, चिरप जेड-ट्रांसफॉर्म की गणना O(''n'' log ''n'') ऑपरेशंस में की जा सकती है जहां n=\max(M,N)।
+व्युत्क्रम चिरप जेड-ट्रांसफॉर्म (आईसीजेडटी) के लिए एक O(''n'' log ''n'') एल्गोरिदम 2003 और 2019 में वर्णित किया गया था।<ref>{{Cite thesis |type=PhD |last=Bostan |first=Alin |date=2003 |title=बुनियादी कंप्यूटर बीजगणित संचालन के लिए कुशल एल्गोरिदम|publisher=Ecole polytechnique |url=https://specfun.inria.fr/bostan/these/These.pdf}}</ref><ref>{{Cite journal|last=Bostan|first=Alin|last2=Schost|first2=Éric|date=2005|title=बिंदुओं के विशेष सेट पर बहुपद मूल्यांकन और प्रक्षेप|journal=Journal of Complexity|language=en|volume=21|issue=4|pages=420–446|doi=10.1016/j.jco.2004.09.009|doi-access=free}}</ref> <ref>[https://scitechdaily.com/engineers-solve-50-year-old-puzzle-in-signal-processing-inverse-chirp-z-transform/ Engineers Solve 50-Year-Old Puzzle in Signal Processing – Inverse Chirp Z-Transform], By IOWA STATE UNIVERSITY OCTOBER 10, 2019</ref>
 ==ब्लूस्टीन का एल्गोरिदम==
 ब्लूस्टीन का एल्गोरिदम<ref name="bluestein">{{Cite journal|last=Bluestein|first=L.|date=1970-12-01|title=असतत फूरियर रूपांतरण की गणना के लिए एक रैखिक फ़िल्टरिंग दृष्टिकोण|journal=IEEE Transactions on Audio and Electroacoustics|volume=18|issue=4|pages=451–455|doi=10.1109/TAU.1970.1162132|issn=0018-9278}}</ref><ref>{{cite web|url=http://www.dsprelated.com/dspbooks/mdft/Bluestein_s_FFT_Algorithm.html |title=ब्लूस्टीन का एफएफटी एल्गोरिदम|publisher=DSPRelated.com}}</ref> सीजेडटी को एक [[कनवल्शन]] के रूप में व्यक्त करता है और तेज़ फूरियर ट्रांसफॉर्म/आईएफएफटी का उपयोग करके इसे कुशलतापूर्वक कार्यान्वित करता है।
-चूंकि डीएफटी सीजेडटी का विशेष मामला है, यह अभाज्य संख्या आकार सहित मनमाने आकार के [[फास्ट फूरियर ट्रांसफॉर्म]] (डीएफटी) की कुशल गणना की अनुमति देता है। (प्राइम साइज के एफएफटी के लिए अन्य एल्गोरिदम, रेडर का एफएफटी एल्गोरिदम | रेडर का एल्गोरिदम, डीएफटी को कनवल्शन के रूप में फिर से लिखकर भी काम करता है।) इसकी कल्पना 1968 में [[लियो ब्लूस्टीन]] द्वारा की गई थी।<ref name="bluestein" /> ब्लूस्टीन के एल्गोरिदम का उपयोग (एकतरफा) जेड-ट्रांसफॉर्म (रेबिनर एट अल।, 1969) के आधार पर डीएफटी की तुलना में अधिक सामान्य परिवर्तनों की गणना करने के लिए किया जा सकता है।
+चूंकि डीएफटी सीजेडटी का विशेष स्तिथि है, यह अभाज्य संख्या आकार सहित इच्छानुसार आकारों के [[फास्ट फूरियर ट्रांसफॉर्म]] (डीएफटी) की कुशल गणना की अनुमति देता है। इस प्रकार से (प्राइम साइज के एफएफटी के लिए अन्य एल्गोरिदम, '''रेडर का एफएफटी एल्गोरिदम |''' रेडर का एल्गोरिदम, डीएफटी को कनवल्शन के रूप में फिर से लिखकर भी कार्य करता है।) इसकी कल्पना 1968 में [[लियो ब्लूस्टीन]] द्वारा की गई थी।<ref name="bluestein" /> किन्तु ब्लूस्टीन के एल्गोरिदम का उपयोग (एकतरफा) जेड-ट्रांसफॉर्म (रेबिनर एट अल।, 1969) के आधार पर डीएफटी की तुलना में अधिक सामान्य परिवर्तनों की गणना करने के लिए किया जा सकता है।
 याद रखें कि डीएफटी को सूत्र द्वारा परिभाषित किया गया है
@@ Line 29: / Line 28: @@
 \qquad
 k = 0,\dots,N-1. </math>
-यह सारांश वास्तव में दो अनुक्रमों का एक संलयन है<sub>''n''</sub> और बी<sub>''n''</sub> द्वारा परिभाषित:
+यह योग वास्तव में दो अनुक्रमों a और bn का एक संलयन है जिसे निम्न द्वारा परिभाषित किया गया है:
 :<math>a_n = x_n e^{-\frac{\pi i}{N} n^2 }</math>
 :<math>b_n = e^{\frac{\pi i}{N} n^2 },</math>
-एन चरण कारकों द्वारा कनवल्शन के आउटपुट को गुणा करने के साथ बी<sub>''k''</sub><sup>*</sup>. वह है:
+कनवल्शन के आउटपुट को N चरण कारकों ''b<sub>k</sub>''<sup>*</sup> से गुणा किया जाता है। वह है:
 :<math>X_k = b_k^* \left(\sum_{n=0}^{N-1} a_n b_{k-n}\right) \qquad k = 0,\dots,N-1. </math>
-यह कनवल्शन, बदले में, एफएफटी की जोड़ी के साथ किया जा सकता है (साथ ही जटिल [[कलरव]] बी की पूर्व-गणना की गई एफएफटी)<sub>''n''</sub>) [[कनवल्शन प्रमेय]] के माध्यम से। मुख्य बात यह है कि ये एफएफटी समान लंबाई एन के नहीं हैं: इस तरह के कनवल्शन की गणना एफएफटी से केवल शून्य-पैडिंग द्वारा 2N-1 से अधिक या उसके बराबर लंबाई तक की जा सकती है। विशेष रूप से, कोई दो या किसी अन्य [[चिकनी संख्या]] आकार की शक्ति तक पैड कर सकता है, जिसके लिए एफएफटी को कुशलतापूर्वक निष्पादित किया जा सकता है। Cooley-Tukey FFT एल्गोरिथ्म|O(N log N) समय में Cooley-Tukey एल्गोरिथ्म। इस प्रकार, ब्लूस्टीन का एल्गोरिदम प्राइम-आकार डीएफटी की गणना करने के लिए एक ओ (एन लॉग एन) तरीका प्रदान करता है, हालांकि समग्र आकार के लिए कूली-टुकी एल्गोरिदम की तुलना में कई गुना धीमा है।
+यह कनवल्शन, परिवर्तन में, [[कनवल्शन प्रमेय]] के माध्यम से एफएफटी की जोड़ी (साथ ही सम्मिश्र [[कलरव]] b<sub>''n''</sub> की पूर्व-गणना की गई एफएफटी))  के साथ किया जा सकता है । इस प्रकार से मुख्य तथ्य यह है कि ये एफएफटी समान लंबाई ''N'' के नहीं हैं: इस तरह के कनवल्शन की गणना एफएफटी से केवल शून्य-पैडिंग द्वारा 2N-1 से अधिक या उसके समान लंबाई तक की जा सकती है। विशेष रूप से, कोई दो या किसी अन्य [[चिकनी संख्या|अत्यधिक समग्र संख्या]] आकार की शक्ति तक पैड कर सकता है, कूली-टुकी एफएफटी एल्गोरिथ्म O(N log N) समय में कूली-टुकी एल्गोरिथ्म जिसके लिए एफएफटी को कुशलतापूर्वक निष्पादित किया जा सकता है। इस प्रकार, ब्लूस्टीन का एल्गोरिदम प्राइम-आकार डीएफटी की गणना करने के लिए एक O(N log N) विधि प्रदान करता है, चूंकि समग्र आकार के लिए कूली-टुकी एल्गोरिदम की तुलना में कई गुना धीमा है।
-ब्लूस्टीन के एल्गोरिदम में कनवल्शन के लिए शून्य-पैडिंग का उपयोग कुछ अतिरिक्त टिप्पणी का पात्र है। मान लीजिए कि हम लंबाई M ≥ 2N–1 पर शून्य-पैड करते हैं। इसका मतलब यह है कि ए<sub>''n''</sub> एक सरणी ए तक बढ़ाया गया है<sub>''n''</sub> लंबाई M की, जहां A<sub>''n''</sub> = ए<sub>''n''</sub> 0 ≤ n < N और A के लिए<sub>''n''</sub> = 0 अन्यथा—शून्य-पैडिंग का सामान्य अर्थ। हालाँकि, बी के कारण<sub>''k''&ndash;''n''</sub> कनवल्शन में शब्द, b के लिए n के सकारात्मक और नकारात्मक दोनों मान आवश्यक हैं<sub>''n''</sub> (ध्यान दें कि बी<sub>&ndash;''n''</sub> = बी<sub>''n''</sub>). शून्य-पैडेड सरणी के डीएफटी द्वारा निहित आवधिक सीमाओं का मतलब है कि -n एम-एन के बराबर है। इस प्रकार, बी<sub>''n''</sub> एक सरणी बी तक बढ़ाया गया है<sub>''n''</sub> लंबाई M की, जहां B<sub>0</sub> = बी<sub>0</sub>, बी<sub>''n''</sub> = बी<sub>''M''&ndash;''n''</sub> = बी<sub>''n''</sub> 0 < n < N, और B के लिए<sub>''n''</sub> = 0 अन्यथा. सामान्य कनवल्शन प्रमेय के अनुसार, ए और बी का कनवल्शन प्राप्त करने के लिए ए और बी को एफएफटी किया जाता है, बिंदुवार गुणा किया जाता है, और उलटा एफएफटी किया जाता है।
+इस प्रकार से ब्लूस्टीन के एल्गोरिदम में कनवल्शन के लिए शून्य-पैडिंग का उपयोग कुछ अतिरिक्त टिप्पणी का पात्र है। मान लीजिए कि हम लंबाई M ≥ 2N–1 पर शून्य-पैड करते हैं। इसका अर्थ यह है कि ''a<sub>n</sub>'' को लंबाई M की एक सरणी  ''A<sub>n</sub>'' तक विस्तारित किया गया है, जहां ''A<sub>n</sub>'' = ''a<sub>n</sub>'' 0 ≤ n < N के लिए और ''A<sub>n</sub>''  = 0 अन्यथा - "शून्य-पैडिंग" का सामान्य अर्थ। चूंकि, कनवल्शन में ''b<sub>k</sub>''<sub>–''n''</sub>  पद के कारण, ''b<sub>n</sub>'' के लिए n के धनात्मक और ऋणात्मक (ध्यान दें कि ''b''<sub>–''n''</sub> = ''b<sub>n</sub>'') दोनों मान आवश्यक हैं। शून्य-पैडेड सरणी के डीएफटी द्वारा निहित आवधिक सीमाओं का अर्थ है कि -n ''M''–''n'' के समान है। इस प्रकार, ''b<sub>n</sub>'' को लंबाई M की एक सरणी ''B<sub>n</sub>''  तक विस्तारित किया गया है, जहां ''B''<sub>0</sub> = ''b''<sub>0</sub>, ''B<sub>n</sub>'' = ''B<sub>M</sub>''<sub>–''n''</sub> = ''b<sub>n</sub>'' 0 < n < N के लिए, और ''B<sub>n</sub>'' = 0  अन्यथा। सामान्य कनवल्शन प्रमेय के अनुसार, a और b का कनवल्शन प्राप्त करने के लिए A और B को एफएफटी किया जाता है, बिंदुवार गुणा किया जाता है, और विपरीत एफएफटी किया जाता है।
-आइए हम इस बारे में और अधिक सटीक हों कि डीएफटी के लिए ब्लूस्टीन के एल्गोरिदम में किस प्रकार के कनवल्शन की आवश्यकता है। यदि अनुक्रम बी<sub>''n''</sub> अवधि एन के साथ एन में आवधिक थे, तो यह लंबाई एन का चक्रीय घुमाव होगा, और शून्य-पैडिंग केवल कम्प्यूटेशनल सुविधा के लिए होगी। हालाँकि, आम तौर पर ऐसा नहीं होता है:
+आइए हम इस बारे में और अधिक स्पष्ट हों कि डीएफटी के लिए ब्लूस्टीन के एल्गोरिदम में किस प्रकार के कनवल्शन की आवश्यकता है। यदि अनुक्रम b<sub>''n''</sub> अवधि n के साथ N में आवधिक थे, तो यह लंबाई N का चक्रीय घुमाव होगा, और शून्य-पैडिंग केवल कम्प्यूटेशनल सुविधा के लिए होगी। चूंकि, सामान्यतः ऐसा नहीं होता है:
 :<math>b_{n+N} = e^{\frac{\pi i}{N} (n+N)^2 } = b_n \left[ e^{\frac{\pi i}{N} (2Nn+N^2) } \right] = (-1)^N b_n .</math>
-इसलिए, N सम और विषम संख्याओं के लिए कनवल्शन चक्रीय है, लेकिन इस मामले में N [[समग्र संख्या]] है और कोई आमतौर पर Cooley-Tukey जैसे अधिक कुशल FFT एल्गोरिदम का उपयोग करेगा। हालाँकि, N विषम के लिए, फिर b<sub>''n''</sub> [[एंटीपेरियोडिक फ़ंक्शन]] है और हमारे पास तकनीकी रूप से लंबाई एन का नकारात्मक चक्रीय घुमाव है। जब एक शून्य-पैड होता है तो ऐसे अंतर गायब हो जाते हैं<sub>''n''</sub> हालाँकि, जैसा कि ऊपर वर्णित है, कम से कम 2N−1 की लंबाई तक। इसलिए, इसे एक सरल रैखिक कनवल्शन के आउटपुट के सबसेट के रूप में सोचना शायद सबसे आसान है (यानी डेटा का कोई वैचारिक विस्तार, आवधिक या अन्यथा नहीं)।
+इसलिए, N सम और विषम संख्याओं के लिए कनवल्शन चक्रीय है, किन्तु इस स्तिथि में N [[समग्र संख्या]] है और कोई सामान्यतः कूली-टुकी जैसे अधिक कुशल एफएफटी एल्गोरिदम का उपयोग करेगा। चूंकि, N विषम के लिए, फिर b<sub>''n''</sub> [[एंटीपेरियोडिक फ़ंक्शन|एंटीपेरियोडिक फलन]] है और हमारे पास तकनीकी रूप से लंबाई N का ऋणात्मक चक्रीय घुमाव है। चूंकि, ऊपर बताए अनुसार एक शून्य-पैड ''a<sub>n</sub>'' को कम से कम 2N−1 की लंबाई तक ले जाने पर ऐसे अंतर विलुप्त हो जाते हैं। इसलिए, इसे एक सरल रैखिक कनवल्शन के आउटपुट के उपसमुच्चय के रूप में विचार कदाचित्स सबसे सरल है (अर्थात डेटा का कोई वैचारिक विस्तार, आवधिक या अन्यथा नहीं) है।
 == z-परिवर्तन ==
@@ Line 52: / Line 51: @@
 \qquad
 k = 0,\dots,M-1, </math>
-एक मनमाना [[जटिल संख्या]] z के लिए और इनपुट और आउटपुट की भिन्न संख्या N और M के लिए। ब्लूस्टीन के एल्गोरिदम को देखते हुए, इस तरह के परिवर्तन का उपयोग किया जा सकता है, उदाहरण के लिए, स्पेक्ट्रम के कुछ हिस्से के अधिक सूक्ष्म अंतर वाले इंटरपोलेशन को प्राप्त करने के लिए (हालांकि ज़ूम एफएफटी के समान आवृत्ति रिज़ॉल्यूशन अभी भी कुल नमूना समय तक सीमित है), मनमाने ढंग से बढ़ाएं स्थानांतरण-फ़ंक्शन विश्लेषण आदि में ध्रुव।
+एक इच्छानुसार  [[जटिल संख्या|सम्मिश्र संख्या]] z के लिए और इनपुट और आउटपुट की भिन्न संख्या N और M के लिए है। ब्लूस्टीन के एल्गोरिदम को देखते हुए, इस तरह के परिवर्तन का उपयोग किया जा सकता है, उदाहरण के लिए, स्पेक्ट्रम के कुछ भाग के अधिक सूक्ष्म अंतर वाले इंटरपोलेशन को प्राप्त करने के लिए (चूंकि ज़ूम एफएफटी के समान आवृत्ति रिज़ॉल्यूशन अभी भी कुल नमूना समय तक सीमित है), इच्छानुसार रूप से से ध्रुवों को बढ़ाएं स्थानांतरण-फ़ंक्शन विश्लेषण आदि।
-एल्गोरिदम को चिरप ज़ेड-ट्रांसफ़ॉर्म एल्गोरिदम करार दिया गया था, क्योंकि फूरियर-ट्रांसफ़ॉर्म केस (|z| = 1) के लिए, अनुक्रम बी<sub>''n''</sub> ऊपर से रैखिक रूप से बढ़ती आवृत्ति का एक जटिल साइनसॉइड है, जिसे [[राडार]] सिस्टम में (रैखिक) चिरप कहा जाता है।
+इस प्रकार से एल्गोरिदम को चिरप ज़ेड-ट्रांसफ़ॉर्म एल्गोरिदम करार दिया गया था, क्योंकि फूरियर-ट्रांसफ़ॉर्म केस (|z| = 1) के लिए, अनुक्रम b<sub>''n''</sub> ऊपर से रैखिक रूप से बढ़ती आवृत्ति का एक सम्मिश्र साइनसॉइड है, जिसे [[राडार]] सिस्टम में (रैखिक) चिरप कहा जाता है।
 ==यह भी देखें==

Anonymous

Search

चिर्प जेड-रूपांतरण: Difference between revisions

Namespaces

More

Page actions

Revision as of 17:06, 23 November 2023

Contents

ब्लूस्टीन का एल्गोरिदम

z-परिवर्तन

यह भी देखें

संदर्भ

सामान्य

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

चिर्प जेड-रूपांतरण: Difference between revisions

Revision as of 17:06, 23 November 2023

ब्लूस्टीन का एल्गोरिदम

z-परिवर्तन

यह भी देखें

संदर्भ

सामान्य

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories