Title An Introduction to the Winograd Discrete Fourier Transform English 4.7 MB 111
```                            An Introduction to the Winograd Discrete Fourier Transform
STARS Citation
ABSTRACT
Abstract
TITLE PAGE
Title Page
i
ii
INTRODUCTION
001
002
003
CHAPTER I WDFT FOR A PRIME NUMBER OF POINTS
1.1 Definition of the DFT
004
005
1.2 Generating the Recorded Set of Elements for a Prime Number of Points N and Restructuring the Matrix
006
007
008
009
010
1.3 Computations on a Cyclic Convolution Matrix
011
012
013
014
015
1.4 Winograd's Theorem on the Minimum Number of Multiplications Needed to Compute the Circular Convolution of Two Length N Sequences
016
1.5 Summary of Steps Needed to Compute the WDFT for a Prime Number of Points
017
018
019
020
021
1.6 Example of a 7 Point WDFT
022
023
024
025
026
027
028
029
030
031
032
033
CHAPTER II WDFT FOR A PRODUCT OF PRIME NUMBER OF POINTS
2.1 Theory Behind the Product of 2 Prime WDFT Algorithm
034
035
036
037
2.2 Summary of Steps Needed to Compute the WDFT for N=Product of Any Two Primes
038
039
2.3 Example of a 15 Point WDFT
040
041
042
043
044
045
046
047
048
049
050
051
052
053
054
055
056
057
058
CHAPTER III WDFT FOR POWERS OF ODD PRIMES
3.1 Theory Behind WDFT for Powers of Odd Primes
059
060
061
3.2 Summary of Steps Needed to Compute the WDFT for Powers of Odd Primes
062
063
3.3 Example of the WDFT for a 9 Point Transform
064
065
066
067
CHAPTER IV DISCUSSION OF COMPUTER SIMULATION AND CONCLUSION
068
069
070
071
072
073
074
APPENDIX A CALCULATIONS USED IN CHAPTER I
075
076
077
078
079
080
081
APPENDIX B WINOGRAD'S ALGORITHMS FOR THE 2, 3, 4, 5, 7, 8, 9, AND 16 POINT TRANSFORMS
082
083
084
085
086
087
088
APPENDIX C LISTING OF OUTPUT AND COMPUTER SIMULATION FOR THE 35 POINT WDFT
089
090
091
092
093
094
095
096
097
098
099
100
101
102
103
104
LITERATURE CITED
105
106
```
##### Document Text Contents
Page 1

University of Central Florida University of Central Florida

STARS STARS

Retrospective Theses and Dissertations

Spring 1979

An Introduction to the Winograd Discrete Fourier Transform An Introduction to the Winograd Discrete Fourier Transform

Janice S. Agnello
University of Central Florida

Part of the Operational Research Commons

Find similar works at: https://stars.library.ucf.edu/rtd

University of Central Florida Libraries http://library.ucf.edu

This Masters Thesis (Open Access) is brought to you for free and open access by STARS. It has been accepted for

STARS Citation STARS Citation
Agnello, Janice S., "An Introduction to the Winograd Discrete Fourier Transform" (1979). Retrospective
Theses and Dissertations. 392.
https://stars.library.ucf.edu/rtd/392

https://stars.library.ucf.edu/
https://stars.library.ucf.edu/
https://stars.library.ucf.edu/
https://stars.library.ucf.edu/rtd
http://network.bepress.com/hgg/discipline/308?utm_source=stars.library.ucf.edu%2Frtd%2F392&utm_medium=PDF&utm_campaign=PDFCoverPages
https://stars.library.ucf.edu/rtd
http://library.ucf.edu/
mailto:[email protected]
https://stars.library.ucf.edu/rtd/392?utm_source=stars.library.ucf.edu%2Frtd%2F392&utm_medium=PDF&utm_campaign=PDFCoverPages
https://stars.library.ucf.edu/
https://stars.library.ucf.edu/

Page 2

ABSTRACT

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 reduc~ the number of multiplies required

to about 2o% 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 pr~ucts 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 sL~ulation is illustrated for the 35 point

transform and its execution time is compared with that of

the Fast Four~er Transform algorithm for 32 points.

Page 55

50

Next, apply the last 3 additions of the 3 point transform 5 times:

-> -> ->
.3 = mJ + 3 ::s,, 0 ml ..,..

-> -> -:>
SJ = 3 mJ s4 + 5 2

-> -> ->
SJ = 3 + m3 6 s4 2

Select the output of the J point trar..sform:

-> ->

fa6,o A3 = m3 = 0 ·o
1 aJ

0,1
3

~-o 12
3

a0,3
3

ao,4

-:> ->
AJ = SJ = J 1 5 al,O

3
al,l

J
al,2
J

al,J
3

al,4

Page 56

= =

J
a2,2

J
a2,J

J
a2,4 .........,__ ___ __,

Using Appendix B apply the preliminary adds of the 5 point transform

J times:

J + J 5 aO,l ao ,, 8 1,1 ,~
= 1 J = c;

al,l + al,4 Sl ? ,_
J + J 5 a2,1 a2 4 s., J

' .l..'

3 J 5
aO,l ao,4 s2,1

= 3 J = <::5
al,l a1,4 """2,2

J 3 5
a2,1 a2,4 5 2,3

Page 110

REFERENCES

1
Schmuel rlinograd, "A New Hethod for Computing the DFT, ''

Proceedin s of IEEE International Conference on ASSP (Hartford,
Conn. : T1ay 1977 , p 366-368,

; ean P. Kol ba, and Thomas W. Parks, ''A Prime Factor
FFT Algorithm Using High-Speed Convolution," IEEE Transactions
on ASSP 24 (August 1977): 281-294.

3Schmuel rllinograd, "Some BilL11ear Forms Whose
!1ultiplicative Complexity Depends on the Field of Constants,''
research report no. RC5669, IBM Research Center, Yorktown
Heights, New York, October 1975.

4
schmuel Winograd, "Cn Computing the Discrete Fourier

Transform," National Academy of Sciences Proceedings 73
(April 1976): 1005-1006.

SHerbert Haupman, Emanuel Vegh, and Janet Fisher,
Table of All Primative Roots for Primes Less Than 000
Washington D. C.: U.S. Government Printing Office, 1970).

6
schmuel W ina grad, "On Computing the Dis crete Fourier

Transform," Mathematics of Computations 32 (January 1978):
175-199.

7Ramesh C. Agarwal, and James W. Cooley, "New
Algorithms for Digital Convolution," IEEE Transactions on
ASSP, 35 (October 1977): 392-409.

Bwynn Smith Notes from Radar Signal Processing Lectures,
Hartin Harietta Aerospace, Orlando, Florida, Spring 1979.

Page 111

106

9communications with Dr. Schmuel Winograd, IBM Research
Center, Yorktown Heights, 19 September 1979.

10
1. Robert Norris, "A Comparative Study of Time

Efficient FFT and. ~-tFTA Programs for General Purpose Computers,"
IEEE Transactions on ASSP, 26 (April 1978): 141-150.