Sliding DFT

In digital signal processing, the sliding discrete Fourier transform (sliding DFT or SDFT) is a recursive algorithm for computing a sequence of discrete Fourier transforms on overlapping data windows. Successive windows differ by only one sample, so the transform for the new window can be obtained by updating the transform of the previous window rather than recomputing it from scratch.

The sliding DFT is useful in applications that require a new spectral estimate for every input sample, especially when only a subset of DFT frequency bins are needed. In these cases, the sliding DFT can require fewer computations than repeatedly evaluating a complete DFT or FFT. The sliding DFT's recursive structure is closely related to resonator based DFT methods such as the Goertzel algorithm.

Definition

Assuming that the hop size between two consecutive DFTs is one 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. 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 a FFT, for instance.

Implementation and computational cost

A single DFT bin of the sliding DFT can be implemented as a comb filter followed by a complex resonator. When calculating multiple frequency bins, the same comb filter can be shared among the resonators for each individual bin. Each new input sample requires one complex multiplication and two real additions.

If all $N$ frequency bins are calculated for every new input sample, each successive $N$-point spectrum has computational complexity $O(N)$, compared with $O(N^{2})$ for direct evaluation of the DFT and $O(N\log N)$ for an FFT. This advantage depends on how frequently a new spectrum is required: if a complete spectrum is required only once every $N$ samples, repeatedly updating the sliding DFT eliminates much of its computational advantage. The method is therefore particularly useful when spectra must be produced at closely spaced sample positions or when only selected frequency bins are required.

Because of its 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.

One approach to frequency domain windowing is to derive a kernel from the desired time domain window, and to apply that kernel to the output of the SDFT. Since the kernel depends on the window and not on the input signal, this means it can be computed in advance

For some commonly used windows, the resulting frequency domain kernel is sparse. For instance, the Hann and Blackman window kernels are sparse, allowing the windowing operation to be implemented using a short convolution across neighboring DFT bins. Kernels for other windows, such as triangular, Gaussian, and Kaiser windows, contain more nonzero coefficients but can be approximated by discarding small values. This allows windowing to be applied while retaining the sample by sample recurrence of the SDFT.

Sliding windowed infinite Fourier transform

The sliding windowed infinite Fourier transform (SWIFT) is an infinite impulse response alternative to the finite-window sliding DFT that uses an exponentially decaying window. A related variant, αSWIFT, combines two SWIFT transforms having different exponential decay rates, producing an effective window proportional to

$$w(x)=e^{-\alpha x}-e^{-\beta x}.$$

This permits a non-rectangular, asymmetric weighting of past samples while retaining recursive sample-by-sample updates.