Sliding DFT

In applied mathematics, the sliding discrete Fourier transform is a recursive algorithm to compute successive STFTs of input data frames that are a single sample apart (hopsize − 1).[1]

Definition

Starting with a DFT at time n,

X_{n}(k)=\sum _{m=0}^{N-1}x(n+m)e^{-j2\pi km/N}

The DFT for time n + 1 can be computed as

{\begin{aligned}X_{n+1}(k)&=\sum _{m=0}^{N-1}x(n+m+1)e^{-j2\pi km/N}\\&=\sum _{m=1}^{N}x(m+n)e^{-j2\pi k(m-1)/N}\\&=e^{j2\pi k/N}\left[\sum _{m=0}^{N-1}x(n+m)e^{-j2\pi km/N}-x(n)+x(n+N)\right]\\&=e^{j2\pi k/N}\left[X_{n}(k)-x(n)+x(n+N)\right].\end{aligned}}

and recursively thereafter as

X_{n+1}(k)=e^{j2\pi k/N}\left[X_{n}(k)+\Delta \right]

with

\Delta =x(n+N)-x(n)

gollark: Remove all nonprimitive types and just copy those.

gollark: The solution is simple.

gollark: There's a better* way. Just make it so that all shapes are actually just a maximally generic Shape of some sort, which can be converted into Option<Rectangle>s.

gollark: (you would ship pregenerated indentation polynomials with macronfmt of course)

gollark: For indenting.

References

Bradford, Russell (2005). "SLIDING IS SMOOTHER THAN JUMPING" (PDF). Proceedings ICMC 2005.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Bradford, Russell (2005). "SLIDING IS SMOOTHER THAN JUMPING" (PDF). Proceedings ICMC 2005.