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

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

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

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

व्युत्क्रम चिर्प जेड-रूपांतरण (आईसीजेडटी) के लिए एक O(n log n) एल्गोरिदम 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.$

यह योग वास्तव में दो अनुक्रमों 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 ऊपर से रैखिक रूप से बढ़ती आवृत्ति का एक सम्मिश्र साइनसॉइड है, जिसे राडार सिस्टम में (रैखिक) चिर्प कहा जाता है।

यह भी देखें

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

संदर्भ

सामान्य

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