Title :
A New Hybrid Algorithm for Computing a Fast Discrete Fourier Transform
Author :
Reed, Irving S. ; Truong, T.K.
Author_Institution :
Department of Electrical Engineering, University of Southern California
fDate :
7/1/1979 12:00:00 AM
Abstract :
In this paper for certain long transform lengths, Winograd´s algorithm for computing the discrete Fourier transform (DFT) is extended considerably. This is accomplisbed by performing the cyclic convolution, required by Winograd´s method, with the Mersenne prime number-theoretic transform developed originally by Rader. This new algorithm requires fewer multiplications than either the standard fast Fourier transform (FFT) or Winograd´s more conventional algorithm. However, more additions are required.
Keywords :
Discrete Fourier transform (DFT); Winograd´s algorithm; fast Fourier transform (FFT); Convolution; Discrete Fourier transforms; Discrete transforms; Fast Fourier transforms; Fourier transforms; Galois fields; Military computing; Propulsion; Roundoff errors; Telecommunication computing; Discrete Fourier transform (DFT); Winograd´s algorithm; fast Fourier transform (FFT);
Journal_Title :
Computers, IEEE Transactions on
DOI :
10.1109/TC.1979.1675393
