The discrete Fourier transform of length (where is even) can be rewritten as the sum of two discrete Fourier transforms, each of length . One is formed from the even-numbered points; the other from the odd-numbered points. Denote the th point of the discrete Fourier transform by . Then
(1)
| |||
(2)
| |||
(3)
|
where and . This procedure can be applied recursively to break up the even and odd points to their even and odd points. If is a power of 2, this procedure breaks up the original transform into transforms of length 1. Each transform of an individual point has for some . By reversing the patterns of evens and odds, then letting and , the value of in binary is produced. This is the basis for the fast Fourier transform.