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