doubt regarding the sentence in sliding dft

Started by abhishek11 3 years ago5 replieslatest reply 3 years ago155 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??

[ - ]
Reply by SlartibartfastJanuary 5, 2022

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.   

[ - ]
Reply by abhishek11January 5, 2022

Thank you very much Robert wolfe and Slartibartfast

[ - ]
Reply by Robert WolfeJanuary 5, 2022

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

[ - ]
Reply by abhishek11January 5, 2022

Suppose we consider a length of M=3 and N=16 which follows the case of M is less than log 2 ( N )

for SDFT we would require =(N+N+N)=3N complex multiplication for M bins but for N bins we would require 16N complex multiplications according to the SDFT equation.

For fft we would require=2N log2 N=8N complex multiplications for N bins. I am bit confused.

Any insight would be a great help.

[ - ]
Reply by Robert WolfeJanuary 5, 2022

M is the number of input samples used, and N is the number of output frequency bins calculated.  For a general FFT, M and N are the same, i.e. N values in time result in N values in frequency.