Partial FFT... Possible?

Hello people,

Standard FFT lets us retrieve amplitudes of evenly distributed
frequencies.
What if I need at some frequency range greater/smaller density of
frequency points...

Let's say I take fft of 1024 sample long chunk. After standard FFT it will
give amplitudes of 
f[i]=i*samplRate/1024

the step is sampleRate/1024

now let's say I want to have step equal to sampleRate/(1024*4) for
frequency range [0; sampleRate/8].

The question is if I can take this FFT only partially, since I'm not
interested in frequencies higher than sampleRate/8.

Any ideas? Tricks?

hq9000 <psy-nn@mail.ru> wrote:
 
> Standard FFT lets us retrieve amplitudes of evenly distributed
> frequencies.
> What if I need at some frequency range greater/smaller 
> density of frequency points...
 
> Let's say I take fft of 1024 sample long chunk. 
> After standard FFT it will give amplitudes of 
> f[i]=i*samplRate/1024
 
> the step is sampleRate/1024
 
> now let's say I want to have step equal to sampleRate/(1024*4) for
> frequency range [0; sampleRate/8].
 
> The question is if I can take this FFT only partially, since I'm not
> interested in frequencies higher than sampleRate/8.

Even asking the question gets complicated.  Note that with the
boundary conditions of the FFT it is required that given 1024
sample inputs that you get 1024 Fourier coefficients out.

Now, if you remove some what do you expect to take
their place?  The closest that I can think of is to do
non-linear regression (curve fitting).  You have a set of
sample points and want the sum of a set of sines/cosines that
best fits the sample data.  You can then use any basis
set you want, even if it isn't a complete basis.

-- glen

Thanks for reply,

Yes, I agree that the question is quite fuzzy.
So let me try to elaborate it more...

I actually have an infinite discrete signal (audio data) that I want to
observe instant frequency distribution. I can do FFTs of any size... And
having fftSize set to 1024 is satisfactory for everything... except lower
frequencies that it provides to poor resolution for (i have logarithmic
scale for frequency dimension).

Obvious solution is to calculate FFT on greater piece of data, but it
causes significant performance penalty (and I actually do NOT need greater
resolution in higher frequency range).

That's why I started thinking about "partial fft".

Ideally it should work like this:
1. I take 1024 point fft of everything... 
2. I take 8192 point "partial" fft for lower part of spectrum.. but limit
the algorithm to only provide coeficients to this interesting range... And
of course it sould be cheaper than to calculated "full" fft with higher
precision.

The question is if there IS or at least CAN be such "partial" FFT.

PS
thanks for regression idea, I will think it over )




>Even asking the question gets complicated.  Note that with the
>boundary conditions of the FFT it is required that given 1024
>sample inputs that you get 1024 Fourier coefficients out.
>
>Now, if you remove some what do you expect to take
>their place?  The closest that I can think of is to do
>non-linear regression (curve fitting).  You have a set of
>sample points and want the sum of a set of sines/cosines that
>best fits the sample data.  You can then use any basis
>set you want, even if it isn't a complete basis.
>
>-- glen
>

On 16 Mar, 13:25, "hq9000" <psy...@mail.ru> wrote:

> I actually have an infinite discrete signal

No, you don't. The signal might be of long duration,
but it is finite.

> (audio data) that I want to
> observe instant frequency distribution.

Can't be done. You can get the the PSD for over
observations taken over a time interval of some
length, but not instantaneous.

> I can do FFTs of any size... And
> having fftSize set to 1024 is satisfactory for everything... except lower
> frequencies that it provides to poor resolution for (i have logarithmic
> scale for frequency dimension).
>
> Obvious solution is to calculate FFT on greater piece of data,

It's the only solution, if you want denser spectrum
coefficients.

> but it
> causes significant performance penalty (and I actually do NOT need greater
> resolution in higher frequency range).
>
> That's why I started thinking about "partial fft".

The 'chirp FFT' algorithm might be useful to you. You have
to work with longer frames of data, but this algorithm only
computes a subset of the DFT coefficients. Check out the
1975 edition of Oppenheim & Schafer's book.

Rune

Hi, thanks for correcting my terminology.

The chirp FFT according to the references I found in the web seems to be
quite complicated for me as non-methematician.. ((((

But if I have no other way I will go for it.

Can I propose to discuss some idea? I've drawn s scheme describing it.

here you go:
http://www.ufo-scientific.com/files/fft_scheme.GIF

Let's say we have a splitting frequence - below it the spectrum should be
denser, and over it - more sparse.

First we split the signal with the filter.. the higher part goes strait to
the ordinary FFT and the lower part undergoes some processing that is
better to be seen at the picture that described here... please have a
look.

Will it work from your point?

thanks.

hq9000 wrote:

> Hello people,
> 
> Standard FFT lets us retrieve amplitudes of evenly distributed
> frequencies.
> What if I need at some frequency range greater/smaller density of
> frequency points...
> 
> Let's say I take fft of 1024 sample long chunk. After standard FFT it will
> give amplitudes of 
> f[i]=i*samplRate/1024
> 
> the step is sampleRate/1024
> 
> now let's say I want to have step equal to sampleRate/(1024*4) for
> frequency range [0; sampleRate/8].
> 
> The question is if I can take this FFT only partially, since I'm not
> interested in frequencies higher than sampleRate/8.
> 
> Any ideas? Tricks?

Constant Q transform is probably what you are looking for:

http://en.wikipedia.org/wiki/Constant_Q_transform


Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com

On Mon, 16 Mar 2009 07:25:16 -0500, "hq9000" <psy-nn@mail.ru> wrote:

>having fftSize set to 1024 is satisfactory for everything... except lower
>frequencies that it provides to poor resolution for (i have logarithmic
>scale for frequency dimension).
>
>Obvious solution is to calculate FFT on greater piece of data, but it
>causes significant performance penalty (and I actually do NOT need greater
>resolution in higher frequency range).

Looks like the wavelet transform might help you.

Greg

>
>Constant Q transform is probably what you are looking for:
>
>http://en.wikipedia.org/wiki/Constant_Q_transform
>
>
>Vladimir Vassilevsky
>DSP and Mixed Signal Design Consultant
>http://www.abvolt.com

Privet, Vladimir!

That is REALLY promising. Thank you.

hq9000 wrote:
> 
> Hello people,
> 
> Standard FFT lets us retrieve amplitudes of evenly distributed
> frequencies.
> What if I need at some frequency range greater/smaller density of
> frequency points...
> 
> Let's say I take fft of 1024 sample long chunk. After standard FFT it will
> give amplitudes of
> f[i]=i*samplRate/1024
> 
> the step is sampleRate/1024
> 
> now let's say I want to have step equal to sampleRate/(1024*4) for
> frequency range [0; sampleRate/8].
> 
> The question is if I can take this FFT only partially, since I'm not
> interested in frequencies higher than sampleRate/8.
> 
> Any ideas? Tricks?


It is pretty simple to accomplish what you want to do. All you have to do is
downsample the data by 4 and then take your 1024 point FFT.

-jim

>It is pretty simple to accomplish what you want to do. All you have to do
is
>downsample the data by 4 and then take your 1024 point FFT.
>
>-jim

Should this downsampling be complemented by any kind of filtering?