# combining small CONSECUTIVE FFTs to make a larger FFT

Started by June 16, 2010
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.

On Wed, 16 Jun 2010 06:44:18 -0500, "Intuitive"
<andrea3891@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
On Wed, 16 Jun 2010 09:15:40 -0400, Greg Berchin <gberchin@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".
On Jun 16, 7:44&#2013266080;am, "Intuitive" <andrea3891@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

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
On Jun 16, 1:59&#2013266080;pm, Vladimir Vassilevsky <nos...@nowhere.com> wrote:
> 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. &#2013266080;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 freq domain), and then > summation just like the even bins.
Vlad, it seems to me that Greg and Clay were on the right track. The whole idea behind the FFT is that it builds an N-point DFT out of two N/2-point DFTs (with some pre- or post-adjustment). Instead of a 2- point butterfly or a 4-point butterfly as the building block to the FFT, think of it as a 128-point butterfly as the building block. I used to know how to do this by heart. Even a decade ago when we were all hanging out here on comp.dsp . But now I have to think about it and rederive the wheel. but i'm pretty sure you can bust up the 1024 term summation into a few 128 term summations of contiguous samples (i think it would be the Decimation-in-Frequency alg) and make some adjustments to the terms going in or coming out. but i really feel to lazy to attack this. maybe i can find it in some lit, but that's work also. r b-j

robert bristow-johnson wrote:

> On Jun 16, 1:59 pm, Vladimir Vassilevsky <nos...@nowhere.com> wrote: > >>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 freq domain), and then >>summation just like the even bins. > > > Vlad, it seems to me that Greg and Clay were on the right track. The > whole idea behind the FFT is that it builds an N-point DFT out of two > N/2-point DFTs (with some pre- or post-adjustment). Instead of a 2- > point butterfly or a 4-point butterfly as the building block to the > FFT, think of it as a 128-point butterfly as the building block. > > I used to know how to do this by heart. Even a decade ago when we > were all hanging out here on comp.dsp . But now I have to think about > it and rederive the wheel. but i'm pretty sure you can bust up the > 1024 term summation into a few 128 term summations of contiguous > samples (i think it would be the Decimation-in-Frequency alg) and make > some adjustments to the terms going in or coming out. but i really > feel to lazy to attack this. maybe i can find it in some lit, but > that's work also.
Robert, I agree that you can do a big FFT by changing the constituent FFTs into something different, like suggested by Greg and Clay. However could you do that using unmodified small FFTs as building blocks? VLV
On Wed, 16 Jun 2010 06:44:18 -0500, "Intuitive"

<andrea3891@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.
On Jun 16, 7:44&#2013266080;am, "Intuitive" <andrea3891@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.
Try googling "Pipelined FFT" you will find a bunch of pertinent papers. Clay
Hi guys!!

In this post I'll try to provide a better explanation of my problem:

I'm developing a Real-time Signal Processing Algorithm on an embedded
system.
Design constrain impose me to elaborate the audio stream using frame of 128
samples.
However some signal processing operations (in the frequency domain) have to
be executed at 1024 samples.
So every 8 frame (1024/8) a 1024 samples fft is executed.
In this way the workload required by the algorithm it is not costant. Some
spikes (caused by the fft calculation) are presented every 8 frame.
I'd like to distribuite the calculation of the 1024 samples FFT in all the
eight frames using smaller FFT (I'm using an optimized DSPLib).
However it is really important to consider that I don't know the value of
the whole sequence because I'm working RT.

At this moment I'm following the advice of Vladimir. I tested the second
approach in matlab and It works. However I don't understand the his first
proposed apporach.
What is the meaning of:
"The best and the simplest is get the data back by inverse FFTs, then
compite the large FFT."
Can you give me a more simple explanation? (Possible step by step).

I don't understand the approach proposed by Greg too. Can you give a better
explanation? (Possible step by step).

Thank you everybody, Andrea!