Cooley-Tukey method

From the time function F t) and the calculation of [IT], the values of G may be found. One way to calculate the G matrix is by a fast Fourier technique called the Cooley-Tukey method. It is based on an expression of the matrix as a product of q square matrices, where q is again related to N by = 2 . For large N, the number of matrix operations is greatly reduced by this procedure. In recent years, more advanced high-speed processors have been developed to carry out the fast Fourier transform. The calculation method is basically the same for both the discrete Fourier transform and the fast Fourier transform. The difference in the two methods lies in the use of certain relationships to minimize calculation time prior to performing a discrete Fourier transform. 

The Cooley-Tukey algorithm is a rather involved mathematical formalism 50) and cannot be explained here in full detail. A short derivation with an illustration of the method for N=4 is given in Appdx 2. Here we use only the result developed there, that the required computer time is proportional to N 2 log 2N because this is the number of operations to be executed in the course of a compu-... 

A relatively simple method for the final passes is illustrated in Figure 4. Note that the two innermost loops correspond to the inner loop of a non-virtual Cooley-Tukey arrangement. The extra loop re-maps the window and resets the window index whenever the innermost loop has finished acting on a block of data. No attempt can be made to minimize the number of sine and cosine calculations within a block because every 2-by-2 transform requires different trigonometric values. A sine look-up table may increase efficiency for the final passes, but this has not yet been verified. 

The discrete FT, eqn [9], can be evaluated in a brute force fashion on a computer using the available sine and cosine functions, eqn [3], but this method is very slow for a large number of points. The FT algorithm of Cooley and Tukey is much faster. The derivation of the Cooley-Tukey algorithm ( fast Fourier transform ) starts by rewriting the exponent in eqn [10] as... 

This Fourier transform process was well known to Michelson and his peers but the computational difficulty of making the transformation prevented the application of this powerful interferometric technique to spectroscopy. An important advance was made with the discovery of the fast Fourier transform algorithm by Cooley and Tukey 29) which revived the field of spectroscopy using interferometers by allowing the calculation of the Fourier transform to be carried out rapidly. The fast Fourier transform (FFT) has been discussed in several places 30,31). The essence of the technique is the reduction in the number of computer multiplications and additions. The normal computer evaluation requires n(n — 1) additions and multiplications whereas the FFT method only requires (n logj n) additions and multiplications. If we have a 4096-point array to Fourier transform, it would require (4096) (4095) or 16.7 million multiplications. The FFT allows us to reduce this to... 

The major advance towards routine use in the mid-infrared region -j j- g. came with a new mathematical method (or algorithm) devised by Cooley and Tukey in 1965 for fast Fourier transformation. This was ... 

As mentioned above, the introduction of pulsed techniques by Ernst and Anderson revolutionized NMR. Called FT NMR because of the Fourier transform required to translate time-domain data into the frequency domain, to the despair of researchers developing alternative methods (see Section 3), the name is still legitimate as it is by far the most commonly used transformation technique. At a time when computer resources were quite scarce, the decisive step toward the Fast FT algorithm made by Cooley and Tukey- was very welcome. After this start, the field developed in parallel to the increase in computer processing power. 

---