Fast algorithms for the discrete Fourier preprocessing transforms

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. >