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
> 

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

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.

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

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

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

Vladimir Vassilevsky wrote:
> 

> 2. The FFT of the size N takes 2N of memory at least. If you insist on 
> the use of the FFT, the only way to reduce the memory load is to 
> decimate your signal.
> 

You can reorder the computations in an FFT so that a size N FFT only 
uses the amount of memory required to hold the complex input or complex 
output (ie. number of samples times the number of bits to represent a 
complex sample).  Look for "in-place FFT algorithm".

Gery 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 not I maybe try the zoom FFT procedure.
>

Nope. The zero padding merely interpolates between the 10 Hz points; it
doesn't reveal any input frequency content between them. Averaging
improves the SNR but does not change the resolution.

FWIW, I was confronted with a very similar problem about a year ago.
After poking around a bit and asking the group I wound up doing a zoom
FFT with a mixer, two stage decimating LPF, and a small complex FFT.

John

Gelber wrote:
> Let's say I have an embedded system with a small amount of RAM and I want to
> make an FFT of sampled data. But I don't need to make the FFT of the whole
> frequency range. Is there some kind of shortcut one can make to achieve this
> and save RAM?

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.

-V

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 not I maybe try the zoom FFT procedure.



I want to be able to make a sound analyzer tool with an ATMEL Atmega16
microcontroller connected with a graphical display presenting the frequency
components.

"Eric Jacobsen" <eric.jacobsen@ieee.org> skrev i meddelandet
news:7e9aj29vtkgaf3ltb5to06minrful1pmdn@4ax.com...
> On Tue, 17 Oct 2006 15:58:25 +0200, "Gelber" <gelb@nospam.com> wrote:
>
> >Let's say I have an embedded system with a small amount of RAM and I want
to
> >make an FFT of sampled data. But I don't need to make the FFT of the
whole
> >frequency range. Is there some kind of shortcut one can make to achieve
this
> >and save RAM?
> >
> >
> >
> >And let's say that the system isn't fast enough to make the FFT on the
fly
> >on the samples.
>
> 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.
>
> Of course, you could prune an FFT to do the same thing, but I think
> the memory saving may not be as big.
>
> Eric Jacobsen
> Minister of Algorithms, Intel Corp.
> My opinions may not be Intel's opinions.
> http://www.ericjacobsen.org