Accession Number:

ADA034982

Title:

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

Descriptive Note:

Technical rept.,

Corporate Author:

ILLINOIS UNIV AT URBANA-CHAMPAIGN COORDINATED SCIENCE LAB

Personal Author(s):

Report Date:

1976-09-01

Pagination or Media Count:

26.0

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

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE