Download An Introduction to the Winograd Discrete Fourier Transform PDF

TitleAn Introduction to the Winograd Discrete Fourier Transform
LanguageEnglish
File Size4.7 MB
Total Pages111
Table of Contents
                            An Introduction to the Winograd Discrete Fourier Transform
	STARS Citation
ABSTRACT
	Abstract
TITLE PAGE
	Title Page
TABLE OF CONTENTS
	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

inclusion in Retrospective Theses and Dissertations by an authorized administrator of STARS. For more information,

please contact [email protected]

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.

Similer Documents