Sliding DFT

Template:Short description Template:Multiple issues 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{array}{cc}{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}[\sum _{m=0}^{N-1}{f}_{m+t}{e}^{-j2\pi mn/N}-f_t+f_{t+N}]\\ & =e^{j2\pi n/N}[F_t(n)-f_t+f_{t+N}].\end{array}$$

From this definition above, the DFT can be computed recursively thereafter. For each frequency bin calculated, the recurrence updates the previous DFT value when a new input sample arrives, rather than needing to recompute the transform over the entire data frame. This makes the sliding DFT useful for applications requiring a new spectral estimate for every input sample, particularly when only a subset of the DFT bins is required. In such applications it can require fewer computations than repeatedly applying an FFT, for instance.

Because of it's recursive nature, finite precision arithmetic can cause numerical errors to accumulate. In the conventional formulation, the complex coefficient in the feedback path corresponds to a pole on the unit circle, so rounding errors in its representation can lead to inaccurate results or instability. Modified forms of the algorithm, such as the modulated sliding DFT, avoid this problem by removing the complex factor from the recursive feedback loop.

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 }$.