In-place butterfly-style FFT of 2-D real sequences
1988
Methodologies for constructing fast algorithms to compute the discrete Fourier transform (DFT) of a 2-D real sequence are introduced. The resulting algorithms are shown to be in-place and butterfly-style as well as the usual 1-D FFT algorithms. Above all, the computational load of these algorithms is reduced to less than one-half of their complex counterparts. Due to the in-place property, the storage requirement is exactly halved. A comparison is made on the basis of arithmetic complexity, storage, and input/output requirements. >
Keywords:
- Mathematics
- Fast Fourier transform
- Butterfly diagram
- Discrete Fourier transform (general)
- Prime-factor FFT algorithm
- Discrete Fourier transform
- Twiddle factor
- Split-radix FFT algorithm
- Discrete mathematics
- Cyclotomic fast Fourier transform
- Theoretical computer science
- Arithmetic
- Discrete sine transform
- Discrete Hartley transform
- Computer science
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
13
References
36
Citations
NaN
KQI