The
DFT is defined by

where

is the input
signal amplitude at time

, and
Note that

.
When

is even, the DFT summation can be split into sums over the
odd and even indexes of the input signal:
where

and

denote the even-
and odd-indexed samples from

. Thus, the length

DFT is
computable using two length

DFTs. The complex factors

are called
twiddle factors. The splitting
into sums over even and odd time indexes is called
decimation in
time. (For
decimation in frequency, the inverse DFT of the
spectrum

is split into sums over even and odd
bin
numbers 
.)
Next Section: Radix 2 FFTPrevious Section: Coherence Function in Matlab