DocumentCode
1140189
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
Issue
7
fYear
1979
fDate
7/1/1979 12:00:00 AM
Firstpage
487
Lastpage
492
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);
fLanguage
English
Journal_Title
Computers, IEEE Transactions on
Publisher
ieee
ISSN
0018-9340
Type
jour
DOI
10.1109/TC.1979.1675393
Filename
1675393
Link To Document