A Semi-Fast Fourier Transform Algorithm Over GF (2 to the mth power).

Abstract

An algorithm which computes the Fourier Transform of a sequence of length n over GF (2 to the mth power) using approximately 2nm multiplications and n squared + nm additions is developed. The number of multiplications is thus considerably smaller than the n squared multiplications required for a direct evaluation, though the number of additions is somewhat larger. Unlike the Fast Fourier Transform, this method does not depend on the factors of n and can be used when n is not highly composite or is a prime. The bit complexity of the algorithm is analyzed in detail. Implementations and applications are briefly discussed. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1976
Accession Number
ADA034982

Entities

People

  • Dilip V. Sarwate

Organizations

  • University of Illinois Urbana–Champaign

Tags

Communities of Interest

  • Energy and Power Technologies
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Circuits
  • Coding
  • Coefficients
  • Composite Materials
  • Computational Complexity
  • Computations
  • Convolution
  • Decoding
  • Electrical Engineering
  • Fast Fourier Transforms
  • Illinois
  • Networks
  • Polynomials
  • Sequences
  • Xor Gates

Readers

  • Analytical Mechanics
  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Electromagnetic Wave Scattering and Antenna Radiation Engineering