A Method for Validating Multidimensional Fast Fourier Transform (FFT) Algorithms

Abstract

A method is described for validating fast Fourier transforms (FFTs) based on the use of simple input functions whose discrete Fourier transforms can be evaluated in closed form. Explicit analytical results are developed for one dimensional and two dimensional discrete Fourier transforms. The analytical results are easily generalized to higher dimensions. The results offer a means for validating the FFT algorithm in one, two, or higher dimensional settings. The general motivation for the work comes from the need to validate the FFT algorithm when it newly implemented on a computer or when new techniques or devices are added to a computer facility to evaluate discrete Fourier transforms. Keywords: Computer Program Verification.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 08, 1987
Accession Number
ADA179998

Entities

People

  • John M. Bergin

Organizations

  • United States Naval Research Laboratory

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Availability
  • Classification
  • Computer Program Verification
  • Computer Programs
  • Computers
  • Digital Signal Processing
  • Discrete Fourier Transforms
  • Fast Fourier Transforms
  • Military Research
  • New Jersey
  • New York
  • Security
  • Signal Processing
  • Test And Evaluation
  • Two Dimensional
  • Validation

Fields of Study

  • Engineering

Readers

  • Finite Element Method (FEM) for solving Partial Differential Equations (PDEs)
  • Image Processing and Computer Vision.