Prev: OMAP-L1x Processor Universal Serial Bus 2.0
Next: Measure frequenzy?
From: Intuitive on 16 Jun 2010 07:44
Hello everybody.

I have got a DSP question for all of you.
I'd like to know if it is possible to obtain a large FFT (for example 1024
samples) combining small SEQUENTIAL FFTs(128 samples).

It is really important for me that the input samples are consecutive (so it
is not possible to apply the usual trick of even and odd samples).
I'm working on a real time system with a RT constraint of 128 samples.
Actually I'm accumulating samples for 8 iterations (128*8=1024) until to
obtain the 1024 samples to perform the FFT of the input signal. However I'd
like to decompose the FFT in small sequential FFTs in order to distribute
the compute for each frame.

If you have any question don't hesitate to contact me.

I'm looking forward to hearing from you, Andrea.




From: Greg Berchin on 16 Jun 2010 09:15
On Wed, 16 Jun 2010 06:44:18 -0500, "Intuitive"
<andrea3891(a)n_o_s_p_a_m.gmail.com> wrote:

>I have got a DSP question for all of you.
>I'd like to know if it is possible to obtain a large FFT (for example 1024
>samples) combining small SEQUENTIAL FFTs(128 samples).
>
>It is really important for me that the input samples are consecutive (so it
>is not possible to apply the usual trick of even and odd samples).
>I'm working on a real time system with a RT constraint of 128 samples.
>Actually I'm accumulating samples for 8 iterations (128*8=1024) until to
>obtain the 1024 samples to perform the FFT of the input signal. However I'd
>like to decompose the FFT in small sequential FFTs in order to distribute
>the compute for each frame.

It's possible, but you have to modify the FFT algorithm slightly.

Start with the sliding DFT formulations that I presented here:
http://groups.google.com/group/comp.dsp/msg/06800ec6bc25deb8?hl=en. Then note
my comment at the end: "Either of these can be reformulated for cases where the
overlap is less than (N-1) points." In your case the "old" samples are all
zeroes. You will build your 1024-point FFT in eight "hops", and each hop will
overlap the previous data set by 896 samples, instead of by just one sample.

The modification to the FFT algorithm is in the denominator of the exponential
terms. A 128-point FFT (DFT) is defined as:

127
X(k) = SUM [x(n)*exp(-j2PIkn/128)]
n=0

However, each of your "small sequential FFTs" needs to be computed as:

127
X(k) = SUM [x(n)*exp(-j2PIkn/1024)] (note "1024" in denominator)
n=0

Greg
From: Greg Berchin on 16 Jun 2010 09:25
On Wed, 16 Jun 2010 09:15:40 -0400, Greg Berchin <gberchin(a)comicast.net.invalid>
wrote:

>You will build your 1024-point FFT in eight "hops", and each hop will
>overlap the previous data set by 896 samples, instead of by just one sample.

Make that, "instead of by 1023 samples".
From: Clay on 16 Jun 2010 10:18
On Jun 16, 7:44 am, "Intuitive" <andrea3891(a)n_o_s_p_a_m.gmail.com>
wrote:
> Hello everybody.
>
> I have got a DSP question for all of you.
> I'd like to know if it is possible to obtain a large FFT (for example 1024
> samples) combining small SEQUENTIAL FFTs(128 samples).
>
> It is really important for me that the input samples are consecutive (so it
> is not possible to apply the usual trick of even and odd samples).
> I'm working on a real time system with a RT constraint of 128 samples.
> Actually I'm accumulating samples for 8 iterations (128*8=1024) until to
> obtain the 1024 samples to perform the FFT of the input signal. However I'd
> like to decompose the FFT in small sequential FFTs in order to distribute
> the compute for each frame.
>
> If you have any question don't hesitate to contact me.
>
> I'm looking forward to hearing from you, Andrea.

Yes, and what you may want to look up is the difference between
decimation in time and decimation in frequency algorithms for the
radix 2 FFT.

IHTH,
Clay


From: Vladimir Vassilevsky on 16 Jun 2010 13:59


Intuitive wrote:

> Hello everybody.
>
> I have got a DSP question for all of you.
> I'd like to know if it is possible to obtain a large FFT (for example 1024
> samples) combining small SEQUENTIAL FFTs(128 samples).

The best and the simplest is get the data back by inverse FFTs, then
compite the large FFT. However you can combine two small FFTs into one
large, and so on, so forth. This is not going to be fast or elegant.
The even bins of the large FFT are done by summation of the bins of the
small FFTs. The odd bins done by the frequency shift of the small FFTs
by 1/2 of the bin (that is sinc interpolation in frq domain), and then
summation just like the even bins.

Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com
 |  Next  |  Last
Pages: 1 2 3
Prev: OMAP-L1x Processor Universal Serial Bus 2.0
Next: Measure frequenzy?