Can anybody explain how I can implement the Fast Fourier Transform (FFT) of length unequal to a power of two in hardware, e.g. FPGA? What is the algorithm for this implementation?

Does anybody know about the probable chips or hardware that are currently used with the FFT length unequal to a power of two?

  • 2
    $\begingroup$ This is way too broad a question than can be usefully answered on this site. The author seems to have made no effort to look for answers e.g. via Internet search before posting here. $\endgroup$ – Dilip Sarwate Jan 24 '12 at 3:41
  • $\begingroup$ I searched but ... there is no right way to find it. Please first search then say. $\endgroup$ – Hossein Jan 24 '12 at 14:40

You need to either factor your FFT size into small prime factors if possible (e.g. 2, 3, 5, 7) and then use appropriate FFT butterflies (this is what FFTW does), otherwise look at padding the FFT with zeroes up to the next power of 2.

  • $\begingroup$ Would padding the data with zeros affect the result of the FFT at all? $\endgroup$ – Paul May 15 '12 at 3:59
  • 1
    $\begingroup$ Padding with zeroes is equivalent to interpolating the output data - you get more apparent resolution but obviously there is no additional information gained. $\endgroup$ – Paul R May 15 '12 at 8:05

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.