c12-2 (Numerical Recipes in C), страница 3

Themethod involves a reordering of the data both before the hierarchical processing andafter it, but it allows a significant reduction in the number of multiplications in thealgorithm. For some especially favorable values of N , the Winograd algorithms canbe significantly (e.g., up to a factor of 2) faster than the simpler FFT algorithmsof the nearest integer power of 2. This advantage in speed, however, must beweighed against the considerably more complicated data indexing involved in thesetransforms, and the fact that the Winograd transform cannot be done “in place.”Finally, an interesting class of transforms for doing convolutions quickly arenumber theoretic transforms.

These schemes replace floating-point arithmetic with510Chapter 12.Fast Fourier TransformCITED REFERENCES AND FURTHER READING:Nussbaumer, H.J. 1982, Fast Fourier Transform and Convolution Algorithms (New York: SpringerVerlag).Elliott, D.F., and Rao, K.R. 1982, Fast Transforms: Algorithms, Analyses, Applications (NewYork: Academic Press).Brigham, E.O. 1974, The Fast Fourier Transform (Englewood Cliffs, NJ: Prentice-Hall). [1]Bloomfield, P. 1976, Fourier Analysis of Time Series – An Introduction (New York: Wiley).Van Loan, C. 1992, Computational Frameworks for the Fast Fourier Transform (Philadelphia:S.I.A.M.).Beauchamp, K.G.

1984, Applications of Walsh Functions and Related Functions (New York:Academic Press) [non-Fourier transforms].Heideman, M.T., Johnson, D.H., and Burris, C.S. 1984, IEEE ASSP Magazine, pp. 14–21 (October).12.3 FFT of Real Functions, Sine and CosineTransformsIt happens frequently that the data whose FFT is desired consist of real-valuedsamples fj , j = 0 . . .

N − 1. To use four1, we put these into a complex arraywith all imaginary parts set to zero. The resulting transform Fn , n = 0 . . . N − 1satisfies FN−n * = Fn . Since this complex-valued array has real values for F0and FN/2 , and (N/2) − 1 other independent values F1 . . . FN/2−1 , it has the same2(N/2 − 1) + 2 = N “degrees of freedom” as the original, real data set. However,the use of the full complex FFT algorithm for real data is inefficient, both in executiontime and in storage required. You would think that there is a better way.There are two better ways.

The first is “mass production”: Pack two separatereal functions into the input array in such a way that their individual transforms canbe separated from the result. This is implemented in the program twofft below.This may remind you of a one-cent sale, at which you are coerced to purchase twoof an item when you only need one. However, remember that for correlations andconvolutions the Fourier transforms of two functions are involved, and this is ahandy way to do them both at once. The second method is to pack the real inputarray cleverly, without extra zeros, into a complex array of half its length.

One thenperforms a complex FFT on this shorter length; the trick is then to get the requiredanswer out of the result. This is done in the program realft below.Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.

Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).integer arithmetic modulo some large prime N +1, and the N th root of 1 by themodulo arithmetic equivalent. Strictly speaking, these are not Fourier transformsat all, but the properties are quite similar and computational speed can be farsuperior. On the other hand, their use is somewhat restricted to quantities likecorrelations and convolutions since the transform itself is not easily interpretableas a “frequency” spectrum..