Accession Number:

AD0728034

Title:

Comparison of Four Fast Fourier Transform Algorithms

Descriptive Note:

Research rept.

Corporate Author:

NAVAL UNDERWATER SYSTEMS CENTER NEWPORT RI

Personal Author(s):

Report Date:

1971-06-03

Pagination or Media Count:

30.0

Abstract:

Comparisons of four FFT Fast Fourier Transform algorithms Brenners, Cooleys, Fishers, and Singletons have been made on the basis of program execution time, storage, and accuracy. Major modifications have been made in the generation of the trigonometric values in the Cooley and Fisher algorithms, with significant improvements in accuracy. Entry of constants in all algorithms has been changed the constants are approximated by the best binary representation for the UNIVAC 1108 computer. Three waveform examples are used in the comparisons, namely, linear FM, random numbers, and a unit ramp. Also, the sizes of the FFTs considered are limited to powers of 2, from 16 through 8192. The results indicate that Singletons and Brenners algorithms have the shortest execution times and occupy the least amount of computer storage, whereas Cooleys and Fishers algorithms are the most accurate. For example, for an FFT of size 1024 on the linear FM waveform, the maximum relative errors for the four algorithms are 0.17 x 10 to the -6th power, 0.63 x 10 to the -7th power, 0.64 x 10 to the -7th power, 0.41 x 10 to the -5th power, respectively. Thus, there is no single best algorithm for all three criteria considered rather, each algorithm has its own area of most effective applicability.

Subject Categories:

  • Theoretical Mathematics
  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE