"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

"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 integer
for
> 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.

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 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
> >
> >
>
>

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
>
>

"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 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.

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

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 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
> > using
>
> In 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 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.
>
> 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
>
>

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
> using

In 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 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.

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

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