Accession Number : ADA100782
Title : Efficient Computer Implementations of Fast Fourier Transforms.
Descriptive Note : Master's thesis,
Corporate Author : AIR FORCE INST OF TECH WRIGHT-PATTERSON AFB OH SCHOOL OF ENGINEERING
Personal Author(s) : Blanken,John David
Report Date : Dec 1980
Pagination or Media Count : 19
Abstract : A comprehensive comparison of the most efficient Discrete Fourier Transform (DFT) techniques is presented. The DFT algorithms selected are the fixed radix Fast Fourier Transform (FFT), mixed radix FET, the Winograd Fourier Transform Algorithm (WFTA), and the Prime Factor Algorithm (PFA). Comparison of the algorithms is based on the number of real multiplications, additions, and memory arrays required as a function of sequence length N. This paper reviews the literature, selects the most efficient DFT FORTRAN programs available, develops the number of real multiplications and additions as a function of N, and compares the algorithms using tables and plots of real multiplications, additions, and memory arrays. Comparison shows that the WFTA and PFA require the least real multiplications and additions, but the fixed radix and mixed radix FFTs require the least memory. The mixed radix FFT is much more flexible than WFTA or PFA since N can be any length sequence. The WFTA and PFA are closely studied and tradeoffs between the two are discussed. Based on the results of the paper, an algorithm is presented to select the most efficient DFT for an N length sequence given the multiply speed, add speed, and memory size of the computer.
Descriptors : *COMPUTERIZED SIMULATION , *FAST FOURIER TRANSFORMS , COMPUTER PROGRAMS , ALGORITHMS , FOURIER TRANSFORMATION , STATE OF THE ART , COMPUTER PROGRAMMING , MATHEMATICAL LOGIC , ARRAYS , THESES , FORTRAN , USER NEEDS , EXPONENTIAL FUNCTIONS , DISCRETE FOURIER TRANSFORMS , SEQUENCES(MATHEMATICS) , CONVOLUTION
Subject Categories : Theoretical Mathematics
Computer Programming and Software
Distribution Statement : APPROVED FOR PUBLIC RELEASE