NASA Logo

NTRS

NTRS - NASA Technical Reports Server

Back to Results
A fast D.F.T. algorithm using complex integer transformsWinograd (1976) has developed a new class of algorithms which depend heavily on the computation of a cyclic convolution for computing the conventional DFT (discrete Fourier transform); this new algorithm, for a few hundred transform points, requires substantially fewer multiplications than the conventional FFT algorithm. Reed and Truong have defined a special class of finite Fourier-like transforms over GF(q squared), where q = 2 to the p power minus 1 is a Mersenne prime for p = 2, 3, 5, 7, 13, 17, 19, 31, 61. In the present paper it is shown that Winograd's algorithm can be combined with the aforementioned Fourier-like transform to yield a new algorithm for computing the DFT. A fast method for accurately computing the DFT of a sequence of complex numbers of very long transform-lengths is thus obtained.
Document ID
19780047502
Acquisition Source
Legacy CDMS
Document Type
Reprint (Version printed in journal)
Authors
Reed, I. S.
(Southern California, University Los Angeles, Calif., United States)
Truong, T. K.
(California Institute of Technology, Jet Propulsion Laboratory, Tracking and Data Acquisition Engineering, Pasadena Calif., United States)
Date Acquired
August 9, 2013
Publication Date
March 16, 1978
Publication Information
Publication: Electronics Letters
Volume: 14
Subject Category
Mathematical And Computer Sciences (General)
Accession Number
78A31411
Funding Number(s)
CONTRACT_GRANT: AF-AFOSR-75-2798
CONTRACT_GRANT: NAS7-100
Distribution Limits
Public
Copyright
Other

Available Downloads

There are no available downloads for this record.
No Preview Available