ScholarLens Back to search
2017•arXiv (Cornell University)Open access

An Algorithm for the 2D Radix-2 Sliding Window Fourier Transform.

Lee F. Richardson, William F. Eddy

Open full text 0 citations

Abstract

We present a new algorithm for the 2D Radix-2 Sliding Window Fourier Transform (SWFT). Our algorithm avoids repeating calculations in overlapping windows by using a tree representation of the Cooley-Tukey Fast Fourier Transform (FFT). For an $N_0 \times N_1$ array and $n_0 = 2^{m_0} \times n_1 = 2^{m_1}$ windows, our algorithm takes $O(N_0 N_1 n_0 n_1)$ operations, which is faster than taking a 2D FFT in each window. We provide a C implementation of the algorithm, compare ours with existing algorithms, and show how the algorithm extends to higher dimensions.

About this research paper

What this paper is about

We present a new algorithm for the 2D Radix-2 Sliding Window Fourier Transform (SWFT). Our algorithm avoids repeating calculations in overlapping windows by using a tree representation of the Cooley-Tukey Fast Fourier Transform (FFT). For an $N_0 \times N_1$ array and $n_0 = 2^{m_0} \times n_1 = 2^{m_1}$ windows, our algorithm takes $O(N_0 N_1 n_0 n_1)$ operations, which is faster than taking a 2D FFT in each window. We provide a C implementation of the algorithm, compare ours with existing algorithms, and show how the algorithm extends to higher dimensions.

Why it matters

A significance statement is not available in the OpenAlex record.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

We present a new algorithm for the 2D Radix-2 Sliding Window Fourier Transform (SWFT). Our algorithm avoids repeating calculations in overlapping windows by using a tree representation of the Cooley-Tukey Fast Fourier Transform (FFT). For an $N_0 \times N_1$ array and $n_0 = 2^{m_0} \times n_1 = 2^{m_1}$ windows, our algorithm takes $O(N_0 N_1 n_0 n_1)$ operations, which is faster than taking a 2D FFT in each window. We provide a C implementation of the algorithm, compare ours with existing algorithms, and show how the algorithm extends to higher dimensions.

Key concepts: Fast Fourier transform, Prime-factor FFT algorithm, Split-radix FFT algorithm, Cooley–Tukey FFT algorithm, Algorithm, Rader's FFT algorithm, Window (computing), Sliding window protocol

Related papers

Related paper 1Related paper 2Related paper 3
Back to paper searchBrowse research topicsOriginal source
An Algorithm for the 2D Radix-2 Sliding Window Fourier Transform. — Research Paper | ScholarLens