Accession Number : AD0646628

Title :   AN ALGOL CONVOLUTION PROCEDURE BASED ON THE FAST FOURIER TRANSFORM.

Descriptive Note : Research memorandum,

Corporate Author : STANFORD RESEARCH INST MENLO PARK CALIF MATHEMATICAL SCIENCES DEPT

Personal Author(s) : Singleton,Richard C.

Report Date : JAN 1967

Pagination or Media Count : 15

Abstract : The body of the report was written as a contribution to the Algorithm section of the Communications of the ACM, and consists of three ALGOL procedures with comments. Two fast Fourier transform procedures, FASTFOURIERS and REVERSEFOURIERC, are included because of their use by procedure CONVOLUTION, but can be used independently. Procedure CONVOLUTION computes the convolution of two real vectors A and B of period n. If a noncircular convolution is wanted, the data vectors are extended by adding zeros before computing. The convolution is computed by first transforming A and B to Fourier coefficient vectors alpha and beta forming the complex conjugate product alpha beta, then computing the Fourier transform of alpha beta. The result of the final step is the desired convolution. Computing time for this method increases as n log 2 n, as compared to n2 for the direct method of computing lagged products. Tests show a 10 to 1 time advantage for the transform method at n = 256.

Descriptors :   (*INTEGRAL TRANSFORMS, ALGORITHMS), (*VECTOR ANALYSIS, *ALGORITHMS), COMPUTER PROGRAMS, PROGRAMMING LANGUAGES, FOURIER ANALYSIS, SERIES(MATHEMATICS)

Subject Categories : Theoretical Mathematics
      Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE