FFT questions

Hi,

I need your help about FFT processing. Some questions will surely
appear simple for many of you but please consider I'm not a
specialist.

I receive a signal which contains many frequencies, let's say from 0
to 30 kHz. What interests me is only the signal at about 9 kHz. In
fact, I'd like to determine the magnitude of the incoming signal at
about 9 kHz.
First, i thought i should filter the incoming signal with a FIR filter
for example and then process a FFT in order to get the magnitude at 9
kHz.
But some questions appear to me :

- Do I really need to filter the incoming signal? Tell me if I'm
wrong, the FFT will process from the 0Hz until Fe/2 (I don't
remember)? We can't make the FFT process from one given frequency to
another one? So filtering isn't useful?

- Of course I'd like the FFT to be the quickest as possible but giving
sufficiently good results. So can anybody give me an advice as far as
the number of points are concerned?

- Tell me once again if I'm wrong : the result I'll get from the FFT
is the square root of the sum of the squared real part and the squared
imaginary part of the signal? In fact we get the "module" (in french)
of the incoming signal for all the calculated frequencies?

- As i work with the TMS320VC5402, can anybody suggest me which FFT
code provided by TI in the dsplib i'd rather use for this application?

- If you see another way to achieve this, please tell me!

Just for information : the DSP works with a 100 MHz frequency. As far
as the sample frequency is concerned i can't tell you now what it is
its value. It will depend on the time i'll need to process the FFT and
other things. If it's possible i'd like it to be 100 kHz minimum.
Another thing which may help you to answer to my questions : the
incoming signal simply comes from an ADC. So i guess it's real (not
complex).

I hope this is clear enough. If you need more data or if something
isn't clear enough tell me about it.

Anyway, thank you very much in advance.

Hi,

I need your help about FFT processing. Some questions will surely
appear simple for many of you but please consider I'm not a
specialist.

I receive a signal which contains many frequencies, let's say from 0
to 30 kHz. What interests me is only the signal at about 9 kHz. In
fact, I'd like to determine the magnitude of the incoming signal at
about 9 kHz.
First, i thought i should filter the incoming signal with a FIR filter
for example and then process a FFT in order to get the magnitude at 9
kHz.
But some questions appear to me :

- Do I really need to filter the incoming signal? Tell me if I'm
wrong, the FFT will process from the 0Hz until Fe/2 (I don't
remember)? We can't make the FFT process from one given frequency to
another one? So filtering isn't useful?

- Of course I'd like the FFT to be the quickest as possible but giving
sufficiently good results. So can anybody give me an advice as far as
the number of points are concerned?

- Tell me once again if I'm wrong : the result I'll get from the FFT
is the square root of the sum of the squared real part and the squared
imaginary part of the signal? In fact we get the "module" (in french)
of the incoming signal for all the calculated frequencies?

- As i work with the TMS320VC5402, can anybody suggest me which FFT
code provided by TI in the dsplib i'd rather use for this application?

- If you see another way to achieve this, please tell me!

Just for information : the DSP works with a 100 MHz frequency. As far
as the sample frequency is concerned i can't tell you now what it is
its value. It will depend on the time i'll need to process the FFT and
other things. If it's possible i'd like it to be 100 kHz minimum.
Another thing which may help you to answer to my questions : the
incoming signal simply comes from an ADC. So i guess it's real (not
complex).

I hope this is clear enough. If you need more data or if something
isn't clear enough tell me about it.

Anyway, thank you very much in advance.

> I'm sorry but I don't understand what means n o/p frequency bins?

FFT's are not my strong field as I have no formal learning on the subject,
but I will take a deep breath and attempt to elucidate.  I trust/hope that
any necessary comments by J. Avins or F. Marshall or others may prevent me
from leading you too far astray.

The symbol n refers to the number of input (common abbreviation = i/p,
sometimes ip) signal data samples which must be collected into a
single-dimension array (sequential memory locations) of RAM memory storage
before running the FFT algorithm.

n is called the size of the FFT.  n typically has a value which is an even
power of 2 (e.g. 64, 256, 1024, 4096), although algorithms exist for
handling non-even binary power sample counts, usually at some computational
cost.

Many FFT algorithms require the input values to be interspersed with
intentionally stored values of 0.0 which are assumed by the algorithm to
represent 'imaginary' input samples.  The FFT i/p values are assumed to be
complex numbers, with the ADC i/p samples being 'real' values, and the
corresponding 'imaginary' values being preset to 0.0.

The input storage array is usually required by most DSP CPU's to be on a
memory address boundary which is a multiple even power of 2 of at least the
size of the FFT (n).

> Above all, what o/p means?

The FFT algorithm does its magic using the input (i/p) array samples and
stores its output (common abbreviation = o/p, sometimes op) data samples in
RAM in a single-dimension array of identical size (64, 256, 1024, ...).

These o/p RAM locations are commonly called the output bins, because the
final complex value accumulated in them once the FFT algorithm has
completed is the sum of many computations.

These o/p bins are in a scrambled-address order, and may need to be
re-ordered, depending on what you want to do next.  Modern DSP CPU's can
handle this with almost zero computational overhead.

Each o/p bin contains a complex number (real & imaginary components) which
may be thought of as containing the deduced phase quadrature (sine &
cosine) amplitudes of the detected signal components for that frequency
(Fsamplerate/bin no).

bin no. means "bin number 0..n-1".  e.g. 0..1023.

To deduce the absolute amplitude (regardless of phase) contained in a
particular o/p bin, you need to do a Pythagoras's theorem (triangle
hypotenuse stuff) computation on the (complex) FFT results.

   Vabs[bin no] = sqrt( realcomp[bin no] ^2 + imaginarycomp[bin no] ^2 )

Only the lower half of the re-ordered o/p bins can be taken to represent
something meaningful in our 'real' world.

The FFT process is symmetrical, meaning that you can do an inverse FFT using
the output bins to create an array of samples which should mimic the
original input values.  I am outside my experience here.

A further complication of the FFT method is the need to avoid having the i/p
sample set start and end at different or non-zero values, which will cause
a full-spectrum 'splat' contribution on all the result bin values.  Which
is what you would expect of any such 'click' anyway.  This effect is
usually minimised by 'windowing' which involves tapering (scaling) the i/p
sample values at the start and end of the i/p sample buffer towards 0.0 to
minimise the 'discontinuity' click.

You could google Hamming, Hanning, Blackman-Harris for windowing functions,
each of which is designed woth different virtues in mind.

All that said, I defer to the other postings which make mention of the
Goertzel algorithm, which can produce fast results.  An FFT will take
umpty-ump times longer.

> If i only make a bandpass filter, how will i get the magnitude of the
> 9 kHz?

You need to be clear in your mind that the ONLY frequency that you will not
be called upon to detect is 9.0000000000000 KHz.  There is always some
error.  Also the only frequency your DSP CPU crystal oscillator will NEVER
generate is that which it is specified to be.  This is well explained in
Douglas Adams's 5-book trilogy (wot?, a 5-book trilogy?) 'Hitch-hikers
Guide to the Galaxy' in the 'Bistro Maths' section.  Therefore you must
specify the allowable frequency margins which will be acceptable and
calculate your bandwidths appropriately.

Note that none of your FFT o/p bin centre (Australian english spelling of
'center') frequencies will be 9.0000000KHz anyway.

Hope this helps, fearing that I may have forgotten something important.
Jim Adamthwaite.

french_student wrote:
> Hi,
> 
> I need your help about FFT processing. Some questions will surely
> appear simple for many of you but please consider I'm not a
> specialist.
> 
> I receive a signal which contains many frequencies, let's say from 0
> to 30 kHz. What interests me is only the signal at about 9 kHz. In
> fact, I'd like to determine the magnitude of the incoming signal at
> about 9 kHz.
> First, i thought i should filter the incoming signal with a FIR filter
> for example and then process a FFT in order to get the magnitude at 9
> kHz.
> But some questions appear to me :
> 
> - Do I really need to filter the incoming signal? Tell me if I'm
> wrong, the FFT will process from the 0Hz until Fe/2 (I don't
> remember)? We can't make the FFT process from one given frequency to
> another one? So filtering isn't useful?
> 
> - Of course I'd like the FFT to be the quickest as possible but giving
> sufficiently good results. So can anybody give me an advice as far as
> the number of points are concerned?
> 
> - Tell me once again if I'm wrong : the result I'll get from the FFT
> is the square root of the sum of the squared real part and the squared
> imaginary part of the signal? In fact we get the "module" (in french)
> of the incoming signal for all the calculated frequencies?
> 
> - As i work with the TMS320VC5402, can anybody suggest me which FFT
> code provided by TI in the dsplib i'd rather use for this application?
> 
> - If you see another way to achieve this, please tell me!
> 
> Just for information : the DSP works with a 100 MHz frequency. As far
> as the sample frequency is concerned i can't tell you now what it is
> its value. It will depend on the time i'll need to process the FFT and
> other things. If it's possible i'd like it to be 100 kHz minimum.
> Another thing which may help you to answer to my questions : the
> incoming signal simply comes from an ADC. So i guess it's real (not
> complex).
> 
> I hope this is clear enough. If you need more data or if something
> isn't clear enough tell me about it.
> 
> Anyway, thank you very much in advance.

Hi,

you can imagine the FFT being N bandpass filters. If you are only
interested in one frequency, an FFT is overkill. FFT has a computing
complexity on O(N*log(N)), whereas doing a single frequency filter
costs you only O(N).

If you're not interested in the phase of your signal, you can reduce
computing even further and end up with a bandpass. Depending on the
application, you could use an IIR bandpass with almost no computing
required.

On the other hand, if you want the *shape* of a peak centered around
9KHz, you could do a filter - downsample - FFT sequence. The effect
is that of the FFT zooming in on the peak, only needing a much smaller
FFT.

Kind regards,

Iwo

french_student wrote:

> Hi,
> 
> I need your help about FFT processing. Some questions will surely
> appear simple for many of you but please consider I'm not a
> specialist.
> 
> I receive a signal which contains many frequencies, let's say from 0
> to 30 kHz. What interests me is only the signal at about 9 kHz. In
> fact, I'd like to determine the magnitude of the incoming signal at
> about 9 kHz.
> First, i thought i should filter the incoming signal with a FIR filter
> for example and then process a FFT in order to get the magnitude at 9
> kHz.
> But some questions appear to me :
> 
> - Do I really need to filter the incoming signal? Tell me if I'm
> wrong, the FFT will process from the 0Hz until Fe/2 (I don't
> remember)? We can't make the FFT process from one given frequency to
> another one? So filtering isn't useful?
> 
> - Of course I'd like the FFT to be the quickest as possible but giving
> sufficiently good results. So can anybody give me an advice as far as
> the number of points are concerned?
> 
> - Tell me once again if I'm wrong : the result I'll get from the FFT
> is the square root of the sum of the squared real part and the squared
> imaginary part of the signal? In fact we get the "module" (in french)
> of the incoming signal for all the calculated frequencies?
> 
> - As i work with the TMS320VC5402, can anybody suggest me which FFT
> code provided by TI in the dsplib i'd rather use for this application?
> 
> - If you see another way to achieve this, please tell me!
> 
> Just for information : the DSP works with a 100 MHz frequency. As far
> as the sample frequency is concerned i can't tell you now what it is
> its value. It will depend on the time i'll need to process the FFT and
> other things. If it's possible i'd like it to be 100 kHz minimum.
> Another thing which may help you to answer to my questions : the
> incoming signal simply comes from an ADC. So i guess it's real (not
> complex).
> 
> I hope this is clear enough. If you need more data or if something
> isn't clear enough tell me about it.
> 
> Anyway, thank you very much in advance.

The Goertzel algorithm is very efficient. It can be looked on as an FFT
that concentrates on one bin, but that confines one to using integers
where a fractional value may be more efficient yet. Explore the links at
http://www.google.com/search?q=goertzel%20algorithm and
http://groups.google.com/groups?q=goertzel%20algorithm

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

"Jerry Avins" <jya@ieee.org> wrote in message
news:40a25737$0$3039$61fed72c@news.rcn.com...
> french_student wrote:
>
> > Hi,
> >
> > I need your help about FFT processing. Some questions will surely
> > appear simple for many of you but please consider I'm not a
> > specialist.
> >
> > I receive a signal which contains many frequencies, let's say from 0
> > to 30 kHz. What interests me is only the signal at about 9 kHz. In
> > fact, I'd like to determine the magnitude of the incoming signal at
> > about 9 kHz.
> > First, i thought i should filter the incoming signal with a FIR filter
> > for example and then process a FFT in order to get the magnitude at 9
> > kHz.
> > But some questions appear to me :
> >
> > - Do I really need to filter the incoming signal? Tell me if I'm
> > wrong, the FFT will process from the 0Hz until Fe/2 (I don't
> > remember)? We can't make the FFT process from one given frequency to
> > another one? So filtering isn't useful?
> >
> > - Of course I'd like the FFT to be the quickest as possible but giving
> > sufficiently good results. So can anybody give me an advice as far as
> > the number of points are concerned?
> >
> > - Tell me once again if I'm wrong : the result I'll get from the FFT
> > is the square root of the sum of the squared real part and the squared
> > imaginary part of the signal? In fact we get the "module" (in french)
> > of the incoming signal for all the calculated frequencies?
> >
> > - As i work with the TMS320VC5402, can anybody suggest me which FFT
> > code provided by TI in the dsplib i'd rather use for this application?
> >
> > - If you see another way to achieve this, please tell me!
> >
> > Just for information : the DSP works with a 100 MHz frequency. As far
> > as the sample frequency is concerned i can't tell you now what it is
> > its value. It will depend on the time i'll need to process the FFT and
> > other things. If it's possible i'd like it to be 100 kHz minimum.
> > Another thing which may help you to answer to my questions : the
> > incoming signal simply comes from an ADC. So i guess it's real (not
> > complex).
> >
> > I hope this is clear enough. If you need more data or if something
> > isn't clear enough tell me about it.
> >
> > Anyway, thank you very much in advance.
>
> The Goertzel algorithm is very efficient. It can be looked on as an FFT
> that concentrates on one bin, but that confines one to using integers
> where a fractional value may be more efficient yet. Explore the links at
> http://www.google.com/search?q=goertzel%20algorithm and
> http://groups.google.com/groups?q=goertzel%20algorithm

I'm not sure I understand your point on integers vs. fractional.  This is my
understanding: the Goertzel algorithm DOES NOT confine/constrain you to using
integers (though this is a common misconception).  That is yet another advantage
of the Goertzel over the DFT/FFT - it can be used to find the component of a
frequency bin centered at any arbitrary frequency, regardless of the data set
length.  The width of the bin is determined by the data set length (e.g. 1024
samples), but it can be centered anywhere one chooses from DC to Nyquist.

Jon Harris wrote:

   ...

> I'm not sure I understand your point on integers vs. fractional.  This is my
> understanding: the Goertzel algorithm DOES NOT confine/constrain you to using
> integers (though this is a common misconception).  That is yet another advantage
> of the Goertzel over the DFT/FFT - it can be used to find the component of a
> frequency bin centered at any arbitrary frequency, regardless of the data set
> length.  The width of the bin is determined by the data set length (e.g. 1024
> samples), but it can be centered anywhere one chooses from DC to Nyquist.

As far as I can see, as long as you conceive Goertzel to be a single-bin
FFT, you are constrained use an integer to define that bin. After all,
FFT bins have integer indices.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

"Jerry Avins" <jya@ieee.org> wrote in message
news:40a2c0fa$0$3047$61fed72c@news.rcn.com...
> Jon Harris wrote:
>
>    ...
>
> > I'm not sure I understand your point on integers vs. fractional.  This is my
> > understanding: the Goertzel algorithm DOES NOT confine/constrain you to
using
> > integers (though this is a common misconception).  That is yet another
advantage
> > of the Goertzel over the DFT/FFT - it can be used to find the component of a
> > frequency bin centered at any arbitrary frequency, regardless of the data
set
> > length.  The width of the bin is determined by the data set length (e.g.
1024
> > samples), but it can be centered anywhere one chooses from DC to Nyquist.
>
> As far as I can see, as long as you conceive Goertzel to be a single-bin
> FFT, you are constrained use an integer to define that bin. After all,
> FFT bins have integer indices.

Ah, there is the rub!  You don't need to conceive the Goertzel as a single-bin
FFT.  It is a single bin, with the same width as the equivalent-length FFT, but
by picking a non-integer "k" (see below), you can center the bin arbitrarily.

Regarding "k", the standard Goertzel coefficient equation is:
coefk = 2*cos((2pi/N)*k)

The assumption that "k" must be integer is a widely held myth!  Many "standard"
papers (including one from Analog Devices on DTMF detection) propagate the myth.
Rick Lyons and I had a conversation about this very issue a while back, and Rick
created a Matlab script showing that the bin can be centered on any arbitrary
frequency by choosing a non-integer k. See: http://tinyurl.com/3h799 and
http://tinyurl.com/2xhce for more details.

Jon Harris wrote:

   ...

> The assumption that "k" must be integer is a widely held myth!  Many "standard"
> papers (including one from Analog Devices on DTMF detection) propagate the myth.
> Rick Lyons and I had a conversation about this very issue a while back, and Rick
> created a Matlab script showing that the bin can be centered on any arbitrary
> frequency by choosing a non-integer k. See: http://tinyurl.com/3h799 and
> http://tinyurl.com/2xhce for more details.

Thank you. I followed the public trace of that conversation. It was
partly responsible for my assertion. It includes the statement from
Rick, "The value k, which defines the frequency at which the filter
resonates, is typically specified to be an integer.  (With k as an
integer, the Goertzel algorithm computes the value of a single bin of an
N-point DFT.)" I trust Rick. Even when he acknowledges the correctness
of my corrigendum but doesn't use it. :-)

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

"Iwo Mergler" <Iwo_dot_Mergler@soton.sc.philips.com> wrote in message
news:Jypoc.261$9V3.3276@ns2.gip.net...
> french_student wrote:
> > Hi,
> >
> > I need your help about FFT processing. Some questions will surely
> > appear simple for many of you but please consider I'm not a
> > specialist.
> >
> > I receive a signal which contains many frequencies, let's say from 0
> > to 30 kHz. What interests me is only the signal at about 9 kHz. In
> > fact, I'd like to determine the magnitude of the incoming signal at
> > about 9 kHz.
> > First, i thought i should filter the incoming signal with a FIR filter
> > for example and then process a FFT in order to get the magnitude at 9
> > kHz.
> > But some questions appear to me :
> >
> > - Do I really need to filter the incoming signal? Tell me if I'm
> > wrong, the FFT will process from the 0Hz until Fe/2 (I don't
> > remember)? We can't make the FFT process from one given frequency to
> > another one? So filtering isn't useful?
> >
> > - Of course I'd like the FFT to be the quickest as possible but giving
> > sufficiently good results. So can anybody give me an advice as far as
> > the number of points are concerned?
> >
> > - Tell me once again if I'm wrong : the result I'll get from the FFT
> > is the square root of the sum of the squared real part and the squared
> > imaginary part of the signal? In fact we get the "module" (in french)
> > of the incoming signal for all the calculated frequencies?
> >
> > - As i work with the TMS320VC5402, can anybody suggest me which FFT
> > code provided by TI in the dsplib i'd rather use for this application?
> >
> > - If you see another way to achieve this, please tell me!
> >
> > Just for information : the DSP works with a 100 MHz frequency. As far
> > as the sample frequency is concerned i can't tell you now what it is
> > its value. It will depend on the time i'll need to process the FFT and
> > other things. If it's possible i'd like it to be 100 kHz minimum.
> > Another thing which may help you to answer to my questions : the
> > incoming signal simply comes from an ADC. So i guess it's real (not
> > complex).
> >
> > I hope this is clear enough. If you need more data or if something
> > isn't clear enough tell me about it.
> >
> > Anyway, thank you very much in advance.
>
> Hi,
>
> you can imagine the FFT being N bandpass filters. If you are only
> interested in one frequency, an FFT is overkill. FFT has a computing
> complexity on O(N*log(N)), whereas doing a single frequency filter
> costs you only O(N).
>
> If you're not interested in the phase of your signal, you can reduce
> computing even further and end up with a bandpass. Depending on the
> application, you could use an IIR bandpass with almost no computing
> required.
>
> On the other hand, if you want the *shape* of a peak centered around
> 9KHz, you could do a filter - downsample - FFT sequence. The effect
> is that of the FFT zooming in on the peak, only needing a much smaller
> FFT.

Iwo,

It is well known that FFT / multiply / IFFT is more computationally
efficient that temporal FIR filtering.  I know it seems counterintuitive.

You are correct in the order of the number of computations for an FFT.
Doing forward and inverse multiplies that by a factor of 2.  Doing the
multiply adds N.  However, the result is N output points in time.  So, the
number of computations *per sample* for an N-point filter could be in the
order of:
[2*N*log(N)+N]/N = 2*log(N) +1

.... something like that.

Now, if a Goertzel method is used then probably there's a further saving in
computations... but I don't know enough to comment.

What I do know is that shortening the input array (e.g. if there are a lot
of input zeros out of N samples) doesn't help the computational load of an
N-point FFT very much at all.
Perhaps you're saying that if there are a lot of "don't care" outputs then
the computational load is O(N)?  How many output points????  In time or in
frequency?

Looking to understand better....

Fred