Hi, First of all, I wanna thank everyone for the answers. Jim A. wrote: "An n-point FFT calculates magnitudes for n o/p frequency bins, most of which you will throw away. You may be (a lot) better off just bandpass filtering the area of interest (9KHz +- xHz) and rectifying the result, as you will have good control over the bandwidth, slope shape etc., with much faster compute times, allowing more/other computing or higher sample rates if desired." I'm sorry but I don't understand what means n o/p frequency bins? Above all, what o/p means? If I just bandpass filter the signal, how will I be able to get the magnitude of the 9kHz? I know how to make a bandpass filter since I already did a FIR one, but I can't see how I can get the magnitude of one frequency from the y[n]. Can I? Could you explain more clearly what you mean by "rectifying the result"? Thanks. Iwo wrote: " 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." It's true that it seemed for me that FFT is overkill since i only need to know the magnitude of one given frequency. You just confirmed what i thought. If i only make a bandpass filter, how will i get the magnitude of the 9 kHz? I'm sorry but could you be clearer about this : "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." I don't understand well. Thank you. Jerry wrote: "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" Thank you Jerry(and Jon too) for this idea and the links. I will study this. Maybe (surely!) I'll have other questions for you! Just a last question : when processing a FFT, can it be done in real-time? Apparently all the samples need to be stored before the FFT processes? Am i wrong? Thanks again everyone.
Online · Live + on demand
February 9-11, 2027
Price goes up Nov 1: register now to lock in today's rate
Register Now →
FFT questions
Started by ●May 12, 2004
Reply by ●May 13, 20042004-05-13
Reply by ●May 13, 20042004-05-13
Fred Marshall wrote:> "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 right, for a random shape/phase filter.> 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 >You may want to re-read the original poster's question. He was only interested in "one frequency". I took that to be a narrow band - one or few FFT bin.> .... 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.The Goertzel algorithm is a FIR bandpass with an efficient algorithm for the generation of the sine/cos term sequence. As long as you're interested in less than log2(N) of bins, Goertzel is faster.> > 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?According to the OP, one - in frequency.> > Looking to understand better.... > > Fred > > >
Reply by ●May 13, 20042004-05-13
french_student wrote:> > It's true that it seemed for me that FFT is overkill since i only need > to know the magnitude of one given frequency. You just confirmed what > i thought. > > If i only make a bandpass filter, how will i get the magnitude of the > 9 kHz?When processing the signal digitally, you could look for the peaks of your filtered signal to get the magnitude. This can be done by computing the first derivative of the signal ( d(n)=x(n)-x(n-1) ). d(n) will change sign around the peak. The traditional, analog way of doing this, is to rectify the signal and then low-pass filter the result. You may have heard of a device called a rectifier, commonly used to make DC out of AC. It's a network of four diodes. The mathematical equivalent is the abs() function. Using C notation: abs(x) == (x<0)?-x:x; It transforms a signal like this /`\ /`\ /_ _\_ _ _/_ _\_ _ _/ \ / \ / \_/ \_/ into something like this /`\ /`\ /`\ /`\ /_ _\/_ _\/_ _\/_ _\_ If you pass this through a lowpass filter, you get a signal which is roughly following the average signal magnitude.> > I'm sorry but could you be clearer about this : "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." I don't > understand well. >There are applications, e.g. a spectral analyser, where it is desireable to not only know the magnitude at "one frequency", but also at frequencies nearby. You can then analyse the spectral shape of the signal around your frequency of interest. Doing a FFT over all frequencies, if you're only interested in, say, 8.8 - 9.2 KHz, wastes computing power. In this case you would do a bandpass for 8.8-9.2KHz. You then downsample the result and run a smaller FFT (less bins) on it. The result would be similar to computing a large FFT but only keeping the output for the frequency range 8.8-9.2KHz.> > Just a last question : when processing a FFT, can it be done in > real-time? Apparently all the samples need to be stored before the FFT > processes? Am i wrong? >Whatever you do, the result will always be available after the input. How far after depends on what you do. As a rule of this universe, the steeper/narrower a filter is, the longer the delay. This also means that you cannot filter for a single frequency because that would mean an infinitely narrow filter and thus infinite delay. Any filter structure (FFT is no exception) will delay the result. A N-point FFT delays by N samples plus whatever time it takes you to compute it. If you want continuous real time operation, you would sample the next block in parallel to computing the current one. As long as you can calculate the FFT as fast as N samples come in you're real time. Kind regards, Iwo
Reply by ●May 13, 20042004-05-13
Jerry Avins <jya@ieee.org> wrote in message news:<40a25737$0$3039>> 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 > > JerryIt's me again! For the moment here are my first two questions about Goertzel: 1) In some papers k=0.5+(N*F)/Fs, and in other ones k=(N*fF)/Fs. Which is the good one? 2) With my DSP (TMS320VC5402) the samples x(n) are in the Q15 format. I think I'll have problems when computing Q0=coeff*Q1-Q2+sample, won't I? Anyway thank you very much. The idea of using the Goertzel algorithm seems to be, for the moment, the best i could find. Apparently it exactly does what i need, so once again, thank you.
Reply by ●May 13, 20042004-05-13
Iwo Mergler wrote:> The Goertzel algorithm is a FIR bandpass with an efficient algorithm > for the generation of the sine/cos term sequence.You meant "IIR" rather than "FIR". -- Jim Thomas Principal Applications Engineer Bittware, Inc jthomas@bittware.com http://www.bittware.com (703) 779-7770 A pessimist is an optimist with experience
Reply by ●May 13, 20042004-05-13
french_student wrote:> Jerry Avins <jya@ieee.org> wrote in message news:<40a25737$0$3039> > >>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 > > > It's me again! For the moment here are my first two questions about > Goertzel: > > 1) In some papers k=0.5+(N*F)/Fs, and in other ones k=(N*fF)/Fs. Which > is the good one?The first equation appears to be an attempt to round k to the nearest integer. As per Jon's assertion, k need not be constrained to an integer value. I'd go with the second one if I were you. -- Jim Thomas Principal Applications Engineer Bittware, Inc jthomas@bittware.com http://www.bittware.com (703) 779-7770 A pessimist is an optimist with experience
Reply by ●May 13, 20042004-05-13
french_student wrote:> Jerry Avins <jya@ieee.org> wrote in message news:<40a25737$0$3039> > >>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 > > > It's me again! For the moment here are my first two questions about > Goertzel: > > 1) In some papers k=0.5+(N*F)/Fs, and in other ones k=(N*fF)/Fs. Which > is the good one?Probably both. I'll bet that the symbols are defined differently, and that the corresponding formulas are correct for each definition.> 2) With my DSP (TMS320VC5402) the samples x(n) are in the Q15 format. > I think I'll have problems when computing Q0=coeff*Q1-Q2+sample, won't > I?Most samples that come from ADCs are integers, but you can construe them any way you like. Q15 on a 16-bit machine is the equivalent of construing integer shifted 15 bits (leaving the sign bit in place. The values of such numbers lie between -1 and 1 - 2^-15. The product of two such numbers is a double that lies between -1 and 1 - 2^-30. The more significant word is the product you will store. Note: When using an integer multiplier, you must shift the less significant word left one place, putting its MSB into carry, then shift the more significant word left to eliminate the "extra sign bit" and shift carry into the LSB. A Q15 multiplier does these operations automatically. When q15 multiplication is an option, it is usually specified by a bit in a control register.> Anyway thank you very much. The idea of using the Goertzel algorithm > seems to be, for the moment, the best i could find. Apparently it > exactly does what i need, so once again, thank you.You're very welcome. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●May 13, 20042004-05-13
french_student wrote:> 1) In some papers k=0.5+(N*F)/Fs, and in other ones k=(N*fF)/Fs. Which > is the good one?Once again, Jim Thomas shows himself to think more deeply than I. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●May 13, 20042004-05-13
jerome_lapeyre_mirande@hotmail.com (french_student) wrote in message news:<b261816f.0405122335.45ae56ee@posting.google.com>...> Hi, > > First of all, I wanna thank everyone for the answers. > > Jim A. wrote: > "An n-point FFT calculates magnitudes for n o/p frequency bins, most > of which > you will throw away. You may be (a lot) better off just bandpass > filtering > the area of interest (9KHz +- xHz) and rectifying the result, as you > will > have good control over the bandwidth, slope shape etc., with much > faster > compute times, allowing more/other computing or higher sample rates if > desired." > > I'm sorry but I don't understand what means n o/p frequency bins? > Above all, what o/p means? > > If I just bandpass filter the signal, how will I be able to get the > magnitude of the 9kHz? I know how to make a bandpass filter since I > already did a FIR one, but I can't see how I can get the magnitude of > one frequency from the y[n]. Can I? > > Could you explain more clearly what you mean by "rectifying the > result"? > > Thanks. >I think things will become clearer if you understand the following: A 9kHz bandpass filter can be implemented as follows: Take two waveforms (sine and cosine waveform at 9Khz) of unit energy. Correlate the two waveforms with the input data. If you take the square root of the sum of the squares of the two correlation values you get the magnitude of the 9kHz component of the signal. This is an FIR bandpass filter with passband confined to 9kHz alone. FFT consists of N such bandpass filters.
Reply by ●May 13, 20042004-05-13
Jerry Avins wrote:> Once again, Jim Thomas shows himself to think more deeply than I.Except for the "again" part ;-) -- Jim Thomas Principal Applications Engineer Bittware, Inc jthomas@bittware.com http://www.bittware.com (703) 779-7770 A pessimist is an optimist with experience
