AN ALGOL CONVOLUTION PROCEDURE BASED ON THE FAST FOURIER TRANSFORM.
STANFORD RESEARCH INST MENLO PARK CALIF MATHEMATICAL SCIENCES DEPT
Pagination or Media Count:
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.
- Theoretical Mathematics
- Computer Programming and Software