{
  "id": "enwiki-001373740970",
  "slug": "cooley-tukey-fft-algorithm",
  "title": "Cooley–Tukey FFT algorithm",
  "qid": "",
  "lead": "The Cooley–Tukey algorithm, named after J. W. Cooley and John Tukey, is the most common fast Fourier transform (FFT) algorithm. It re-expresses the discrete Fourier transform (DFT) of an arbitrary composite size N = N_1N_2 in terms of N 1 smaller DFTs of sizes N 2 , recursively, to reduce the computation time to O(N log N) for highly composite N (smooth numbers). Because of the algorithm's importance, specific variants and implementation styles have become known by their own names, as described below. Because the Cooley–Tukey algorithm breaks the DFT into smaller DFTs, it can be combined arbitrarily with any other algorithm for the DFT. For example, Rader's or Bluestein's algorithm can be used to handle large prime factors that cannot be decomposed by Cooley–Tukey, or the prime-factor algorithm can be exploited for greater efficiency in separating out relatively prime factors. The algorithm, along with its recursive application, was invented by Carl Friedrich Gauss. Cooley and Tukey independently rediscovered and popularized it 160 years later.",
  "body": "The Cooley–Tukey algorithm, named after J. W. Cooley and John Tukey, is the most common fast Fourier transform (FFT) algorithm. It re-expresses the discrete Fourier transform (DFT) of an arbitrary composite size N = N_1N_2 in terms of N 1 smaller DFTs of sizes N 2 , recursively, to reduce the computation time to O(N log N) for highly composite N (smooth numbers). Because of the algorithm's importance, specific variants and implementation styles have become known by their own names, as described below. Because the Cooley–Tukey algorithm breaks the DFT into smaller DFTs, it can be combined arbitrarily with any other algorithm for the DFT. For example, Rader's or Bluestein's algorithm can be used to handle large prime factors that cannot be decomposed by Cooley–Tukey, or the prime-factor algorithm can be exploited for greater efficiency in separating out relatively prime factors. The algorithm, along with its recursive application, was invented by Carl Friedrich Gauss. Cooley and Tukey independently rediscovered and popularized it 160 years later. X_k = \\sum_{n=0}^{N-1} x_n e^{-\\frac{2\\pi i}{N} nk}, where n is an integer ranging from 0 to N-1 . Radix-2 DIT first computes the DFTs of the even-indexed inputs (x_{2m}=x_0, x_2, \\ldots, x_{N-2}) and of the odd-indexed inputs (x_{2m+1}=x_1, x_3, \\ldots, x_{N-1}) , and then combines those two results to produce the DFT of the whole sequence. This idea can then be performed recursively to reduce the overall runtime to O(N log N). This simplified form assumes that N is a power of two; since the number of sample points N can usually be chosen freely by the application (e.g. by changing the sample rate or window, zero-padding, etcetera), this is often not an important restriction. The radix-2 DIT algorithm rearranges the DFT of the function x_n into two parts: a sum over the even-numbered indices n={2m} and a sum over the odd-numbered indices n={2m+1} : X_k = \\sum_{m=0}^{N/2-1} x_{2m}e^{-\\frac{2\\pi i}{N} (2m)k} + \\sum_{m=0}^{N/2-1} x_{2m+1} e^{-\\frac{2\\pi i}{N} (2m+1)k} One can factor a common multiplier e^{-\\frac{2\\pi i}{N}k} out of the second sum, as shown in the equation below. It is then clear that the two sums are the DFT of the even-indexed part x_{2m} and the DFT of odd-indexed part x_{2m+1} of the function x_n . Denote the DFT of the Even-indexed inputs x_{2m} by E_k and the DFT of the Odd-indexed inputs x_{2m + 1} by O_k and we obtain: X_k= \\underbrace{\\sum \\limits_{m=0}^{N/2-1} x_{2m} e^{-\\frac{2\\pi i}{N/2} mk}}_{\\text{DFT of even-indexed part of } x_n} {} + e^{-\\frac{2\\pi i}{N}k} \\underbrace{\\sum \\limits_{m=0}^{N/2-1} x_{2m+1} e^{-\\frac{2\\pi i}{N/2} mk}}_{\\text{DFT of odd-indexed part of } x_n} = E_k + e^{-\\frac{2\\pi i}{N}k} O_k\\qquad\\text{ for }k=0,\\dots,\\frac N2-1. Note that the equalities hold for k=0,\\dots,N-1 , but the crux is that E_k and O_k are calculated in this way for k=0,\\dots,\\frac N2-1 only. Thanks to the periodicity of the complex exponential, X_{k+\\frac{N}{2}} is also obtained from E_k and O_k : \\begin{align} X_{k + \\frac{N}{2}} & = \\sum \\limits_{m=0}^{N/2-1} x_{2m} e^{-\\frac{2\\pi i}{N/2} m(k + \\frac{N}{2})} + e^{-\\frac{2\\pi i}{N}(k + \\frac{N}{2})} \\sum_{m=0}^{N/2-1} x_{2m+1} e^{-\\frac{2\\pi i}{N/2} m(k + \\frac{N}{2} )} \\\\ & = \\sum_{m=0}^{N/2-1} x_{2m} e^{-\\frac{2\\pi i}{N/2} mk} e^{-2\\pi m i} + e^{-\\frac{2\\pi i}{N}k}e^{-\\pi i} \\sum_{m=0}^{N/2-1} x_{2m+1} e^{-\\frac{2\\pi i}{N/2} mk} e^{-2\\pi m i} \\\\ & = \\sum_{m=0}^{N/2-1} x_{2m} e^{-\\frac{2\\pi i}{N/2} mk} - e^{-\\frac{2\\pi i}{N}k} \\sum_{m=0}^{N/2-1} x_{2m+1} e^{-\\frac{2\\pi i}{N/2} mk} \\\\ & = E_k - e^{-\\frac{2\\pi i}{N}k} O_k \\end{align} We can rewrite X_k and X_{k+\\frac{N}{2}} as: \\begin{align} X_k & = E_k + e^{-\\frac{2\\pi i}{N}{k}} O_k \\\\ X_{k+\\frac{N}{2}} & = E_k - e^{-\\frac{2\\pi i}{N}{k}} O_k \\end{align} This result, expressing the DFT of length N recursively in terms of two DFTs of size N/2, is the core of the radix-2 DIT fast Fourier transform. The algorithm gains its speed by re-using the results of intermediate computations to compute multiple DFT outputs. Note that final outputs are obtained by a +/− combination of E_k and O_k \\exp(-2\\pi i k/N) , which is simply a size-2 DFT (sometimes called a butterfly in this context); when this is generalized to larger radices below, the size-2 DFT is replaced by a larger DFT (which itself can be evaluated with an FFT). This process is an example of the general technique of divide and conquer algorithms; in many conventional implementations, however, the explicit recursion is avoided, and instead one traverses the computational tree in breadth-first fashion. The above re-expression of a size-N DFT as two size-N/2 DFTs is sometimes called the Danielson–Lanczos lemma, since the identity was noted by those two authors in 1942 (influenced by Runge's 1903 work ). They applied their lemma in a \"backwards\" recursive fashion, repeatedly doubling the DFT size until the transform spectrum converged (although they apparently didn't realize the linearithmic [i.e., order N&nbsp;log&nbsp;N] asymptotic complexity they had achieved). The Danielson–Lanczos work predated widespread availability of mechanical or electronic computers and required manual calculation (possibly with mechanical aids such as adding machines); they reported a computation time of 140 minutes for a size-64 DFT operating on real inputs to 3–5 significant digits. Cooley and Tukey's 1965 paper reported a running time of 0.02 minutes for a size-2048 complex DFT on an IBM 7094 (probably in 36-bit single precision, ~8 digits). Rescaling the time by the number of operations, this corresponds roughly to a speedup factor of around 800,000. (To put the time for the hand calculation in perspective, 140 minutes for size 64 corresponds to an average of at most 16 seconds per floating-point operation, around 20% of which are multiplications.) if N = 1 then X 0 ← x 0 trivial size-1 DFT base case else X 0,...,N/2−1 ← ditfft2(x, N/2, 2s) DFT of (x 0 , x 2s , x 4s , ..., x (N-2)s ) X N /2,...,N−1 ← ditfft2(x+s, N/2, 2s) DFT of (x s , x s +2s , x s +4s , ..., x (N-1)s ) for k = 0 to (N/2)-1 do combine DFTs of two halves: p ← X k q ← exp(−2πi/N k) X k +N/2 X k ← p + q X k +N/2 ← p − q end for end if Here, ditfft2 (x,N,1), computes X=DFT(x) out-of-place by a radix-2 DIT FFT, where N is an integer power of 2 and s=1 is the stride of the input x array. x+s denotes the array starting with x s . (The results are in the correct order in X and no further bit-reversal permutation is required; the often-mentioned necessity of a separate bit-reversal stage only arises for certain in-place algorithms, as described below.) High-performance FFT implementations make many modifications to the implementation of such an algorithm compared to this simple pseudocode. For example, one can use a larger base case than N=1 to amortize the overhead of recursion, the twiddle factors \\exp[-2\\pi i k/ N] can be precomputed, and larger radices are often used for cache reasons; these and other optimizations together can improve the performance by an order of magnitude or more. (In many textbook implementations the depth-first recursion is eliminated in favor of a nonrecursive breadth-first approach, although depth-first recursion has been argued to have better memory locality. ) Several of these ideas are described in further detail below. More generally, Cooley–Tukey algorithms recursively re-express a DFT of a composite size N = N 1 N 2 as: Perform N 1 DFTs of size N 2 . Multiply by complex roots of unity (often called the twiddle factors). Perform N 2 DFTs of size N 1 . Typically, either N 1 or N 2 is a small factor (not necessarily prime), called the radix (which can differ between stages of the recursion). If N 1 is the radix, it is called a decimation in time (DIT) algorithm, whereas if N 2 is the radix, it is decimation in frequency (DIF, also called the Sande–Tukey algorithm). The version presented above was a radix-2 DIT algorithm; in the final expression, the phase multiplying the odd transform is the twiddle factor, and the +/- combination (butterfly) of the even and odd transforms is a size-2 DFT. (The radix's small DFT is sometimes known as a butterfly, so-called because of the shape of the dataflow diagram for the radix-2 case.) The general Cooley–Tukey factorization rewrites the indices k and n as k = N_2 k_1 + k_2 and n = N_1 n_2 + n_1 , respectively, where the indices k a and n a run from 0..N a -1 (for a of 1 or 2). That is, it re-indexes the input (n) and output (k) as N 1 by N 2 two-dimensional arrays in column-major and row-major order, respectively; the difference between these indexings is a transposition, as mentioned above. When this re-indexing is substituted into the DFT formula for nk, the N_1 n_2 N_2 k_1 cross term vanishes (its exponential is unity), and the remaining terms give X_{N_2 k_1 + k_2} = \\sum_{n_1=0}^{N_1-1} \\sum_{n_2=0}^{N_2-1} x_{N_1 n_2 + n_1} e^{-\\frac{2\\pi i}{N_1 N_2} \\cdot (N_1 n_2 + n_1) \\cdot (N_2 k_1 + k_2) } = \\sum_{n_1=0}^{N_1-1} \\left[ e^{-\\frac{2\\pi i}{N_1N_2} n_1 k_2 } \\right] \\left( \\sum_{n_2=0}^{N_2-1} x_{N_1 n_2 + n_1} e^{-\\frac{2\\pi i}{N_2} n_2 k_2 } \\right) e^{-\\frac{2\\pi i}{N_1} n_1 k_1 } = \\sum_{n_1=0}^{N_1-1} \\left( \\sum_{n_2=0}^{N_2-1} x_{N_1 n_2 + n_1} e^{-\\frac{2\\pi i}{N_2} n_2 k_2 } \\right) e^{-\\frac{2\\pi i}{N_1N_2} n_1(N_2k_1+k_2) } . where each inner sum is a DFT of size N 2 , each outer sum is a DFT of size N 1 , and the [...] bracketed term is the twiddle factor. An arbitrary radix r (as well as mixed radices) can be employed, as was shown by both Cooley and Tukey as well as Gauss (who gave examples of radix-3 and radix-6 steps). Cooley and Tukey originally assumed that the radix butterfly required O(r 2 ) work and hence reckoned the complexity for a radix r to be O(r 2 &nbsp;N/r&nbsp;log r N) = O(N&nbsp;log 2 (N)&nbsp;r/log 2 r); from calculation of values of r/log 2 r for integer values of r from 2 to 12 the optimal radix is found to be 3 (the closest integer to e, which minimizes r/log 2 r). This analysis was erroneous, however: the radix-butterfly is also a DFT and can be performed via an FFT algorithm in O(r log r) operations, hence the radix r actually cancels in the complexity O(r&nbsp;log(r)&nbsp;N/r&nbsp;log r N), and the optimal r is determined by more complicated considerations. In practice, quite large r (32 or 64) are important in order to effectively exploit e.g. the large number of processor registers on modern processors, and even an unbounded radix r= also achieves O(N&nbsp;log&nbsp;N) complexity and has theoretical and practical advantages for large N as mentioned above. The best-known reordering technique involves explicit bit reversal for in-place radix-2 algorithms. Bit reversal is the permutation where the data at an index n, written in binary with digits b 4 b 3 b 2 b 1 b 0 (e.g. 5 digits for N=32 inputs), is transferred to the index with reversed digits b 0 b 1 b 2 b 3 b 4 . Consider the last stage of a radix-2 DIT algorithm like the one presented above, where the output is written in-place over the input: when E_k and O_k are combined with a size-2 DFT, those two values are overwritten by the outputs. However, the two output values should go in the first and second halves of the output array, corresponding to the most significant bit b 4 (for N=32); whereas the two inputs E_k and O_k are interleaved in the even and odd elements, corresponding to the least significant bit b 0 . Thus, in order to get the output in the correct place, b 0 should take the place of b 4 and the index becomes b 0 b 4 b 3 b 2 b 1 . And for next recursive stage, those 4 least significant bits will become b 1 b 4 b 3 b 2 , If you include all of the recursive stages of a radix-2 DIT algorithm, all the bits must be reversed and thus one must pre-process the input (or post-process the output) with a bit reversal to get in-order output. (If each size-N/2 subtransform is to operate on contiguous data, the DIT input is pre-processed by bit-reversal.) Correspondingly, if you perform all of the steps in reverse order, you obtain a radix-2 DIF algorithm with bit reversal in post-processing (or pre-processing, respectively). The logarithm (log) used in this algorithm is a base 2 logarithm. The following is pseudocode for iterative radix-2 FFT algorithm implemented using bit-reversal permutation. algorithm iterative-fft is input: Array a of n complex values where n is a power of 2. output: Array A the DFT of a. bit-reverse-copy(a, A) n ← a.length for s = 1 to log(n) do m ← 2 s ω m ← exp(−2πi/m) for k = 0 to n-1 by m do ω ← 1 for j = 0 to m/2 – 1 do t ← ω A[k + j + m/2] u ← A[k + j] A[k + j] ← u + t A[k + j + m/2] ← u – t ω ← ω ω m return A The bit-reverse-copy procedure can be implemented as follows. algorithm bit-reverse-copy(a,A) is input: Array a of n complex values where n is a power of 2. output: Array A of size n. n ← a.length for k = 0 to n – 1 do A[rev(k)] := a[k] Alternatively, some applications (such as the computation of convolution products) work equally well on bit-reversed data, so one can perform forward transforms, processing, and then inverse transforms all without bit reversal to produce final results in the natural order. Many FFT users, however, prefer natural-order outputs, and a separate, explicit bit-reversal stage can have a non-negligible impact on the computation time, even though bit reversal can be done in O(N) time and has been the subject of much research. Also, while the permutation is a bit reversal in the radix-2 case, it is more generally an arbitrary (mixed-base) digit reversal for the mixed-radix case, and the permutation algorithms become more complicated to implement. Moreover, it is desirable on many hardware architectures to re-order intermediate stages of the FFT algorithm so that they operate on consecutive (or at least more localized) data elements. To these ends, a number of alternative implementation schemes have been devised for the Cooley–Tukey algorithm that do not require separate bit reversal and/or involve additional permutations at intermediate stages. The problem is greatly simplified if it is out-of-place: the output array is distinct from the input array or, equivalently, an equal-size auxiliary array is available. The algorithm performs every stage of the FFT out-of-place, typically writing back and forth between two arrays, transposing one \"digit\" of the indices with each stage, and has been especially popular on SIMD architectures. Even greater potential SIMD advantages (more consecutive accesses) have been proposed for the Pease algorithm, which also reorders out-of-place with each stage, but this method requires separate bit/digit reversal and O(N log N) storage. One can also directly apply the Cooley–Tukey factorization definition with explicit (depth-first) recursion and small radices, which produces natural-order out-of-place output with no separate permutation step (as in the pseudocode above) and can be argued to have cache-oblivious locality benefits on systems with hierarchical memory. A typical strategy for in-place algorithms without auxiliary storage and without separate digit-reversal passes involves small matrix transpositions (which swap individual pairs of digits) at intermediate stages, which can be combined with the radix butterflies to reduce the number of passes over the data.",
  "categories": [
    "101986889",
    "114437564",
    "22935437",
    "23302980",
    "23603337",
    "26220375",
    "63697623",
    "63706498",
    "63706574",
    "68328988"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1373740970",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1788796013.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001373740970",
    "type": "webpage",
    "title": "Cooley–Tukey FFT algorithm",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/cooley-tukey-fft-algorithm",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          21
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          21
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001373740970",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1373740970",
    "note": "Immutable snapshot enwiki-001373740970"
  }
}