How to make FFT when having small amount of RAM?

On Oct 17, 12:28 pm, "Gery" <g...@ddd.com> wrote:
> I have an idea.
>
> Could I do it like this? If I sample 100 samples at say 10 kHz, multiply
> them with a window function and then zero pad them with 900 zeros. Then I
> make an FFT of the band in interest. I repeat this 10 times and accumulate
> the bins (100 bins). Would I get a frequenzy resolution of 10 Hz with this
> method?

If you repeat non-zero-padded FFTs on successive windows
of data, and use phase vocoder analysis instead of just
accumulating, you might be able to get a much higher frequency
resolution of any well seperated spectra.  You won't be able
to resolve multiple spectra in one bin using phase vocoder
analysis, but you might be able to resolve a far more precise
(sub-bin resolution) frequency of a sinusoid spaced several
bins apart from interfering signals and surrounded by a low
enough noise floor, by using sequences of shorter DFT/FFTs
this way.


IMHO. YMMV.
-- 
Ron N.
http://www.nicholson.com/rhn

Viognier wrote:
> Another technique, called the Chirp Z transform, may be of use. The
> technique can compute the z transform of N points on the unit circle.
> Unlilke the FFT, the N points can be any number and can reside at any
> interval in the band.

No, the chirp-z algorithm (Bluestein's FFT algorithm) requires a buffer
of length >= 2N-1, so it requires *more* storage than doing the full
FFT (which only requires a buffer of length N to store the input and
output).

Steven

Eric Jacobsen wrote:
> Depending on how many output samples (bins) you want, you could
> compute the DFT for just the bins of interest.   You'll need an input
> buffer of length N, and an output buffer of only the length needed.

Actually, you don't need an input buffer at all, which is the whole
advantage of this technique.

Since the DFT/DTFT formula (or Goertzel and similar) requires only a
single sequential pass through the input, you can compute it on the fly
and discard each input after you have used it.

Steven

stevenj@alum.mit.edu wrote:

>
> No, the chirp-z algorithm (Bluestein's FFT algorithm) requires a buffer
> of length >= 2N-1, so it requires *more* storage than doing the full
> FFT (which only requires a buffer of length N to store the input and
> output).
>
> Steven

Perhaps, but with the Chirp Z algorithm I can pick N to be just the
quantity needed (even a prime number) rather than some power of 2 as is
required by the FFT. I also have more control of the resolution of the
frequency spacing of these N points with the CZT.  Again, If you don't
need to do a full FFT, a CZT may be of use.

Viognier wrote:
> Perhaps, but with the Chirp Z algorithm I can pick N to be just the
> quantity needed (even a prime number) rather than some power of 2 as is
> required by the FFT.

FFTs don't require the size to be a power of two; this is a scurrilous
rumor. Many FFT algorithms, most notably the ubiquitous Cooley-Tukey
algorithm, work for any composite size (although many FFT
*implementations* are limited to powers of two), and a couple of
algorithms (Bluestein's and Rader's) work for prime sizes (but are
slower and take more memory).  If you use e.g. FFTW (www.fftw.org) or
the Intel MKL, it will automatically use a composite-size algorithm
when possible and a prime-size algorithm when not.

> I also have more control of the resolution of the
> frequency spacing of these N points with the CZT.  Again, If you don't
> need to do a full FFT, a CZT may be of use.

Careful, the CZT doesn't actually give you more "resolution"...it only
allows you to *interpolate* a portion of the spectrum, which is not the
same thing.  And the CZT is *not* faster that a full FFT if you only
need a few of the frequency bins but with the same spacing.  Even if
you want 2-3 times the "resolution" it would be faster to do a full FFT
with zero padding.  (A CZT requires two FFTs of length >= 2N-1, or
three FFTs if you include initialization time.)

And, in any case, as I pointed out, the original poster asked for a way
to compute a few frequency bins with *less memory* than a full FFT, and
the CZT will certainly not do that.   The only way to save memory is to
use a method that does not require you to store the input, such as
applying the DTFT formula directly.

Steven

Thank you all for your answers. Now I have more informatin about different 
methods.

I think the zoom-FFT sounds like the most apropriate for my project if it 
manages to run the low pass filter at the sampel rate.

Or else I must add a RAM memory to the microcontroller to buffer my sampels.

Thank you all.

<stevenj@alum.mit.edu> wrote in message 
news:1161184757.717044.53510@k70g2000cwa.googlegroups.com...
> Viognier wrote:
>> Perhaps, but with the Chirp Z algorithm I can pick N to be just the
>> quantity needed (even a prime number) rather than some power of 2 as is
>> required by the FFT.
>
> FFTs don't require the size to be a power of two; this is a scurrilous
> rumor. Many FFT algorithms, most notably the ubiquitous Cooley-Tukey
> algorithm, work for any composite size (although many FFT
> *implementations* are limited to powers of two), and a couple of
> algorithms (Bluestein's and Rader's) work for prime sizes (but are
> slower and take more memory).  If you use e.g. FFTW (www.fftw.org) or
> the Intel MKL, it will automatically use a composite-size algorithm
> when possible and a prime-size algorithm when not.
>
>> I also have more control of the resolution of the
>> frequency spacing of these N points with the CZT.  Again, If you don't
>> need to do a full FFT, a CZT may be of use.
>
> Careful, the CZT doesn't actually give you more "resolution"...it only
> allows you to *interpolate* a portion of the spectrum, which is not the
> same thing.  And the CZT is *not* faster that a full FFT if you only
> need a few of the frequency bins but with the same spacing.  Even if
> you want 2-3 times the "resolution" it would be faster to do a full FFT
> with zero padding.  (A CZT requires two FFTs of length >= 2N-1, or
> three FFTs if you include initialization time.)
>
> And, in any case, as I pointed out, the original poster asked for a way
> to compute a few frequency bins with *less memory* than a full FFT, and
> the CZT will certainly not do that.   The only way to save memory is to
> use a method that does not require you to store the input, such as
> applying the DTFT formula directly.
>
> Steven
>