## doubt regarding the sentence in sliding dft

Started by 2 years ago5 replieslatest reply 2 years ago150 views
I am not able to understand  the line mentioned just above figure 4 in the article by E. Jacobsen and R.lyons, "The Sliding DFT"

How to interpret this line:

"When output computations are required every M input samples, and M is less than log 2 ( N ), the sliding DFT can be computationally superior to traditional FFT implementations even when all N DFT outputs are required. "

can anyone explain with numerical example??

[ - ]

Using the numbers from the example above with N = 512, if the slide distance, M = N and a new FFT is needed every 512 samples, then the FFT requires fewer computations than the sliding DFT, which has to be recomputed every input sample.  The accumulation of required computations for the sliding DFT is clearly much larger than the FFT.

The statement you're asking about is talking about the rough break-even point, where the sliding DFT becomes more computationally efficient than the FFT.   So if the slide distance (M) is larger than log2(N) = 9, you may be better off using an FFT every M samples, assuming that you need all N samples.  Since the DFT can be computed in a sparse fashion, where you only compute the output samples that you need and ignore the rest, this break-even point can move to much larger M since the FFT generally needs to always compute all N samples.   For example, if you only need DFT outputs around a particular frequency of interest, say you only need twenty samples around bin number 100, then you only need to do 20/512 the normal computations and the sliding DFT will likely be more computationally efficient than the FFT in most cases.

Since there are more FFT algorithms and implementations available these days, that break-even point may be dependent on specific algorithms and implementations.

[ - ]

Thank you very much Robert wolfe and Slartibartfast

[ - ]

Let's say you want to generate 512 DFT outputs for every 4 samples input.

M = 4

N = 512

log2( N ) = 9

4 < 9

so sliding DFT can be computationally superior to traditional FFT implementations, i.e. more efficient, take less processor cycles

[ - ]