Algorithms.
Saved in:
| Title: | Algorithms. |
|---|---|
| Authors: | Herriot, J. G. |
| Source: | Communications of the ACM. Mar1969, Vol. 12 Issue 3, p179-187. 9p. |
| Subjects: | ALGOL (Computer program language), Mathematical convolutions, Fourier transforms, Fourier analysis, Virtual storage (Computer science), Computer storage devices |
| Abstract: | This article discusses the ALGOL convolution procedure based on the fast Fourier transform. The operation of convolution is used in computing autocorrelation and cross-correlation functions, in digital filtering of time series, and many other applications. Procedure Convolution computes the convolution of two real vectors of dimension. The special features of this procedure are the usual reordering of the fast Fourier transform results is avoided, and the return from frequency to time is made with a transform of dimension n/2 instead of n. The two vectors A and B are first transformed with a single complex Fourier transform of dimension n. Procedure Convolution uses-procedure REALTRAN but repeated here with revisions to improve accuracy on computers using truncated floating-point arithmetic. Procedures FFT4 and REVFFT4 are also used and perform the same computation as procedures FFT2 and REVFFT2 given for use on a system with virtual memory. The transform procedures given are organized without regard to the problem of memory overlay. |
| Database: | Engineering Source |
Be the first to leave a comment!
