Bluestein's FFT for arbitrary \(N\) on the hypercube (Q1179208): Difference between revisions
From MaRDI portal
Removed claims |
Changed an Item |
||
Property / author | |||
Property / author: James S. Otto / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Manfred Tasche / rank | |||
Normal rank |
Revision as of 07:26, 11 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Bluestein's FFT for arbitrary \(N\) on the hypercube |
scientific article |
Statements
Bluestein's FFT for arbitrary \(N\) on the hypercube (English)
0 references
26 June 1992
0 references
Let \(N>1\) be an arbitrary integer, not necessarily a power of 2. The algorithm of \textit{L. I. Bluestein} [A linear filtering approach to the computation of the discrete Fourier transform, 1968 NEREM Record, Boston, MA, Nov. 6-8, 218-219 (1968). Reprinted in: Papers on Digital Signal Processing, ed. A. V. Oppenheim, M.I.T. Press, Cambridge, MA, 171-172 (1969)] for the discrete Fourier transform of length \(N\) (\(DFT(N)\)) consists the following steps: 1. The \(DFT(N)\) is expressed as a Toeplitz matrix-vector-product. 2. This product is imbedded in a cyclic convolution of length \(2^ r \geq 2N-2\). 3. The cyclic convolution is evaluated using \(DFT(2^ r)\). Because of its minimal communication requirements, Bluestein's fast Fourier transformation (\(FFT\)) is realized as an algorithm on hypercube architecture. With \(2^ d\) processors, an ordered Bluestein \(FFT\) requires \(2d\) communication cycles with packet length \(N/2^{d+1}\). For fine-grain computations, Bluestein's \(FFT\) requires \(20\log_ 2N\) computational cycles.
0 references
fast Fourier transform
0 references
discrete Fourier transform
0 references
cyclic convolution
0 references
algorithm on hypercube architecture
0 references