I have looked at an article by Kevin Banks which specifies the following use of the Goerzel Algorithm for tone detection: It shows the following recursive technique where the detection decision is made after N samples: -------------article-------------------------------- Defining: w = (2*?/N)*k cosine = cos w sine = sin w coeff = 2 * cosine For the per-sample processing you're going to need three variables. Let's call them Q0, Q1, and Q2. Q1 is just the value of Q0 last time. Q2 is just the value of Q0 two times ago (or Q1 last time). Q1 and Q2 must be initialized to zero at the beginning of each block of samples. For every sample, you need to run the following three equations: Q0 = coeff * Q1 - Q2 + sample Q2 = Q1 Q1 = Q0 After running the per-sample equations N times, it's time to see if the tone is present or not. real = (Q1 - Q2 * cosine) imag = (Q2 * sine) magnitude2 = real2 + imag2 -------------------------- Now if I understand this correctly, this very simple two-delay alrogrithm should be able to be used as a simple filter in real time for the tone by using y(n) = real * cosine + imag * sine which turns out to be y(n) = Q1 * cosine + Q2 * cos2w if I have done my trig ID algebra correctly. This may be obvious to seasoned vetrans of DSP but I do not qualify in that realm. Does this make sense and has anyone used such a filter? Even if it is not very good as long as it doesn't damp the desired signal it is so cheap that it will certainly help. Thanks, Brian begin 666 0209feat2eq1.gif M1TE&.#EALP`E`( ``/___P```"P`````LP`E```"_X2/J<OM#Z.<M-J+<\B\ M^Y]LX&B(Y(FFI<J9[ M?;@S-](TK=JZ_\]Y3`4N!X<3(0W:*")?(J<0P&5-/ ME';55'_0XM-+!$S!)N\7'")OQF@QTY;UP<PK(CVL6]/9>#[U_/;EAM?T$0<W MY[:6QGA@IM<D.#A9E4=("3E9N%2!**?H5$?(5^GW*+G@9Z=V*:IA\9-H5U,F M6"I9V1IYF:OJ: 4;(JMK&<;JJ(>*W.#;JRR:&_$L_+N9YGSW$$MKF[F\E=VV MJ[D*Z$DN$=5KO4P>S:,=!Q)=2YS:!_E8[8H_#A__CEDV&><"'<&7;QL_3)'$ M[?L'D1DR; YQ=:.VT)>_A^<1.UIS6*/?H'4<&::JI0_4J94L6[I\"3.FRX\5 M4U8SY<T5G&FZY'D<9C"=R* /=QK+1.^G4F@\[YED4X;=1(OO?"Y-857JP9)7 MN\K@%$RKUR-9);X"2T'AV$YE3[8`U@ECCCUM@I*J!TH@ID!H!CIHNU!;D+D[ MH"H::1<I$)M'VP64>U8H9"S@^EI\JOC/-:(:J2@%+"7QT,R(_;;K5QFD4X^@ M0UL>C1F=6\?>'GO^#)'N9<2HE=PZ#"[MU=9I7^,\6M><YEV&589<2AR'[9_1 MYZW56USUB>K6KWN_/9;[=Q;BQYN'40``(?\+36%T:%1Y<&4P,#&2! ```P<* M`0**:P*&/0,!```!`HII`HIN`HIT``*6* *6*0`"BB #`0```0**, **+@** M-0*&*P,.```!`HI.`HHJ`HIT`HIA`HIR`HIG`HIE`HIT`HI?`HIF`HIR`HIE M`HIQ``$"BG,"BF$"BFT"BG "BFP"BF4"BE\"BG("BF$"BG0"BF4````"EB@" 'EBD`````.P`` ` end

# Goertzel detector to Goertzel filter?

Started by ●January 12, 2004

Reply by ●January 13, 20042004-01-13

Hello Brian, Yes you can use the Goertzel algo as a filter where you compute an output for every sample, but remember that if you hit the filter with a signal whose frequency is on or very close to the Goertzel's resonant frequency that the output just keeps growing and growing. So that is why people generally implement a forgetting scheme. Also if you run a signal very close in frequency to the center frequency of the Goertzel filter,you will notice a type of beat frequency in the output which could screw you over. Classically with the Goertzel you just get one value per data block and then the two delay values are reset to zero. Or use simple filters that have their poles inside of the unit circle (the Goertzel have them on the unit circle) so the impulse response is a decaying sinusoid, thus old samples have little effect on the current output. snip of Goertzel program> > Now if I understand this correctly, this very simple two-delay alrogrithm > should be able to be used as a simple filter in real time for the tone by > usingIn fact the Goertzel algo is derived by taking the expression for a DFT of a single frequency - writing in recursive form - multipling by the complex conjugate of the original denominator so as to create a real only recursion term - and then noticing that on the N+1th sample this is the same expression as a second order filter with the poles on the unit circle. So the filter approach arises naturally from the derivation, but the aforementioned problems can also appear.> > y(n) = real * cosine + imag * sine > which turns out to be > > y(n) = Q1 * cosine + Q2 * cos2w > > if I have done my trig ID algebra correctly. > > This may be obvious to seasoned vetrans of DSP but I do not qualify inthat> realm. Does this make sense and has anyone used such a filter? Even if it > is not very good as long as it doesn't damp the desired signal it is so > cheap that it will certainly help.Now the Goertzel is just a recursive way to find the DFT of a signal at a single frequency. Do you need to measure how much of a single frequency is present? Or do you want to pass your single through a narrowband filter and then do something with it after filtering? If you are wanting to just detect a tone and have a continuous measure of its presence, you may want to consider a sliding Goertzel. This will work well and still be quite simple in implementation. Clay

Reply by ●January 13, 20042004-01-13

Clay, THanks for the explanation. All I really want is a not too expensive bandpass filter that will get rid of everything outside of the two tones I use for FSK decoding. After the filtering I apply my integrate and dump scheme, which seems to work quite well even without any filtering. However, low frequency noise or frequencies of which the desired tones are near multiples of the noise seem to confuse it. I do know that if I sing into a mike and superpose that noise onto my desired signal I can make sounds that rapidly degrade the integrate and dump decoder (granted I sing with a much more powerful signal than the signal and I also know that I can sing the tones themselves or create their harmonics which gives the scheme no chance). Nevertheless, a not too costly band pass filter that would eliminate the bulk of the noise outside the regions of interest would be helpful. Right now the integrate and dump scheme is very cheap as it costs only one set of computations every sample. [I make a contribution to the running integral which replaces the contribution N samples previous]. So I have been looking for a low-tap bandpass filter. I made my own bandpass FIR filter by inverse transforming a cosine profile centered on the desired frequency and though this filter does the job quite well, it takes lots of taps. I can find no way to make use of previous computations so I have to repeat ALL the computations every sample. Not so good. IIR filters seems to be much less costly but....they are harder for me to understand. Brian "Clay S. Turner" <CSTurner@WSE.Biz> wrote in message news:2KLMb.5168$eq.446@bignews6.bellsouth.net...> Hello Brian, > Yes you can use the Goertzel algo as a filter where you compute an output > for every sample, but remember that if you hit the filter with a signal > whose frequency is on or very close to the Goertzel's resonant frequency > that the output just keeps growing and growing. So that is why people > generally implement a forgetting scheme. Also if you run a signal veryclose> in frequency to the center frequency of the Goertzel filter,you willnotice> a type of beat frequency in the output which could screw you over. > > Classically with the Goertzel you just get one value per data block andthen> the two delay values are reset to zero. Or use simple filters that have > their poles inside of the unit circle (the Goertzel have them on the unit > circle) so the impulse response is a decaying sinusoid, thus old samples > have little effect on the current output. > > > > snip of Goertzel program > > > > > > Now if I understand this correctly, this very simple two-delayalrogrithm> > should be able to be used as a simple filter in real time for the toneby> > using > > In fact the Goertzel algo is derived by taking the expression for a DFT ofa> single frequency - writing in recursive form - multipling by the complex > conjugate of the original denominator so as to create a real onlyrecursion> term - and then noticing that on the N+1th sample this is the same > expression as a second order filter with the poles on the unit circle. So > the filter approach arises naturally from the derivation, but the > aforementioned problems can also appear. > > > > > > y(n) = real * cosine + imag * sine > > which turns out to be > > > > y(n) = Q1 * cosine + Q2 * cos2w > > > > if I have done my trig ID algebra correctly. > > > > This may be obvious to seasoned vetrans of DSP but I do not qualify in > that > > realm. Does this make sense and has anyone used such a filter? Even ifit> > is not very good as long as it doesn't damp the desired signal it is so > > cheap that it will certainly help. > > Now the Goertzel is just a recursive way to find the DFT of a signal at a > single frequency. Do you need to measure how much of a single frequency is > present? Or do you want to pass your single through a narrowband filterand> then do something with it after filtering? If you are wanting to justdetect> a tone and have a continuous measure of its presence, you may want to > consider a sliding Goertzel. This will work well and still be quite simple > in implementation. > > Clay > >

Reply by ●January 13, 20042004-01-13

"Clay S. Turner" <CSTurner@WSE.Biz> wrote in message news:2KLMb.5168$eq.446@bignews6.bellsouth.net...> > > > y(n) = real * cosine + imag * sine > > which turns out to be > > > > y(n) = Q1 * cosine + Q2 * cos2w > > > > if I have done my trig ID algebra correctly. > > > > This may be obvious to seasoned vetrans of DSP but I do not qualify in > that > > realm. Does this make sense and has anyone used such a filter? Even ifit> > is not very good as long as it doesn't damp the desired signal it is so > > cheap that it will certainly help. > > Now the Goertzel is just a recursive way to find the DFT of a signal at a > single frequency. Do you need to measure how much of a single frequency is > present? Or do you want to pass your single through a narrowband filterand> then do something with it after filtering? If you are wanting to justdetect> a tone and have a continuous measure of its presence, you may want to > consider a sliding Goertzel. This will work well and still be quite simple > in implementation.Just to pick nits (a favorite sport here on comp.dsp), I wouldn't say that the Goertzel is _just_ a recursive way to find the DFT of a signal at a single frequency. By using a non-integer "K" parameter in the Goertzel algorithm, you can use it to find the frequency content of _any_ frequency*, not just one of the DFT bins. In this way, it can give you data you couldn't have gotten from just a DFT. -Jon * subject to the Nyquist criteria of course

Reply by ●January 13, 20042004-01-13

Hello Jon, There is nothing about the defn of the DFT's kernel that says k has to be an integer. People just chose k to be an integer so they know they are picking a standard vector in a complete basis set with known normalization. But simply the Goertzel method is a recursive way to evaluate the sum in a DFT. So when you have H(k) = sum(n=0;N-1) f(n) exp((-2pi j k n)/N) as the standard computational element in a DFT, the Goertzel method is another way of calculating it. And yes k doesn't have to be an integer. But if you plan on using things such as Parseval's thoerem, then you will need to let k be an integer, or you will have to make some adjustments. So the restriction on k being an integer doesn't come from the summation, but it rather comes from desiring to have the properties that come from using a complete orthogonal basis set. Clay "Jon Harris" <goldentully@hotmail.com> wrote in message news:bu1f53$ble5c$1@ID-210375.news.uni-berlin.de...> > > Just to pick nits (a favorite sport here on comp.dsp), I wouldn't say that > the Goertzel is _just_ a recursive way to find the DFT of a signal at a > single frequency. By using a non-integer "K" parameter in the Goertzel > algorithm, you can use it to find the frequency content of _any_frequency*,> not just one of the DFT bins. In this way, it can give you data you > couldn't have gotten from just a DFT. > > -Jon > > * subject to the Nyquist criteria of course > >

Reply by ●January 13, 20042004-01-13

Thanks for the clarification, Clay. Just wondering, can the FFT algorithm be used with non-integer K as well? That would allow, for example, shifting the frequency of all bins some fractional-bin amount which might be useful in some obscure application? Or does the FFT rely on K being an integer for some computation reasons? Just a thought. "Clay S. Turner" <CSTurner@WSE.Biz> wrote in message news:GWYMb.44009$PP5.9350@bignews4.bellsouth.net...> Hello Jon, > > There is nothing about the defn of the DFT's kernel that says k has to bean> integer. People just chose k to be an integer so they know they arepicking> a standard vector in a complete basis set with known normalization. But > simply the Goertzel method is a recursive way to evaluate the sum in aDFT.> > So when you have H(k) = sum(n=0;N-1) f(n) exp((-2pi j k n)/N) as the > standard computational element in a DFT, the Goertzel method is anotherway> of calculating it. And yes k doesn't have to be an integer. But if youplan> on using things such as Parseval's thoerem, then you will need to let k be > an integer, or you will have to make some adjustments. So the restriction > on k being an integer doesn't come from the summation, but it rather comes > from desiring to have the properties that come from using a complete > orthogonal basis set. > > Clay > > > "Jon Harris" <goldentully@hotmail.com> wrote in message > news:bu1f53$ble5c$1@ID-210375.news.uni-berlin.de... > > > > > Just to pick nits (a favorite sport here on comp.dsp), I wouldn't saythat> > the Goertzel is _just_ a recursive way to find the DFT of a signal at a > > single frequency. By using a non-integer "K" parameter in the Goertzel > > algorithm, you can use it to find the frequency content of _any_ > frequency*, > > not just one of the DFT bins. In this way, it can give you data you > > couldn't have gotten from just a DFT. > > > > -Jon > > > > * subject to the Nyquist criteria of course > > > > > >

Reply by ●January 13, 20042004-01-13

"Jon Harris" <goldentully@hotmail.com> wrote in message news:bu1nqu$c66lh$1@ID-210375.news.uni-berlin.de...> Thanks for the clarification, Clay. Just wondering, can the FFT algorithm > be used with non-integer K as well? That would allow, for example,shifting> the frequency of all bins some fractional-bin amount which might be useful > in some obscure application? Or does the FFT rely on K being an integerfor> some computation reasons? Just a thought.Hello Jon, The short answer is yes the FFT expects the frequencies to be integral. Basically the FFT algo in one form or another exploits the periodicity of the complex exponential. Think about the DFT's kernel where you have exp(2pi j k*n/N) If k,n, and N are all integers, then for some values the product of n and k will be bigger than N, so this term will be redundant to a term for another set of n and k for the same N. So in a sense these two multiples are factored out and made into one term. I know this is a bit of a simplification, but I think you can see how some values would repeat. Also if the symmetry properties of the real and imaginary components of the complex exponential are also exploited even more reduction can be done. So if the frequency becomes nonintegral, I would say in the most general cases these means for reduction go away or at the very least become severely reduced. Now in the case where you want all of the frequencies shifted by some common fractional amount, I'd say yes this is possible with some preprocessing of the data. A simple way would be to first modulate your data with a complex exponential[1] and then FFT it. Of course you just may be able to find a different N that puts the bin centers where you need them. Clay [1] Here I'm just applying Heaviside's frequency shifting theorem.

Reply by ●January 13, 20042004-01-13

"Jon Harris" <goldentully@hotmail.com> wrote...> Thanks for the clarification, Clay. Just wondering, can the FFT algorithm > be used with non-integer K as well? That would allow, for example, shifting > the frequency of all bins some fractional-bin amount which might be useful > in some obscure application? Or does the FFT rely on K being an integer for > some computation reasons? Just a thought.If you want to shift the frequency of *all* bins by the *same* fractional amount, that just corresponds to multiplying the input by a linear phase, after which you can use the FFT as usual. This is the standard time/frequency shift property of Fourier transforms. If you want a linear sequency of k that aren't separated by integral values, you can use the chirp-z algorithm (based on the FFT). If you want a non-uniform sequence of k values, you need to use one of the non-equispaced algorithms (which do exist, but are a lot slower than a plain FFT). Cordially, Steven G. Johnson