Radix 2 FFT
When

is a power of

, say

where

is an integer,
then the above DIT decomposition can be performed

times, until
each
DFT is length

. A length

DFT requires no multiplies. The
overall result is called a
radix 2 FFT. A different radix 2
FFT is derived by performing
decimation in frequency.

A
split radix FFT is theoretically more efficient than a pure
radix 2 algorithm [
73,
31] because it
minimizes real arithmetic operations. The term ``split radix'' refers
to a DIT decomposition that combines portions of one radix 2 and two
radix 4 FFTs [
22].
A.3On modern general-purpose
processors, however, computation time is often not minimized by
minimizing the arithmetic operation count (see §
A.7 below).
Radix 2 FFT Complexity is N Log N
Putting together the length
DFT from the

length-

DFTs in
a radix-2 FFT, the only multiplies needed are those used to combine
two small DFTs to make a DFT twice as long, as in Eq.

(
A.1).
Since there are approximately

(complex) multiplies needed for each
stage of the DIT decomposition, and only

stages of DIT (where

denotes the log-base-2 of

), we see that the total number
of multiplies for a length

DFT is reduced from

to

, where

means ``on the order of

''. More
precisely, a complexity of

means that given any
implementation of a length-

radix-2 FFT, there exist a constant

and integer

such that the computational complexity

satisfies
for all

. In summary, the complexity of the radix-2 FFT is said
to be ``N log N'', or

.
Next Section: Fixed-Point FFTs and NFFTsPrevious Section: Decimation in Time