How can implement Sliding DFT(Discrete Fourie Transform) on a signal?

Consider a Signal by length of 1000, and Define a Window that window_size is 350, how can i implement Sliding DFT on this signal??? I write a code like following code but I am not sure because I don.t know compeletly Sliding Concept in DFT

data_len=1000;

win_size=350;

Win_cnt=data_len/win_size;

for count=1:win_size:Win_cnt*overlap ff_A(:,count:count+win_size-1)=fft(A(:,count:count+win_size-1),win_size); end

Answer 1

[Russell Nakano]

Hello Amin,

You can find an easy-to-follow tutorial for a "sliding DFT" solution in [1].

The benefit of the sliding DFT technique is that for a window size of N, the computational cost of computing the N point DFT at each time t>=N is O(N), whereas if you were to feed an FFT with the N values of the window at time t, the cost would be O(N * log(N)). In a conventional FFT-based approach, at each time step you gather up the N values that comprise your window, compute the FFT at the cost of O(N * log(N)). For the subsequent time step, you remove the oldest value, insert the newest value, and compute another FFT without reusing any of the previous computation. Intuitively, that seems like there's a missed opportunity to reuse previous computations.

The writeup includes snippets of Matlab code that demonstrates how the sliding DFT algorithm works. It also references the original literature [2,3]. In particular, there are some stability considerations that need to be accounted for.

Finally, [4] is a concrete C++ implementation of the ideas in [2], including the stability workaround.

References

1. Hatzinakos, Dimitrios. 2005. “The Sliding DFT - Tutorial. ECE 431, Spring 2005.” University of Toronto. https://www.comm.utoronto.ca/~dimitris/ece431/slidingdft.pdf.
2. Jacobsen, Eric, and Richard Lyons. 2003. “The Sliding DFT.” IEEE Signal Processing Magazine, March 2003.
3. Jacobsen, Eric, and Richard Lyons. 2004. “An Update to the Sliding DFT.” IEEE Signal Processing Magazine, January 2004.
4. Philippa, Bronson. 2016. Sliding Discrete Fourier Transform (C++). https://github.com/bronsonp/SlidingDFT.