चिर्प जेड-रूपांतरण

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

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

$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 गणना किए जाने वाले बिंदुओं की संख्या है।

डीएफटी की तरह, चिरप जेड-ट्रांसफॉर्म की गणना ओ (एन लॉग एन) ऑपरेशंस में की जा सकती है जहां <मैथ डिस्प्ले = "इनलाइन"> एन = \ मैक्स (एम, एन) </मैथ>। व्युत्क्रम चिरप जेड-ट्रांसफॉर्म (आईसीजेडटी) के लिए एक ओ(एन लॉग एन) एल्गोरिदम का वर्णन 2003 में किया गया था, और 2019 में.

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

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

चूंकि डीएफटी सीजेडटी का विशेष मामला है, यह अभाज्य संख्या आकार सहित मनमाने आकार के फास्ट फूरियर ट्रांसफॉर्म (डीएफटी) की कुशल गणना की अनुमति देता है। (प्राइम साइज के एफएफटी के लिए अन्य एल्गोरिदम, रेडर का एफएफटी एल्गोरिदम | रेडर का एल्गोरिदम, डीएफटी को कनवल्शन के रूप में फिर से लिखकर भी काम करता है।) इसकी कल्पना 1968 में लियो ब्लूस्टीन द्वारा की गई थी। ब्लूस्टीन के एल्गोरिदम का उपयोग (एकतरफा) जेड-ट्रांसफॉर्म (रेबिनर एट अल।, 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.$

यह सारांश वास्तव में दो अनुक्रमों का एक संलयन है_n और बी_n द्वारा परिभाषित:

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

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

एन चरण कारकों द्वारा कनवल्शन के आउटपुट को गुणा करने के साथ बी_k^*. वह है:

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

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

ब्लूस्टीन के एल्गोरिदम में कनवल्शन के लिए शून्य-पैडिंग का उपयोग कुछ अतिरिक्त टिप्पणी का पात्र है। मान लीजिए कि हम लंबाई M ≥ 2N–1 पर शून्य-पैड करते हैं। इसका मतलब यह है कि ए_n एक सरणी ए तक बढ़ाया गया है_n लंबाई M की, जहां A_n = ए_n 0 ≤ n < N और A के लिए_n = 0 अन्यथा—शून्य-पैडिंग का सामान्य अर्थ। हालाँकि, बी के कारण_k–n कनवल्शन में शब्द, b के लिए n के सकारात्मक और नकारात्मक दोनों मान आवश्यक हैं_n (ध्यान दें कि बी_–n = बी_n). शून्य-पैडेड सरणी के डीएफटी द्वारा निहित आवधिक सीमाओं का मतलब है कि -n एम-एन के बराबर है। इस प्रकार, बी_n एक सरणी बी तक बढ़ाया गया है_n लंबाई M की, जहां B₀ = बी₀, बी_n = बी_M–n = बी_n 0 < n < N, और B के लिए_n = 0 अन्यथा. सामान्य कनवल्शन प्रमेय के अनुसार, ए और बी का कनवल्शन प्राप्त करने के लिए ए और बी को एफएफटी किया जाता है, बिंदुवार गुणा किया जाता है, और उलटा एफएफटी किया जाता है।

आइए हम इस बारे में और अधिक सटीक हों कि डीएफटी के लिए ब्लूस्टीन के एल्गोरिदम में किस प्रकार के कनवल्शन की आवश्यकता है। यदि अनुक्रम बी_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 समग्र संख्या है और कोई आमतौर पर Cooley-Tukey जैसे अधिक कुशल FFT एल्गोरिदम का उपयोग करेगा। हालाँकि, N विषम के लिए, फिर b_n एंटीपेरियोडिक फ़ंक्शन है और हमारे पास तकनीकी रूप से लंबाई एन का नकारात्मक चक्रीय घुमाव है। जब एक शून्य-पैड होता है तो ऐसे अंतर गायब हो जाते हैं_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) के लिए, अनुक्रम बी_n ऊपर से रैखिक रूप से बढ़ती आवृत्ति का एक जटिल साइनसॉइड है, जिसे राडार सिस्टम में (रैखिक) चिरप कहा जाता है।

यह भी देखें

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

संदर्भ

सामान्य

• लियो आई. ब्लूस्टीन, असतत फूरियर ट्रांसफॉर्म की गणना के लिए एक रैखिक फ़िल्टरिंग दृष्टिकोण, पूर्वोत्तर इलेक्ट्रॉनिक्स अनुसंधान और इंजीनियरिंग मीटिंग रिकॉर्ड '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