# Decomposing a DFT into multiple FFT calls

I'm using a good fast FFT implementation (vDSP) that will only work on power of 2 blocks of audio data. Now I have a problem where I would like to be able to apply the calculations to non powers of 2 audio.

Some degree of reading around suggests that I can do this by breaking the DFT into smaller power of 2 blocks.

Can anyone explain how to do this, if indeed it is possible at all? I have been unable to find any explanations of how to do it ...

• This answer explains the Cooley-Tukey factorization and it has an example of how to compute a length 1536 (3x512) FFT. But you could also just zero-pad your data to the next power of 2. Mar 11 '15 at 11:23
• @MattL. Cool! More than anything knowing what the name of the algorithm is helps a ton!
– Goz
Mar 11 '15 at 12:01
• Padding to the next power of 2 doesn't give the same results as the shorter DFT, though. I've fallen foul of that before ...
– Goz
Mar 11 '15 at 12:03
• No, but it is a valid DFT of the signal, just evaluated at a different set of frequencies. It contains the same information as the shorter DFT (i.e. if needed one can be computed from the other). Mar 11 '15 at 12:17
• The problem is that there is no efficient method to do that. I just wanted to point out that the FFT of the zero-padded data obviously contains the complete information about the signal, so in most applications it's advantageous to use it, especially if you only have a power-of-2 FFT routine. Mar 11 '15 at 13:55

The simplest thing to do if you have access to only a power-of-two FFT is to zero-pad your data going into the $N=2^p$ FFT and interpolate what comes out. i think that's what MATLAB does for fft() for non-power-of-two DFT.