# Precompute parts of an FFT on streamed data inputs

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.

• I take this is digital logic, not software, right? Commented Jun 6, 2018 at 14:02
• 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. Commented Jun 6, 2018 at 14:02
• DST=“day light savings time”? Probably not. So could you define less used acronyms, please
– user28715
Commented Jun 6, 2018 at 14:13
• @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 Commented Jun 6, 2018 at 14:32
• @A_A sometimes I don't dare to link to a pdf with an unknown copyright status Commented Jun 6, 2018 at 14:43

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

• Isn't the O(N^2) against )(NlogN) true only for the first "frame" of the DFT though? Commented Aug 25, 2020 at 12:52

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

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?