How should I design FFT with fixed samples - always 2000, sampling frequency is also 2000, memory is external, there is no need to get sorted array.
As far I know it may go like factoring 2000 into $2^4 * 5^3$ and creating stages, maybe using optimal 16 point FFT or like in this paper about prime sizes to some power, but how the proper way of designing FFT from scratch looks like?

I am going to write it in C, but I am interested in design, a way to create optimal (in the number of multiplications and additions, counting real addition as 1, complex addition as 2, real multiplication as 1, complex multiplication as 6) FFT of given length with input being real signal and output being complex.

  • 1
    $\begingroup$ The honest answer is: While you can derive a minimum-operation FFT, that's rarely the fastest one. If you want a fast one, write a few different implementations, and try until you find the one that works best on your specific machine. Things like caching values instead of recomputing them have very different benefits on different CPUs! FFTW does exactly that – it has several implementations for the FFT, tries out the most promising ones (or all, if you ask it to), and then uses the one that performs best. Look at the FFTW source code (warning: not pretty). $\endgroup$ Jan 8, 2020 at 18:01
  • $\begingroup$ Thank you for hints! Yes, minimal operations metric is in fact not very practical one considering cache and having various architectures, but I am looking for design derivation, an attempt to better understand how to create one, how to transform DFT to FFT when length is not power of 2. The mere radix-2 or radix-4 FFT, FFTW with padding and so on are highpy practical ways, but the way it was created is shrouded in mystery. This excersise is to stop using FFT as black box. $\endgroup$
    – Evil
    Jan 8, 2020 at 18:14
  • $\begingroup$ If your goal is knowledge, I'd suggest you start by getting your hands on the works referenced in that paper. Alternately, try to pick out some key phrases so that you can do a search and find papers. I believe that the field of FFT algorithms on vectors of prime or near-prime lengths is well established enough that there should be some good books out there, if you really want a deep dive. $\endgroup$
    – TimWescott
    Jan 8, 2020 at 19:56
  • 1
    $\begingroup$ i can almost guarantee you that, whatever your application, you will do better using an FFT (that is in the can, such as FFTW) of 2048 or 4096 samples. zero pad, if necessary. $\endgroup$ Jan 8, 2020 at 22:41
  • 1
    $\begingroup$ and if your goal is knowledge, i might suggest getting a copy of Oppenhiem and Schafer, Discrete-Time Signal Processing. $\endgroup$ Jan 8, 2020 at 22:43


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.