4

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 ...

Goz
  • 475
  • 1
  • 9
  • 21
  • 4
    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. – Matt L. 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). – Matt L. Mar 11 '15 at 12:17
  • @MattL. How would you go about computing the true (ie shorter) DFT from the padded FFT? – Goz Mar 11 '15 at 12:21
  • 2
    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. – Matt L. Mar 11 '15 at 13:55
  • up-arrow. looks like i said the same thing as you, @MattL. 15 hours later. – robert bristow-johnson Mar 12 '15 at 06:42

3 Answers3

4

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.

robert bristow-johnson
  • 20,661
  • 4
  • 38
  • 76
1

perhaps the material at the following web page would be of interest to you: Rick Lyons - Computing Large DFTs Using Small FFTs. [-Rick-]

lennon310
  • 3,590
  • 19
  • 24
  • 27
Richard Lyons
  • 5,777
  • 13
  • 25
0

By padding, you are losing some of the information in certain bins. You may also get some measurement errors. Why not optimizing your calculation to support a power of 2 FFT? Play with the sampling rate or the length of data acquisition.

Matt L.
  • 89,963
  • 9
  • 79
  • 179
Moti
  • 340
  • 1
  • 6