Moving discrete fourier transform

Abstract

A common approach to signal or image processing using the discrete Fourier transform (DFT) is to extract a portion of the signal by windowing, and then to form the DFT of the window contents. By moving the window appropriately, the entire signal may be covered. The moving fast Fourier transform (MFFT) algorithms developed in the paper apply to the particular case where the window is moved one data point along the signal between successive transforms. The MFFT ‘updates’ the DFT to reflect the new window contents, using less computation than in directly evaluating the new transform with the FFT algorithm. The MFFT has computational order Nin 1 — d and N2in 2 — d, a factor of log2Nimprovement over the FFT. MFFT algorithms are derived for use with the boxcar, split-triangular, Hanning, Hamming and Blackman windows. Generalisation to piecewise linear and piecewise polynomial windows is discussed.