Editing Cooley–Tukey FFT algorithm (section)

== Idea ==
[[File:Cooley-tukey-general.png|thumb|right|300px|The basic step of the Cooley–Tukey FFT for general factorizations can be viewed as re-interpreting a 1d DFT as something like a 2d DFT. The 1d input array of length ''N'' = ''N''<sub>1</sub>''N''<sub>2</sub> is reinterpreted as a 2d ''N''<sub>1</sub>&times;''N''<sub>2</sub> matrix stored in [[column-major order]]. One performs smaller 1d DFTs along the ''N''<sub>2</sub> direction (the non-contiguous direction), then multiplies by phase factors (twiddle factors), and finally performs 1d DFTs along the ''N''<sub>1</sub> direction. The transposition step can be performed in the middle, as shown here, or at the beginning or end.  This is done recursively for the smaller transforms.]]

More generally, Cooley–Tukey algorithms recursively re-express  a DFT of a composite size ''N'' = ''N''<sub>1</sub>''N''<sub>2</sub> as:<ref name=DuhamelVe90>Duhamel, P., and M. Vetterli, "Fast Fourier transforms: a tutorial review and a state of the art," ''Signal Processing'' '''19''', 259–299 (1990)</ref>

# Perform ''N''<sub>1</sub> DFTs of size ''N''<sub>2</sub>.
# Multiply by complex [[roots of unity]] (often called the [[twiddle factor]]s).
# Perform ''N''<sub>2</sub> DFTs of size ''N''<sub>1</sub>.

Typically, either ''N''<sub>1</sub> or ''N''<sub>2</sub> is a small factor (''not'' necessarily prime), called the '''radix''' (which can differ between stages of the recursion).  If ''N''<sub>1</sub> is the radix, it is called a '''decimation in time''' (DIT) algorithm, whereas if ''N''<sub>2</sub> 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 (FFT algorithm)|butterfly]], so-called because of the shape of the [[dataflow diagram]] for the radix-2 case.)