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

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

Started by ●January 13, 2010

Reply by ●January 13, 20102010-01-13

Afinko wrote:>I want to compute e.g. 8192 point FFT from signal that is sampled withFs>= 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?

Reply by ●January 14, 20102010-01-14

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

Reply by ●January 14, 20102010-01-14

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�s a lot of over sampling for a 2.5khz-3khz signal. Is that Fs number something you selected, or is it something you�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 �bin� 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�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�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�s still a lot of work. There�s also zero padding to give you interpolated results. But keep in mind that this doesn�t really improve your �resolution� in the frequency domain the same way that using a longer sampling interval will do. With zero padding, you�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�m not really sure what your overall goal might be. As Michael noted, for 4096 points over a 500 hz range, you�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

Reply by ●January 14, 20102010-01-14

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

Reply by ●January 14, 20102010-01-14

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

Reply by ●January 14, 20102010-01-14

On Jan 14, 4:40�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. > AfiYou 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