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

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

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

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.

Afi
```
```I found that "ZOOM FFT" is exactly what I was looking for.

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