Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Engineering
An Introduction To The Winograd Discrete Fourier Transform, Janice S. Agnello
An Introduction To The Winograd Discrete Fourier Transform, Janice S. Agnello
Retrospective Theses and Dissertations
This paper illustrates Winograd's approach to computing the Discrete Fourier Transform (DFT). This new approach changes the DFT into a cyclic convolution of 2 sequences, and illustrates shortcuts for computing this cyclic convolution. This method is known to reduce the number of multiplies required to about 20% less than the number of multiplies used by the techniques of the Fast Fourier Transform. Three approaches are discussed, one for prime numbers, one for products of primes, and lastly one for powers of odd primes. For powers of 2 Winograd's algorithm is, in general, inefficient and best if it is not used. …