Cooley -Tukey algorithm

In practice, one uses a less redundant fast Fourier transform algorithm, e.g.. the Cooley-Tukey algorithm rather than the expression shown above. Possible problems connected with discrete Fourier transfomiation (DFT) include... 

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-... 

This short derivation of the Cooley-Tukey algorithm is given to demonstrate the principle it cannot illuminate all the details and aspects of an actual computation. In that respect, the reader is referred to the literature 49,50,97)... 

The derivation of the Cooley-Tukey algorithm now requires that all integers m, n, N be converted to binary numbers to take advantage of the periodicity of the function e . Let us assume... 

Potentially, the most inefficient part of any algorithm acting on virtual data is the memory redefinition operation. Virtual arrays residing entirely in extended memory can be manipulated much more quickly than virtual arrays residing wholly or partially on disk. Therefore, it is desirable to keep as much of the virtual array as possible in the primary storage. The re-map operation, while orders of magnitude more efficient than disk I/O, is still relatively slow, however, and care should be taken to minimize the number of these operations. With this constriction in mind, the Cooley-Tukey algorithm can be modified to act on a virtual data set. 

After the last block has been transformed, the data has been subjected to I passes of a Cooley-Tukey algorithm. All that remains to complete the transform are the final M-I passes. During these passes, the data points for the 2-by-2 transforms are always in different blocks of the array. Thus, dual windows are necessary. Furthermore, subsequent passes act on different blocks of data, and an approach in which multiple passes are performed for discrete blocks of data (as in the internal transforms) is impossible. Consequently, the final passes are characterized by extensive re-mapping each block in the array is re-mapped once during each pass. To make matters worse, two windows are in use and the block size is reduced to half the size of the window used for the internal transform. As in the bit reversal routine, the speed-limiting step, therefore, is the re-map operation. 

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... 

The Cooley-Tukey algorithm is general and can be applied to any Fourier transform, but the computation is greatly simplified if AT is a base 2 number, that is, AT = 2 , where a is a positive integer. The factorization procedure may be demonstrated easily for the case when AT = 4 = 2. In this example, Eq. 4.13 becomes... 

Thus you can see the analogy to a projection of a specific cosine component from the interferogram, although the details of the Cooley-Tukey algorithm are much more complicated. If we apply the projection idea to many (thousands) cos(nx) waves, we can find a fine-grained bar graph that... 

---