1
$\begingroup$

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

$\endgroup$
7
  • 3
    $\begingroup$ 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. $\endgroup$
    – Matt L.
    Mar 11 '15 at 11:23
  • $\begingroup$ @MattL. Cool! More than anything knowing what the name of the algorithm is helps a ton! $\endgroup$
    – Goz
    Mar 11 '15 at 12:01
  • $\begingroup$ 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 ... $\endgroup$
    – Goz
    Mar 11 '15 at 12:03
  • $\begingroup$ 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). $\endgroup$
    – Matt L.
    Mar 11 '15 at 12:17
  • 2
    $\begingroup$ 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. $\endgroup$
    – Matt L.
    Mar 11 '15 at 13:55
1
$\begingroup$

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.

$\endgroup$
3
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

perhaps the material at the following web page would be of interest to you: http://www.dsprelated.com/showarticle/63.php. [-Rick-]

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.