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

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 kevin●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 Rune Allnor●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 Michael Plante●January 13, 20102010-01-13

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?

Reply by Afinko●January 13, 20102010-01-13

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