Accession Number:

ADA133087

Title:

Comparison of Arithmetic Requirements for the PFA (Prime Factor Algorithm), WFTA (Winograd Fourier Transform Algorithm), SWIFT, MFFT (Mixed Radix Fast Fourier Transform), FFT (Fast Fourier Transform) and DFT (Discrete Fourier Transform) Algorithms

Descriptive Note:

Technical rept.

Corporate Author:

ARMY MISSILE COMMAND REDSTONE ARSENAL AL ADVANCED SENSORS DIRECTORATE

Personal Author(s):

Report Date:

1982-11-01

Pagination or Media Count:

61.0

Abstract:

This discrete Fourier transform DFT is a powerful reversible mapping transform for discrete data sequences with mathematical properties analogous to those of the Fourier transform. The DFT can be used for spectral analysis of time series, fast correlation of sequences, fast convolution of sequences for the purpose of digital filtering, and for radar digital beamforming. The ever increasing importance of the DFT algorithm has led to the development of several more efficient algorithms requiring far less arithmetic computations than the DFT. This report examines the multidimensional DFT decomposition theory central to many of these algorithms and gives a brief introduction to the radix-2 fast Fourier transform FFT, radix-4 FFT, mixed radix fast Fourier transform MFFT, prime factor algorithm PFA, Winograd Fourier transform WFTA, and SWIFT algorithms. In addition, the arithmetic complexity of these algorithms is compared for various one and two-dimensional transform sizes. Included in the comparison are the number of real additions, real multiplications, total real operations, total equivalent real multiplications, and integrated circuit chips required for each algorithm.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE