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: <@178948413851697152> https://en.m.wikipedia.org/wiki/AMULET_microprocessor

gollark: I think the trendy thing is just aggressive power/clock gating now.

gollark: There were some asynchronous CPUs ages ago.

gollark: ```haskelldata Thing = Whatever Int | Bla String```Good luck implementing that sort of thing without loads of boilerplate.

gollark: ADTs are really great, indeed.

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.