View source for गोएर्टज़ेल एल्गोरिदम

{{Short description|Technique in digital signal processing}}
गर्ट्जेल एल्गोरिथ्म एक तकनीक है जिसका उपयोग अंकीय संकेत संसाधन(डीएसपी) में असतत फूरियर परिवर्तन(डीएफटी) के व्यक्त शब्दों की कुशल मूल्यांकन के लिए किया जाता है। यह कुछ व्यावसायिक अनुप्रयोगों में उपयुक्त होता है, जैसे कि पारंपरिक अनुरूप टेलीफोन के कुंजीपटल के पुश बटन द्वारा उत्पन्न द्वितोन बहु-आवृत्ति संकेतन(डीटीएमएफ़) टोन की पहचान में। यह एल्गोरिथ्म पहली बार 1958 में जेराल्ड गोर्ट्जेल द्वारा वर्णित किया गया था।<ref>{{Citation |first=G. |last=Goertzel |date=January 1958 |title= An Algorithm for the Evaluation of Finite Trigonometric Series |journal= American Mathematical Monthly |volume=65 |issue=1 |pages=34&ndash;35 |doi=10.2307/2310304 |jstor=2310304 }}</ref>

डीएफटी की तरह, गोएर्टज़ेल एल्गोरिदम एक [[पृथक संकेत]] से एक चयनित आवृत्ति घटक का विश्लेषण करता है।<ref>{{Citation |last=Mock |first=P. |url=http://focus.ti.com/lit/an/spra168/spra168.pdf |title=Add DTMF Generation and Decoding to DSP-μP Designs |journal=EDN |date=March 21, 1985 |issn=0012-7515 }}; also found in DSP Applications with the TMS320 Family, Vol. 1, Texas Instruments, 1989.</ref><ref>{{Citation |first=Chiouguey J. |last=Chen |url=http://focus.ti.com/lit/an/spra066/spra066.pdf |title=Modified Goertzel Algorithm in DTMF Detection Using the TMS320C80 DSP| publisher=Texas Instruments |series=Application Report |id=SPRA066 |date=June 1996 }}</ref><ref>{{Citation |last=Schmer |first=Gunter |url=http://focus.ti.com/lit/an/spra096a/spra096a.pdf |title=DTMF Tone Generation and Detection: An Implementation Using the TMS320C54x |publisher=Texas Instruments |series=Application Report |id=SPRA096a |date= May 2000 }}</ref>सीधे डीएफटी की गणनाओं के विपरीत, गोर्ट्जेल एल्गोरिथ्म प्रत्येक परिस्थिति में एक एकल वास्तविक मूल्य वाला समक लागू करता है, जिसे वास्तविक मूल्य वाले अंकगणित का उपयोग वास्तविक मूल्य वाले इनपुट अनुक्रमों के लिए किया जाता है। पूर्ण वर्णक्रम को आवरण करने के लिए (बिना कोई एक नए आँकड़े धारा के लिए जहां समक पुनर्गणन के लिए पूनः प्रयुक्त किए जाते हैं, जिसका गणनात्मक संकट अस्थिर डीएफटी के समक प्रायोजन होता है), गोर्ट्जेल एल्गोरिथ्म तेज [[फूरियर परिवर्तन]](एफएफटी) एल्गोरिथ्मों की तुलना में अधिक संकट का क्रम होता है, लेकिन एक छोटी संख्या के चयनित आवृत्ति घटकों की गणना के लिए, यह संख्यात्मक रूप से अधिक कुशल है। गोएर्टज़ेल एल्गोरिदम की सरल संरचना इसे छोटे संसाधित और अंतर्निहित अनुप्रयोगों के लिए उपयुक्त बनाती है।

गोर्ट्जेल एल्गोरिथम को "उलटे रूप में" एक ज्यावक्रीय संश्लेषण  कार्य के रूप में भी उपयोग किया जा सकता है, जिसमें प्रति उत्पन्न नमूने के लिए केवल 1 गुणा और 1 घटाना की आवश्यकता होती है।<ref>{{Citation |last1=Cheng |first1=Eric |last2=Hudak |first2=Paul |url=http://haskell.cs.yale.edu/wp-content/uploads/2011/01/AudioProc-TR.pdf |archive-url=https://web.archive.org/web/20170328022024/http://haskell.cs.yale.edu/wp-content/uploads/2011/01/AudioProc-TR.pdf |url-status=dead |archive-date=2017-03-28 |title=Audio Processing and Sound Synthesis in Haskell |date=January 2009 }}</ref>



== एल्गोरिथ्म ==
{{cleanup|section|reason=inconsistent styles between equations and labels|date=February 2014}}
मुख्य गोर्ट्जेल एल्गोरिथ्म में का मुख्य गणना एक [[डिजिटल फ़िल्टर|अंकीय फ़िल्टर]]  के रूप में होती है, और इस कारण इसे अधिकतर एक गोर्ट्जेल फ़िल्टर के रूप में कहा जाता है। फ़िल्टर द्विमत्रीय में एक इनपुट अनुक्रम पर प्रवृत्ति करता है  <math>x[n]</math> एक प्राचल के द्वारा <math>\omega_0</math>, जो विश्लेषण की जाने वाली आवृत्ति देता है, प्रति नमूने धनात्मकरण किया जाता है।

पहले स्तर पर एक आवर्ती अनुक्रम की गणना करता है, <math>s[n]</math>:
{{NumBlk|:|<math> s[n] = x[n] + 2 \cos(\omega_0) s[n-1] - s[n-2]. </math>|1}}
दूसरे स्तर पर, निम्नलिखित फ़िल्टर को <math>s[n]</math>, पर लागू किया जाता है, जिससे आउटपुट अनुक्रम उत्पन्न होता है <math>y[n]</math>:
{{NumBlk|:|<math>y[n] = s[n] - e^{-j \omega_0} s[n-1].</math>|2}}

पहले फ़िल्टर स्तर को देखा जा सकता है कि यह एक द्वितीय-क्रम आईआईआर फ़िल्टर है जिसमें एक प्रत्यक्ष-रूप संरचना है। इस विशेष संरचना का यह गुण होता है कि इसके आंतरिक स्थिति परिवर्तनीय चरण से पिछले आउटपुट मानों के समान होते हैं। आवश्यकता होने पर, इनपुट मानों <math>x[n]</math> के लिए <math>n < 0</math>, सभी को समान 0 माना जाता है। प्रारंभिक फ़िल्टर स्थिति स्थापित करने के लिए ताकि मूल्यांकन नमूने <math>x[0]</math> पर आरंभ हो सके, फ़िल्टर स्थितियों को प्रारंभिक मान दिए जाते हैं <math>s[-2] = s[-1] = 0</math>. अलाभकारी जोखिम से बचने के लिए, आवृत्ति <math>\omega_0</math> अधिकतर सीमित की जाती है 0 से π तक क्योंकि (न्यूक्विस्ट-शैनन नमूना दिया गया है); इस श्रेणी के बाहर की मान उपयोग में बिना मतलब नहीं है, लेकिन यह इस श्रेणी के अंदर उपनाम आवृत्ति का उपयोग करने के समान है, क्योंकि घातीय कार्य का एक आवधि होती है 2π में <math>\omega_0</math>में।

दूसरे चरण के निस्पंदनको एक [[परिमित आवेग प्रतिक्रिया]] के रूप में देखा जा सकता है, क्योंकि इसकी गणनाएँ इसके पिछले आउटपुट में से किसी भी का उपयोग नहीं करती हैं।

Z-परिवर्तन विधियों का प्रयोग फ़िल्टर सोपानी की गुणविशेषताओं का अध्ययन करने के लिए किया जा सकता है। पहले फ़िल्टर चरण के Z परिवर्तन, जो समीकरण (1) में दिया गया है, का है:
{{NumBlk|:|<math>\begin{align}
 \frac{S(z)}{X(z)} &= \frac{1}{1 - 2 \cos(\omega_0) z^{-1} + z^{-2}} \\
  & = \frac{1}{(1 - e^{+j \omega_0} z^{-1})(1 - e^{-j \omega_0} z^{-1})}.
\end{align}</math>|3}}
समीकरण (2) में दिए गए दूसरे फ़िल्टर चरण का Z परिवर्तन है
{{NumBlk|:|<math>\frac{Y(z)}{S(z)} = 1 - e^{-j \omega_0}z^{-1}.</math>|4}}
दो फ़िल्टर चरणों के सोपानी का संयुक्त स्थानांतरण फ़ंक्शन तब होता है
{{NumBlk|:|<math>\begin{align} 
 \frac{S(z)}{X(z)} \frac{Y(z)}{S(z)} = \frac{Y(z)}{X(z)} &= \frac{(1 - e^{-j \omega_0}z^{-1})}{(1 - e^{+j \omega_0} z^{-1})(1 - e^{-j \omega_0} z^{-1})} \\
 &= \frac{1}{1 - e^{+j \omega_0} z^{-1}}.
\end{align}</math>|5}}
यह वापस एक समकालिक समय-डोमेन अनुक्रम में परिवर्तित किया जा सकता है, और शब्दों को वापस लाए जा सकते हैं पहले इनपुट शब्द के सूचकांक पर <math>n = 0</math>:{{citation needed|date=February 2014}}
{{NumBlk|:|<math> \begin{align}
 y[n] &= x[n] + e^{+j \omega_0} y[n-1] \\
  &= \sum_{k=-\infty}^{n}x[k] e^{+j \omega_0 (n-k)} \\ 
  &= e^{j \omega_0 n} \sum_{k=0}^{n} x[k] e^{-j \omega_0 k} \qquad \text{since }\forall k < 0, x[k] = 0.
\end{align} </math>|6}}

== संख्यात्मक स्थिरता ==
यह देखा जा सकता है कि फ़िल्टर के [[Z परिवर्तन]] का [[ध्रुव (जटिल विश्लेषण)]] निम्नलिखित स्थित है: <math>e^{+j \omega_0}</math> और <math>e^{-j \omega_0}</math>, जो एक इकाई त्रिज्या के मूल पर केंद्रित विकल्प त्रिज्या के वृत्तीय परिप्रेक्ष्य पर स्थित हैं। यह गुणवत्ता सुनिश्चित करती है कि फ़िल्टर प्रक्रिया मामूली रूप से स्थिर है और [[संख्यात्मक त्रुटि]] एकत्रित होने की संभावना होती है जब कम-गुणस्तर अंकगणित और लंबे इनपुट अनुक्रमों का उपयोग करके गणना की जाती है।<ref>{{cite journal|last1=Gentleman|first1=W. M.|title=फूरियर गुणांक की गणना के लिए गोएर्टज़ेल (वाट) विधि का एक त्रुटि विश्लेषण|journal=The Computer Journal|date=1 February 1969|volume=12|issue=2|pages=160–164|doi=10.1093/comjnl/12.2.160|doi-access=free}}</ref> एक संख्यात्मक रूप से स्थिर संस्करण क्रिश्चियन रीन्स्च द्वारा प्रस्तावित किया गया था।<ref>{{Citation |first1=J. |last1=Stoer |first2=R. |last2=Bulirsch |date=2002 |title= Introduction to Numerical Analysis |publisher= Springer |isbn=9780387954523}}</ref>


== डीएफटी गणना ==
महत्वपूर्ण स्थिति में, एक डीएफटी शब्द की गणना के लिए निम्नलिखित विशेष प्रतिबंधन लागू होते हैं।
* फ़िल्टरउस सूचकांक पर समाप्त होती  है <math>n = N</math>, जहाँ <math>N</math> डीएफटी के इनपुट अनुक्रम की मात्राओं की संख्या है।
* गोएर्टज़ेल विश्लेषण के लिए चुनी गई आवृत्तियाँ विशेष रूप में प्रतिबंधित होती हैं।
{{NumBlk|::|<math>\omega_0 = 2 \pi \frac{k}{N}.</math>|7}}
*सूचकांक संख्या <math>k</math> यह दर्शाता है कि डीएफटी की "आवृत्ति बिन" सूचकांक संख्याओं के समुच्चय से चुना गया है
{{NumBlk|::|<math>k \in \{ 0, 1, 2, ..., N-1 \}. </math>|8}}

इन प्रतिस्थापनों को समीकरण (6) में बनाना और उस पद का अवलोकन करना <math>e^{+j 2 \pi k} = 1</math>, समीकरण (6) फिर निम्नलिखित रूप लेता है:
{{NumBlk|:|<math>y[N] =  \sum_{n=0}^{N} x[n]e^{-j 2 \pi \frac{n k}{N}}. </math>|9}}

हम देख सकते हैं कि समीकरण (9) का दाहिना पक्ष डीएफटी शब्द <math>X[k]</math> के परिभाषित सूत्र के बहुत ही समान है, लेकिन बिल्कुल वैसा नहीं है जैसा कि डीएफटी के सूचकांक संख्या <math>k</math>के लिए होता है। समीकरण (9) में दिखाए गए योग के लिए <math>N+1</math> इनपुट शब्द की आवश्यकता होती है, लेकिन एक डीएफटी का मूल्यांकन करते समय केवल <math>N</math> इनपुट शब्द उपलब्ध होते हैं।एक सरल लेकिन सुरुचिपूर्ण समीचीन है कि इनपुट अनुक्रम <math>x[n]</math> को एक और कृत्रिम मूल्य के साथ <math>x[N] = 0</math> के साथ विस्तारित किया जाए।<ref>{{cite web|url=http://cnx.org/content/m12024/latest/ |title=गोएर्टज़ेल का एल्गोरिदम|publisher=Cnx.org |date=2006-09-12 |access-date=2014-02-03}}</ref> हम समीकरण (9) से देख सकते हैं कि अंतिम परिणाम पर गणना से मानवीय प्रभाव वही है जैसे कि <math>x[N]</math> शब्दक निकालना, इस प्रकार उचित DFT मूल्य प्राप्त होता है।

हालाँकि, एक और उत्कृष्ट दृष्टिकोण है जिससे अतिरिक्त फ़िल्टर उत्तीर्ण बचाया जा सकता है। समीकरण (1) से, हम यह देख सकते हैं कि जब विस्तारित इनपुट मान <math>x[N] = 0</math> अंतिम चरण में प्रयुक्त होता है,
{{NumBlk|:|<math>s[N] =  2 \cos(\omega_0) s[N-1] - s[N-2].</math>|10}}
इस प्रकार, एल्गोरिथ्म निम्नलिखित रूप में पूरा किया जा सकता है:
* इस प्रकार, आईआईआर फ़िल्टर को इनपुट पद <math>x[N-1]</math> की प्रसंस्करण के बाद समाप्त करें।
* समीकरण (10) का उपयोग करके पिछले आउटपुट <math>s[N]</math> और <math>s[N-1]</math> से<math>s[N-2]</math> को निर्मित करें।
* समीकरण (2) का उपयोग कीजिए जिसमें परिकलित <math>s[N]</math> मान और फ़िल्टर की अंतिम सीधी गणना द्वारा प्राप्त <math>s[N-1]</math> के साथ करें।

अंतिम दो गणितीय क्रियाएँ बीजगणितीय रूप से संयोजित करके सरलित की जाती हैं:
{{NumBlk|:|<math>\begin{align}
 y[N] & = s[N] - e^{-j 2 \pi \frac{k}{N}} s[N-1] \\
  & = (2 \cos(\omega_0) s[N-1] - s[N-2]) - e^{-j 2 \pi \frac{k}{N}} s[N-1] \\
  & =  e^{j 2 \pi \frac{k}{N}} s[N-1] - s[N-2].
\end{align}</math>|11}}

ध्यान दें कि फ़िल्टर अद्यतनीकरण को शब्द <math>N-1</math> पर रोकना और समीकरण (11) की बजाय सीधे समीकरण (2) का लागू करना, अंतिम फ़िल्टर स्थिति अद्यतनीकरण को छोड़ देता है, जिससे गलत चर के साथ परिणाम मिलता है।<ref>{{cite web|url=http://www.eetimes.com/design/signal-processing-dsp/4024443/The-Goertzel-Algorithm |title=Electronic Engineering Times &#124; Connecting the Global Electronics Community |publisher=EE Times |access-date=2014-02-03}}</ref>

गोएर्टज़ेल एल्गोरिदम के लिए चुनी गई विशेष फ़िल्टर संरचना उसके निपुण डीएफटी(DFT) गणना की कुंजी है। हम देख सकते हैं कि केवल एक आउटपुट मान है <math>y[N]</math> का उपयोग डीएफटी(DFT)  की गणना के लिए किया जाता है, इसलिए अन्य सभी आउटपुट मानों की गणनाओं को छोड़ दिया जाता है। चूँकि एफआईआर फ़िल्टर की गणना नहीं की जाती है, इसलिए आईआईआर चरण की गणनाएँ <math>s[0], s[1]</math>, आदि की जाती हैं। पहले चरण के आंतरिक स्थिति को अद्यतन करने के बाद, उन्हें तुरंत छोड़ दिया जा सकता है।

ऐसा लगता है कि यह एक विरोधाभास छोड़ता है: एल्गोरिदम को पूरा करने के लिए, आईआईआर फ़िल्टरचरण को एक बार मूल दो आउटपुट्स का उपयोग करके मूल्यांकन किया जाना चाहिए, जबकि गणनात्मक प्रशासन के लिए आईआईआर फ़िल्टर चरण अपने आउटपुट मूल्यों को छोड़ देता है। यहाँ प्रत्यक्ष-रूप फ़िल्टर संरचना की गुणवत्ताएँ लागू होती हैं। आईआईआर फ़िल्टर के दो आंतरिक स्थिति चरण आउटपुट के अंतिम दो मान प्रदान करते हैं, जो एफआईआर फ़िल्टर चरण की मूल्यांकन के लिए आवश्यक होते हैं।

== अनुप्रयोग ==

=== शक्ति-स्पेक्ट्रम मान ===
समीकरण (6) की जाँच करते हुए, एक अंतिम आईआईआर फ़िल्टर पास के माध्यम से मान <math> y[N]</math> की गणना के लिए एक सहायक इनपुट मान <math> x[N]=0 </math> का उपयोग करके पिछले मान <math>y[N-1]</math>पर 1 के परिमाण के एक संज्ञाक गुणक का लागू होता है। इस परिणामस्वरूप, <math>y[N]</math> और <math>y[N-1]</math> समतुल्य सिग्नल शक्ति का प्रतिनिधित्व करते हैं। समीकरण (11) को लागू करके मान <math>y[N]</math> से सिग्नल शक्ति की गणना करना या समीकरण (2) को लागू करके मान <math>y[N-1]</math>से सिग्नल शक्ति की गणना करना एक समान रूप से मान्य है। दोनों मामलों में निम्नलिखित अभिव्यक्ति से निर्देशित होते हैं जिनका डीएफटी मान <math>X[k]</math>द्वारा प्रतिनिधित किया जाता है:
{{NumBlk|:|<math>\begin{align}
  X[k] \, X'[k] & = y[N] \, y'[N] = y[N-1] \, y'[N-1] \\
  & = s^2[N-1] + s^2[N-2] - 2 \cos \left(2 \pi \frac{k}{N} \right) \, s[N-1] \, s[N-2].
\end{align} </math>|12}}

नीचे दिए गए [[छद्मकोड]] में, वास्तविक-मूल्य वाले इनपुट आँकड़े को  मूल<code>x</code> में संग्रह किया जाता है और चरणशील फ़िल्टर से आउटपुट इतिहास को अस्थायी रूप से <code>sprev</code> और <code>sprev2</code> में संग्रह किया जाता है। <code>Nterms</code> सरणी में नमूनों की संख्या है, और <code>Kterm</code> रुचि की आवृत्ति का प्रतिनिधित्व करता है, जिसे नमूना अवधि से गुणा किया जाता है।

 Nterms यहां परिभाषित हैं
 यहां Kterm का चयन किया गया
 ω = 2 × π × Kterm / Nterms;
 गुणांक�:= 2 × cos(ω)
 
 स्प्रेव�:= 0
 स्प्रेव2�:= 0
 0 से Nterms-1 की सीमा में प्रत्येक सूचकांक ''n'' के लिए करें
     ss:= x[n] + गुणांक × स्प्रेव - स्प्रेव2
     sprev2v:= sprev
     स्प्रेव�:= एस
 अंत
 
 शक्ति�:= स्प्रेव<sup>2</sup>+sprev2<sup>2</sup> - (coeff × sprev × sprev2)

यह संभव है<ref>{{cite web |date=August 25, 2011 |first=Wilfried |last=Elmenreich |title=गोएर्टज़ेल फ़िल्टर का उपयोग करके आवृत्ति का कुशलतापूर्वक पता लगाना|url=http://netwerkt.wordpress.com/2011/08/25/goertzel-filter/ |access-date=16 September 2014}}</ref> गणनाओं को ऐसे संगठित करने के लिए कि आने वाले नमूनों को एकल रूप से एक [[सॉफ़्टवेयर ऑब्जेक्ट]] को प्रस्तुत किया जाता है जो अपडेट के बीच फ़िल्टर स्थिति को बनाए रखता है, और अन्य प्रसंस्करण पूरी होने के बाद अंतिम शक्ति परिणाम तक पहुँचा जा सकता है।

=== वास्तविक-मूल्यवान अंकगणित के साथ एकल डीएफटी शब्द ===
वास्तविक-मूल्य वाले इनपुट डेटा का मामला अधिकतर उत्पन्न होता है, विशेष रूप से अंतर्निहित प्रणाली में जहां इनपुट धाराओं भौतिक प्रक्रियाओं के सीधे मापों से परिणत होती हैं। जब इनपुट आँकड़े वास्तविक-मूल्य वाले होते है, तो फ़िल्टर की आंतरिक स्थिति चरण <code>sprev</code> और <code>sprev2</code> को भी वास्तविक मूल्य वाले होने के कारण, पहले IIR चरण में कोई भी जटिल अंकगणित की आवश्यकता नहीं होती है। वास्तविक-मूल्य अंकगणित के लिए अनुकूलित करने के लिए सामान्यत: उपयुक्त वास्तविक मूल्य आँकड़े प्रकारों को चरणों के लिए लागू करना बहुत सरल होता है।

इनपुट मान <math>x[N-1]</math>, का उपयोग करके गणनाएँ करने के बाद और फ़िल्टर परिणामों को समाप्त करने के बाद, समीकरण (11) को लागू करके डीएफटी मान का मूल्यांकन किया जाना आवश्यक होता है। अंतिम गणना जटिल-मूल्य अंकगणित का उपयोग करती है, लेकिन इसे वास्तविक मूल्य अंकगणित में बदला जा सकता है, वास्तविक और काल्पनिक शब्दों को अलग करके:
{{NumBlk|:|<math>\begin{align} 
  c_r  &= \cos(2 \pi \tfrac{k}{N}), \\
  c_i  &= \sin(2 \pi \tfrac{k}{N}), \\
  y[N] &= c_r s[N-1] - s[N-2] +  j c_i s[N-1].
\end{align} 
</math>|13}}

शक्ति-स्पेक्ट्रम आवेदन के साथ तुलना करते समय, यह एकमात्र अंतर है कि समापन के लिए उपयुक्त गणना होती है:

(सिग्नल शक्ति कार्यान्वयन में जैसे आईआईआर फ़िल्टर गणनाएँ की गई हैं, वैसे ही यहाँ भी आईआईआर फ़िल्टर गणनाएँ की जाती हैं)

XKreal = sprev * cr - sprev2;
XKimag = sprev * ci;
</पूर्व>

=== चरण का पता लगाना ===
यह आवेदन एक ही डीएफटी मान <math>X[k]</math>, की मूल्यांकन की आवश्यकता है, जैसा कि पिछले खंड में चर्चित किया गया था, वास्तविक मूल्य वाले या जटिल मूल्य वाले इनपुट 

धारा का उपयोग करके। फिर सिग्नल चरण का मूल्यांकन किया जा सकता है, जैसे कि:{{NumBlk|:|<math> \phi = \tan^{-1}\frac{\Im(X[k])}{ \Re(X[k])}, </math>|14}}
व्युत्क्रम स्पर्शज्या फलन की गणना करते समय अपशिष्टताओं, चतुर्थांश, और इसी प्रकार की स्थितियों के लिए उपयुक्त सावधानियाँ लेना महत्वपूर्ण है।

=== वास्तविक अंकगणित में जटिल संकेत ===
चूंकि जटिल सिग्नल वास्तविक और काल्पनिक भागों में रूपांतरित होते हैं, इसलिए गोएर्टज़ेल एल्गोरिथ्म को वास्तविक अंकगणित में रूपांतरित किया जा सकता है, वास्तविक भागों के क्रम के ऊपर अलग से गणना करने से <math>y_\text{r}[n]</math>, प्राप्त होता है, और काल्पनिक भागों के क्रम के ऊपर अलग से गणना करने से <math>y_\text{i}[n]</math> प्राप्त होता है। इसके बाद, दो जटिल मूल्य वाले आंशिक परिणामों को पुनर्संयोजित किया जा सकता है:
{{NumBlk|:|<math>y[n] = y_\text{r}[n] + j y_\text{i}[n].</math>|15}}

== अभिकलनात्मक जटिलता ==
{{Refimprove section|date=February 2014}}
* [[अभिकलनात्मक जटिलता सिद्धांत]] के अनुसार, एक सेट के <math>M</math> डीएफटी मानों की गणना, <math>N</math> मूल्यों वाले आंकड़ा समुच्चय पर <math>M</math> गोएर्टज़ेल एल्गोरिथम के अनुप्रयोगों का उपयोग करके, हर कार्य की लागत <math>K</math> के साथ संभावितता है, तो [[मात्रकीय जटिलता]] होगी <math>O(KNM)</math>.

: एक एकल DFT बिन <math>X(f)</math> की गणना के लिए जिसकी आयतन अनुक्रम <math>N</math> है, गोर्टजेल एल्गोरिदम को <math>2 N</math> गुणांकण और <math>4\ N</math> जोड़/घटाव की गणना कुंडली के अंदर में आवश्यक होती है, साथ ही 4 गुणांकण और 4 अंतिम जोड़/घटाव, कुल मिलाकर <math>2 N + 4</math> गुणांकण और <math>4 N + 4</math> जोड़/घटाव की गणना की आवश्यकता होती है। यह हर एक आवृत्तियाँ <math>M</math> के लिए दोहराया जाता है।

* इसके विपरीत, <math>N</math> मूल्यों वाले आंकड़ा समुच्चय पर एफएफटीका उपयोग करने की मात्रकीय जटिलता निम्नलिखित होती है: <math>O(KN\log_2(N))</math>.

: इसे सीधे लागू करना कठिन हो सकता है क्योंकि यह एफएफटी एल्गोरिदम पर निर्भर करता है, लेकिन एक विशिष्ट उदाहरण एक रेडिक्स -2 एफएफटी हो सकता है, जिसमें प्रत्येक DFT बिन के लिए  <math>2 \log_2(N)</math> गुणांकण और <math>3 \log_2(N)</math> जोड़/घटाव की आवश्यकता होती है, और यह <math>N</math> बिन के प्रत्येक के लिए होता है।

मात्रकीय जटिलता आदेश अभिव्यक्तियों में, जब गणना की गई मानों की संख्या <math>M</math>, <math>\log N</math> से छोटी होती है, तो गोर्टजेल एल्गोरिदम का लाभ स्पष्ट होता है। लेकिन क्योंकि एफएफटी कोड तुलनात्मक रूप से जटिल होता  है,

"प्रतिक्रिया की लागत प्रति काम की इकाई" का कारक <math>K</math> सामान्यता एफएफटी के लिए अधिक होता है, और व्यावहारिक लाभ गोर्टजेल एल्गोरिदम के पक्ष में होता है, यहाँ तक कि <math>M</math>, <math>\log_2(N)</math> से कई बार बड़ा भी  हो सकता है।

एक नियम के रूप में, एक तर्क तय करने के लिए कि क्या एक रेडिक्स-2 एफएफटी या गोएर्टज़ेल एल्गोरिदम अधिक निपुण है, आपको आंकड़ा समुच्चय में नियोजन की दिशा में ऊपर <math>N</math> की संख्या को आसपास की शुद्ध शक्ति 2 <math>N_2</math>, तक बढ़ाएं, और गोर्टजेल एल्गोरिदम अगर निम्न मान हो तो उससे तेज़ होने की संभावना है:
:<math>M \le \frac{5 N_2}{6 N} \log_2(N_2)</math>
एफएफटी कार्यान्वयन और प्रसंस्करण प्लेटफ़ॉर्मों का संबंधित प्रदर्शन पर महत्वपूर्ण प्रभाव होता है। कुछ एफएफटी कार्यान्वयन<ref>{{Citation |last1=Press|last2=Flannery|last3=Teukolsky|last4=Vetterling|title=Numerical Recipes, The Art of Scientific Computing|publisher=Cambridge University Press|year=2007|chapter=Chapter 12}}</ref> आंतरिक जटिल संख्या गणनाएँ करके स्वतः संकेतक उत्पन्न करने के लिए काम करती हैं, जिससे उनकी "काम की इकाई प्रति लागत K" को पर्याप्त बढ़ा देती है। एफएफटी और डीएफटी एल्गोरिदम परिसंख्याति की उत्कृष्ट दिशा में पूर्व-गणित के संकेतक मूल्यों के तालिकाएँ उपयोग कर सकते हैं, लेकिन इसके लिए बाहरी मेमोरी में बफ़र की गई संकेतक मूल्यों के अधिक पहुँच की आवश्यकता होती है, जो बड़ी रूप से कैश संघर्ष बढ़ा सकता है, जिससे कुछ अंकगणितिक फायदों को कम किया जा सकता है।

दोनों एल्गोरिदम लगभग एक कारक 2 की दिशा में कुशलता प्राप्त करते हैं जब वास्तविक मूल्य वाले के अतिरिक्त जटिल मूल्य वाले इनपुट आंकड़ा का उपयोग किया जाता है। हालाँकि, ये लाभ गोएर्टज़ेल एल्गोरिदम के लिए स्वाभाविक होते हैं लेकिन ये एफएफटी के लिए बिना कुछ एल्गोरिदम प्रकार{{which|date=February 2014}} का उपयोग किए बिना प्राप्त नहीं होंगे, जो वास्तविक मूल्य वाले  आँकड़े का परिवर्तन करने के लिए विशेषज्ञ हैं।

== यह भी देखें ==
* ब्लूस्टीन का एफएफटी एल्गोरिदम (चिर्प-जेड)
* [[आवृत्ति पारी कुंजीयन]] (एफएसके)
* [[चरण-शिफ्ट कुंजीयन]] (पीएसके)

== संदर्भ ==
{{reflist|30em}}


==अग्रिम पठन==
* {{Citation |last1=Proakis |first1= J. G. |first2=D. G. |last2= Manolakis |title=Digital Signal Processing: Principles, Algorithms, and Applications |location= Upper Saddle River, NJ |publisher=Prentice Hall |year=1996 |pages=480–481 |bibcode= 1996dspp.book.....P |ref=none}}


==बाहरी संबंध==
* {{webarchive |url=https://web.archive.org/web/20180628024641/http://en.dsplib.org/content/goertzel/goertzel.html |title=Goertzel Algorithm}}
* [http://www.embedded.com/design/configurable-systems/4006427/A-DSP-algorithm-for-frequency-analysis A DSP algorithm for frequency analysis]
* [https://www.embedded.com/the-goertzel-algorithm The Goertzel Algorithm by Kevin Banks]
[[Category: एफएफटी एल्गोरिदम]] [[Category: अंकीय संकेत प्रक्रिया]] 



[[Category: Machine Translated Page]]
[[Category:Created On 10/08/2023]]