Algorithm 991: The 2D tree sliding window discrete Fourier transform

DOI10.1145/3264426MaRDI QIDQ5237424zbMATH OpenOpenAlexWikidataFDO

Authors Lee F. Richardson, William F. Eddy

Publication date 18 October 2019

Published in ACM Transactions on Mathematical Software (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1707.08213

zbMATH Keywords

data structurefast Fourier transform

Mathematics Subject Classification ID

Numerical methods for discrete and fast Fourier transforms (65T50)

Abstract: We present a new algorithm for the 2D Sliding Window Discrete Fourier Transform (SWDFT). Our algorithm avoids repeating calculations in overlapping windows by storing them in a tree data-structure based on the ideas of the Cooley- Tukey Fast Fourier Transform (FFT). For an $N_{0}imes{N}_1$ array and $n_{0}imes{n}_1$ windows, our algorithm takes $O(N_0{N}_1{n}_0{n}_1)$ operations. We provide a C implementation of our algorithm for the Radix-2 case, compare ours with existing algorithms, and show how our algorithm easily extends to higher dimensions.

Recommendations

• Windowed discrete Fourier transform for shifting data
• Vector radix 2 2 sliding fast Fourier transform
• New fast algorithm for two-dimensional discrete Fourier transform DFT(2ⁿ; 2)
• A new efficient algorithm to compute the two-dimensional discrete Fourier transform
• scientific article; zbMATH DE number 3885286

Cited in

(5)

• Fixed-point error analysis and an efficient array processor design of two-dimensional sliding DFT
• Windowed discrete Fourier transform for shifting data
• Vector radix 2 2 sliding fast Fourier transform
• Sliding spatial frequency processing of discrete signals
• Algorithm 991

This page was built for publication: Algorithm 991: The 2D tree sliding window discrete Fourier transform

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5237424)