Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

For example, if I need to calculate 15 point fft, I can use DFT. But it is a long process. As far as I know, FFT can be used when the size is 2^n. What are the efficient ways to perform a 15 point DFT?

share|improve this question

2 Answers 2

It's a common misconception that FFT is limited to radix $2$. Mixed-radix versions are mentioned in both the Wikipedia articles on the Cooley–Tukey algorithm and on FFT in general (search for "mixed"). For your rather small example of $15$ points, this might not yield a significant speed-up, but for larger sizes with small prime factors it can be quite significant. Note also the possibility of zero-padding your data up to a power of $2$, which may or may not be an option in your application.

share|improve this answer

If you want to use FFT to compute a non-cyclic convolution, then zero padding works. Because a DFT can be expressed as a non-cyclic convolution, this gives you the Bluestein FFT as one option for computing the FFT for arbitrary $n$ in time $O(n \log n)$. However, this is rarely the fastest way to compute the FFT. In fact, the Cooley-Tukey FFT works for arbitrary composite numbers, and the Rader's FFT is able to reduce the FFT for a prime number $n$ to a cyclic convolution of length $n-1$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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