University of Central Florida
An Introduction to the Winograd Discrete Fourier Transform
Abstract
dc:description.abstractThis 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. A computer simulation is illustrated for the 35 point transform and its execution time is compared with that of the Fast Fourier Transform algorithm for 32 points.
Degree
thesis:*- Grantor dc:publisher
- University of Central Florida
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Agnello, Janice S.
- Contributors dc:contributor
-
- Bauer, Christian S.
- <p><a href="https://www.wikidata.org/wiki/Q57708477">Christian S. Bauer, Jr. (Q57708477)</a></p> <p><a href="http://viaf.org/viaf/155956728">University of Central Florida. College of Engineering</a> [VIAF]</p><p><a href="http://id.loc.gov/authorities/names/n82027354.html">University of Central Florida. College of Engineering</a> [LC]</p>
Subjects
dc:subject × 9- Fourier analysis
- Fourier transformations
- Winograd algorithm
- Discrete Fourier transform (DFT)
- Cyclic convolution methods
- Prime-length and power-of-prime transforms
- Multiply-count optimization in DFT algorithms
- Operational Research
- Fourier analysis; Fourier transformations; Fourier transformations--Computer programs; Convolutions (Mathematics)--Computer programs; Signal processing--Digital techniques--Computer programs; Fourier analysis--Computer programs; Transformations (Mathematics)--Computer programs
Rights
dc:rights- Statement dc:rights
-
- Public Domain
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
- DP0013247