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?
Tell me more
×
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.
|
|
|
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. |
|||
|
|
|
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$. |
|||
|
|
