# Obtaining large fft from smaller ffts

DSP, Plug-in and Host development discussion.
RELATED
PRODUCTS
Mayae
KVRian
Topic Starter
562 posts since 1 Jan, 2013 from Denmark
Lets say I have K M-sized dfts, how would I go on about obtaining a N sized dft (where N = K * M)? N and K will always be a power of 2.

example (in weird pseudo):

Code: Select all

``````M = 16
K = 4
N = M * K (64)

for i = 0 to K
dfts[i] = fft(x[i * M .. (i + 1) * M], M)

full_dft = fft(x[0 .. N], N)

// how to make dfts[0 .. K] == full_dft?``````
It should be possible, since most fft's work exactly this way. I suspect I need some sort of butterfly, although I'm unsure of how to implement it.

Miles1981
KVRian
1379 posts since 26 Apr, 2004 from UK
Yes, it's actually implementing the last pieces of the FFT algorithm (hopefully).
I haven't done the math, but try to do it by starting from the DFT and use a k-size butterfly. The thing is that the order of the samples you are using for the smaller FFTs may screw you.

avasopht
KVRist
163 posts since 19 Apr, 2014 from London
Hmm, but the twiddle factors are dependant on the number of input samples, meaning that the calculations would be different.

Plus the DIF would still require the smaller FFTs to require input samples from received by the other smaller FFTs (check the flow diagrams).

Mayae
KVRian
Topic Starter
562 posts since 1 Jan, 2013 from Denmark
Miles1981 wrote:Yes, it's actually implementing the last pieces of the FFT algorithm (hopefully).
I haven't done the math, but try to do it by starting from the DFT and use a k-size butterfly. The thing is that the order of the samples you are using for the smaller FFTs may screw you.
Yes, I always dreaded the day where I had to write my own FFT. But perhaps it is time.
avasopht wrote:Hmm, but the twiddle factors are dependant on the number of input samples, meaning that the calculations would be different.

Plus the DIF would still require the smaller FFTs to require input samples from received by the other smaller FFTs (check the flow diagrams).
Yeah I'm realizing now it isn't as easy as I thought it would be. FFTs utilize recursion by computation of even and odd samples, not N/2 blocks.

Miles1981
KVRian
1379 posts since 26 Apr, 2004 from UK
Actually, it's not that complicated once you have the math. The most daunting part is reording the data at the end (because before it's loops on blocks and these loops swap the even and odd parts).

avasopht
KVRist
163 posts since 19 Apr, 2014 from London
I just happen to have a written a very fast bit reversal table generator (in case it's ever needed).

But going back to the desired task at hand, Decimation in Frequency divides the task into N/2 children unlike Decimation in Time which divides by odd/even. Unfortunately the recursion still requires input from both blocks meaning that you cannot combine smaller FFTs. Also as mentioned before, the twiddle factors don't match up.

JCJR
KVRAF
3080 posts since 17 Apr, 2005 from S.E. TN
I've wondered if crude mulrirate-- Harmonic 0 of a small fft has everything below harmonic 1. Maybe collect a bunch of harmonic 0 from the little fft's, and fft that array of harmonic 0's for the longer term lower frequencies?

camsr
KVRAF
7239 posts since 17 Feb, 2005
JCJR wrote:I've wondered if crude mulrirate-- Harmonic 0 of a small fft has everything below harmonic 1. Maybe collect a bunch of harmonic 0 from the little fft's, and fft that array of harmonic 0's for the longer term lower frequencies?
How could that make sense? The result of the FFT is a scalar value of amplitude and phase, not frequency.

JCJR
KVRAF
3080 posts since 17 Apr, 2005 from S.E. TN
camsr wrote:
JCJR wrote:I've wondered if crude mulrirate-- Harmonic 0 of a small fft has everything below harmonic 1. Maybe collect a bunch of harmonic 0 from the little fft's, and fft that array of harmonic 0's for the longer term lower frequencies?
How could that make sense? The result of the FFT is a scalar value of amplitude and phase, not frequency.
Thanks Camsr

Maybe makes no sense at all. Perhaps wavelets or other multirate would be better.

If it worked, harmonic spacing might be "inconvenient".

Harmonic 0 is the level of dc. Was thinking for instance if you do a series of 16 sample fft- The harmonic 0 of each tiny fft is the instantaneous dc of that little bunch of samples. After performing 16 tiny fft, the resulting array of harmonic 0 values might be like a lowpassed, lower rate signal which you could fft again.