I've implemented Radix-2 & Radix-4, DIT & DIF variants of the cooley-tukey FFT algorithm and they perform well on test data.

Now for a project, my algorithms will be applied to a real-time data stream of complex values. My current approach is window-based, meaning that I'm creating a buffer that stores values in a 2d array for a certain amount of time and after that, the FFT is applied to the matrix stored in the buffer.

As far as my understanding of the algorithm goes (having implemented it and read some papers on DFT/FFT in general but no prior experience in DSP), there is no way of speeding this up by doing some computation live as the data points arrive in the stream connector?

I was wondering if this is correct since I did not find any literature/paper that does this. Any hint is appreciated.

Edit: Example for clarification

Say my input is a Matrix of size N x N of complex numbers and I'm getting the values one point at a time from the data stream, can I do anything more than just buffering them in a 2d array and doing the FFT after a certain time.

  • $\begingroup$ I take this is digital logic, not software, right? $\endgroup$ – Marcus Müller Jun 6 '18 at 14:02
  • 2
    $\begingroup$ Gardner's 1995 paper "Efficient convolution without input-output delay" has something on combining smaller FFT results to get a bigger one. But I don't know if it is efficient if you don't need the smaller ones. $\endgroup$ – Olli Niemitalo Jun 6 '18 at 14:02
  • $\begingroup$ @MarcusMüller I'm sorry I don't quite understand what you mean by 'digital logic'? My implementations are all software based if that's your question? $\endgroup$ – Claudio Brasser Jun 6 '18 at 14:07
  • $\begingroup$ @OlliNiemitalo Thank you, I'll take a look at it! $\endgroup$ – Claudio Brasser Jun 6 '18 at 14:07
  • 1
    $\begingroup$ DST=“day light savings time”? Probably not. So could you define less used acronyms, please $\endgroup$ – user28715 Jun 6 '18 at 14:13

A sliding DFT can be used to compute the equivalent of a new FFT as each input element arrives. However, the cost of a sliding DFT is O(N^2), not O(NLogN).


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.