integer arithmetic modulo some large prime N +1, and the N th root of 1 by the modulo arithmetic equivalent. Strictly speaking, these are not Fourier transforms at all, but the properties are quite similar and computational speed can be far superior. On the other hand, their use is somewhat restricted to quantities like correlations and convolutions since the transform itself is not easily interpretable as a “frequency” spectrum. | 510 Chapter 12. Fast Fourier Transform integer arithmetic modulo some large prime N 1 and the Nth root of 1 by the modulo arithmetic equivalent. Strictly speaking these are not Fourier transforms at all but the properties are quite similar and computational speed can be far superior. On the other hand their use is somewhat restricted to quantities like correlations and convolutions since the transform itself is not easily interpretable as a frequency spectrum. CITED REFERENCES AND FURTHER READING Nussbaumer . 1982 FastFourier TransformandConvolutionAlgorithms New York SpringerVerlag . Elliott . and Rao . 1982 Fast Transforms Algorithms Analyses Applications New York Academic Press . Brigham . 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 . . Beauchamp . 1984 Applications of Walsh Functions and Related Functions New York Academic Press non-Fourier transforms . Heideman . Johnson . and Burris . 1984 IEEE ASSP Magazine pp. 14-21 October . FFT of Real Functions Sine and Cosine Transforms It happens frequently that the data whose FFT is desired consist of real-valued samples fj j 0 . .N - 1. To use fourl we put these into a complex array with all imaginary parts set to zero. The resulting transform Fn n 0 . .N - 1 satisfies FN-n Fn. Since this complex-valued array has real values for F0 and Fn 2 and N 2 - 1 other independent values F1. FN 2-i it has the same 2 N 2 - 1 2 N degrees of freedom as the original real data set. However the use of the full complex FFT algorithmfor real data is inefficient both in execution time 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 separate real functions into the input array in such a way that their individual transforms
