Obtaining large fft from smaller ffts

[Mayae]

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]

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]

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]

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.

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]

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]

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]

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]

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]

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.