Goertzel Algorithm Generalized to Non-integer Multiples of Fundamental Frequency

RESEARCH Open Access Goe zel algo i hm gene alized o non-in ege mul iples o undamen al equency Pe Sysel and Pa el Rajmic * Abs ac The a icle deals wi h he Goe zel algo i hm, used o es ablish he modulus and phase o ha monic componen s o a signal. The ad an ages o he Goe zel app oach o e he DFT and he FFT in cases o a ew ha monics o in e es a e highligh ed, wi h he a icle p o iding deepe and mo e accu a e analysis han can be ound in he li e a u e, including he memo y complexi y. Bu he main emphasis is placed on he gene aliza ion o he Goe zel algo i hm, which allows us o use i also o equencies which a e no in ege mul iples o he undamen al equency. Such an algo i hm is de i ed a he cos o negligibly inc easing he compu a ional and memo y complexi y. Keywo ds: Goe zel algo i hm, gene aliza ion, spec um, DFT, DTFT, DTMF 1 In oduc ion In he case o disc e e- ime signals, he disc e e Fou ie ans o m (DFT) is widely used o spec al analysis. The equencies o he ha monics in he DFT always depend on he leng h o he ans o m, N, and hey a e in ege mul iples o he undamen al equency  = s N,whe e s ep esen s he sampling equency. Thus, Δ gi es he equency esolu ion o he DFT. In he case, when he ans o m leng h Nis no a mul iple o he signal pe iod, he signal is a sum o ha monic componen s whose equencies a e no in eg al mul i- ples o he undamen al equency. Such componen s a e no exp essible in he N-poin DFT spec um by a single spec al line— his e ec is called “leakage”in o he neighbo ing DFT spec al coe icien s, placed a he in ege mul iples o Δ [1]. The e o e, he ans o m leng h Nalways needs o be chosen wi h espec o he desi ed accu acy o he e- quency esolu ion. The compu a ional complexi y o he DFT inc eases quad a ically wi h he numbe o sam- ples/ equencies, and hus in p ac ice we use almos exclusi ely he as Fou ie ans o m algo i hm (FFT), whose compu a ional complexi y is linea i hmic (linea - loga i hmic). When he ask is o iden i y he modulus and/o phase o a single o o jus a ew o he e- quency componen s, e en he FFT is o no ad an age, because i always compu es all he equency compo- nen s, mos o which a e disca ded, as being o no in e - es . In such si ua ions, me hods specialized in compu ing a subse o ou pu equencies can be exploi ed wi h g ea bene i . Besides he Goe zel algo- i hm, which deals wi h single equencies sepa a ely, i is wo h men ioning he so-called p uned-FFT [2,3], which is also connec ed o he zoom-FFT algo i hm [1], and he ans o m decomposi ion o So ensen and Bu - us [3], which e icien ly combines he ideas o he spli - adix FFT and he Goe zel app oach. Howe e , he essen ial disad an age o ounding equencies o he nea es in ege mul iples (and he inaccu acy hus in o- duced) emains i using any o hese me hods, including he classical e sion o he Goe zel algo i hm. In Sec ion 2, we i s show he de i a ion o he com- mon Goe zel algo i hm in de ail. While his may seem supe luous, i will be necessa y o e e back o a num- be o i s pa icula s eps in he la e sec ions. Then he compu a ional and memo y complexi y o he Goe zel algo i hm and he FFT is compa ed. In Sec ion 3, we p o ide he announced gene aliza ion o he Goe zel algo i hm, so ha i is possible o use i also o he non-in eg al mul iples o he undamen al equency. Such a gene aliza ion has been men ioned be o e, e.g., * Co espondence: [email p o ec ed] Depa men o Telecommunica ions, Facul y o Elec ical Enginee ing and Communica ion, B no Uni e si y o Technology, Pu kyňo a 118, 612 00 B no, Czech Republic Sysel and Rajmic EURASIP Jou nal on Ad ances in Signal P ocessing 2012, 2012:56 h p://asp.eu asipjou nals.com/con en /2012/1/56 © 2012 Sysel and Rajmic; licensee Sp inge . This is an Open Access a icle dis ibu ed unde he e ms o he C ea i e Commons A ibu ion License (h p://c ea i ecommons.o g/licenses/by/2.0), which pe mi s un es ic ed use, dis ibu ion, and ep oduc ion in any medium, p o ided he o iginal wo k is p ope ly ci ed. in [4,1], bu jus o he compu a ion o he modulus, no he phase o a ha monic componen . 1.1 Example o u iliza ion o Goe zel algo i hm—DTMF The Goe zel algo i hm is ypically used o equency de ec ion in he elephone one dialing (dual- one mul i- equency, DTMF), whe e he meaning o he signaling is de e mined by wo ou o a o al o eigh equencies being simul aneously p esen [5]. The equencies o each o he wo g oups o ou signaling ones we e cho- sen such ha he equencies o hei highe ha monics o in e modula ion p oduc s we e su icien ly dis an . The equencies chosen o he DTFM ha e a big leas common mul iple. Hence, using a digi al ecei e wi h a sampling equency o 8 kHz, he pe iod o DTMF sig- nal amoun s o se e al ens o housands o samples. In p ac ice, howe e , he ans o m leng h Nmus be much smalle , so na u ally he e ec o spec um leak- age will appea . Fo example, wi h N= 205, ins ead o he accu a e equency 770 Hz he modulus a app oxi- ma ely 780.5 Hz (= 20·8000/205) is compu ed. This si ua ion is illus a ed in Figu e 1, whe e i is e iden ha he maximum occu s a he non-in ege mul iple o he undamen al equency. The alue N= 205 is o en used in p ac ice [6], because one o he local minima o he sum o squa ed ela i e de ia ions o he signaling equencies is expe i- enced p ecisely o his leng h. In his si ua ion, he de ia ion is app oxima ely equal o 1.4%, while he ansmi e equency ole ance is 1.8%. Ne e heless, in some applica ions o he Goe zel algo i hm he de ia- ion om he exac equency can exceed a p esc ibed ole ance, and hus bo h he DFT and he Goe zel algo- i hm would be o li le use. Using he app oach p esen ed in his a icle i is no necessa y o ound he equencies a which de ec ion is desi ed; i is possible o de e mine he modulus and phase o a componen a an a bi a y (e en non-in ege ) equency. The numbe o ope a ions and memo y equi emen s inc eases only negligibly wi h his app oach. 1.2 No a ion In he ollowing ex , we assume a disc e e signal xo leng h N, whose samples can be complex, {x[n]} = {x[0], x[1],..., x[N-1]}.Symbolk ep esen s he numbe (index) o he ha monic componen in he DFT, hus k ÎN. Howe e , in he la e pa s o he ex , we will wo k also wi h kÎℝ. The uni s ep signal is deno ed by {u[n]}, whils u[n] = 1 o n≥0, u[n] = 0 o n<0. 2 S anda d Goe zel algo i hm 2.1 De i a ion o s anda d Goe zel algo i hm The algo i hm in en ed by Goe zel [7] se es o com- pu e he k h DFT componen o he signal {x[n]} o leng h N, i.e., X[k]= N−1  n=0 x[n]e−j2πkn N,k=0,...,N−1. (1) Mul iplying he igh side o his equa ion by 1=e j2πkN Nleads o i s equi alen X[k]=e j2πkN N N−1  n=0 x[n]e−j2πkn N,(2) which can be ea anged in o X[k]= N−1  n=0 x[n]e−j2πkn−N N.(3) The igh side o (3) can be unde s ood as a disc e e linea con olu ion o signals {x[n]} and {h k [n]}, p o ided 020 40 60 80 100 120 140 160 180 200 −1.5 −1 −0.5 0 0.5 1 1.5 ime [samples] 00.005 0.01 0.015 0.02 0.025 ime [s] 17.5 18 18.5 19 19.5 20 20.5 21 21.5 22 22.5 23 0 20 40 60 80 100 ha monics module 17.5 18 18.5 19 19.5 20 20.5 21 21.5 22 22.5 23 −3 −2 −1 0 1 2 3 ha monics phase 700 720 740 760 780 800 820 840 860 880 equency [Hz] 700 720 740 760 780 800 820 840 860 880 equency [Hz] Figu e 1 The pic u e a he op shows he sum o wo ha monic signals wi h equencies 770 and 1477 Hz. I is 205 samples ob ained wi h s = 8000 Hz. The bo om pic u e shows he spec um o he signal: he DFT coe icien s (1) a e depic ed wi h black ill, he ed ones a e he alues o DTFT o a non-in ege mesh o equencies (22). Sysel and Rajmic EURASIP Jou nal on Ad ances in Signal P ocessing 2012, 2012:56 h p://asp.eu asipjou nals.com/con en /2012/1/56 Page 2 o 8 ha he elemen s o he la e signal a e de ined by hk[]=e j2πk Nu[] . In ac , i {y k [n]} deno es he esul o such a con olu ion, hen i holds o i s en ies: yk[m]= ∞  n=−∞ x[n]hk[m−n], (4) which can be ew i en as yk[m]= N−1  n=0 x[n]ej2πkm−n Nu[m−n](5) whe e he compac suppo o he signal {x[n]} is aken in o conside a ion. Compa ing (3) and (5), i is clea ha he desi ed X[k] is he N h sample o he con olu ion, i.e., X[k]=yk[N](6) o an a bi a y bu ixed k= 0,..., N- 1. This means ha he equi ed alue can be ob ained as he ou pu sample in ime No an IIR linea sys em wi h he impulse esponse {h k [n]}. The ans e unc ion H k (z) o his sys em will now be de i ed; i is he L- ans o m o i s impulse esponse [8], hus Hk(z)= ∞  n=−∞ hk[n]z−n(7) = ∞  n=−∞ ej2πkn Nu[n]z−n(8) = ∞  n=0 ej2πkn Nz−n(9) = ∞  n=0 (ej2πk Nz−1) n ,(10) which can be iewed as a geome ic se ies wi h he i s e mbeingequal oej2πk0 Nz−0=1and wi h he quo ien q=e j2πk Nz−1.Fo |q|<1,i.e.,|z|>1, hese - ies is con e gen and i s sum equals he desi ed ans e unc ion: Hk(z)= 1 1−ej2πk Nz−1 .(11) The co esponding di e ence equa ion is yk[n]=x[n]+e j2πk Nyk[n−1], wi h yk[−1] = 0. (12) This i s o de di e ence equa ion con ains a com- plex mul iplica ion ac o , which is compu a ionally demanding. To sa e he compu a ional cos , he ans- mission unc ion can be ex ended in bo h he nume a o and he denomina o by he conjuga e o (1 −ej2πk Nz−1), which leads o Hk(z)= 1−e−j2πk Nz−1 1−e−j2πk Nz−11−ej2πk Nz−1(13) =1−e−j2πk Nz−1 1−2cos2πk Nz−1+z−2.(14) The espec i e di e ence equa ion o his second o de IIR sys em is y k [n]=x[n]−x[n−1]e −j2πk N +2cos  2πk N  y k [n−1] −y k [n−2 ] (15) wi h x[-1] = y[-1] = y[-2] = 0. Such a s uc u e can be desc ibed using he s a e a iables: s[n]=x[n]+2cos2πk Ns[n−1] −s[n−2], (16) while he ou pu is gi en by yk[n]=s[n]−e−j2πk Ns[n−1] (17) and we se s[-1] = s[-2] = 0. The signal low g aph ep esen ing he sys em is depic ed in Figu e 2. The s a e-space desc ip ion is ad an ageous because only he ou pu sample y[N] is o in e es . The algo i hm i e a es he eal-numbe -only sys em (16) o (N+1) imes (beginning wi h he sample wi h he ime index 0; in he las i e a ion he inpu sample x[N] is pu equal o x[n]yk[n] s [ n ] z−1 −e−j2 π k N 2cos2 π k Ns[n−1] z−1 −1s [ n−2 ] Figu e 2 Signal low g aph o second o de Goe zel sys em wi h indica ed s a e a iables. Sysel and Rajmic EURASIP Jou nal on Ad ances in Signal P ocessing 2012, 2012:56 h p://asp.eu asipjou nals.com/con en /2012/1/56 Page 3 o 8 ze o). Only in he las s ep is he ou pu y k [N] calcula ed acco ding o (17) using only a single complex mul iplica- ion. As men ioned ea lie , he alue in y k [N]is he desi ed spec al coe icien X[k]. The Goe zel algo i hm can hence be conside ed as an IIR il e ing p ocess, while only a single ou pu sample is o in e es . The algo i hm is p esen ed s ep by s ep in Figu e 3. 2.2 Compa ison o Goe zel algo i hm and FFT 2.2.1 P ope ies The Goe zel algo i hm in ac pe o ms he compu a- ion o a single DFT coe icien . Compa ed o he DFT, i has se e al ad an ages, because o which i is used. - Fi s o all, he Goe zel algo i hm is ad an ageous in si ua ions when only alues o a ew spec al com- ponen s a e equi ed (as in he DTMF example in Sec ion 1.1), no he whole spec um. In such a case he algo i hm can be signi ican ly as e . - The e iciency o using he FFT algo i hm o he compu a ion o DFT componen s is s ongly de e - mined by he signal leng h N.Themos e ec i e case is when Nis a powe o wo. On he con a y, Ncan be a bi a y in he case o he Goe zel algo- i hm, and he compu a ional complexi y does no a y. - The compu a ion can be ini ia ed a an a bi a y momen , e en a he e y ime o he a i al o he e y i s inpu sample; i is no necessa y o wai o he whole da a block as in he case o he FFT. Thus, he Goe zel algo i hm can be less demanding om he iewpoin o he memo y capaci y and i can pe - o m a a e y low la ency. Also, he Goe zel algo i hm does no need any eo de ing o inpu o ou pu da a in he bi - e e se o de [1]. - Finally, as will be shown la e in he a icle, he modulus and phase can be es ablished also o he non-in eg al spec al indexes k, aising he compu a- ional e o only negligibly. The e o e he Goe zel algo i hm is con enien in cases when, o some ea- son, i is equi ed o de ec ha monic signals o non- in eg al equencies, o , signals wi h a limi ed num- be o samples which causes a dec ease o he DFT equency esolu ion. 2.2.2 Compu a ional and memo y complexi ies In he ollowing analysis, ope a ions which can be pe - o med be o e he i s da a sample has been ecei ed a e no conside ed. Speci ically, he cons an s A,B,Cin Figu e 3 can be p ecompu ed. The memo y pe o mance is handled in a minimalis scena io, i.e., such ha i would no be possible o implemen he algo i hm wi h ewe s o- age loca ions. The FFT algo i hm used wi h Nbeing a powe o wo has compu a ional demands p opo ional o Nlog 2 N, he absolu e numbe depends on he pa icula implemen a- ion. Usually he numbe o eal-numbe ope a ions ound in he li e a u e is app oxima ely 6Nlog 2 N( aking one complex mul iplica ion as a combina ion o ou mul ipli- ca ions and wo summa ions). When wo king wi h eal signals, a numbe o ope a ions can be a oided; howe e , i is a he cos o inc eased complexi y o he algo i hm, and, i is no ue ha he demands can be educed by hal , as can be ead, o example in [9]. Fo his eason, we conside he s anda d “complex”FFT e en o eal signals. I we analyze he numbe o ope a ions o he s an- da d Goe zel algo i hm, we ealize ha o a eal inpu Inpu s: index k∈Zo he DFT spec al componen ; signal xo leng h N Ou pu : y, ep esen ing X[k]acco ding o (6) %P ecalcula ion o cons an s A=2 π k N B=2cosA C=e−jA %S a e a iables s0=0 s1=0 s2=0 %Main loop o i=0:N−1%Nmul iplica ions, 2Naddi ions s0=x[i]+B·s1−s2%co esponds o (16) s2=s1 s1=s0 end %Finalizing calcula ions s0=B·s1−s2%co esponds o (16) wi h ze o inpu ; 1 mul iplica ion and 1 addi ion y=s0−s1·C%co esponds o (17); 4 mul iplica ions and 3 addi ions Figu e 3 S anda d Goe zel algo i hm. Sysel and Rajmic EURASIP Jou nal on Ad ances in Signal P ocessing 2012, 2012:56 h p://asp.eu asipjou nals.com/con en /2012/1/56 Page 4 o 8 signal, N eal mul iplica ions and 2N eal addi ions a e pe o med in he main loop. So he o al numbe o ope a ions is app oxima ely 3N o a single equency; we omi he small numbe o ope a ions needed o p e- compu ing B=2cos2πk N,C=e −j2πk Nand he conclud- ing complex mul iplica ion (one o each equency k). Thus, i N equencies we e o in e es , he Goe zel algo- i hm would be o quad a ic complexi y as he DFT is. To answe he ques ion “ o how many equencies K is i mo e ad an ageous o exploi he Goe zel algo- i hm han he FFT”we compa e 3NK <6Nlog2N K<2log2N,(18) which ep esen s a mo e accu a e esul han o example [[8], p. 635], whe e he sha pe inequali y K< log 2 N, based solely on a compa ison o he o de o magni ude, is p esen ed. Such a esul , howe e , holds only o Nbeing a powe o wo; o he wise he inequal- i y (18) can e en be mo e a o able o he Goe zel algo i hm. The o mula (18) says ha he compu a ion should be as e han he FFT as long as he numbe o equen- cies does no exceed 2 log 2 N. Fo example, wi h a sig- nal o leng h N= 32 he Goe zel algo i hm is p e e able i K≤9.In hecaseo N= 128 Goe zel domina es o e he FFT i K≤13. In ac , he algo i hm in oduced in [3] can be e en mo e e icien han his. I combines he good p ope ies o bo h he FFT and he Goe zel algo i hm, p oducing a DFT decomposi ion simila o he one used in he spli - adix FFT. The dominance o he algo i hm o So ensen and Bu us o e he FFT is gua an eed e en o K<N/2. An expe imen al compa ison o his app oach wi h he Goe zel algo i hm showed ha he Goe zel algo i hm pe o ms ac ually be e han hei algo i hm when K≤4 o K≤5 o a wide ange o N. I should be no iced, how- e e , ha he algo i hm om [3] has o wo k wi h a whole da a block, and also he complexi y being compa ed does no include ea angemen o he inpu da a sequence. Using he FFT algo i hm equi es a memo y space o a leas 2N, which con ains he eal and imagina y pa s o signal samples. Also he N alues o he ans o ma- ion ke nel, sin and cos (so-called widdle ac o s), a e o en p ecompu ed and s o ed. The FFT calcula ion i sel can be pe o med wi h no alues being mo ed in memo y (i.e., in-place), howe e , wi h ega d o he impossibili y o s a ing he compu a ion un il he las sample o a block o da a is ecei ed, a bu e o a leas 2Nin size mus be used. In he case o eal signals, N memo y loca ions a e enough. Thus, he o e all FFT memo y demand is 4N o eal signals. Fo each conside ed equency, he Goe zel algo i hm equi es: loca ions o sa ing wo s a e a iables, he eal cons an B, he eal and imagina y pa s o he p ecom- pu ed C, and he eal and imagina y pa s o he inal esul . The e is no need o implemen inpu bu e ing, because he compu a ion can be un as he new signal samples a i e. Simila ly, he ou pu signal can be o e - w i en a e he las sample has a i ed. In many cases i will he e o e no be necessa y o use bu e ing a he ou pu side ei he . The o al memo y complexi y o he Goe zel algo i hm is hus 7Kposi ions. Combining all he abo e oge he , he Goe zel algo- i hm will be less memo y-demanding han he FFT i 7K <4N K<4 7N.(19) A compa ison o (19) and (18) leads o he conclusion ha , i we look o a numbe K o which he Goe zel algo i hm domina es o e he FFT om bo h he mem- o y and he compu a ional iewpoin s, hen: o N≥13 o mula (18) is decisi e, because o hese Ni holds 4 7N>2log2N;on he o he hand, o NÎ{2,..., 12} (which is unusual in p ac ice), he decisi e o mula is (19), because o hese Ni holds 4 7N>2log2N;ne e - heless, as he di e ence o he igh and he le sides does no exceed 2 in his case, we can conclude, wi h a small loss o gene ali y, ha he compa ison o he e ec i eness o he wo algo i hms can be based jus on ela ion (18). 3 Gene alized Goe zel algo i hm Fo mula (2) holds o in ege - alued konly. In such a case, he in ege numbe o pe iods o he ans o ma- ion ke nel, e−j2πkn N,co esponds o he signal leng h N. In he case o kÎℝ, o mulas (1) and (2) a e gene - ally no longe in ag eemen . (The pe iod o he ans o - ma ion ke nel no longe co esponds o N,hence he s anda d app oach canno be used.) In Sec ions 3.1 and 3.2, we will gene alize he algo- i hm such ha i includes also he non-in eg al- alued mul iples o he undamen al equency. The complexi y o he no el app oach is analyzed in Sec ion 3.3. And, as shown in Sec ion 3.4, he non-in ege case can be ea- ed by he s anda d algo i hm using a small ick; how- e e , his is a he cos o inc eased compu a ional e o . 3.1 Gene alizing o non-in ege k In ac , when kis no in ege - alued, we can no longe speak o he DFT (1), a he o he disc e e- ime Fou ie ans o m (DTFT), which is de ined by Sysel and Rajmic EURASIP Jou nal on Ad ances in Signal P ocessing 2012, 2012:56 h p://asp.eu asipjou nals.com/con en /2012/1/56 Page 5 o 8 X(ω)= ∞  n=−∞ x[n]e−jωn,ω∈R.(20) Wi h he no a ion ωk=2πk Nwe can w i e ha X(ωk)= ∞  n=−∞ x[n]e−j2πkn N(21) = N−1  n=0 x[n]e−j2πkn N,k,ωk∈R,(22) whe e we exploi ed he compac ness o he suppo o he signal {x[n]}. The de i a ion o he gene alized Goe zel algo i hm is analog o he echnique p esen ed in Sec ion 2. Com- pa ed o ha , howe e , we ex end o mula (22) a he e y beginning by uni y in he o m o ej2πkN N·e−j2πkN N=1 o k∈R,(23) leading o X(ωk)=e j2πkN N·e−j2πkN N N−1  n=0 x[n]e−j2πkn N(24) =e −j2πkN N N−1  n=0 x[n]ej2πkN−n N(25) =e −j2πk N−1  n=0 x[n]ej2πkN−n N.(26) Since he sum in (26) is iden ical o (3), he de i a ion o he gene alized algo i hm can p oceed using he same s eps as in Sec ion 2.1, wi h one no ewo hy change: he equa ion ha cha ac e izes he ou pu using s a e a i- ables (17) will now be o he o m yk[n]=s[n]−e−j2πk Ns[n−1]·e−j2πk.(27) Indeed his is so, since he “co ec ion cons an ”,e - j2πk , depends only on he index o he equency compo- nen , which emains cons an h oughou he compu a- ion. The complex cons an is equal o one o kÎZ, which shows ha his is indeed a gene aliza ion. In ac , he only a ia ion compa ed o he s anda d Goe zel algo i hm is he mul iplica ion by his cons an a he e y end o he algo i hm. The cons an e -j2πk a ec s only he phase o he esul , no he module. Among o he hings, his means ha he in e es in he modules o he componen s wi h non-in ege kcan be sa is ied using he s anda d algo- i hm. Indeed, o example [4] uses i in his way. In cases when he phase plays a ole ( he delay o a signal is de ec ed, o example), howe e , he use o his “co - ec ion cons an ”is necessa y. A sho ema k can be ound in [[1], p. 531], desc ibing he possiblili y o com- pu ing he Goe zel esul s also o non-in ege - alued k; howe e , i misleads he eade in ha he phase case is no dis inguished a all. 3.2 Reducing numbe o i e a ions I will be shown in his sec ion ha he las i e a ion o he Goe zel algo i hm can be subs i u ed by me ely a single complex mul iplica ion, ins ead o pe o ming i in he usual manne . F om equa ion (5) we can exp ess yk[N]= N−1  n=0 x[n]e−j2πkn−N Nu[N−n] = N−1  n=0 x[n]e−j2πkn−N N (28) and also yk[N−1] = N−1  n=0 x[n]e−j2πkn−(N−1) Nu[(N−1) −n] = N−1  n=0 x[n]e−j2πkn−N Ne−j2πk1 N. (29) A compa ison o (28) and (29) leads o he o mula which cha ac e izes he ela ionship be ween he las wo samples o he con olu ion: yk[N]=yk[N−1] ·e+j2πk N.(30) This means ha he e y las i e a ion o he adi- ional Goe zel algo i hm can be eplaced by a simple mul iplica ion by ej2πk N.Rela ion (30) holds o y k [N] and y k [N-1] due o he limi ed suppo o x[n]. No hing simila , howe e , holds o samples y k [N-1] and y k [N-2], due o he e m u[·]. Combining ej2πk Nand he phase co ec ion cons an o non-in ege k(see (27)) esul s in he o e all con- s an D=e −j2πk·e+j 2πk N=e −j2πk N(N−1).(31) This way he sho ened gene alized algo i hm is ob ained, as is summa ized in Figu e 4. Sysel and Rajmic EURASIP Jou nal on Ad ances in Signal P ocessing 2012, 2012:56 h p://asp.eu asipjou nals.com/con en /2012/1/56 Page 6 o 8 3.3 Compu a ional and memo y complexi ies The compu a ional complexi y o he gene alized Goe - zel algo i hm desc ibed in Sec ion 3.1 (wi hou he sho ening in Sec ion 3.2) g ows by one complex mul i- plica ion (i.e., ou eal mul iplica ions and wo eal addi ions) compa ed o he adi ional app oach. The memo y equi emen s inc ease by wo posi ions, which con ain he eal and imagina y pa s o he co ec ion cons an e -j2πk . Al hough sa ing one i e a ion in he main loop acco d- ing o Sec ion 3.2 esul s in lowe ing he compu a ional e o by wo addi ions and one mul iplica ion, he need o he inal complex mul iplica ion cancels such a bene- i . This means: he e is no ad an age in sho ening he main loop in case o in ege - alued k; in such a case he adi ional algo i hm as de ined in Sec ion 2 is he mos e icien one. Howe e , in he case o non-in ege - alued k he i e a- ion educ ion does make sense, since joining he co ec- ion cons an s in o a single one (31) leads o he o e all g ow h o compu a ion complexi y by h ee eal mul ipli- ca ions (i would be ou eal mul iplica ions and wo eal addi ions i he educ ion was no exploi ed.) Conside ing he memo y, such a case equi es wo mo e posi ions o he eal and imagina y pa s o (31), compa ed o he s an- da d algo i hm. I is e iden ha he compu a ional and memo y com- plexi ies o he gene alized case a e only negligibly g ea e . The main ad an age o sho ening he loop acco ding o Sec ion 3.2 can be seen in ha , o example, in con inuous ope a ion, i is no necessa y o pe o m he las i e a ion and i is possible o s a p ocessing he inpu sample x[N] in he ime spa ed. 3.4 Ye ano he app oach u ilizing s anda d Goe zel algo i hm I will be shown ha , by a ick, he compu a ion equi ed o kÎℝcan be ans o med in o in ege - alued p oblem, whe e he s anda d Goe zel algo i hm can be u ilized—so no modi ica ions a e needed. How- e e , i is a he cos o aising he compu a ional com- plexi y, which is e en g ea e han wi h he gene alized Goe zel algo i hm (Figu e 4). S a ing om (22) again, he kÎℝcan be di ided in o i s in ege pa ⌊k⌋ÎZ and he emainde  k∈[0, 1), i.e., k=k+ˆ k.This way, (22) can be ew i - en as X(ωk)= N−1  n=0 x[n]e−j2πˆ kn Ne−j2πkn N.(32) I we deno e he signal c ea ed by mul iplying ele- men wise {x[n]} and {e−j2πˆ kn N}by {ˆ x[n]}, he p e ious ela ion can be w i en in he o m o X(ωk)= N−1  n=0 ˆ x[n]e−j2πkn N,(33) whose igh side is a usual DFT o signal ˆ x(which is complex!) and hus can be compu ed by he s anda d Goe zel algo i hm. Inpu s: equency “index” k∈R; signal xo leng h N Ou pu : y, ep esen ing X( ω k)acco ding o eq. (20) %P ecalcula ion o cons an s A=2 π k N B=2cosA C=e−jA D=e−j2 π k N(N−1) %S a e a iables s0=0 s1=0 s2=0 %Main loop o i=0:N−2%one i e a ion less han adi ionally s0=x[i]+B·s1−s2%(16) s2=s1 s1=s0 end %Finalizing calcula ions s0=x[N−1]+B·s1−s2%co esponds o (16) y=s0−s1·C y=y·D%cons an subs i u ing he i e a ion N−1, and co ec ing he phase a he same ime Figu e 4 Gene alized Goe zel algo i hm wi h sho ened i e a ion loop. The changes, compa ed o he s anda d Goe zel algo i hm om Figu e 3, a e ma ked in colo . Sysel and Rajmic EURASIP Jou nal on Ad ances in Signal P ocessing 2012, 2012:56 h p://asp.eu asipjou nals.com/con en /2012/1/56 Page 7 o 8 Rega ding he memo y complexi y, in case o eal- ime p ocessing i is o ad an age o p ecompu e and s o e he signal {e−j2πˆ kn N}. I is complex and he e o e equi es 2Nmemo y loca ions. Fu he mo e, in con as o he adi ional algo i hm, we also need 2Nposi ions o s o e ˆ x, which is complex (ins ead o Nin he adi- ional, eal case). To compu e ˆ xwe need 2N eal mul iplica ions. In he s anda d Goe zel algo i hm (Figu e 3) he Ni e a ions o he main loop wo k wi h eal numbe s only (suppos- ing he inpu signal o be eal). In he app oach p e- sen ed abo e, he numbe o eal ope a ions is doubled. I is he e o e clea ha he gene alized algo i hm acco ding o Figu e 4 bea s he abo e al e na i e app oach om bo h he compu a ional and he memo y iewpoin s. 4 So wa e Two Ma lab unc ions a e a ailable o download a URL [10]. The unc ion named goe zel_classic.m ealizes he s anda d Goe zel algo i hm o kÎZ; he gene alized (and sho ened) algo i hm o kÎℝis implemen ed in he unc ion goe zel_gene al_sho ened.m. The s uc- u e o he unc ions co esponds o he pseudocodes in Figu es 3 and 4. Indexing he ec o elemen s, howe e , s a s wi h “1”in Ma lab, which di e s om ou heo e- ical desc ip ion, whe e i s a s wi h “0”. 5 Conclusion The a icle p esen ed he gene aliza ion o he Goe zel algo i hm. The no el app oach allows us o employ also he non-in ege - alued mul iples o he undamen al e- quency, making i possible o compu e he Fou ie ans o m in disc e e- ime (DTFT) his way. The main ad an age consis s in ha in a ious applica ions whe e he Goe zel algo i hm is u ilized, i is no longe neces- sa y o ound he equencies o desi e, hus ob aining mo e accu a e esul s. The a icle shows ha his is eached a he cos o only a negligible ise in compu a- ional and memo y complexi ies. Fu he mo e, i has been shown ha he e y las i e a ion o he algo i hm can be subs i u ed wi h a mul iplica ion which is li le mo e e ec i e. Acknowledgemen s This wo k was suppo ed by p ojec s o he Czech Minis y o Educa ion, You h and Spo s MSM0021630513, he Czech Minis y o Indus y and T ade FR-TI2/220, and he Czech Science Founda ion 102/09/1846. Compe ing in e es s The au ho s decla e ha hey ha e no compe ing in e es s. Recei ed: 10 May 2011 Accep ed: 6 Ma ch 2012 Published: 6 Ma ch 2012 Re e ences 1. RG Lyons, Unde s anding Digi al Signal P ocessing, 2nd edn. (P en ice Hall PTR, NJ, 2004) 2. P Duhamel, M Ve e li, Fas Fou ie ans o ms: A u o ial e iew and a s a e o he a . Signal P ocess.19, 259 (1990). doi:10.1016/0165-1684(90)90158-U 3. H So ensen, C Bu us, E icien compu a ion o he DFT wi h only a subse o inpu o ou pu poin s. IEEE T ansn Signal P ocess.41(3), 1184 (1993). doi:10.1109/78.205723 4. SL Gay, J Ha ung, GL Smi h, Algo i hms o Mul i-Channel DTMF De ec ion o he WE DSP32 Family, in IEEE on P oceedings o In e na ional Con e ence on Acous ics, Speech, and Signal P ocessing Glasgow, 1134–1137 (1989) 5. Q.23, Technical Fea u es o Push-Bu on Telephone Se s (ITU-T, Gene a, 1988) 6. P Mock, Add DTMF gene a ion and decoding o DSP-uP designs, in Digi al Signal P ocessing Applica ions wi h he TMS320 Family, ol. 1. (P en ice-Hall, NJ, 1987), pp. 543–557 7. G Goe zel, An algo i hm o he e alua ion o ini e igonome ic se ies. Am. Ma h Mon hly. 65(1), 34 (1958). doi:10.2307/2310304 8. AV Oppenheim, RW Scha e , JR Buck, Disc e e- ime Signal P ocessing, 2nd edn. (P en ice-Hall, NJ, 1998) 9. Wikipedia con ibu o s. in Wikipedia: he F ee Encyclopedia, (Wikipedia Founda ion, S . Pe e sbu g, Flo ida, 2010), h p://en.wikipedia.o g/wiki/ Goe zel_algo i hm. 29. 6. 2005, 19. 1. 2010 [ci . 6. 4. 2010] 10. P Rajmic, Ma lab codes o he gene alized Goe zel algo i hm (2012). h p://www.ma hwo ks.com/ma labcen al/ ileexchange/35103 doi:10.1186/1687-6180-2012-56 Ci e his a icle as: Sysel and Rajmic: Goe zel algo i hm gene alized o non-in ege mul iples o undamen al equency. EURASIP Jou nal on Ad ances in Signal P ocessing 2012 2012:56. Submi you manusc ip o a jou nal and bene i om: 7 Con enien online submission 7 Rigo ous pee e iew 7 Immedia e publica ion on accep ance 7 Open access: a icles eely a ailable online 7 High isibili y wi hin he i eld 7 Re aining he copy igh o you a icle Submi you nex manusc ip a 7 sp inge open.com Sysel and Rajmic EURASIP Jou nal on Ad ances in Signal P ocessing 2012, 2012:56 h p://asp.eu asipjou nals.com/con en /2012/1/56 Page 8 o 8