Fast algorithms for the discrete Fourier preprocessing transforms
1992
It is pointed out that the two-stage Fourier algorithms are useful in a variety of applications in signal/image processing and recognition. The first stage, known as the DFPT (discrete Fourier preprocessing transform), has the potential of very fast and low-cost implementation, say, in a VLSI chip, as well as high-quality performance in applications without the second stage. The DFT (discrete Fourier transform), the RDFT (real DFT), or any other DFPT can be obtained if the second stage is completed. Since the second stage consists of independent blocks of circular correlations, they can be computed in fast sequential or parallel architectures. There are two groups of fast algorithms for the computation of DFPTs. The first group involves the representation of a DFPT in terms of skew-circular correlations (SCCs), which are then computed by fast SCC algorithms or parallel architectures such as semisystolic arrays. The second group involves the fast computation of a DFPT, including the DFT and the RDFT, by the implementationally simplest DFPT, such as class 2, case V DFPT. >
Keywords:
- Discrete Fourier transform
- Pseudo-spectral method
- Fast Fourier transform
- Prime-factor FFT algorithm
- Discrete Fourier transform (general)
- Non-uniform discrete Fourier transform
- Butterfly diagram
- Algorithm
- Cyclotomic fast Fourier transform
- Theoretical computer science
- Mathematics
- Discrete-time Fourier transform
- Discrete Hartley transform
- Discrete sine transform
- Computer science
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
10
References
3
Citations
NaN
KQI