Forums

How to effectively compute FFT from f_min to f_max, where f_min in not zero?

Started by Afinko January 13, 2010
Hi,
I want to compute e.g. 8192 point FFT from signal that is sampled with Fs
= 48kHz, but 8192 samples (or 4096) should represent frequencies e.g.
2500Hz to 3000Hz. I will need to implement it in SHARC DSP, therefore to
compute huge FFT from 0 to 48kHz and then take a small part (2.5kHz-3kHz)
is not an effective way. Is there any effective way?

Thanks,
Afi


Afinko wrote:

>I want to compute e.g. 8192 point FFT from signal that is sampled with
Fs
>= 48kHz, but 8192 samples (or 4096) should represent frequencies e.g. >2500Hz to 3000Hz. I will need to implement it in SHARC DSP, therefore to >compute huge FFT from 0 to 48kHz and then take a small part
(2.5kHz-3kHz)
>is not an effective way. Is there any effective way?
I assume you want 8192 bins between 2.5k and 3k, meaning 786k samples for your "huge FFT", right? Do you actually have about 8-16 seconds of data? When you say effective, do you mean efficient? If so, first see if you can do it at all w/o computing the extraneous samples; if not, I don't know what "effective" means here. You might have to do a block, drop data, and repeat. Why the fine resolution?
On 13 Jan, 19:29, "Afinko" <afi...@gmail.com> wrote:
> Hi, > I want to compute e.g. 8192 point FFT from signal that is sampled with Fs > = 48kHz, but 8192 samples (or 4096) should represent frequencies e.g. > 2500Hz to 3000Hz. I will need to implement it in SHARC DSP, therefore to > compute huge FFT from 0 to 48kHz and then take a small part (2.5kHz-3kHz) > is not an effective way. Is there any effective way?
You could compute the coeffcients straight forward, using the DFT. But then, 8192 points @ 48 kHz gives an FFT bin width on the order of 6 Hz, meaning that the band of interest is taken care of in less than 100 coefficients. It might be more efficient to compute your 8192 pt full-band FFT and then use some sort of interpolation to fill in the bins in the band of interest. Rune
On 13 Jan, 19:29, "Afinko" <afi...@gmail.com> wrote:

>> I want to compute e.g. 8192 point FFT from signal that is sampled with Fs >> = 48kHz, but 8192 samples (or 4096) should represent frequencies e.g. >> 2500Hz to 3000Hz.
That&#2013266066;s a lot of over sampling for a 2.5khz-3khz signal. Is that Fs number something you selected, or is it something you&#2013266066;re stuck with? And do you really want to compute 8192 points over a 500 hz range in frequency? That would imply starting with a much larger FFT to represent the overall frequency range from 0 to Fs/2, and then pruning the graph or applying some other means to reduce the calculations. Just as an example, with Fs = 48k and N = 8192, your &#2013266065;bin&#2013266066; spacing in the frequency domain is sample rate/N = 5.8593...hz. And the total length of time over which you collect your 8192 samples is the inverse: N/sample rate = .170666... seconds. So are you really stuck with having to use that high sample rate and estimate something in about 171 ms? If not, then to get a finer grained frequency spectrum, you&#2013266066;d lower the sample rate and use a large N (e.g.: sample rate = 8khz, N = 2048 gives you a frequency domain spacing of 3.90625 hz, and a total sampling interval of .256 seconds). It&#2013266066;s a time-bandwidth thing - longer sampling interval in time = closer spacing in frequency. As for computing 8192 points over a 500 hz range in frequency, well, you can prune a larger graph to reduce the calculations (e.g.: 2 stage bit reverse in/sequential out algorithm with a heavily pruned second stage consisting of one butterfly of size 8192). That&#2013266066;s still a lot of work. There&#2013266066;s also zero padding to give you interpolated results. But keep in mind that this doesn&#2013266066;t really improve your &#2013266065;resolution&#2013266066; in the frequency domain the same way that using a longer sampling interval will do. With zero padding, you&#2013266066;re getting more (interpolated) points in the frequency domain from the same sampling interval. But a large FFT with a lot of zero padding can be reduced quite a bit, depending on the numbers. There are other things you might do (low pass filter/decimate, then compute large FFT, etc.), but I&#2013266066;m not really sure what your overall goal might be. As Michael noted, for 4096 points over a 500 hz range, you&#2013266065;d need a very long sampling interval (N/sample rate = 8.192 seconds, or twice that with N = 8192) to get non-interpolated results. Kevin McGee
Thank you Michael, Rune and Kevin,

to go more deeply about what is my goal:
Yes, I really need a 4096 points describing 500 Hz range, exactly at range
2.5 kHz - 3 kHz. 16 seconds of data is not a problem. I can do the
decimation to the approx. 4 kHz sample rate. Effectively means to compute
this spectrum with small computation power and small memory usage on DSP. I
do not want to compute the large FFT from 0 Hz to Fs/2 and then to take
just the part of interest.

I am looking for some "mathematical trick" about how to compute FFT only
for frequency range of interest. I do not know if something like this
exist, that is why I am asking on this forum.

Zero padding is not a solution, i need a real resolution, not just an
interpolation.

Even the way how to compute FFT from Fs/4 to Fs/2 would be very helpful
for me.

Thanks in advance.
Afi
I found that "ZOOM FFT" is exactly what I was looking for.
http://www.dewtronics.com/tutorials/dspintro/advanced/files/zoomfft.pdf

Thanks,
Afi
On Jan 14, 4:40&#2013266080;am, "Afinko" <afi...@gmail.com> wrote:
> Thank you Michael, Rune and Kevin, > > to go more deeply about what is my goal: > Yes, I really need a 4096 points describing 500 Hz range, exactly at range > 2.5 kHz - 3 kHz. 16 seconds of data is not a problem. I can do the > decimation to the approx. 4 kHz sample rate. Effectively means to compute > this spectrum with small computation power and small memory usage on DSP. I > do not want to compute the large FFT from 0 Hz to Fs/2 and then to take > just the part of interest. > > I am looking for some "mathematical trick" about how to compute FFT only > for frequency range of interest. I do not know if something like this > exist, that is why I am asking on this forum. > > Zero padding is not a solution, i need a real resolution, not just an > interpolation. > > Even the way how to compute FFT from Fs/4 to Fs/2 would be very helpful > for me. > > Thanks in advance. > Afi
You can use the Zoom FFT approach, which is essentially frequency shifting, low pass filter and FFT. Another alternative is to use the Chirp Z Transform - It allows a more general evaluation than just the complete unit circle. It can be used for evaluating just a portion of the unit circle, as well as a curve off the unit circle. Cheers, David