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). The calculation for the sliding DFT is closely related to Goertzel algorithm.

Definition

Assuming that the hopsize between two consecutive DFTs is 1 sample, then

$${\begin{aligned}F_{t+1}(n)&=\sum _{k=0}^{N-1}f_{k+t+1}e^{-j2\pi kn/N}\\&=\sum _{m=1}^{N}f_{m+t}e^{-j2\pi (m-1)n/N}\\&=e^{j2\pi n/N}\left[\sum _{m=0}^{N-1}f_{m+t}e^{-j2\pi mn/N}-f_{t}+f_{t+N}\right]\\&=e^{j2\pi n/N}\left[F_{t}(n)-f_{t}+f_{t+N}\right].\end{aligned}}$$

From this definition above, the DFT can be computed recursively thereafter. However, implementing the window function on a sliding DFT is difficult due to its recursive nature, therefore it is done exclusively in a frequency domain.

Sliding windowed infinite Fourier transform

It is not possible to implement asymmetric window functions into sliding DFT. However, the IIR version called sliding windowed infinite Fourier transform (SWIFT) provides an exponential window and the αSWIFT calculates two sDFTs in parallel where slow-decaying one is subtracted by fast-decaying one, therefore a window function of $w(x)=e^{-x\alpha }-e^{-x\beta }$.

Another way to obtain higher-order ones is to cascade SWIFT in series, similar to ones for IIR filters. The obtained windowing function is $w(x)=e^{-x}x^{\mathrm {order} -1}$, where the "order" parameter is number of cascades.

Caveats

Unlike other FFT algorithms and like IIR filters, the sliding DFT requires contiguous stream of data, which is not always possible. However, there's is a way to calculate sliding DFT where the stream of data is not contiguous (e.g. in foobar2000 visualizations) is use of $\mathrm {playbackTime} -\mathrm {previousPlaybackTime}$ where playbackTime is the current playback time and previousPlaybackTime is the playback time at the time of the calculation, both in samples (or in milliseconds, which requires conversion from ms to samples) to calculate the length needed to cover new data while avoiding old data that are already covered by previous sDFT calculations, but again, this is not always possible.

Moreover, due to recursive nature, there are numerical stability (especially on applications with integers or fixed-point arithmetic) issues because the poles of IIR filters are very close to the unit circle, so why damping parameter exists to force poles to go inside the unit circle.