I am an FPGA engineer with some DSP experience, facing the situation of implementing a 1023 points FFT in a spread spectrum demodulator.

As a straightforward solution, I would zero pad to 1024 and use an IP. But I have been given the task to optimize the design : the key parameter here is area, since the sample rate is really low (< 30 Msps) and there is possibility of reusing logic, but latency optimization would be also interesting.

My question is: can anyone refer me to bibliography hinting non-radix 2 FFT implementations comparing performance/implementation constraints tradeoffs?


  • $\begingroup$ >> factor(1023) ans = 3 11 31 $\endgroup$
    – user28715
    Dec 5 '19 at 19:57

The FFT is just a fast method to implement the Discrete Fourier Transform (DFT). It's based on the idea that you can break a large DFT down into a bunch of smaller ones and the combine the results for the final DFT. That requires the DFT length to be broken down into it's prime factors. The more and the smaller the prime factors are, the more efficient the algorithm. That's why a power of 2 is the best choice: the prime factors are small (they are all 2) and there is a lot of them.

1023 is awkward since the prime factors are 3, 11 & 31, so the efficiency gain you can get from an FFT over a straight DFT algorithm is limited. Stating the obvious: a 1024 FFT would be much faster, take a lot less code and data memory and will essentially have the same latency as a 1023 FFT. You better have a VERY good reason to not zero-pad one sample.

For the basics on prime factor FFT see https://en.wikipedia.org/wiki/Prime-factor_FFT_algorithm.


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.