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.
