0
$\begingroup$

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.

Improve this question
$\endgroup$
10
  • $\begingroup$ I take this is digital logic, not software, right? $\endgroup$
    – Marcus Müller
    Commented Jun 6, 2018 at 14:02
  • 3
    $\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
    Commented Jun 6, 2018 at 14:02
  • 1
    $\begingroup$ DST=“day light savings time”? Probably not. So could you define less used acronyms, please $\endgroup$
    – user28715
    Commented Jun 6, 2018 at 14:13
  • 1
    $\begingroup$ @MarcusMüller Ah I get your point now. It's actually part of the project to code the FFTs by myself, it's not supposed to be competitive in terms of running time with highly optimized libraries. I was just curious if there is a way to achieve the above mentioned $\endgroup$
    – Claudio Brasser
    Commented Jun 6, 2018 at 14:32
  • 1
    $\begingroup$ @A_A sometimes I don't dare to link to a pdf with an unknown copyright status $\endgroup$
    – Olli Niemitalo
    Commented Jun 6, 2018 at 14:43

3 Answers 3

Reset to default
1
$\begingroup$

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).

Improve this answer
$\endgroup$
1
  • $\begingroup$ Isn't the O(N^2) against )(NlogN) true only for the first "frame" of the DFT though? $\endgroup$
    – ZaellixA
    Commented Aug 25, 2020 at 12:52
1
$\begingroup$

If you look at the standard picture of an fft decimation-in-time flow graph, you’ll see that there are N/2 butterfly operations in the first column, each of which require only 2 inputs to execute. So in theory you can begin executing a particular butterfly in the first column as soon as the 2 butterfly inputs have arrived from the stream. However, fft algorithms are so efficiently coded that I doubt you would get any real benefit from this approach

Bob

Improve this answer
$\endgroup$
0
$\begingroup$

Are the input blocks processed back-to-back or with overlap? Applying a window function is commonly done with overlapped input.

One length N FFT can be calculated from two N/2 FFTs plus some pre/post processing. If you look at the radix 2 dit/dif schematics, you should see if one suits your needs.

When you ask for «faster», is that reduced compute latency? Or reduced resource usage?

Improve this answer
$\endgroup$

Your Answer

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

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